Approximation search source reconstruction localization algorithm

Question

Goal

To determine the coordinates of some signal source in a 3D space, given the coordinates of four observers and the time at which each saw the signal, as well as the velocity of the signal.

Algorithm

The algorithm is more-or-less comprised of two pieces: the approximation search algorithm, and the localization algorithm. Approximation search can be described simply as follows:

Suppose we have some function, f(x), and we want to find an x such that f(x) = y. We begin by choosing some search interval, [xi, xf], and we probe some evenly-spaced points along this interval with some step, da. We remember the point with the least error, and feed that error back into the algorithm. We recursively increase accuracy, reducing da and restricting the search interval to around each progressively better solution. We stop when we've reached the maximum number of iterations (configurable).

The localization bit is simply the computation of the error. I could explain it, however I find that the code does so itself far better than I could hope to in words.

Issues

In my opinion, the code is a bit messy and slightly more difficult to read than I'd like. Similarly, I'm not sure how I feel about the nested loops. Of course, I don't want to overcomplicate things simply to get rid of nested loops, however if there's a nicer way to do this, I'm all ears.

It's also slow. This is Python, of course, so I shouldn't expect it to perform like a similarly implemented algorithm in, say, C/C++, however I'm certainly interested in increasing search speed.

Lastly, it's been a while since I've done anything in Python, so I'm interested in a critique of my style. The goal is readability, and not necessarily 'standards' compliance.

Tear it apart. Don't hold back!

import math
from dataclasses import dataclass
@dataclass
class Approximate:
 ai: float; af: float
 da: float; n : int
 # Default values
 aa: float = 0
 ei: float = -1
 a : float = 0
 e : float = 0
 i : int = 0
 done: bool = False
 stop: bool = False
 def step(self):
 if (self.ei < 0) or (self.ei > self.e):
 self.ei = self.e
 self.aa = self.a
 if (self.stop):
 self.i += 1
 if (self.i >= self.n):
 self.done = True
 self.a = self.aa
 return # Max iter
 # Restrict to window around 'solution'
 self.ai = self.aa - self.da
 self.af = self.aa + self.da
 self.a = self.ai
 # Increase accuracy
 self.da *= 0.1
 self.ai += self.da
 self.af -= self.da
 self.stop = False
 else:
 # Probe some points in [ai,af] with step da
 self.a = self.a + self.da
 if (self.a > self.af):
 self.a = self.af
 self.stop = True
def localize(recv):
 ax = Approximate(0, 5000, 32, 10)
 ay = Approximate(0, 5000, 32, 10)
 az = Approximate(0, 5000, 32, 10)
 dt = [0, 0, 0, 0]
 while not ax.done:
 ay = Approximate(0, 5000, 32, 10, 0, 0)
 while not ay.done:
 az = Approximate(0, 5000, 32, 10, 0, 0)
 while not az.done:
 for i in range(4):
 x = recv[i][0] - ax.a
 y = recv[i][1] - ay.a
 z = recv[i][2] - az.a
 baseline = math.sqrt((x * x) + (y * y) + (z * z))
 dt[i] = baseline / 299800000
 # Normalize times into deltas from zero
 baseline = min(dt[0], dt[1], dt[2], dt[3])
 for j in range(4):
 dt[j] -= baseline
 error = 0
 for k in range(4):
 error += math.fabs(recv[k][2] - dt[k])
 ay.e = error
 ax.e = error
 az.step()
 ay.step()
 ax.step()
 # Found solution
 print(ax.aa)
 print(ay.aa)
 print(az.aa)

• RootTwo: Sample input and output would be helpful.
• RootTwo: For a closed form solution (e.g., non-iterative) search for "Bancroft's Algorithm".
• Reinderien: Years later: why not just use scipy?

Answer 1

Remove empty lines after if/else. Remove empty lines in general, this has too many. Use the new math.dist. Add comments about how the approximation works. Add docstrings.

If you want to make it more readable, pull out sub-loops into functions. That reduces nesting depth, which is just too high here--it's a problem you don't run into often. Also, don't use names like 'ei'.

One approach to make it more readable (but maybe slower), rewrite 'approximate' as a function taking in: a function to compute, an interval to search, and a maximum number of iterations. Also, you could use scipy or another specialized package which has this built-in.

If you want to make it more readable AND fast, don't use this solution. Use some other maximization method, for example gradient descent. These are also available as prebuilt tools, so it should be readable.

Last, in this case, I think there is probably a very direct answer specific to the problem. Look up GPS algorithms, because this is more or less how they work (although the speed is always the speed of light)

• Zachary Vance: No, I don't know how gradient descent works. If you can take the derivative, do that--it looks like you should be able to here. I think you should be able to approximate the derivative by sampling at very small offsets around your current point, and dividing by the distance. Or since 3D is a low dimensionality, you can also just sample at offsets, move to the smallest, and repeat, without mucking with derivatives. This depends on avoiding local minima.