Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-05-24
2003-09-02
Nguyen, Tan Q. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S215000, C342S357490
Reexamination Certificate
active
06615135
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to on-board, vehicle navigation systems, and more particularly, to such a system usable with a positioning system, such as a global positioning system (GPS), for accurately determining the position of a mobile receiver, such as a GPS receiver, by reducing relatively low and high frequency noise components corrupting the signals received from the GPS satellites using predictive and map-matching algorithms.
BACKGROUND OF THE INVENTION
On-board vehicle navigation systems often rely on the Global positioning System (GPS) for sensing an absolute or actual position of a vehicle hosting the on-board system. Such on-board navigation systems include a mobile GPS receiver installed in the vehicle, and typically integrated with a host of other sensors, such as an odometer and/or gyroscope. The mobile GPS receiver senses a vehicle position, referred to as a GPS position, based on signals received at the GPS receiver from a plurality of GPS satellites, as is known.
However, the accuracy of the GPS position suffers because of problems associated with multipath reflections of the GPS satellite signals, and from artificial accuracy degradation caused by Selective Availability (SA) resulting from military control of the GPS satellites. For example, SA can induce a positional error on the order of one-hundred meters, with a root-mean-square (RMS) error of approximately forty meters. In addition to the multipath and SA, clock jitter and transient loss-of-signal conditions further degrade GPS position accuracy.
U.S. Pat. No. 5,087,919 discloses one application of an on-board navigation system, wherein GPS positions from a GPS receiver are matched to street locations stored in a map database of the on-board system. The on-board system displays the map matched GPS positions along with map based topological information, such as a city street network. The system uses a two step process to match a GPS position with a street represented in the map database. First, the process identifies candidate streets represented in the map database within a predetermined distance of the GPS position. Second, beginning with the nearest candidate street, the process steps individually through the candidate streets to identify a candidate street having a heading or direction “substantially matching” a heading or travelling direction of the vehicle, determined based on the GPS positions.
Requiring a “substantial match” between the street and vehicle headings tends to be too strict or limiting a map matching criterion because it does not take into account error in the vehicle heading caused by the error or noise sources previously mentioned. Consequently, the map matching process unnecessarily eliminates a valid street (where the vehicle is actually located), and most likely all streets, from consideration when the vehicle heading and the valid street heading fail to meet the substantially matching criterion because of such error. On the other hand, if the criterion is substantially relaxed or significantly expanded to accommodate such error, the map matching process tends to erroneously select invalid streets where the vehicle is not located because the criterion is insufficiently selective.
Accordingly, in a map matching algorithm for matching a position of a receiver derived from a satellite signal with a probable position on a street represented in a map database, there is a need to reduce the probability that a valid street is eliminated from consideration because of a corrupted vehicle heading, and that an invalid street is erroneously selected.
Emergency vehicle applications of the on-board navigation system require a rapid, accurate response from the on-board navigation system. Emergency vehicle applications include navigation or fleet management of emergency vehicles, such as police and fire fighting vehicles, carrying the on-board navigation system. In such applications, it is highly desirable to associate the position of the emergency vehicle with a street on a city street network, within approximately five seconds after activating the GPS receiver in the on-board navigation system. The position indicated by the on-board system after five seconds, and typically displayed as mentioned above, must accurately associate the emergency vehicle with the correct street on which the vehicle is travelling, so as to reduce navigational errors and thus decrease emergency vehicle response time.
Accordingly, in an on-board navigation system including a GPS receiver, a need exists for rapidly and accurately associating a position derived by the GPS receiver with a position on a map, such as street position, within five seconds or less after activating the receiver.
On-board vehicle navigation systems commonly include a predictive filter, such as a Kalman Filter (KF), to improve the accuracy of the degraded GPS positions, and to integrate the GPS positions with information from the other sensors. As is known, the KF predictively filters a measured variable over time to derive expected or predicted values of the variable. For example, Kalman filters typically filter a series of GPS positions to derive a series of predicted positions of the GPS receiver. In deriving such predictions, the KF applies a weighing function, known as the Kalman gain, which is optimized by the Kalman filtering process to produce a minimum error variance. An important aspect of the KF includes adaptive adjustment of the Kalman gain responsive to continuous feedback of the error variance.
Importantly, the KF provides an accurate prediction only when the measured variable supplied to the KF is corrupted by uncorrelated or white noise. This means the noise corrupting consecutive measurements, such as consecutive GPS positions, must be uncorrelated for the KF to work effectively. Otherwise, correlated noise, inducing correlated error in the GPS positions, tends to throw the Kalman gain, and thus the predictions, off-track. Stated otherwise, if the noise corrupting the GPS positions has a time constant substantially greater than the time between consecutive GPS position measurements, then such low frequency noise tends to render the KF ineffective. As a result, the KF is ineffective at removing the relatively low frequency or slowly varying noise component from the GPS positions. On the other hand, in the absence of such low frequency noise, if the noise corrupting the GPS positions has a time constant on the order of, or less than, the time between consecutive GPS position measurements, then the KF arrives at accurate predictions. As a result, the KF can filter such a relatively high frequency or fast varying noise component from the GPS positions.
Because the KF responds favorably and unfavorably to high (uncorrelated) and low (correlated) frequency noise, respectively, it is instructive to broadly categorize the noise/errors due to Selective Availability, multipath, clock jitter, and transient-loss-of-signal as having high and/or low frequency noise components. Selective Availability has been empirically determined to vary slowly over hundreds of seconds, and is thus considered a low frequency error bias corrupting GPS positions, and consequently, KF predictions. This is especially true for modem GPS receivers that provide frequent GPS position updates, for example, once every second. The effects of multipath can vary drastically from second to second as the mobile GPS receiver travels quickly past, for example, buildings, trees, and bridges. On the other hand, multipath effects can vary slowly as the mobile receiver travels past, for example, large bodies of water. Multipath errors thus exhibit both low and high frequency noise components. Transient-loss-of-signal is considered to exhibit both low and high frequency noise components, while clock jitter is characteristically, only short term in nature.
U.S. Pat. No. 5,416,712 discloses a system for reducing correlated error corrupting GPS positions. The system includes a modified KF in combination with external sensors, such as an odometer
Lowe Hauptman & Gilman & Berner LLP
Nguyen Tan Q.
PRC Inc.
Tran Dalena
LandOfFree
Satellite based on-board vehicle navigation system including... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Satellite based on-board vehicle navigation system including..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Satellite based on-board vehicle navigation system including... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070182