Package jmri.jmrix.rps

Class Ash2_2Algorithm

java.lang.Object

jmri.jmrix.rps.AbstractCalculator

jmri.jmrix.rps.Ash2_2Algorithm

All Implemented Interfaces:

Calculator

public class Ash2_2Algorithm
extends AbstractCalculator

Implementation of 2.1th 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.

RPSpos2.2 program description.

As in previous versions, 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 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 procedure 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 also computes the variance of the residual errors (differences between measured receiver distances and those from the computed position) which is used to monitor the progress of the iterative solution and it implements the rejection of the measurement with the largest residual when it is deemed to be an outlier. The second technique is not as fast as the first, but is ultimately more accurate.

The solution proceeds in seven stages, much like those in versions 2.0 and 2.1. Stage 0 does 50 One-At-A-Time iterations with the receivers in the sorted order. As in previous versions, it starts from a position far, far below any likely final point. Stage 1 continues the One-At-A-Time iterations with the receivers in reverse order. Every 50 such iterations the All-Together procedure is run to check the variance but not to reject outliers. The One-At-A-Time procedure usually converges in 20-50 iterations, however for occasional positions the convergence is much slower. The program moves on to the next stage after a total of 750 iterations, or sooner if it appears that no further improvement can be had. If the variance indicates that convergence has been achieved and there are no significant errors, then the program skips directly to Stage 6.

Stage 2 is where the outliers are rejected. This is only run when there are more than 6 receivers; if there are 5 or 6, Stage 3 is run instead; if 4 receivers, Stage 4 (sometimes). By this time a correct, but not particularly accurate, position should have been obtained. The One-At-A-Time technique is continued for an additional 200 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 iterations 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 should be quite accurate, at least for the measurements that are still in play. At this point the All-Together procedure is run to compute the variance and eliminate an outlier. Unlike version 2.1, the receiver with the largest residual error is always discarded--if it is actually OK, it will be put back in Stage 5. The entire stage-2 procedure is repeated until the number of receivers has been reduced to 6 or until the iteration count reaches 2000, then moves on to Stage 3.

Stages 3 and 5 are new to version 2.2. Stage 3 runs only with 6 and 5 receivers. It solves for all subsets with one receiver removed by running the One-At-A-Time iteration 250 times, with weights and fade-out, and then using All-Together to check the variances of the residuals. The receiver which was removed resulting in the subset with the smallest variance is then discarded as possibly being errored. Unlike the outlier rejection of Stage 2, which often discards the wrong receiver, this procedure usually gets it right. But it is too computationally intensive to use with a large number of receivers.

Stage 4 runs only with 4 receivers and rejects an "outlier" using the same procedure as Stage 2. However, it is only run if the variance is considerably more than just marginally large, i.e. not if there are only small random measurement errors. With one error in 4 receivers it is theoretically impossible to determine which one. But, what the heck, there's no harm in trying. And if it should happen to succeed in ousting the errored receiver and there are also previously-rejected good receivers that Stage 5 can put back, then the measurement is salvaged and the correct position is reported with no error code.

At this point we may be down to four receivers only (or perhaps three), but they should be all good receivers. Stage 5 runs the One-At-A-Time iteration 300 times, with weights and fade-out, and then the All-Together procedure to get a good solution with only the remaining receivers. Then all of the rejected receivers are checked to see if any of them agree with this solution and if so they are put back into the list of good receivers. The reason for doing this is that the outlier rejection often rejects the wrong receiver. Since this means we need to do this put-back anyway, Stages 2 to 4 are arranged to keep on rejecting receivers regardless of whether it does any good. But Stages 2 to 4 do check the variance and skip to this stage if it indicates that there are no more significant errors.

Stage 6 is similar to Stage 3 of version 2.1 except that it runs the One-At-A-Time iteration in addition to the All-Together iteration, both using weights according to distance, with the intent to produce a more refined result. First it runs the One-At-A-Time iteration 250 more times, with weights and fade-out, to make sure the solution is close since the All-Together iterations sometimes converge rather slowly. Unlike version 2.1, it does not attempt to discard outliers. The iterations continue until the All-Together procedure can do no more or until the total iteration count reaches 5000. (Note that a single instance of All-Together increments the iteration count by the number of receivers currently in use.)

Like version 2.1, this version does not always, or even usually, run through all the iterations, but instead cuts them short and also cuts out stages when the solution has converged. The total number of iterations is between 342 (with only 3 receivers) and 5000. The estimated execution time ranges from 0.13 to ~2.0 milliseconds (1.0 GHz Pentium III).

Input/output is the same as for previous versions and is described in the e-mail with version 1.0 sent on 11/17/06.

Return values are the same as with version 2.1. These are as follows.

 >= 4    OK.  Value = number of receivers used.
  3    Probably OK.  3 receivers used.
  1,2    Questionable.  Maybe OK, maybe not.
  0    No solution.  Don't even think about using it.  (Position outside the known universe.)
  -1,-2    Not used.
 <= -3    Variance of residuals too big.  Probably no good.  Value = minus number of receivers used.
 (Perhaps close if input is noisy or receiver locations are sloppy.)
 

Variance too big means RMS residuals > 30 microseconds, i.e. about 0.4 inch or 1.0 cm. This is about as small a threshold as I dare use lest random errors occasionally make good measurements appear bad.

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. These are described in the e-mail with that version sent on 12/9/06.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	Ash2_2Algorithm.RetVal	Internal class to handle return value.

Field Summary

Fields

Modifier and Type	Field	Description
static int	NERR
static int	NMAX
(package private) static int	offset
static int	SMAX
static int	TMAX
static int	TMIN
(package private) double	Vs
(package private) double	Xt
(package private) double	Yt
(package private) double	Zt

Fields inherited from class jmri.jmrix.rps.AbstractCalculator

nr, sensors, Tr, Xr, Yr, Zr

Constructor Summary

Constructors

Constructor	Description
Ash2_2Algorithm(javax.vecmath.Point3d[] sensors, double vsound)
Ash2_2Algorithm(javax.vecmath.Point3d[] sensors, double vsound, int offset)
Ash2_2Algorithm(javax.vecmath.Point3d sensor1, javax.vecmath.Point3d sensor2, javax.vecmath.Point3d sensor3, double vsound)
Ash2_2Algorithm(javax.vecmath.Point3d sensor1, javax.vecmath.Point3d sensor2, javax.vecmath.Point3d sensor3, javax.vecmath.Point3d sensor4, double vsound)

Method Summary

Modifier and Type	Method	Description
Measurement	convert(Reading r)
Measurement	convert(Reading r, javax.vecmath.Point3d guess)	Seed the conversion using an estimated position
Measurement	convert(Reading r, Measurement last)	Seed the conversion using a last measurement
(package private) Ash2_2Algorithm.RetVal	RPSpos(int nr, double[] Tr, double[] Xr, double[] Yr, double[] Zr, double Vs, double Xt, double Yt, double Zt)

Methods inherited from class jmri.jmrix.rps.AbstractCalculator

prep, summarize

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

Vs

double Vs

Xt

double Xt

Yt

double Yt

Zt

double Zt

offset

static int offset

TMAX

public static int TMAX

TMIN

public static int TMIN

SMAX

public static int SMAX

NMAX

public static int NMAX

NERR

public static int NERR

Constructor Detail

Ash2_2Algorithm

public Ash2_2Algorithm(javax.vecmath.Point3d[] sensors,
                       double vsound,
                       int offset)

Ash2_2Algorithm

public Ash2_2Algorithm(javax.vecmath.Point3d[] sensors,
                       double vsound)

Ash2_2Algorithm

public Ash2_2Algorithm(javax.vecmath.Point3d sensor1,
                       javax.vecmath.Point3d sensor2,
                       javax.vecmath.Point3d sensor3,
                       double vsound)

Ash2_2Algorithm

public Ash2_2Algorithm(javax.vecmath.Point3d sensor1,
                       javax.vecmath.Point3d sensor2,
                       javax.vecmath.Point3d sensor3,
                       javax.vecmath.Point3d sensor4,
                       double vsound)

Method Detail

convert

public Measurement convert(Reading r)

convert

public Measurement convert(Reading r,
                           javax.vecmath.Point3d guess)

Seed the conversion using an estimated position

convert

public Measurement convert(Reading r,
                           Measurement last)

Seed the conversion using a last measurement

RPSpos

Ash2_2Algorithm.RetVal RPSpos(int nr,
                              double[] Tr,
                              double[] Xr,
                              double[] Yr,
                              double[] Zr,
                              double Vs,
                              double Xt,
                              double Yt,
                              double Zt)