Editing True-range multilateration (section)

== Solution methods ==
{{expand section|date=June 2017}}
''True-range multilateration'' algorithms may be partitioned based on 
* problem space dimension (generally, two or three), 
* problem space geometry (generally, Cartesian or spherical) and 
* presence of redundant measurements (more than the problem space dimension).
Any pseudo-range multilateration algorithm can be specialized for use with true-range multilateration. 

=== Two Cartesian dimensions, two measured slant ranges (trilateration) ===

[[File:2D Trilat Scenario 2019-0116.jpg|thumb|Fig. 1 2-D Cartesian true-range multilateration (trilateration) scenario. '''C1''' and '''C2''' are centers of circles having known separation <math>U</math>. '''P''' is point whose <math>(x,y)</math> coordinates are desired based on <math>U</math> and measured ranges <math>r_1</math> and <math>r_2</math>.]]

An analytic solution has likely been known for over 1,000 years, and is given in several texts.<ref name="Geyer" /> Moreover, one can easily adapt algorithms for a three dimensional Cartesian space.

The simplest algorithm employs analytic geometry and a station-based coordinate frame. Thus, consider the circle centers (or stations) '''C1''' and '''C2''' in Fig. 1 which have known coordinates (e.g., have already been surveyed) and thus whose separation <math>U</math> is known. The figure 'page' contains '''C1''' and '''C2'''. If a third 'point of interest' '''P''' (e.g., a vehicle or another point to be surveyed) is at unknown point <math>(x,y)</math>, then Pythagoras's theorem yields

: <math> \begin{align}
r_1^2 & = x^2 + y^2  \\[4pt]
r_2^2 & = (U-x)^2 + y^2
\end{align} </math>

Thus,  
{{NumBlk|::|
<math> \begin{align}
x & = \frac { r_1^2 - r_2^2 + U^2 } {2 U}   \\[4pt]
y & = \pm \sqrt{r_1^2 - x^2}
\end{align} </math>
|{{EquationRef|1}}}}

Note that <math>y</math> has two values (i.e., solution is ambiguous); this is usually not a problem. 

While there are many enhancements, Equation {{EquationNote|1}} is the most fundamental true-range multilateration relationship. Aircraft DME/DME navigation and the trilateration method of surveying are examples of its application. During World War II [[Oboe (navigation)|Oboe]] and during the Korean War [[SHORAN]] used the same principle to guide aircraft based on measured ranges to two ground stations. SHORAN was later used for off-shore oil exploration and for aerial surveying. The Australian Aerodist aerial survey system utilized 2-D Cartesian true-range multilateration.<ref name="Aerodist">[http://www.adastra.adastron.com/equip/aerodist.htm Adastra Aerial Surveys] retrieved Jan. 22, 2019.</ref>  This 2-D scenario is sufficiently important that the term ''trilateration'' is often applied to all applications involving a known baseline and two range measurements.

The baseline containing the centers of the circles is a line of symmetry. The correct and ambiguous solutions are perpendicular to and equally distant from (on opposite sides of) the baseline. Usually, the ambiguous solution is easily identified. For example, if '''P''' is a vehicle, any motion toward or away from the baseline will be opposite that of the ambiguous solution; thus, a crude measurement of vehicle heading is sufficient. A second example: surveyors are well aware of which side of the baseline that '''P''' lies. A third example: in applications where '''P''' is an aircraft and '''C1''' and '''C2''' are on the ground, the ambiguous solution is usually below ground.

If needed, the interior angles of triangle '''C1-C2-P''' can be found using the trigonometric [[law of cosines]]. Also, if needed, the coordinates of '''P''' can be expressed in a second, better-known coordinate system—e.g., the [[Universal Transverse Mercator coordinate system|Universal Transverse Mercator (UTM) system]]—provided the coordinates of '''C1''' and '''C2''' are known in that second system. Both are often done in surveying when the trilateration method is employed.<ref name="PSU">[https://www.e-education.psu.edu/natureofgeoinfo/c5_p12.html "The Nature of Geographic Information: Trilateration"], Pennsylvania State Univ., 2018.</ref> Once the coordinates of '''P''' are established, lines '''C1-P''' and '''C2-P''' can be used as new baselines, and additional points surveyed. Thus, large areas or distances can be surveyed based on multiple, smaller triangles—termed a ''traverse''.

An implied assumption for the above equation to be true is that <math>r_1</math> and <math>r_2</math> relate to the same position of '''P'''. When '''P''' is a vehicle, then typically <math>r_1</math> and <math>r_2</math> must be measured within a synchronization tolerance that depends on the vehicle speed and the allowable vehicle position error. Alternatively,  vehicle motion between range measurements may be accounted for, often by dead reckoning.

A trigonometric solution is also possible (side-side-side case). Also, a solution employing graphics is possible. A graphical solution is sometimes employed during real-time navigation, as an overlay on a map.

=== Three Cartesian dimensions, three measured slant ranges ===
[[File:3D Trilat Scenario 2019-0116.jpg|thumb|Fig. 2 3-D True-Range Multilateration Scenario. C1, C2 and C3 are known centers of spheres in the x,y plane. P is point whose (x,y,z) coordinates are desired based on its ranges to C1, C2 and C3.]]
[[File:3D Trilateration.jpg|thumb|right|220px|3-D '''Tri'''lateration limits the potential positions amount to two (here A or B)]]

There are multiple algorithms that solve the 3-D Cartesian true-range multilateration problem directly (i.e., in closed-form) – e.g., Fang.<ref name="Fang1">"Trilateration and extension to global positioning system navigation", B.T. Fang, ''Journal of Guidance, Control, and Dynamics'', vol. 9 (1986), pp 715–717.</ref>  Moreover, one can adopt closed-form algorithms developed for pseudo range [[multilateration]].<ref name="Sirola">"[https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=06995137cf1a12d6adf75b6e2246e44fe6c5aa6d Closed-form Algorithms in Mobile Positioning: Myths and Misconceptions]", Niilo Sirola, ''Proceedings of the 7th Workshop on Positioning, Navigation and Communication 2010 (WPNC'10)'', March 11, 2010.</ref><ref name="Geyer">{{cite book|last=Geyer|first=Michael|date=June 2016|title=Earth-Referenced Aircraft Navigation and Surveillance Analysis|url=https://rosap.ntl.bts.gov/view/dot/12301|location=U.S. DOT National Transportation Library|publisher=U.S. DOT John A. Volpe National Transportation Systems Center}}</ref> Bancroft's algorithm<ref name="Bancroft">[https://ieeexplore.ieee.org/search/searchresult.jsp?searchWithin=p_Authors:.QT.Bancroft,%20S..QT.&searchWithin=p_Author_Ids:37296953500&newsearch=true "An Algebraic Solution of the GPS Equations"], Stephen Bancroft, ''IEEE Transactions on Aerospace and Electronic Systems'', Volume: AES-21, Issue: 7 (Jan. 1985), pp 56–59.</ref> (adapted) employs vectors, which is an advantage in some situations.

The simplest algorithm corresponds to the sphere centers in Fig. 2. The figure 'page' is the plane containing '''C1''', '''C2''' and '''C3'''. If '''P''' is a 'point of interest' (e.g., vehicle) at <math>(x,y,z)</math>, then Pythagoras's theorem yields the slant ranges between '''P''' and the sphere centers:

: <math> \begin{align}
r_1^2 & = x^2 + y^2 + z^2  \\[4pt]
r_2^2 & = (x-U)^2 + y^2 + z^2  \\[4pt]
r_3^2 & = (x-V_x)^2 + (y-V_y)^2 + z^2
\end{align} </math>

Thus, the coordinates of '''P''' are:

{{NumBlk|::|
<math> \begin{align}
x & = \frac { r_1^2 - r_2^2 + U^2 } {2 U}   \\[4pt]
y & = \frac { r_1^2 - r_3^2 + V_x^2 + V_y^2 - 2 V_x x } {2 V_y}  \\[4pt]
z & = \pm \sqrt{r_1^2 - x^2 - y^2}
\end{align} </math>
|{{EquationRef|2}}}}

The plane containing the sphere centers is a plane of symmetry. The correct and ambiguous solutions are perpendicular to it and equally distant from it, on opposite sides.

Many applications of 3-D true-range multilateration involve short ranges—e.g., precision manufacturing.<ref name="Schneider" /> Integrating range measurement from three or more radars (e.g., FAA's [[ERAM]]) is a 3-D aircraft surveillance application. 3-D true-range multilateration has been used on an experimental basis with GPS satellites for aircraft navigation.<ref name="Zhang">[https://www.ucalgary.ca/engo_webdocs/GL/97.20112.ZNZhang.pdf ''Impact of Rubidium Clock Aiding on GPS Augmented Vehicular Navigation''], Zhaonian Zhang; University of Calgary; December, 1997.</ref> The requirement that an aircraft be equipped with an atomic clock precludes its general use. However, GPS receiver clock aiding is an area of active research, including aiding over a network. Thus, conclusions may change.<ref name="Langley2">[https://www.gpsworld.com/innovation-reducing-the-jitters/ "How a Chip-Scale Atomic Clock Can Help Mitigate Broadband Interference"]; Fang-Cheng Chan, Mathieu Joerger, Samer Khanafseh, Boris Pervan, and Ondrej Jakubov; ''GPS World --  Innovations''; May 2014.</ref> 3-D true-range multilateration was evaluated by the International Civil Aviation Organization as an aircraft landing system, but another technique was found to be more efficient.<ref name="Evans">[https://ieeexplore.ieee.org/document/5005109 "Microwave Landing System"]; Thomas E. Evans; ''IEEE Aerospace and Electronic Systems Magazine''; Vol. 1, Issue 5; May 1986.</ref> Accurately measuring the altitude of aircraft during approach and landing requires many ground stations along the flight path.

=== Two spherical dimensions, two or more measured spherical ranges ===
[[Image:Sun Moon (annotated).gif|right|thumb|300px|Fig. 3 Example of celestial navigation altitude intercept problem (lines of position are distorted by the map projection)]]
This is a classic celestial (or astronomical) navigation problem, termed the ''altitude intercept'' problem (Fig. 3). It's the spherical geometry equivalent of the trilateration method of surveying (although the distances involved are generally much larger). A solution at sea (not necessarily involving the Sun and Moon) was made possible by the [[marine chronometer]] (introduced in 1761) and the discovery of the 'line of position' (LOP) in 1837. The solution method now most taught at universities (e.g., U.S. Naval Academy) employs [[spherical trigonometry]] to solve an oblique spherical triangle based on [[sextant]] measurements of the 'altitude' of two heavenly bodies.<ref name="Todhunter">[https://www.gutenberg.org/files/19770/19770-pdf.pdf ''Spherical Trigonometry''], Isaac Todhunter, MacMillan; 5th edition, 1886.</ref><ref name="Casey">''A treatise on spherical trigonometry, and its application to geodesy and astronomy, with numerous examples'', John Casey, Dublin, Hodges, Figgis & Co., 1889.</ref> This problem can also be addressed using vector analysis.<ref name="Veness">[https://www.movable-type.co.uk/scripts/latlong-vectors.html "Vector-based geodesy"], Chris Veness. 2016.</ref> Historically, graphical techniques – e.g., the [[intercept method]] – were employed. These can accommodate more than two measured 'altitudes'. Owing to the difficulty of making measurements at sea, 3 to 5 'altitudes' are often recommended.

As the earth is better modeled as an ellipsoid of revolution than a sphere, iterative techniques may be used in modern implementations.<ref name="Kaplan">"STELLA (System To Estimate Latitude and Longitude Astronomically)", George Kaplan, John Bangert, Nancy Oliversen; U.S. Naval Observatory, 1999.</ref> In high-altitude aircraft and missiles, a celestial navigation subsystem is often integrated with an inertial navigation subsystem to perform automated navigation—e.g., U.S. Air Force [[Lockheed SR-71 Blackbird|SR-71 Blackbird]] and [[Northrop Grumman B-2 Spirit|B-2 Spirit]].

While intended as a 'spherical' pseudo range multilateration system, Loran-C has also been used as a 'spherical' true-range multilateration system by well-equipped users (e.g., Canadian Hydrographic Service).<ref name="Grant" /> This enabled the coverage area of a Loran-C station triad to be extended significantly (e.g., doubled or tripled) and the minimum number of available transmitters to be reduced from three to two. In modern aviation, slant ranges rather than spherical ranges are more often measured; however, when aircraft altitude is known, slant ranges are readily converted to spherical ranges.<ref name="Geyer" />

=== Redundant range measurements ===

When there are more range measurements available than there are problem dimensions, either from the same '''C1''' and '''C2''' (or '''C1''', '''C2''' and '''C3''') stations, or from additional stations, at least these benefits accrue: 
* 'Bad' measurements can be identified and rejected
* Ambiguous solutions can be identified automatically (i.e., without human involvement) -- requires an additional station
* Errors in 'good' measurements can be averaged, reducing their effect.

The iterative [[Gauss–Newton algorithm]] for solving [[non-linear least squares]] (NLLS) problems is generally preferred when there are more 'good' measurements than the minimum necessary. An important advantage of the Gauss–Newton method over many closed-form algorithms is that it treats range errors linearly, which is often their nature, thereby reducing the effect of range errors by averaging.<ref name="Sirola" /> The Gauss–Newton method may also be used with the minimum number of measured ranges. Since it is iterative, the Gauss–Newton method requires an initial solution estimate.

In 3-D Cartesian space, a fourth sphere eliminates the ambiguous solution that occurs with three ranges, provided its center is not co-planar with the first three. In 2-D Cartesian or spherical space, a third circle eliminates the ambiguous solution that occurs with two ranges, provided its center is not co-linear with the first two.

=== One-time application versus repetitive application ===

This article largely describes 'one-time' application of the true-range multilateration technique, which is the most basic use of the technique. With reference to Fig. 1, the characteristic of 'one-time' situations is that point '''P''' and at least one of '''C1''' and '''C2''' change from one application of the true-range multilateration technique to the next. This is appropriate for surveying, celestial navigation using manual sightings, and some aircraft DME/DME navigation.

However, in other situations, the true-range multilateration technique is applied repetitively (essentially continuously). In those situations, '''C1''' and '''C2''' (and perhaps '''Cn, n = 3,4,...''') remain constant and '''P''' is the same vehicle. Example applications (and selected intervals between measurements) are: multiple radar aircraft surveillance (5 and 12 seconds, depending upon radar coverage range), aerial surveying, Loran-C navigation with a high-accuracy user clock (roughly 0.1 seconds), and some aircraft DME/DME navigation (roughly 0.1 seconds). Generally, implementations for repetitive use: (a) employ a 'tracker' algorithm<ref name="Bar-Shalom">''Tracking and Data Fusion: A Handbook of Algorithms''; Y. Bar-Shalom, P.K. Willett, X. Tian; 2011</ref> (in addition to the multilateration solution algorithm), which enables measurements collected at different times to be compared and averaged in some manner; and (b) utilize an iterative solution algorithm, as they (b1) admit varying numbers of measurements (including redundant measurements) and (b2) inherently have an initial guess each time the solution algorithm is invoked.

=== Hybrid multilateration systems ===

Hybrid multilateration systems – those that are neither true-range nor pseudo range systems – are also possible. For example, in Fig. 1, if the circle centers are shifted to the left so that '''C1''' is at <math>x_1^\prime = - \tfrac{1}{2} U, y_1^\prime = 0</math> and '''C2''' is at <math>x_2^\prime = \tfrac{1}{2} U, y_2^\prime = 0</math> then the point of interest '''P''' is at

: <math> \begin{align}
x^\prime & = \frac { (r_1^\prime + r_2^\prime)(r_1^\prime - r_2^\prime) } {2 U}   \\[4pt]
y^\prime & = \pm \frac { \sqrt{ (r_1^\prime + r_2^\prime)^2 - U^2 } \sqrt{ U^2 - (r_1^\prime - r_2^\prime)^2 } } {2 U}
\end{align} </math>

This form of the solution explicitly depends on the sum and difference of <math>r_1^\prime</math> and <math>r_2^\prime</math> and does not require 'chaining' from the <math>x^\prime</math>-solution to the <math>y^\prime</math>-solution. It could be implemented as a true-range multilateration system by measuring <math>r_1^\prime</math> and <math>r_2^\prime</math>.

However, it could also be implemented as a hybrid multilateration system by measuring <math>r_1^\prime + r_2^\prime</math> and <math>r_1^\prime - r_2^\prime</math> using different equipment – e.g., for surveillance by a [[multistatic radar]] with one transmitter and two receivers (rather than two monostatic [[radar]]s). While eliminating one transmitter  is a benefit, there is a countervailing 'cost': the synchronization tolerance for the two stations becomes dependent on the propagation speed (typically, the speed of light) rather that the speed of point '''P''', in order to accurately measure both <math>r_1^\prime \pm r_2^\prime</math>.

While not implemented operationally, hybrid multilateration systems have been investigated for aircraft surveillance near airports and as a GPS navigation backup system for aviation.<ref name="Narins">[https://www.nap.edu/read/13292/chapter/13 "Alternative Position, Navigation, and Timing: The Need for Robust Radionavigation"]; M.J. Narins, L.V. Eldredge, P. Enge, S.C. Lo, M.J. Harrison, and R. Kenagy; Chapter in ''Global Navigation Satellite Systems''Joint Workshop of the National Academy of Engineering and the Chinese Academy of Engineering (2012).</ref>