Method and apparatus for maximum likelihood estimation direct integer search in differential carrier phase attitude determination systems

• US 5,296,861 A
• Filed: 11/13/1992
• Issued: 03/22/1994
• Est. Priority Date: 11/13/1992
• Status: Expired due to Term

• Current Assignee: Trimble Navigation Limited (Trimble Inc.)
• Original Assignee: Trimble Navigation Limited (Trimble Inc.)
• Inventors: Knight, Donald T.
• Primary Examiner(s): Blum, Theodore M.
• Application Number:
  US07/976,174
• Time in Patent Office: 494 Days
• Field of Search: 342/357, 342/442, 342/446, 342/451
• US Class Current: 342/357.38
• CPC Class Codes: G01S 19/55 Carrier phase ambiguity resolution; Floating ambiguity; LAMBDA [Least-squares AMBiguity Decorrelation Adjustment] method
• CPC Class Codes: G01S 3/46 using antennas spaced apart and measuring phase or time difference between signals therefrom, i.e. path-difference systems

Abstract

A method for comparing the relative phase of carrier signals received from GPS satellites to determine the roll, pitch and azimuth attitude of ships, aircraft, land vehicles, or survey instruments, accomplishes a maximum likelihood estimation (MLE) optimum solution over the full range of integers and vehicle attitudes. The problem is formulated as an MLE optimization, where vehicle attitude and integers are regarded as parameters to be adjusted to maximize probability of first-difference carrier phase measurements that are actually generated by hardware. Formulation results in weighted-fit error W as the objective criterion to minimize. A Kalman filter is introduced, having same objective criterion. Minimizing computation in Kalman filter leads to a decision tree for the integers. Two ways are shown to prune decision tree. The first is to exclude impossible combinations, such as those that produce an antenna upside down. The second is to generate a lower bound for W at each branch of the tree. A running sum is kept at each stage moving down the tree. When that sum exceeds a reasonableness bound or the current best W found elsewhere in the search, it is guaranteed that all subsequent integer combinations further down the current branch will produce a larger W and the remainder of the current branch can be cut off, speeding up the search.

Claims

1. An apparatus for determining a direction or heading in a reception environment that includes radio reflections, reception noise, antenna phase center motion, temperature-sensitive drifts and detected signal phase corruption, comprising:

a pair of GPS antennas separated by a known first physical distance that exceeds one wavelength of a radio carrier signal emitted by a GPS satellite for simultaneously receiving radio carrier signals emitted by radio transmitter in at least four corresponding GPS satellite each having a known position;

a pair of first and second phase coherent GPS correlators connected to the pair of GPS antennas and having respective first and second correlator outputs derived from said GPS satellite radio carrier signal as independently received by each of the pair of GPS antennas wherein said first and second correlator outputs include a phase difference representative of a phase difference that exists in the pair of GPS antennas for said GPS satellite radio carrier signal;

first computer means connected to the pair of first and second phase coherent GPS correlators for determining a first plurality of possible headings to a first of said GPS satellites based on a single first phase difference between said first and second correlator outputs for a first radio carrier signal from said first GPS satellite, wherein said first plurality of possible headings includes more than one possible heading due to whole cycle carrier phase ambiguities;

second computer means connected to the pair of first and second phase coherent GPS correlators for determining a second plurality of possible headings to a second of said GPS satellites based on a single second phase difference between said first and second correlator outputs for a second radio carrier signal from said second GPS satellite, wherein said second plurality of possible headings includes more than one possible heading due to whole cycle carrier phase ambiguities;

third computer means connected to the pair of first and second phase coherent GPS correlators for determining a third plurality of possible headings to a third of said GPS satellites based on a single third phase difference between said first and second correlator outputs for a third radio carrier signal from said third GPS satellite, wherein said third plurality of possible headings includes more than one possible heading due to whole cycle carrier phase ambiguities;

fourth computer means connected to the pair of first and second phase coherent GPS correlators for determining a fourth plurality of possible headings to a fourth of said GPS satellites based on a single fourth phase difference between said first and second correlator outputs for a fourth radio carrier signal from said fourth GPS satellite, wherein said fourth plurality of possible headings includes more than one possible heading due to whole cycle carrier phase ambiguities; and

simultaneous heading solution computer means connected to the first through fourth computer means for matching said first through said fourth pluralities of possible headings and for identifying at least one geometry for the pair of antennas that satisfies at least three of said first through fourth plurality of possible headings and eliminating any additional geometries for the pair of antennas that satisfies at least three of said first through fourth plurality of possible headings that have a less perfect fit to said respective geometries before identifying any geometry for the pair of antennas that satisfies four of said first through fourth plurality of possible headings.

2. The apparatus of claim 1, further comprising:

a single local oscillator connected to phase coherently drive the pair of first and second GPS correlators.

3. The apparatus of claim 1, further comprising:

fifth computer means connected to the pair of first and second phase coherent GPS correlators for determining a fifth plurality of possible headings to a fifth of said GPS satellites based on a single fifth phase difference between said first and second correlator outputs for a fifth radio carrier signal from said fifth GPS satellite, wherein said fifth plurality of possible headings includes more than one possible heading due to whole cycle carrier phase ambiguities; and

wherein the simultaneous heading solution computer means matches said first through said fifth pluralities of possible headings and identifies at least one geometry for the pair of antennas that satisfies at least three of said first through fifth plurality of possible headings and eliminates any additional geometries for the pair of antennas that satisfy at least three of said first through fifth plurality of possible headings that have a less perfect fit to said respective geometries before identifying any geometry for the pair of antennas that satisfies four of said first through fifth plurality of possible headings.

4. An apparatus for determining a direction or heading in a reception environment that includes radio reflections, reception noise, non-common antenna phase center motion, temperature-sensitive drifts and other corruption of detected signal phase, comprising:

a pair of GPS antennas for simultaneously receiving a plurality of radio carrier signals emitted by radio transmitters aboard a plurality of GPS satellites wherein the pair of antennas are separated by a known physical distance that exceeds one wavelength of said radio carrier signals;

a pair of first and second correlators having respective first and second correlator outputs derived from said GPS satellite radio carrier signals as received by each of the pair of GPS antennas;

means for coherently driving the pair of first and second correlators and for obtaining a phase difference that exists between said first and second correlator outputs responsive to said GPS satellite radio carrier signals and said separation of the pair of GPS antennas;

first computer means connected to the pair of first and second phase coherent GPS correlators for determining a plurality of possible unambiguous carrier phase differences between said first and second correlator outputs for each respectively received GPS satellite radio carrier signal, wherein all the possible unambiguous carrier phase differences of any given received signal include a single common whole cycle ambiguity integer;

second computer means connected to the pair of first and second phase coherent GPS correlators for determining a unique combination of unambiguous carrier phase differences, from among all possible combinations inclusive of all said received GPS satellite radio carrier signals, having a superior heading solution fit with said unambiguous carrier phase differences compared to all other possible combinations likewise inclusive of all said received GPS satellite radio carrier signals; and

third computer means connected to the pair of first and second phase coherent GPS correlators for determining direction or heading based on said unambiguous carrier phase differences of a best-fit combination inclusive of all said received GPS satellite radio carrier signals.

5. The apparatus of claim 4, wherein:

the first, second and third computer means each include means to determine combinations of unambiguous carrier phase differences that exclude one or more of said received GPS satellite radio carrier signals, and in cases where said exclusive combination exhibits a weighted-fit error that exceeds another combination error inclusive of all said received GPS satellite radio carrier signals, the first, second and third computer means avoid evaluating of all other combinations, inclusive or exclusive, that contain said present exclusive combination as a smaller part, wherein the detection of an exclusive combination with weighted-fit error that exceeds a predetermined maximum value does not further process larger combinations that contain said present exclusive combination.

6. A computer-implemented method for determining a navigational heading in a reception environment that includes radio reflections, reception noise, antenna phase center motion, temperature-sensitive drifts and detected signal phase corruption, the method comprising the steps of:

inputting phase measurement data from a set of GPS correlators connected to a trio of GPS antennas mounted to a vehicle and separated from one another by more than one GPS carrier frequency wavelength and having a phase output measurement subject to whole-cycle carrier phase ambiguity;

calculating in a computer connected to said GPS correlators a maximum likelihood estimation (MLE) optimization procedure expressible in computer program pseudocode as;

space="preserve" listing-type="tabular">______________________________________ -x.sub.0 = 0 U.sub.0 = 0 W.sub.best = W.sub.max for n.sub.1 = from.sub.1 . . . to.sub.1 do begin y.sub.1 = (θ

.sub.1 + n.sub.1) - H.sub.1 -x.sub.0 U.sub.1 = U.sub.0 + y.sub.1.sup.2 /v.sub.1 if (U.sub.1 <

W.sub.best) then .sup. begin .sup. -x.sub.1 = -x.sub.0 + K.sub.1 y.sub.1 .sup. for n.sub.2 = from.sub.2 . . . to.sub.2 do begin y.sub.2 = (θ

.sub.2 + n.sub.2) - H.sub.2 - x.sub.1 U.sub.2 = U.sub.1 + y.sub.2.sup.2 /v.sub.2 if (U.sub.2 <

W.sub.best) then begin -x.sub.2 = -x.sub.1 + K.sub.2 y.sub.2 . . . for n.sub.m = from.sub.m . . . to.sub.m do begin y.sub.m = (θ

.sub.m + n.sub.m) - H.sub.m -x.sub.m-1 U.sub.m = U.sub.m-1 + y.sub.m.sup.2 /v.sub.m if (U.sub.m <

W.sub.best) then begin -x.sub.best = -x.sub.m-1 + K.sub.m y.sub.m -n.sub.best = (n.sub.1, n.sub.2, . . . , n.sub.m) W.sub.best = U.sub.m end end end end .sup. end end ______________________________________

where θ

_i are first-difference carrier phase measurements derived from said phase coherent GPS correlators, U_i is a weighted-fit error that appears at a stage "i" of a tree, W_best is a best weighted-fit error, from₁...to₁, from₂...to₂ through from_m...to_m are the outer limits of whole cycle carrier ambiguities, H_i =[LOS_i |1] is an observation matrix containing a line-of-sight unit vector that points into a direction of a GPS signal arrival, and where v_i and K_i are pre-computed, wherein a final integer combination is selected on the basis of a best fit with the measured carrier phase, as indicated by a weighted-fit error, and X-_best, n_best, and W_best, represent a desired optimum antenna position, an integer combination and an associated weighted-fit error;

determining a range of integers that are possible for a first baseline drawn between two of said GPS antennas, given only the known constraints on vehicle roll and pitch, wherein only a small range of integers is possible if said vehicle cannot roll or pitch significantly relative to any GPS satellites that are substantially vertically overhead;

processing all phase measurements from a shortest baseline between said GPS antennas to determine a first-antenna position, searching a range of integers determined in the previous step using a four-state filter that solves in geodetic coordinates for a single antenna position and a single cable bias;

verifying that antenna vertical coordinates are within a limit set by a maximum vehicle roll and pitch for integer combinations that survive the previous step;

verifying that the baselength computed from said antenna coordinates matches a known baselength to within a noise tolerance;

using said known baselength as a reference measurement and normalizing an antenna position vector to unit length to serve as Kalman observation matrix H, and assigning a measurement variance R to cover a non-linearity that results from H being slightly perturbed by noise in the phase measurements from said GPS correlators;

if said integer combination and antenna coordinate survive to this step, calculating an arc of coordinates that are possible for a second antenna, assuming that said first antenna coordinate is true, and determining a range of integers that are possible for said second baseline, while adding a margin to allow for a phase measurement noise;

processing all phase measurements of said second baseline to determine a second antenna position;

verifying that a surviving one of said antenna vertical coordinates is within a limit set by a maximum vehicle roll and pitch;

verifying that a baselength computed from a second antenna coordinates matches a known baselength to within a noise tolerance;

verifying that an included angle relative to a first antenna agrees with a known angle q to within a noise tolerance;

using a known baselength of said second baseline as a very accurate measurement, a measurement variance R is assigned to cover a non-linearity, accumulating U with this measurement and abandoning a search at any step where U exceeds W_best ;

computing a Y-axis of a reference antenna coordinate system by normalizing a second antenna position vector, which yields a vector of unit length, in geodetic coordinates, that points along the roll axis of an antenna coordinate system, and determines two degrees of freedom of this coordinate frame, wherein the other antenna position determines a plane containing both antenna baselines and a Z-axis of said antenna coordinate system is defined to be normal to this plane, with a polarity chosen in such a way that the Z-axis always points somewhere toward the sky;

determining whether any GPS satellite line-of-sight vectors lie below said X-Y plane, wherein valid phase measurements are not possible for signal direction of arrival that is below the antenna ground plane and where a cutoff angle of -5°

is used to allow for noise in a frame orientation, and to allow a margin for low-elevation gain;

mechanizing a five-state filter for small roll, pitch and yaw angles that rotate this frame into an antenna orientation that yields a closest agreement with measured phase, wherein closest agreement is equivalent to minimum weighted-fit error W using eight phase measurements;

comparing W from with a best W, if the new W is better, then updating W_best and saving this set of integers and associated attitude as a MLE optimum;

continuing to search until all integer combinations have been exhausted; and

outputting a value representing the relative attitude of said baselines drawn among said GPS antennas.

7. The method of claim 6, wherein:

said v_i and K_i are pre-computed in said computer in a computer-implemented method expressible in computer program pseudocode as;

space="preserve" listing-type="tabular">______________________________________ -x.sub.0 = 0 P.sub.0 = diag (∞

, ∞

, ∞

, R.sub.b) for i = 1 . . . m do begin y.sub.i = (θ

.sub.1 + n.sub.i) - H.sub.i -x.sub.i-1 v.sub.i = H.sub.i P.sub.i-1 H.sub.i.sup.T + R.sub.i K.sub.i = P.sub.i-1 H.sub.i.sup.T /v.sub.i -x = -x.sub.i-1 + K.sub.i y.sub.i P.sub.i = (I - K.sub.i H.sub.i)P.sub.i-1 end. ______________________________________