Class Ash1_1Algorithm
 All Implemented Interfaces:
Calculator
public class Ash1_1Algorithm extends Object implements Calculator
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 nonplanar for the size of the measurement errors. The greater the errors, the greater the nonplanarity must be to avoid he bug.
I had hoped to be able to devise some measure of the nonplanarity 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 2050 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:
 The origin can be anywhere, but the zaxis must be vertical with positive z upward.
 In general, the transmitter should be below some or all of the receivers. How much below depends on the receiver configuration.
 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 linesofsight 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.
 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 nonplanar 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 nonplanar 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 inchesWalter's spec.), and large (+/2.5 inches) measurement errors. Half of the configurations consisted of a 10 x 20foot 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 rathersmall oval test track with 4 receivers and a 14foot square and an 8foot cube (mentioned above). Large, 100receiver configurations include a 25 x 10 x 5foot space with receivers randomly located throughout (rather unrealistic) and a 100 x 10 x 5foot 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 20footdiameter 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 closelyspaced 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

Constructor Summary
Constructors Constructor Description Ash1_1Algorithm(Point3d[] sensors, double vsound)
Ash1_1Algorithm(Point3d sensor1, Point3d sensor2, Point3d sensor3, double vsound)
Ash1_1Algorithm(Point3d sensor1, Point3d sensor2, Point3d sensor3, Point3d sensor4, double vsound)

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

Field Details

Vs
double Vs 
Xt
double Xt 
Yt
double Yt 
Zt
double Zt 
sensors

OFFSET
The following is the original algorithm, as provided by Ash as a C routine See Also:
 Constant Field Values

TMAX
 See Also:
 Constant Field Values

TMIN
 See Also:
 Constant Field Values

NMAX
 See Also:
 Constant Field Values

x
double x 
y
double y 
z
double z 
x0
double x0 
y0
double y0 
z0
double z0 
Rmax
double Rmax 
xi
double xi 
yi
double yi 
zi
double zi 
ri
double ri 
xj
double xj 
yj
double yj 
zj
double zj 
rj
double rj 
xk
double xk 
yk
double yk 
zk
double zk 
rk
double rk


Constructor Details

Ash1_1Algorithm

Ash1_1Algorithm

Ash1_1Algorithm
public Ash1_1Algorithm(Point3d sensor1, Point3d sensor2, Point3d sensor3, Point3d sensor4, double vsound)


Method Details

convert
 Specified by:
convert
in interfaceCalculator

convert
Seed the conversion using an estimated position Specified by:
convert
in interfaceCalculator

convert
Seed the conversion using a last measurement Specified by:
convert
in interfaceCalculator

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