Class Ash2_0Algorithm

  • All Implemented Interfaces:
    Calculator

    public class Ash2_0Algorithm
    extends AbstractCalculator
    Implementation of 2nd 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. Here is a summary of the features of the new program from Robert Ashenfelter:

    1. It is completely iterative. No more exact solutions for sets of three receivers. No more weighted averages of such solutions.
    2. Although both the old and the new versions can accept an unlimited number of receivers, the old version only processes a maximum of 15 while the new version processes up to 50.
    3. The accuracy of the new version is approximately the same as for the old version, perhaps marginally better. However for more than 15 receivers it is significantly better.
    4. It has been designed to specifically reject receiver measurements with gross errors, i.e. those which are so large that there is no possible position solution when they are combined with other measurements. It does so much better than version 1.1. (However, version 1.1 has deficiencies in this regard and is not as good at this as version 1.0.)
    5. It is slightly faster.
    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, now set at 50.

    Next it discards those receivers with gross measurement errors. All possible pairs of receivers are checked to see if the sum of their measured ranges is less than, or the difference is greater than, the distance between the receivers. Counts are maintained for each receiver and the one with the largest count is booted out. The proceedure is repeated until there are no more failures. If fewer than three receivers are left there can be no solution and an error code is returned.

    Two iterative techniques are used which I call "One-At-A-Time" and "All-Together." The first 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. This simple technique usually converges quite rapidly. The second technique accumulates the adjustments for all receivers and then computes and applies an average for all. It is not as fast but is ultimately more accurate.

    The solution proceeds in four stages, the first two of which are like the preliminary solution in version 1.1. Stage 0 does 50 One-At-A-Time iterations with the receivers in the sorted order. As in version 1.1, it starts from a position far, far below any likely final point. Stage 1 continues with the receivers chosen at random until it has iterated 1000 times. The procedure usually converges in 20-50 iterations, however 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.

    Stage 2 continues the One-At-A-Time technique for an additional 250 iterations with the receivers in reverse order ending with the closest receiver. Weights are applied assuming that close measurements are more accurate than distant ones. The weights fade out during the stage so that at the end the adjustments are very small. This fade-out fixes a problem with the One-At-A-Time technique in that it gives undue weight to the last receiver. The result at this point is quite good and the program could well stop here but it doesn't. Stage 3 runs the All-Together iteration 15 times, also using weights according to distance, to produce a more refined result.

    The program always runs through all the iterations regardless of how fast or slow the solution converges. Only at the end does it compute the variance of the residuals (differences between measured receiver distances and those from the computed position) to check the result. The execution time ranges from 0.8 millisecond with 3 receivers to 1.3 millisecond with 50 or more receivers (1.0 GHz Pentium III).

    Input/output is the same as for versions 1.0 and 1.1. As before, the function returns 0 if all seems well and 1 if there are fewer than 3 usable receivers (with the reported position outside the known universe). A return value of 2 indicates that the variance of the residuals exceeds a fixed threshold so the reported position is questionable. The threshold is set at 30 microseconds which is equivalent to a standard deviation of 0.4 inch or 1.0 cm. This is about as small as I dare set it. Usually the reported position is garbage (because of errors in the input data) when the return value is 2, but it could be close if the input is merely excessively noisy. Likewise, the reported position is usally OK when the return value is 0 but this cannot be guaranteed. After all, errors in the data could happen to mimic good values for a wrong position. These return values tend to less reliable when the program is overloaded with too many large errors.

    The restrictions on the configuration of transmitters and receivers, necessary to prevent the program from reporting a spurious position, are the same as those for version 1.1.

    As before, I have tested the program with a large number of different receiver configurations having from 3 to 100 receivers and with many transmitter locations. In addition to small random measurement errors, I have added the simulation of large errors to the tests. To simulate such an error, I pick a random receiver and replace its time delay with a random value between 0 and 35,000 microseconds (equivalent to 0 to 40 feet). Depending on the configuration, this may result in a gross error or the error may be too small for this but still so large as to cause the solution to fail. Some results for four receivers and one large error are that with Larry's small initial test layout the program rejects the error and computes a correct position 90% of the time, while with a more-typical layout it may be only 50%. Performance improves to 80% correct for the typical layout with six receivers.