6
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Sample input and output would be helpful. \$\endgroup\$
    – RootTwo
    Commented Oct 24, 2020 at 6:35
  • \$\begingroup\$ For a closed form solution (e.g., non-iterative) search for "Bancroft's Algorithm". \$\endgroup\$
    – RootTwo
    Commented Apr 21, 2022 at 5:36
  • \$\begingroup\$ Years later: why not just use scipy? \$\endgroup\$
    – Reinderien
    Commented Aug 22, 2023 at 20:33

1 Answer 1

2
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 4, 2020 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.