Monday, July 4, 2016

Most Likely Position from 3 LOPs

Richard E. Rice and David Burch


This is an update of work done originally in 2012. We have used it in our classes but not published it. We revive it here with new examples and free apps for computation and experimentation with the solution. Details of the derivations are published in another format. The derivation applies to n LOPs with random and systematic variances. This example is three only, addressing the navigator's famous "cocked hat" problem.

Position fixes in navigation are inevitably determined by the intersection of two or more lines of position (LOP). When there are more than two LOPs, they will intersect in multiple places, and it is the job of the navigator to decide which point on the plot to consider the most likely position based on these intersections and anything else that might be known about the measurements. The most common scenario is to have three judiciously chosen LOPs,  each of which might be an average of several measurements.


   Practicing navigators have tended to choose the best position within the triangle of intersecting LOPs (cocked hat) as some central value of their choice, based on their experience and the actual sights at hand. In most cases this is an adequate solution, but in rare cases we might want to choose the best possible location based on all that we know about the three LOPs. These can be celestial sights, or they could be three compass or gyro bearing lines. More to the point, they could be two bearings of standard accuracy and a range line (transit) that can be a very accurate LOP,  or equivalently, one very good celestial sight and two that were not as good due to poor horizon or fewer sights in the sequence.
In short, if we are to apply more sophisticated analysis, we need to have enough extra data to justify it, including the individual uncertainties in each sight, assumed to be random errors that can be characterized  in terms of a standard deviation—and we must keep in mind that there could be a constant systematic error that applies to each of the sights. 
It can be shown that if the standard deviations of the sights are all the same (no one LOP better than another), and there is no systematic error that applies to all of them, then the most likely position is located at what is called the symmedian point of the triangle, which is discussed at length at online math resources. It is a bit tedious to plot this point, but worth noting that it is not any of the center points commonly used underway. These points can be quite different as the triangle becomes more acute (a poorer fix to begin with), but the overall assigned uncertainly is usually large enough to encompass this difference.

Figure 1. Several center points of a triangle. Gray, the centroid, is the intersection of any two medians, vertex to center of the opposite side. Red, the incenter,  is the intersection of any two bisectors of the angles. The symmedian point is the intersection of any two symmedians (S), found by reflecting the median lines (M) over the bisector lines (B). These points are discussed in the References at the end of this note.

Once you are convinced that the standard deviations are not the same, then the symmedian point is no longer correct. For example, if one line (of a terrestrial fix) is a navigational range (transit), then that should bias the fix toward that line, and the other two compass bearings are effectively just showing where you are on that line. 

We have developed a new solution to the most likely position that is relatively easy to evaluate by hand, and very easy to solve with a calculator or programmed function, a sample of which we provide below. The result for the most likely position can be written as:

P = q1Q1 + q2Q2 + q3Q3,
where  qi = si2 σi2 / Σ (sj2 σj2).

In this formalism the most likely point is determined from the sides of the triangle (si) and the standard deviation of each line (σi) without reference to the intersection angles. 
Consider a sample triangle of sides 10, 9, and 13 that have corresponding standard deviations of 1, 2, and 3. The units are arbitrary, chosen for convenience of measurement on the nautical chart or plotting sheet in use. Once the LOPs have been plotted, it is the task of the navigator to assign a standard deviation ("sigma") to each of the LOPs.
For a graphic solution, it is easiest to use rectilinear coordinates (x.y), as shown in Figure 2. The orientation of the coordinates is chosen to align with one of the LOPs, and the location of the third point is measured from the chart in the same units, (5.7, 6.9) in this case. In this example:

Σ (sj2 σj2) = 100 × 1 + 81 × 4 + 169 × 9 = 1945,

and
q1 = 100/1945 = 0.051, 
q2 = 324/1945 = 0.167,
q3 = 1521/1945 = 0.782.

Then with Q1 = (0, 0), Q2 = (13, 0), and Q3 = (5.7, 6.9), we get:
P = 0.051 × (0,0) + 0.167 × (13,0) + 0.782 × (5.7,6.9) 
  =  (0, 0) + (2.2, 0) + (4.5, 5.4) 
  =  (6.7, 5.4).

This process may seem complex at first glance, but that is tied in large part to the compact notation. After working a few examples the procedure becomes more fluid. This is the first solution we have seen that offers a fast practical way to answer this question accounting for different standard deviations in the LOPs.

Figure 2.  Most likely point P (6.7, 5.4) determined from three LOPs, without systematic error. The standard deviation (sigma) of each LOP is shown schematically to match the units chosen to measure the sides of the triangle from the chart. If the units were miles, a choice of incircle or centroid (they are about the same in this triangle) would be wrong by 3 miles.

Practical solutions

First, we could compute the location of the answer P as Px, Py, relative to the x-axis that runs along the s3 side (Q1 to Q2) using either a form or a spreadsheet as shown in Figure 3. 

Figure 3. Spreadsheet for solving most likely position.

With a blank form, we input the 3 sides and the 3 sigmas (yellow), then compute the A values and find B, the sum of these, then find the A/B values.

Doing it manually, we need to read or measure the location of Q3 (x3, y3), as shown in Figure 5. Note the x2 value is the same as s3, because with this approach we choose the x-axis along that line. Next we need to fill in the form with these quick multiplications and sums, and we end up with the answer Px, Py.

Download MLP-Form-333.pdf

Figure 4. Sample of the work form. The sample example is included as are optional ways that Px and Py show up based on the choice for Q1.

On the other hand, with this computation in a spreadsheet or simple app the computations can be automated, and we just enter the three sides and three sigmas and then Px, Py are computed automatically. Here is a free Windows app you can use to check your manual solution. It just solves for Px, Py as outlined above.

Download MLP.exe

A few examples of finding MLP manually with the form are given below. The plots were made in a navigation program.

Figure 5. Finding the x,y values of point Q3 of the example from Figure 2 using the divider tool in Expedition. Most navigation programs have a similar measurement or range and bearing tool. The triangle can be reproduced using the route tool.
Figures 5 and 6 show how the above example could be solved on the screen of a navigation program, either from the actual LOPs, or a reproduced triangle using a route tool.


Figure 6. Plotting the most likely position (Px,Py) using the divider tool. 

Celestial Navigation Example 1.

Below is an example of a cel nav fix with unequal standard deviations. It is one of some 160 fixes carried out on a 1982 ocean voyage by cel nav alone, documented in the book Hawaii by Sextant (HBS).

Figure 7. Celestial fix from 5 sights of Vega, 3 sights of Venus, and 2 sights of Polaris. The estimated sigmas based on the spread of the sights is given in Figure 7. The 3 LOPs selected for the fix were based on the fit slope method, described in the book. The length of the sides were based on the separation of the two Polaris sights, 4.2' = 4.2 nmi.

The data from these sights are presented in the the figure below, and then the position is plotted.

Figure 8. Data for the 3 LOPs of Figure 6.



Figure 8. Expanded plot of Figure 7 with the MLP plotted as a green circle.
The result is as might be expected, but definitely not the centroid nor the symmedian, which would be off by about 1 mile.  The fix is forced to the Venus line, which was very good, i.e., ±0.7' (approximately nautical miles), which is about as good as we can expect for cel nav, and then favoring the Venus-Vega intersection. The Polaris sight only served to pull the fix off of that intersection. Note, too, that the fit-slope method we recommend in our cel nav training is crucial to this type of analysis.

Celestial Navigation Example 2.

Here is another example, also from HBS, with a link to the background to getting the best triangle from the raw data. See Analysis of a Celestial Navigation Sight Session, which shows what we need to do before we ask for MLP.


Figure 9. Plot of Altair-Vega-Jupiter fix. The vertical scale is in miles. We see Q3 (2.5, 1.5) and MLP (1.9, 1.5) plotted.




Figure 10. MLP for Altair-Vega-Jupiter fix using our interactive MLP app (see download links, end of this note).  Just drag the corners of the triangle for different shapes, and add sigma and fixed errors digitally. The ellipses mark the 50% and 90% confidence distributions centered on the most likely position.

Once a fixed systematic error is applied to all sights, the direction of the LOPs makes a difference, which accounts for the arrowheads on the LOPs. With the above sights there were no known systematic errors so the directions did not matter. It is always best to take sights that are as close to 120º apart as this will minimize these fixed errors.  The interactive MPL app is a good way to study how these errors affect the MLP.


Compass Bearings Example 1.

Below is an example using compass bearing LOPs. These measurements are from Andrés Ruiz González  who is the author of Navigational AlgorithmsHe has made many valuable contributions to navigators, worldwide. He posted this data in the NavL discussion forum on Dec 16, 2010. The boat was not moving. The rough sigma estimates are my own, based on target distance off and an estimated bearing uncertainty of ± 1º, sigma = distance off x tan (1º). This was a hockey puck compass, which can be read to that precision, but we never know for sure with compass bearings and subsequent plotting, variation values, etc. The vessel icon marks his stationary position from GPS.






Figure 11. Compass bearing LOPs to targets with direction and distance off shown. The assigned sigma values are shown for each and shown schematically. The three sides (green, blue, red) are 0.15, 0.37, and 0.44 nmi). MLP (0.42, 0.02) is plotted as a yellow dot, relative to Q1 (0.36, 0.11). .

The plot looks complex with all of these annotations, but the three distances needed to solve for MLP takes just seconds once the triad of LOPs is plotted.  Below shows the solution for Px,Py by hand using the form and computed from the MLP app.  Using the form we need to measure location of Q3, shown in the figure in light magenta.


Figure 12. Solving MLP with a form and calculator(top),  or using the digital MLP app (bottom). With the form we need to measure Q3, but this is not needed in the app, or a programed solution. The sides are named for the opposite intersection.

Returning to the bearing fix in Figure 11, we see the MLP is more or less as expected., essentially at the intersection of the two best LOPs, with the third one just pulling it off a bit.  We learn more from the graphic app. 


Figure 13. The graphic solution showing MLP (black dot) and the symmedian (green dot). This version of the graphic app does not let us set digital values precisely, but the next version does. With this one we just drag corners to make a triangle and use the sliders to set sigma and fixed error.

The vessel location outside of the triangle is still within the 90% probability distribution of the data as interpreted and almost within the smaller 50% range. A small (negative) systematic error pushes the MLP toward the actual vessel location, as seen below.



Figure 14. Adding systematic errors. It appears that a positive fixed error is definitely in the wrong direction. The 0.08 nmi used here as a common error to each sight  (all scaled by x10) corresponds very roughly to 1º error over the average distance off of the targets (4.5 nmi).

We cannot be very conclusive on this specific fix without actual data for all sights, rather than just the three LOPs. However, these were taken by an experienced navigator, so even without the data recorded or available, there was certainly a mental averaging of the sights before they would be recorded, and the estimated sigmas are based on known variances in bearing LOPs. The experimental addition of a fixed error in Figures 13 and 14 do give some hint on possible further analysis—an operation that is figuratively like making a trial maneuver with ARPA!

 Since one of the targets was farther off than the other two, we might consider the two close ones as being valid LOPs and the farther one being an indicator of a fixed compass error, with the thought that the larger distance off exposed this error that we could not detect in bearings to the closer targets. We then assume we can estimate the fixed error by forcing the distant one to coincide with the closer ones. Then we correct the other two for this presumed fix error for a new triangle, as shown below.


Figure 15. Using a distant sight compared to closer ones to estimate a fixed error. This pushes the triangle in the right direction, but we could also see that from the graphic app solution. The offset of the distant sight (1º) was coincidentally the same as the sigma of the assumed random errors of each sight.


The other factor in bearing fixes is deviation. For careful work we need to confirm there is no deviation at the location we are when we take the sights. To check for this underway interrupts the voyage, namely we need to take a bearing a distant object standing in the same location as we swing ship. With no deviation, this bearing will remain constant on all headings. Since there are likely places to stand for such bearings, it is possible do check this ahead of time in local waters. It is more important on power-driven vessels than it is from the cockpit of a non-steel sailboat.

Many aspects of bearing fixes can be practiced in your own neighborhood or marina. For land based practice you can use Google Earth to make a chart. Just about any compass will serve for practice. An example is shown below using an iPhone compass. A quick way to estimate sigma is use the small angle rule, sigma (per degree) = distance off/60. In the above case we would get, for example, 3.5 nmi/60 = 0.06. In the example below the distances are in 10's of yards.

Compass Bearings Example 2.

Here is an example from taken another post on Compass Bearing Fixes, along with the data of the fix given in that link.


Figure 16. Bearing fix in the neighborhood. The green circle was an estimate of the sighting location plotted before the sights were taken. In retrospect, it would have been better to have been more precise documenting that at the time, which was possible, assuming integrity in the Google images. The red dot marks the MLP. The data are below. The sigmas were based on distance off and a 1º bearing uncertainty. This is discussed in the above link to this exercise, which includes the actual sight data, five sights of each target.


The linked article to compass bearing fixes outlines the role bearing fixes with discussion of optimizing accuracy and the affects of uncertainty.  The celestial fix link presented earlier does the same for cel nav sights.

What can be done with this formalism?

The interactive graphic app lets users investigate various configurations, with and without a fixed error. This lets us confirm mathematically what we know from practice, plus we learn more. For example, we know if one LOP is much better than the other two, then the fix is on that line and the other two just show us where on that line.
We can also demonstrate that if all sigma are the same and there is no fixed error, then the fix is at the symmedian point, or show that with three sights 120º apart, with the same sigmas, that a fixed error just makes the triangle larger, but the fix remains in the center of the triangle. Change that to three sights 60º apart and the fix is outside of the triangle, even though the triangle looks identical.
Practice with the app also makes us more aware of how important it is to have some estimate of the sigmas for each line, or at least to make a decision if they are about the same or one more uncertain.  This comes up in many phases of navigation. At sea the horizon could be poorer in one direction than the other, for example, or distorted by bright moon light. In piloting, we could have one bearing target less well defined than others, or we could have a range line (transit) for one of the LOPs which makes is very good, compared to compass bearings, and so on.
In short, the interactive MLP app can be used to train ones intuition about choosing the MLP, so that the actual computation would not add that much underway. We can always just state such things in the classroom, or tediously plot out the variations, but now we can just drag the triangles around and vary sigmas and fixed errors to practice.
We can also sometimes get indirectly an indication that there are errors we have missed. We can look at the probability distribution of the standard deviation and keep that in mind when we look at the app's graphic plot.  If we have a triangle that is notably larger than the sigmas would imply, then we have indication that we may have underestimated them or that there is a fixed error we did not know about.... or maybe one of the sights has errors we did not know about.
We also point that this formalism is easy to incorporate into any navigation program that is computing a fix from LOPs or sextant sights. The only new input that would be required is the sigmas for the individual targets. Then an effective radius of the 50% and 90% probability ellipses could also be computed and displayed.

Downloads

MLP work form:  MLP-Form-333.pdf  (for solving manually)

Stand alone digital solution, PC only: MLP.exe   (Enter 3 sides and 3 sigmas to get MLP relative to Q1)

Below are for graphically manipulating triangle and variances to see solution and probabilities; includes the digital solution as well. Must be online to run the apps.

Web based interactive graphic and digital solutions Mac beta:  MLP-Mac-beta11.app.zip

Web based interactive graphic and digital solutions Windows beta:  MLP-Win-beta11.zip

References

In one of the references at the end of the list from the Royal Institute of Navigation (RIN), the editor says "I don't ever want to see another paper on the cocked hat."  Maybe he is retired now.


00. Errors in Position Lines, Admiralty Manual of Navigation, Vol. 3 (1938), Chapter XIII. 

01. Accuracy of Position Finding Using Three or Four Lines of Position, S.A. Goudsmit, 1946, ION.

02. Stansfield, R. G. (1947). Journal of the Institute of Electrical Engineers, Vol. 94, Ilia, No. 15 , p. 762

03. Some Observations of Refraction at Low Altitudes and of Astronomical Position-line Accuracy, B. Chr. Peterson, 1952, RIN, Vol. V, No. 1, p. 31-38.

04. The Treatment of Navigational Errors, E. W. Anderson, 1952, ION, Vol. V, No. 2, p. 103-124.

05. The Treatment of Simultaneous Position Data in the Air, J. B. Parker, 1952, RIN, Vol. V, No. 3, p. 235-250.

06. Determining the Most Probable Position, J. B. Parker, 1953, RIN, Vol. VI, No. 1, p. 44-58.

07. Accuracy of Position Finding Using Three or Four Lines of Position, P. L. Nightingale, 1953, RIN, Vol. VI, No. 3, p. 321-324.

08. Estimating the Position, P. G. Redgment, 1953, RIN, Vol. VI, No. 3, p. 324-327.

09. The Use of Bisectors in Selecting the Most Probable Position, M. Bini, 1955, ION, Vol. VIII, No. 3, p. 195-204.

10. The Use of Bisectors, Alan Davies, 1956, RIN, Vol. IX, No. 3, p. 345-348.

11. The Cocked Hat, Charles H. Cotter, 1961, RIN, Vol. XIV, No. 2, p. 223-230.

12. The Cocked Hat, J. B. Parker, 1961, RIN, Vol. XIV, No. 4, p. 473-476.

13. Interpreting Astro-position Lines at Sea, M. W. Richey, 1962, RIN, Vol. 15, No. 3, p. 341-343.

14. Errors and Accuracy of Position, LOPS, and Fixes, T. R. Sternberg, 1963, ION, Vol. 10, No. 4, p. 379-394.

15. Contour-Based Position Lines, J. Garcia-Frias, 1967, RIN, Vol. 20, No. 2, p. 146-150.

16. On the 95 per cent Probability Circle of a Vessel’s Position - I (2 LOPs), T. Hiraiwa, 1967, RIN, Vol. 20, No. 3, p. 258-270.

17. The Franklin Piloting Technique, Ernest Brown and Byron Franklin, 1967, ION, Vol. 14, No. 2, p. 157-161. See also Bowditch, 1977, Section 1009.

18. Celestial Fix-lnternal or External?, Alton B. Moody, 1972, ION, Vol. 19, No. 4, p. 338-343.

19. Accuracy Contours for Horizontal Angle Position Lines, E. M. Goodwin and J. F. Kemp, 1973, RIN, Vol. 26, No. 4, p. 481-485.

20. Optimal Estimation of a Multi-Star Fix, C. DeWIT, 1974, ION, Vol. 21, No. 4, p. 320-325

21. 

22. On the 95 per cent Probability Circle of a Vessel’s Position - II (3 LOPs different sigma), T. Hiraiwa, 1980, RIN, Vol. 33, No. 2, p. 223-226.

23. Most Probable Fix Position Reduction, G. D. Morrison, 1981, ION, Vol. 28, No. 1, p. 1-8.

24. The Cocked Hat, L. Lee, 1991, RIN, Vol. 44, No. 3, p. 433-433.

25. The Cocked Hat, P. J. D. Gething, 1992, RIN, Vol. 45, No. 1, p. 143-143.

26. Random Cocked Hats, Ian Cook, 1993, RIN, Vol. 46, No. 1, p. 132-137.

___

27. A theorem of Jacobi and its generalization, Mark Berman, 1988, Biometrika, Vol. 75, No. 4, p. 779-83.

28. Wikipedia entry on symmdian point.

29. Wikipedia entry on triangles.

No comments: