Class Ash1_1Algorithm

  • All Implemented Interfaces:
    Calculator

    public class Ash1_1Algorithm
    extends java.lang.Object
    implements Calculator
    Implementation of version 1.1 algorithm for reducing Readings

    This algorithm was provided by Robert Ashenfelter based in part on the work of Ralph Bucher in his paper "Exact Solution for Three Dimensional Hyperbolic Positioning Algorithm and Synthesizable VHDL Model for Hardware Implementation".

    Neither Ashenfelter nor Bucher provide any guarantee as to the intellectual property status of this algorithm. Use it at your own risk. The following is a summary of this version from Robert Ashenfelter:

    When the receivers are in a plane or nearly so there is a spurious solution on the other side of the plane from the correct solution and in certain situations the version 1.0 program may choose the wrong solution.

    It turns out that those situations are when the receiver configuration is not sufficiently non-planar for the size of the measurement errors. The greater the errors, the greater the non-planarity must be to avoid he bug.

    I had hoped to be able to devise some measure of the non-planarity of the receiver configuration and to set some threshold below which the program would switch to a different algorithm but this didn't seem to be working out very well. After trying several things, I have chosen to use an iterative procedure to determine an approximate solution.

    Here is a description of the new program.

    As before the first thing it does is sort the receivers in order of increasing time delay, discarding those that failed or are too far or too near, and using the closest ones. There is a maximum that are used, still set at 15.

    Next it computes a preliminary transmitter position which is used to discriminate against spurious solutions and to compute weights. This is the part of the program that has been changed to fix the bug. The new algorithm looks at one receiver at a time and moves the estimated position directly toward or away from it such that the distance is equal to the measured value. After going through the receivers once in order, it then chooses them at random until it has iterated some fixed number of times. This is set at 1000 although the procedure usually converges in 20-50 iterations; for occasional positions the convergence is much slower. The random order is used because the procedure was occasionally observed to get stuck in a loop when using a repetitive fixed order. Rather than start with the origin as the initial position, it now starts from a position far, far below. This removes the restriction that the origin must be below the receivers.

    Finally, as before, the transmitter position is computed as a weighted average of the GPS solutions for all possible sets of three receivers. (For 15 receivers, that's 455 solutions.) The weights are the same as before. Unless one of them chooses a spurious solution, both versions of the program produce the same computed position.

    Restrictions:

    1. The origin can be anywhere, but the z-axis must be vertical with positive z upward.
    2. In general, the transmitter should be below some or all of the receivers. How much below depends on the receiver configuration.
    3. If the receivers are in a plane, or nearly so, the transmitter must absolutely be below the plane. As it approaches the plane (such that the lines-of-sight to the receivers make shallow angles with respect to the plane), the accuracy degrades and ultimately the program may report failure. If above the plane, the program reports incorrect positions.
    4. If the receivers are not in a plane, it may be possible to move the transmitter up among them. In general it should remain inside or below the volume of space contained by the receivers. However if the configuration is sufficiently non-planar the transmitter can go farther. But the limits are uncertain and there is no warning as it approaches a limit; the reported position suddenly jumps to somewhere else, or perhaps it jumps back and forth depending on measurement errors. An extreme example is 8 receivers at the corners of a cube, which is about as non-planar as it gets. In this case the transmitter can go outside the cube by several times the width of the cube, both laterally and vertically, before the program gets into trouble.

    I have tested the program with nearly 20 different receiver configurations having from 3 to 100 receivers. Most were tested at 60 or more transmitter locations and with infinitesimal, nominal (+/-0.25 inches--Walter's spec.), and large (+/-2.5 inches) measurement errors. Half of the configurations consisted of a 10 x 20-foot room with the ceiling 5 feet above the lowest transmitter positions and the receivers (from 3 to 18) located on the walls and/or ceiling. Other configurations are Larry Wade's rather-small oval test track with 4 receivers and a 14-foot square and an 8-foot cube (mentioned above). Large, 100-receiver configurations include a 25 x 10 x 5-foot space with receivers randomly located throughout (rather unrealistic) and a 100 x 10 x 5-foot space with receivers arranged in 4 rows of 25, one row on each long wall and two rows on the ceiling. Performance (i.e. accuracy of the measured transmitter position) is excellent throughout this latter space.

    Two other configurations are 20-foot-diameter geodesic domes with receivers located at the vertices of the triangular faces of the domes, one with 16 receivers and one with 46. Performance is good throughout the interior of these domes, but surprisingly it is no better with 46 receivers than with 16, near the perimeter a bit worse. Presumably this is because of the limited number of closest receivers used by the position program. In order to do justice to this, or any other configuration with closely-spaced receivers, the program needs to use data from more than the 15 receivers currently used.

    As a result of all this testing, I feel pretty confident that version 1.1 works reliably if used within the restrictions listed above. But the disclaimer about "usability and correctness" stays.

    The execution time is increased a little by all those iterations. It now ranges from 0.5 millisecond with 3 receivers to 1.9 millisecond with 15 or more receivers (1.0 GHz Pentium III).

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) static class  Ash1_1Algorithm.RetVal
      Internal class to handle return value.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static int NMAX  
      (package private) static int OFFSET
      The following is the original algorithm, as provided by Ash as a C routine
      (package private) double ri  
      (package private) double rj  
      (package private) double rk  
      (package private) double Rmax  
      (package private) Point3d[] sensors  
      (package private) static int TMAX  
      (package private) static int TMIN  
      (package private) double Vs  
      (package private) double x  
      (package private) double x0  
      (package private) double xi  
      (package private) double xj  
      (package private) double xk  
      (package private) double Xt  
      (package private) double y  
      (package private) double y0  
      (package private) double yi  
      (package private) double yj  
      (package private) double yk  
      (package private) double Yt  
      (package private) double z  
      (package private) double z0  
      (package private) double zi  
      (package private) double zj  
      (package private) double zk  
      (package private) double Zt