Vehicle navigational system and method

A vehicle navigational system and method for tracking a vehicle, including a programmed computer, sensors for sensing the distance traveled and heading of the vehicle, and a stored map data base identifying a map of an area over which the vehicle is moving, in which the computer calculates and advances dead reckoned positions of the vehicle in response to distance and heading data, provides data identifying a contour of equal probability containing the dead reckoned positions and having a probability of containing the actual location of the vehicle, derives multiparameters from the map data base, and updates a given dead reckoned position and the contour using a highly developed vehicle navigational algorithm if a more probable dead reckoned position exists based upon the given dead reckoned position, the contour and the derived multi-parameters.

FIELD OF THE INVENTION 
The present invention relates generally to an apparatus and method for 
providing information to improve the accuracy of tracking vehicles movable 
primarily over streets, as well as to an automatic vehicle navigational 
system and method for tracking the vehicles as they move over the streets. 
A portion of the disclosure of this patent document contains materials to 
which a claim of copyright protection is made. The copyright owner has no 
objection to the facsimile reproduction by anyone of the patent document 
or the patent disclosure, as it appears in the Patent and Trademark Office 
patent file or records, but reserves all other rights whatsoever. 
BACKGROUND OF THE INVENTION 
A variety of automatic vehicle navigational systems has been developed and 
used to provide information about the actual location of a vehicle as it 
moves over streets. A common purpose of the vehicle navigational systems 
is to maintain automatically knowledge of the actual location of the 
vehicle at all times as it traverses the streets (i.e., track the 
vehicle). A given navigational system may be utilized in the vehicle to 
provide the vehicle operator with knowledge of the location of the vehicle 
and/or at a central monitoring station that may monitor the location of 
one or more vehicles. 
For example, one general approach to such vehicle navigational systems is 
known as "dead reckoning", in which the vehicle is tracked by advancing a 
"dead reckoned position" from measured distances and courses or headings. 
A system based upon dead reckoning principles may, for example, detect the 
distance traveled and heading of the vehicle using distance and heading 
sensors on the vehicle. These distance and heading data are then processed 
by, for example, a computer using known equations to calculate 
periodically a dead reckoned position DRP of the vehicle. As the vehicle 
moves along a street, an old dead reckoned position DRP.sub.o is advanced 
to a new or current dead reckoned position DRP.sub.c in response to the 
distance and heading data being provided by the sensors. 
One problem with prior systems using dead reckoning is the accumulation of 
error that occurs as the dead reckoned positions are advanced. This error 
occurs, in part, as a result of inherent limitations on the achievable 
accuracy of the distance and heading sensors, which thus provide data that 
do not precisely identify the distance traveled nor the heading of the 
vehicle. Unless compensation for this error is made, the dead reckoned 
positions will become increasingly imprecise or inaccurate. 
Prior dead reckoning vehicle navigational systems have been developed and 
have attempted to solve this problem of the accumulation of error by 
providing additional information to the dead reckoned positions. 
Generally, the additional information may be a map corresponding to the 
streets of a given area over which the vehicle may be moving. The map is 
stored in memory as a map data base and is accessed by the computer to 
process this stored information in relation to the dead reckoned 
positions. 
U.S. Pat. No. 3,789,198, issued Jan. 29, 1974, discloses a vehicle location 
monitoring system using dead reckoning for tracking motor vehicles, 
including a technique for compensating for accumulated errors in the dead 
reckoned positions. In this system, a computer accesses a stored map data 
base, which is a table or array having a 2-dimensional, orthogonal grid of 
entries of coordinates X.sub.st Y.sub.st that may or may not correspond to 
driveable surfaces, such as streets St. Storage locations in the array 
that correspond to streets are indicated by a logic 1, while all other 
storage locations are filled with a logic 0. 
In accordance with a vehicle navigational algorithm of the patent, a dead 
reckoned position DRP of the vehicle is periodically calculated, which 
position DRP is identified and temporarily stored in the computer as 
coordinates X.sub.old Y.sub.old. Then, to compensate for the accumulated 
error, the array is interrogated at a location corresponding to the 
coordinates X.sub.old Y.sub.old. If a logic 1 is found, the vehicle is 
defined as corresponding to a known driveable surface and no correction is 
made. If a logic 0 is found, representing no driveable surface, adjacent 
entries in the array are interrogated, as specifically described in the 
patent. If a logic 1 is then found at one of these adjacent entries, 
coordinates X.sub.old Y.sub.old are corrected or updated to coordinates 
X.sub.st Y.sub.st corresponding to the logic 1 that was found, and these 
latter coordinates then become X.sub.old Y.sub.old to advance the dead 
reckoned position. If no logic 1 is found after such interrogations, then 
no change is made to the original X.sub.old Y.sub. old and the 
corresponding dead reckoned position DRP is advanced. 
Another example of an automatic vehicle navigational system that uses a map 
data base to correct for the accumulation of errors in tracking a vehicle 
is disclosed in a publication entitled "Landfall: A High Resolution 
Vehicle-Location System", by D. King, GEC Journal of Science and 
Technology, Vol. 45, No. 1, 1978, pages 34-44. As described in the 
publication, the term Landfall is an acronym for Links and Nodes Database 
For Automatic Landvehicle Location, in which a stored map data base 
comprises roads (links) that are interconnected by junctions (nodes) 
having inlet/outlet ports. Thus, any mapped area is regarded merely as a 
network of nodes, each containing a number of inlet/outlet ports, and 
interconnected links. 
The publication describes the basic vehicle navigational algorithm used 
under the Landfall principle by assuming that a vehicle is on a road or 
link moving toward a node which it will enter by an input port. As the 
vehicle moves forward, the motion is detected by a distance encoder and 
the "distance-to-go", i.e., the distance to go to the next node, is 
decremented until it becomes zero, corresponding to the entry point of the 
input port of such a node. Then, as the vehicle exits one of several 
output ports of the node, a change of heading of the vehicle at the exit 
point with respect to the entry point is measured. Then, the map data base 
for that node is scanned for an exit port matching the measured change in 
heading and, once identified, this exit port leads to the entry point of 
another node and the distance-to-go to that other node. Landfall attempts 
to compensate for the accumulation of error resulting from the achievable 
accuracy of the distance encoder by cancelling the error when the vehicle 
encounters a node and turns onto an exit port. More details of this 
vehicle navigational algorithm are disclosed in the publication. 
A common problem with the above-mentioned systems is the use of limited 
information to compensate for the accumulation of error, so as to 
accurately track a vehicle. For example, in the vehicle navigational 
system of the patent, this limited information is a coarse and simplistic 
representation of streets by logic 1 and logic 0 data of the map data 
base. In the Landfall system, a relatively simplistic assumption is made 
that vehicles are always on a street of the map. 
Furthermore, in addition to using limited information to correct for the 
accumulation of error, the vehicle navigational algorithms of the patent 
and Landfall do not develop an estimate of correct location accuracy and 
use this information in dependence with the map data base to determine if 
the vehicle is on a street or not. Systems that do not maintain this 
estimate are more likely to update the position incorrectly or to fail to 
update the position when it should be. 
SUMMARY OF THE INVENTION 
It is an object of the present invention to provide a novel apparatus and 
method for improving the accuracy of tracking a vehicle as it moves over 
streets. 
It is another object of the present invention to provide a novel apparatus 
and method for compensating for the accumulation of error in the vehicle 
navigational system usable by a vehicle as it moves over streets. 
It is still another object of the present invention to accurately keep 
track of the vehicle should the vehicle move on and off the streets. 
The above and other objects are obtained in one aspect of the present 
invention which is an apparatus for providing information to improve the 
accuracy of tracking a vehicle movable over streets in a given area, 
including first means for providing data identifying respective positions 
of the vehicle, each position having an accuracy relative to an actual 
location of the vehicle and one of the positions being a current position, 
second means for providing a map data base of the streets, and means for 
deriving any of a plurality of parameters in dependence on one or more 
respective positions of the vehicle and the streets of the map data base 
to determine if a more probable current position exists. 
In a related aspect, the invention is a method for providing information to 
improve the accuracy of tracking a vehicle movable over streets in a given 
area, including the steps of providing data identifying respective 
positions of the vehicle, each position having an accuracy relative to an 
actual location of the vehicle and one of the positions being a current 
position, providing a map data base of the streets, and deriving any of a 
plurality of parameters in dependence on one or more respective positions 
of the vehicle and the streets of the map data base to determine if a more 
probable current position exists. 
Thus, in these apparatus and method aspects of the present invention, a 
significant amount of information in the form of the plurality of 
parameters may be derived from the positions of the vehicle and the map 
data base. Furthermore, and as will be described more fully below, this 
information may be used not necessarily to correct or update the current 
position of the vehicle, but at least to determine if a more probable 
current position exists. 
In another aspect, the present invention is an apparatus for automatically 
tracking a vehicle movable about streets of an overall given area, 
including first means for providing first data identifying respective 
positions of the vehicle as the vehicle moves about the streets, each 
position having a certain accuracy and one of the positions being a 
current position, second means for providing second data being an estimate 
of the accuracy of the respective positions of the vehicle, the estimate 
changing as the vehicle moves about the streets to reflect the accuracy of 
the respective positions, third means for providing a map data base of the 
streets of the given area, and means for determining if a more probable 
position than the current position exists in response to the first data, 
the second data and the map data base. 
In a related aspect, the present invention is a method for automatically 
tracking a vehicle movable about streets of an overall given area 
including providing first data identifying respective positions of the 
vehicle as the vehicle moves about the streets, each position having a 
certain accuracy and one of the positions being a current position, 
providing second data being an estimate of the accuracy of the respective 
positions of the vehicle, the estimate changing as the vehicle moves about 
the streets to reflect the accuracy of the respective positions, providing 
a map data base of the streets of the given area, and determining if a 
more probable position than the current position exists in response to the 
first data, the second data and the map data base. 
With these apparatus and method aspects of the present invention, the 
vehicle is tracked by determining if a more probable position than the 
current position exists. If a more probable current position is 
determined, then the current position is corrected (updated), but if a 
more probable position cannot be found, the current position is not 
updated. This determination is made in response to the data about the 
positions of the vehicle, the data which are an estimate of the accuracy 
of the respective positions of the vehicle and the map data base.

DETAILED DESCRIPTION OF THE INVENTION 
I. Introduction 
The present invention will be discussed specifically in relation to 
automatic vehicle location system using dead reckoning, which is one 
approach to tracking a vehicle movable over streets. However, the present 
invention may have application to other approaches to the problem of 
automatic vehicle location for tracking vehicles moving over streets, 
including, for example, "proximity detection" systems which use signposts 
that typically are, for example, low power radio transmitters located on 
streets to sense and transmit information identifying the location of a 
passing vehicle, as well as to Landfall-type systems previously described. 
The present invention also may have application in conjunction with yet 
other systems of providing information of the location of a vehicle 
movable over streets, such as land-based radio and/or satellite location 
systems. Still furthermore, the vehicle that will be discussed may be a 
motor vehicle, such as a car, a recreational vehicle (RV), a motorcycle, a 
bus or other such type of vehicle primarily movable over streets. 
FIGS. 1A-1C are used to explain the basic principles of dead reckoning for 
tracking a moving vehicle V. Accordingly, FIG. 1A shows an XY coordinate 
system in which a vehicle V is moving over an actual street St from an 
arbitrary first or old location L.sub.o at coordinates X.sub.o Y.sub.o to 
a new or current location L.sub.c at coordinates X.sub.c Y.sub.c. 
Assume that an old dead reckoned position DRP.sub.o has been calculated, as 
described below, which coincides with the actual location L.sub.o of the 
vehicle V, thereby also having coordinates X.sub.o Y.sub.o. Assume also 
that a new or current dead reckoned position DRP.sub.c is to be calculated 
when the vehicle V is at its new or current location L.sub.c. The old dead 
reckoned position DRP.sub.o is advanced to the current dead reckoned 
position DRP.sub.c by a calculation using well-known equations as follows: 
EQU X.sub.c +X.sub.0 +.DELTA.D.multidot.cos (H) (1) 
EQU Y.sub.c =Y.sub.0 +.DELTA.D.multidot.sin (H) (2) 
where X.sub.c Y.sub.c are the coordinates of DRP.sub.c, .DELTA.D is a 
measured distance traveled by the vehicle V between L.sub.o and L.sub.c, 
and H is a measured heading of the vehicle V. 
The illustration and discussion of FIG. 1A assumes that there has been no 
error in calculating the current dead reckoned position DRP.sub.c. That 
is, the current dead reckoned position DRP.sub.c is shown to coincide 
exactly with the actual location L.sub.c of the vehicle V, whereby L.sub.c 
and DRP.sub.c have the identical coordinates X.sub.c Y.sub.c. 
FIG. 1B illustrates the more general situation in which errors are 
introduced into the calculation of the current dead reckoned position 
DRP.sub.c. As a result, the current dead reckoned position DRP.sub.c will 
differ from the actual location L.sub.c of the vehicle V by an error E. 
This error E can arise due to a number of reasons. For example, the 
measurements of the distance .DELTA.D and the heading H obtained with 
distance and heading sensors (not shown in FIGS. 1A-1C) on the vehicle V 
may be inaccurate. Also, equations (1) and (2) are valid only if the 
vehicle V travels over distance .DELTA.D at a constant heading H. Whenever 
the heading H is not constant, error is introduced into the calculation. 
Moreover, the error E, unless compensated, will on average accumulate as 
the vehicle V continues to move over the street St since X.sub.c Y.sub.c 
becomes X.sub.o Y.sub.o for each new calculation of the dead reckoned 
position DRP.sub.c in accordance with equations (1) and (2). This is 
indicated in FIG. 1B by showing the vehicle V at a subsequent new location 
L'.sub.c, together with a subsequent current dead reckoned position 
DRP'.sub.c and an accumulated error E'.sub.&gt; E. Thus, any given DRP.sub.c 
has a certain inaccuracy associated with it corresponding to the error E. 
FIG. 1C is used to explain generally the manner in which the error E 
associated with a given current dead reckoned position DRP.sub.c is 
compensated. FIG. 1C shows the vehicle V at location L.sub.c, together 
with a current dead reckoned position DRP.sub.c and an error E, as 
similarly illustrated in FIG. 1B. In accordance with the present 
invention, a determination will be made if a more probable position than 
the current dead reckoned position DRP.sub.c exists. If it is determined 
that a more probable position does exist, then the current dead reckoned 
position DRP.sub.c is changed or updated to a certain XY coordinate 
corresponding to a point on the street St, identified as an updated 
current dead reckoned position DRP.sub.cu. The DRP.sub.cu may or may not 
coincide with the actual location L.sub.c of the vehicle (shown in FIG. 1C 
as not coinciding), but has been determined to be the most probable 
position at the time of updating. Alternatively, at this time it may be 
determined that no more probable position than the current dead reckoned 
position DRP.sub.c can be found, resulting in no changing or updating of 
the current dead reckoned position DRP.sub.c. If the updating does occur, 
then the XY coordinates of the DRP.sub.cu become X.sub.o Y.sub.o in 
equations (1) and (2) for the next advance, whereas if no updating occurs 
at this time, then the XY coordinates of the DRP.sub.c become X.sub.o 
Y.sub.o. 
II. Exemplary System Hardware 
FIG. 2 illustrates one embodiment of an automatic vehicle navigational 
system 10 of the present invention. A computer 12 accesses a data storage 
medium 14, such as a tape cassette or floppy or hard disk, which stores 
data and software for processing the data in accordance with a vehicle 
navigational algorithm, as will be described below. For example, the 
computer 12 can be an IBM Personal Computer (PC) currently and widely 
available in the marketplace, that executes program instructions disclosed 
below. 
System 10 also includes means 16 for sensing distances .DELTA.D traveled by 
the vehicle V. For example, the means 16 can constitute one or more wheel 
sensors 18 which sense the rotation of the non-driven wheels (not shown) 
respectively of the vehicle V and generate analog distance data over lines 
20. An analog circuit 22 receives and conditions the analog distance data 
on lines 20 in a conventional manner, and then outputs the processed data 
over a line 24. 
System 10 also includes means 26 for sensing the heading H of the vehicle 
V. For example, means 26 can constitute a conventional flux gate compass 
28 which generates heading data over a line 30 for determining the heading 
H. The previously described wheel sensors 18 also can be differential 
wheel sensors 18 for generating heading data as a part of overall means 
26. An advantage of possibly using both the flux gate compass 28 and the 
differential wheel sensors 18 to provide heading data to the computer 12 
will be discussed below. 
The computer 12 has installed in it an interface card 32 which receives the 
analog distance data from means 16 over line 24 and the analog heading 
data from means 26. Circuitry 34 on the card 32 converts and conditions 
these analog data to digital data identifying, respectively, the distance 
.DELTA.D traveled by the vehicle V and heading H of the vehicle V shown in 
FIGS. 1A-1C. For example, the interface card 32 may be the commercially 
available Tecmar Lab Tender Part No. 20028, manufactured by Tecmar, Solon, 
(Cleveland), Ohio. 
The system 10 also includes a display means 36, such as a CRT display or 
XYZ monitor 38, for displaying a map M of a set of streets {St} and a 
symbol S.sub.v of the vehicle V, which are shown more fully in FIG. 3. 
Another computer interface card 40 is installed in the computer 12 and is 
coupled to and controls the display means 36 over lines 42, so as to 
display the map M, the symbol S.sub.v and relative movement of the symbol 
S.sub.v over the map M as the vehicle V moves over the set of streets 
{St}. The card 40 responds to data processed and provided by the card 32 
and the overall computer 12 in accordance with the vehicle navigational 
algorithm of the present invention to display such relative movement. As 
another example, the display means 36 and the circuitry of card 40 may be 
one unit sold commercially by the Hewlett-Packard Company, Palo Alto, 
California as model 1345A (instrumentation digital display). 
The system 10 also includes an operator control console means 44 having 
buttons 46 by which the vehicle operator may enter command data to the 
system 10. The console means 44 communicates over a line 48 with the means 
32 to input the data to the computer 12. For example, the command data may 
be the initial XY coordinate data for the initial DRP when the system 10 
is first used. Thereafter, as will be described, this command data need 
not be entered since the system 10 accurately tracks the vehicle V. 
The system 10 may be installed in a car. For example, the monitor 38 may be 
positioned in the interior of the car near the dashboard for viewing by 
the driver or front passenger. The driver will see on the monitor 38 the 
map M and the symbol S.sub.v of the vehicle V. Pursuant to the vehicle 
navigational algorithm described below, the computer 12 processes a 
substantial amount of data to compensate for the accumulation of error E 
in the dead reckoned positions DRP, and then controls the relative 
movement of the symbol S.sub.v and the map M. Therefore, the driver need 
only look at the monitor 38 to see where the vehicle V is in relation to 
the set of streets {St} of the map M. 
Moreover, a number of different maps M may be stored on the storage medium 
14 as a map data base for use when driving throughout a given geographical 
area, such as the San Francisco Bay Area. As the vehicle V is driven from 
one given area to another, the appropriate map M may be called by the 
driver by depressing one of the buttons 46, or be automatically called by 
the computer 12, and displayed on the monitor 38. System 10 will perform 
its navigational functions in relation to the map data base, using a part 
of the map data base defined as the navigation neighborhood of the 
vehicle. The map M which currently is being displayed on the monitor 38 
may or may not correspond precisely to the navigation neighborhood. 
III. Information Used to Improve the Accuracy of Tracking the Vehicle V 
(The Map M; The DRP; The Estimate of the Accuracy of the DRP) 
A. The Map M 
1. The Map M Generally 
FIG. 3 shows the map M of a given area (part of the map data base) or 
navigation neighborhood having a set of streets {St} over which the 
vehicle V may move. For example, the street identified as "Lawrence 
Expressway" may correspond to a street St.sub.1, the street identified as 
"Tasman Drive" may correspond to a street St.sub.2 and the street 
identified as "Stanton Avenue" may correspond to a street St.sub.3. Also 
shown is the vehicle symbol S.sub.v which is displayed on the monitor 38. 
Thus, the vehicle V may move along Lawrence Expressway, then make a left 
turn onto Tasman Drive and then bear right onto Stanton Avenue, and this 
track will be seen by the vehicle operator via the relative movement of 
the symbol S.sub.v and map M. 
2. The Map Data Base 
(a) Introduction 
The map M is stored on the storage medium 14 as part of the map data base 
which is accessed by the computer 12. This map data base includes, as will 
be further described, data identifying (1) a set of line segments {S} 
defining the set of streets {St}, (2) street widths W, (3) vertical slopes 
of the line segments S, (4) magnetic variation of the geographical area 
identified by the map M, (5) map accuracy estimates, and (6) street names 
and street addresses. 
(b) Set of Line Segments {S} 
FIG. 4A is used to explain the data stored on medium 14 that identify a set 
of line segments {S} defining the set of streets {St}. Each such street St 
is stored on the medium 14 as as algebraic representation of the street 
St. Generally, each street St is stored as one or more arc segments, or, 
more particularly, as one or more straight line segments S. As shown in 
FIG. 4A, each line segment S has two end points EP.sub.1 and EP.sub.2 
which are defined by coordinates X.sub.1 Y.sub.1 and X.sub.2 Y.sub.2, 
respectively, and it is these XY coordinate data that are stored on the 
medium 14. The course (heading) of the segment S can be determined from 
the end points. 
(c) Street Width W 
The streets St of any given map M may be of different widths W, such as a 
six-lane street like Lawrence Expressway, a four-lane street like Stanton 
Avenue and a two-lane street like Tasman Drive, all illustrated in the map 
M of FIG. 3. Data identifying the respective widths W of each street St 
are stored on the medium 14 as part of the map data base. The width W of 
the street St is used as part of an update calculation described more 
fully below. 
(d) Vertical Slope of a Line Segment S 
FIG. 4B is used to explain correction data relating to the vertical slope 
of a given street St and which are part of the map data base stored on 
medium 14. FIG. 4B-1 shows a profile of the actual height of a street St 
which extends over a hill. The height profile of the actual street St is 
divided into line parts P.sub.1 -R.sub.5 for ease of explanation, with 
each part P.sub.1 -P.sub.5 having a true length l.sub.1 -l.sub.5. FIG. 
4B-2 shows the same parts P.sub.1 -P.sub.5 as they are depicted on a flat 
map M as line segments S.sub.1 -S.sub.5. Parts P.sub.1, P.sub.3 and 
P.sub.5 shown in FIG. 4B-1 are flat and, therefore, their true lengths 
l.sub.1, l.sub.3 and l.sub.5 are accurately represented on the map M, as 
shown in FIG. 4B-2. However, the true length l.sub.2 and l.sub.4 of 
sloping parts P.sub.2 and P.sub.4 shown in FIG. 4B-1 are foreshortened in 
FIG. 4B-2 from l.sub.2 and l.sub.4 to l'.sub.2 and l'.sub.4. This 
constitutes map foreshortening errors which are proportional to the cos 
.alpha. and the cos .beta., respectively, these angles .alpha. and .beta. 
being shown in FIG. 4B-1. Such foreshortening errors always occur whenever 
a 3-dimensional surface is depicted on a 2-dimensional or flat map M. 
Consequently, the XY coordinates of the respective end points EP of line 
segments S.sub.2 and S.sub.4 shown in FIG. 4B-2 do not reflect the actual 
lengths l.sub.2 and l.sub.4 of the actual street St. Therefore, the map 
data base can store vertical slope correction data for these segments 
S.sub.2 and S.sub.4 to compensate for the foreshortening errors. The 
correction data may be stored in the form of a code defining several 
levels of slope. For example, in some places these slope data may be coded 
at each segment S. In other areas these slope data are not encoded in the 
segment S but may be coded to reflect overall map accuracy, as described 
below. 
Furthermore, FIG. 4B-3 is a plot of the heading H measured by the means 26 
for each segment S.sub.1 -S.sub.5 as the vehicle V traverses the street St 
having the height profile shown in FIG. 4B-1. Any segment S having a 
vertical slope, such as corresponding parts P.sub.2 and P.sub.4 of the 
actual street St, may introduce through "magnetic dip angles", errors in 
the compass heading readout of the flux gate compass 28 of the means 26 as 
the vehicle V moves over parts P.sub.2 and P.sub.4. Where the map data 
base contains correction data for a segment S having a vertical slope, the 
compass heading errors also may be corrected. 
Thus, when foreshortening errors are coded on each segment S, and if the 
position (DRP) of the vehicle V has been recently updated to a segment S, 
as further described below, and has not since turned or otherwise been 
detected as leaving that segment S, then the dead reckoning equations (1) 
and (2) can be modified to equations (1') and (2'): 
EQU X.sub.c =X.sub.o +C.sub.F .multidot..DELTA.D.multidot.cos (H') (1') 
EQU Y.sub.c =Y.sub.o +C.sub.F .multidot..DELTA.D.multidot.sin (H') (2') 
Here the foreshortening coefficients C.sub.F are calculated from 
foreshortening and other data coded for the selected segment S, as is the 
corrected heading H'. 
(e) Magnetic Variation of the Geographic Area 
The map data base may contain correction data to relate magnetic north to 
true north and magnetic dip angles to determine heading errors due to the 
vertical slope of streets St, thereby accounting for the actual magnetic 
variation of a given geographic area. Because these are continuous and 
slowly varying correction factors only a few factors need be stored for 
the entire map data base. 
(f) Map Accuracy Estimate 
The map M is subject to a variety of other errors including survey errors 
and photographic errors which may occur when surveying and photographing a 
given geographic area to make the map M, errors of outdated data such as a 
new street St that was paved subsequent to the making of the map M, and, 
as indicated above, a general class of errors encountered when describing 
a 3-dimensional earth surface as a 2-dimensional flat surface. 
Consequently, the map data base may contain data estimating the accuracy 
for the entire map M, for a subarea of the map M or for specific line 
segments S. The navigational algorithm described below may use these map 
accuracy data to set a minimum size of an estimate of the accuracy of the 
updated dead reckoned position DRP.sub.cu also as described more fully 
below. Additionally, some streets St in the map M are known to be 
generalizations of the actual locations (e.g., some trailer park roads). 
The map accuracy data may be coded in such a way as to identify these 
streets St and disallow the navigational algorithm from updating to these 
generalized streets St. 
B. The Dead Reckoned Position DRP 
The present invention provides information on the current dead reckoned 
position DRP.sub.c of the vehicle V by using certain sensor data about 
wheel sensors 18 and compass 28 and the computations of equations (1) and 
(2) or (1') and (2'). In addition, sensor calibration information derived 
in the process of advancing and updating the dead reckoned positions DRP, 
as will be described below, is used to improve the accuracy of such sensor 
data and, hence, the dead reckoned position accuracy. 
c. The Estimate of the Accuracy of the DRP 
1. The Estimate--Generally 
The present invention provides and maintains or carries forward as the 
vehicle V moves, an estimate of the accuracy of any given dead reckoned 
position DRP. Every time the dead reckoned position DRP is changed, i.e., 
either advanced from the old dead reckoned position DRP.sub.o to the 
current dead reckoned position DRP.sub.c or updated from the DRP.sub.c to 
the updated current dead reckoned position DRP.sub.cu, the estimate is 
changed to reflect the change in the accuracy of the DRP. The estimate 
embodies the concept that the actual location of the vehicle V is never 
precisely known, so that the estimate covers an area that the vehicle V is 
likely to be within. As will be described below, the estimate of the 
accuracy of a given dead reckoned position DRP can be implemented in a 
variety of forms and is used to determine the probability of potential 
update positions of a given DRP.sub.c to a DRP.sub.cu. 
2. The Estimate as a Probability Density Function or as a Contour of Equal 
Probability (CEP) 
FIG. 5A generally is a replot of FIG. 1B on an XYZ coordinate system, where 
the Z axis depicts graphically a probability density function PDF of the 
actual location of the vehicle V. Thus, FIG. 5A shows along the XY plane 
the street St, together with the locations L.sub.o and L.sub.c and the 
current dead reckoned position DRP.sub.c previously described in 
connection with FIG. 1B. As shown in FIG. 5A, the peak P of the 
probability density function PDF is situated directly above the DRP.sub.c. 
The probability density function PDF is shown as having a number of 
contours each generated by a horizontal of XY plane slicing through the 
PDF function at some level. These contours represent contours of equal 
probability CEP, with each enclosing a percentage of the probability 
density, such as 50% or 90%, as shown. 
FIG. 5B is a projection of the contours CEP of FIG. 5A onto the XY 
coordinates of the map M. A given contour CEP encloses an area A having a 
certain probability of including the actual location of the vehicle V. 
Thus, for example, the 90% contour CEP encloses an area A which has a 0.9 
probability of including the actual location of the vehicle V. As will be 
further described, as the old dead reckoned position DRP.sub.o is advanced 
to the current dead reckoned position DRP.sub.c and the error E 
accumulates, as was described in relation to FIG. 1B, the area A of the 
CEP will become proportionately larger to reflect the accumulation of the 
error E and the resulting reduction in the accuracy of the DRP.sub.c ; 
however, when the DRP.sub.c is updated to the DRP.sub.cu, as was described 
in connection with FIG. 1C, then the area A of the CEP will be 
proportionately reduced to reflect the resulting increase in the accuracy 
of the DRP.sub.cu. Whether expanded or reduced in size, the CEP still 
represents a constant probability of including the actual location of the 
vehicle V. As will be described, the CEP has a rate of growth or expansion 
which will change, accordingly, as certain measurements and other 
estimates change. 
FIG. 5C is similar to FIG. 5B, except that it shows one example of a 
specific implementation of the CEP that is used in accordance with the 
present invention, as will be further described. For this implementation, 
a contour CEP is approximated by a rectangle having corners RSTU. The CEP 
is stored and processed by the computer 12 as XY coordinate data defining 
the corners RSTU, respectively. 
In other words, the CEP, whether stored and used in an elliptical, 
rectangular or other such shape, may be considered to constitute a 
plurality of points, each identified by XY coordinate data, defining a 
shape enclosing an area A having a probability of including the actual 
location of the vehicle V. 
FIG. 5C-1 shows graphically the expansion or enlargement of the CEP as the 
vehicle V moves over a street St and as an old dead reckoned position 
DRP.sub.o is advanced to a current dead reckoned position DRP.sub.c. In 
FIG. 5C-1, a given DRP.sub.o is shown as not necessarily coinciding with 
an actual location L.sub.o of the vehicle V, i.e., there is an 
accumulation error E. Surrounding the DRP.sub.o is the CEP having an area 
A that is shown as containing the actual location L.sub.o of the vehicle 
V. Upon the advancement of the DRP.sub.o to the DRP.sub.c, when the 
vehicle V has moved to the location L.sub.c, the CEP will have been 
expanded from the area A defined by corners RSTU to the area A' defined by 
corners R'S'T'U'. More specifically, as the vehicle V moves from the 
location L.sub.o to the location L.sub.c, the computer 12 processes 
certain data so that the CEP may grow from area A to area A' at a varying 
rate, as will be described below. Also, the manner in which the XY 
coordinate data of the corners RSTU are changed to define corners R'S'T'U' 
will be described below. 
FIG. 5C-2 shows graphically the reduction in size of the CEP. FIG. 5C-2 
indicates that at the time of the vehicle V is at the location L.sub.c, 
the vehicle navigational algorithm of the present invention has determined 
that a more probable current position than the DRP.sub.c exists, so that 
the latter has been updated to the DRP.sub.cu, as explained in FIG. 1C. 
Consequently, the expanded CEP having corners R'S'T'U' is also updated to 
a CEP.sub.u having an area A" with corners R"S"T"U" to reflect the 
increased certainty in the accuracy of the DRP.sub.cu. Again, the 
CEP.sub.u having the area A" surrounds the DRP.sub.cu with a probability 
of including the actual location of the vehicle V. The detailed manner in 
which the CEP is updated to the CEP.sub.u by the computer 12 will be 
described more fully below. 
While area A, area A' and area A" of the respective CEPs have been 
described above and shown to include the actual location of the vehicle V, 
since the CEP is a probability function, it does not necessarily have to 
contain the actual location of the vehicle V. The vehicle navigational 
algorithm described below still uses the CEP to determine if a more 
probable current dead reckoned position DRP exists. 
3. Other Embodiments of the Estimate and its Growth 
The estimate of the accuracy of a given dead reckoned position DRP, which 
has a probability of containing the actual location of the vehicle V, may 
be implemented in embodiments other than the CEP. For example, the 
estimate may be a set of mathematical equations defining the PDF. Equation 
A is an example of a PDF of a DRP advancement assuming independent zero 
mean normal distributions of errors in heading and distance, and to first 
order approximation, independence of errors in the orthogonal directions 
parallel and perpendicular to the true heading direction. 
##EQU1## 
where 
EQU P=.DELTA.D.sub.T sin H.sub..epsilon. 
and 
D.tbd.distance parellel to true heading direction 
.DELTA.D.sub.T .tbd.true distance of DRP advance 
.sigma..sub.D .tbd.standard deviation of distance sensor error (a 
percentage) 
H.sub..epsilon. .tbd.heading error 
P.tbd.distance perpendicular to true heading direction 
.sigma..sub.P .tbd.standard deviation of position error perpendicular to 
true heading direction (a percentage) which is a function of .sigma..sub.H 
and .DELTA.D.sub.T 
.sigma..sub.H .tbd.standard deviation of heading sensor error 
Equation B is an example of a similar PDF of the accumulated error. Its 
axes, .theta. and .phi., have an arbitrary relation to D and P depending 
upon the vehicle's past track. 
##EQU2## 
where 
.theta..tbd.major axis 
.phi..tbd.minor axis perpendicular to .theta. 
.sigma..sub..theta. .tbd.standard deviation of errors accumulated in 
.theta. direction 
.sigma..sub..phi. .tbd.standard deviation of errors accumulated in .phi. 
direction 
Assuming independence of errors, the vehicle position probability density 
function PDF after an advance can be calculated by two dimension 
convolution of the old PDF (equation B) and the current PDF (equation A) 
and their respective headings. A new PDF of the form of equation B could 
then be approximated with, in general, a rotation of axis .theta. to some 
new axis .theta.' and .phi. and .phi.' and an adjustment of 
.sigma..sub..theta. and .sigma..sub..phi.. The computer 12 can then 
calculate the probability of potential update positions in accordance with 
these mathematical PDF equations thus providing information similar to 
that of the CEP as the vehicle V moves. 
Alternatively, the computer 12 can store in memory a table of values 
defining in two dimensions the probability distribution. The table can be 
processed to find similar information to that contained in the CEP, as 
described more fully below. 
In addition, the rate of growth of the CEP can be embodied in different 
ways. Besides the method described below, the rate of growth could be 
embodied by a variety of linear filtering techniques including Kalman 
filtering. 
IV. Parameters Derived by the Computer to Improve the Accuracy of Tracking 
the Vehicle V 
A. Parameters--Generally 
Computer 12 will derive and evaluate from the above-described information 
one or more parameters that may be used to determine if a more probable 
position than the current dead reckoned position DRP.sub.c exists. These 
"multi-parameters", any one or more of which may be used in the 
determination, include (1) the calculated heading H of the vehicle V in 
comparison to the headings of the line segments S, (2) the closeness of 
the current dead reckoned position DRP.sub.c to the line segments S in 
dependence on the estimate of the accuracy of the DRP.sub.c, such as the 
CEP in the specific example described above, (3) the connectivity of the 
line segments S to the line segment S corresponding to a preceding 
DRP.sub.cu, (4) the closeness of the line segments S to one another (also 
discussed below as "ambiguity"), and (5) the correlation of the 
characteristics of a given street St, particularly the headings or path of 
the line segments S of the given street St, with the calculated headings H 
which represent the path of the vehicle V. FIGS. 6A-6D show graphically 
and are used to explain the parameters (1)-(4) derived by the computer 12. 
More details of these and other parameters will be discussed below in 
relation to the details of the vehicle navigational algorithm. 
B. Parameters--Specifically 
1. Heading H 
FIG. 6A shows in illustration I the measured heading H of the vehicle V. 
FIG. 6A also shows in respective illustrations II-IV a plurality of line 
segments S, for example line segments S.sub.1 -S.sub.3, stored in the map 
data base. These segments S.sub.1 -S.sub.3 may have, as shown, different 
headings h.sub.1 -h.sub.3, as may be calculated from the XY coordinate 
data of their respective end points EP. The heading H of the vehicle V is 
compared to the respective headings h of each segment S in the map data 
base corresponding to the navigation neighborhood currently used by the 
navigation algorithm, such as segments S.sub.1 -S.sub.3. Depending on this 
heading comparison, computer 12 determines if one or more of these 
segments S qualifies as a "line-of-position" or L-O-P in determining if a 
more probable current dead reckoned position DRP.sub.c exists. Such 
segments S qualifying as L-O-Ps are candidates for further consideration 
to determine if a DRP.sub.c is to be updated to DRP.sub.cu. 
2. Closeness of DRP.sub.c Related to Estimate 
FIG. 6B is used to explain one example of the closeness parameter with 
respect to the estimate of the accuracy of the DRP. Specifically, one 
criterion that is considered is whether a given line segment S intersects 
or is within the CEP. Segments S intersecting the CEP are more likely to 
correspond to the actual location of the vehicle V than segments S not 
intersecting the CEP. A given line segment S doesn't intersect the CEP if, 
for example, all four corners RSTU (or R'S'T'U') are on one side of the 
CEP. As shown in FIG. 6B, which illustrates eight representative line 
segments S.sub.1 -S.sub.8, segments S.sub.2 -S.sub.4 and S.sub.6 -S.sub.7 
(S.sub.6 and S.sub.7 correspond to one given street St) do not intersect 
the CEP and, therefore, are not considered further. Segments S.sub.1, 
S.sub.5 and S.sub.8 do intersect the CEP and, therefore, qualify as L-O-Ps 
or candidates for further consideration in determining if a more probable 
current dead reckoned position DRP.sub.c exists, as will be described 
below. FIG. 6B happens to show that the actual location of the vehicle V 
at this time is on a street St corresponding to segment S.sub.8. 
As an alternative, assume that the embodiment of the estimate being used is 
the table of entries of values of the probability density function PDF 
described above. The computer 12 may determine the distance and heading 
between a given line segment s and the DRP.sub.c. From this and the table 
of PDF's the computer 12 can determine the most probable position along 
the segment S and the probability associated with that position. Any 
probability less than a threshold will result in the given line segment S 
not being close enough to the current dead reckoned position DRP.sub.c to 
be a likely street St on which the vehicle V may be moving, whereas any 
probability greater than the threshold may constitute such a likely street 
St. In addition, these probability values can be used to rank the relative 
closeness of candidate segments S. 
3. Connectivity of the Line Segments S 
It is more probable that a given line segment S corresponds to a street St 
on which the vehicle V is moving if it is connected to a line segment S 
previously determined to contain the updated current dead reckoned 
position DRP.sub.cu. FIG. 6C graphically illustrates several possible ways 
in which two line segments S.sub.1 and S.sub.2 are deemed connected. As 
shown in Example I of FIG. 6C, any two line segments S.sub.1 and S.sub.2 
are connected if an intersection i of these two segments S.sub.1 and 
S.sub.2 is within a threshold distance of the end points EP of the two 
segments, S.sub.1, and S.sub.2, respectively. Alternatively, two line 
segments S.sub.1 and S.sub.2 are interconnected if the intersection i is 
inclusive of the end points EP, as shown by Example II and Example III in 
FIG. 6C. 
To test for connectivity, for example, and with reference to Examples I-III 
of FIG. 6C, the line segment S.sub.1 may be the segment S corresponding to 
the preceding updated current dead reckoned position DRP.sub.cu while line 
segment S.sub.2 may be a segment S being presently evaluated in connection 
with updating the current dead reckoned position DRP.sub.c. Computer 12 
will compute from segment data contained in the navigation neighborhood of 
the map data base, the connectivity to determine if this segments S.sub.2 
qualifies under this connectivity test. That is, the present invention 
considers that the vehicle V more likely will move about interconnected 
streets St and line segments S of a given street St, rather than about 
unconnected streets St or unconnected line segments S of a given street 
St. Other segments S may or may not so qualify under this connectivity 
parameter. Since the present invention also allows for the vehicle V to 
move off and on the set of streets {S} of the map data base, this 
connectivity test is not absolute but is one of the parameters used in the 
updating process more fully described later. 
4. Closeness of Line Segments S to One Another (Ambiguity) 
FIG. 6D shows two line segments S.sub.1 and S.sub.2 on opposite sides of 
the current dead reckoned position DRP.sub.c. As will be further 
described, the computer 12 ultimately may determine that these two line 
segments S.sub.1 and S.sub.2 are the only two remaining line segments S 
that may likely correspond to the actual street St on which the vehicle V 
is moving. However, if the computer 12 determines that these two segments 
S.sub.1 and S.sub.2 are too close together, or that the distance between 
S.sub.1 and DRP.sub.c is insignificantly different than the distance 
between S.sub.2 and DFP.sub.c, then one segment S.sub.1 or S.sub.2 may be 
as likely as the other segment S.sub.1 or S.sub.2 to correspond to the 
street St on which the vehicle V is actually moving. In this ambiguous 
event, neither segment S.sub.1 nor S.sub.2 is selected as a more probable 
segment and the current dead reckoned position DRP.sub.c is not updated at 
this time. 
5. Correlation 
(a) Generally 
The correlation parameter generally described the closeness of fit of a 
recent portion of the path taken by the vehicle V to the path defined by 
segments S in the navigation neighborhood. The correlation parameter is 
computed differently depending upon whether the vehicle V is turning or 
not. If the vehilce V is not turning a simple path matching is calculated, 
as described below in section 5(b). If the vehicle V is turning a 
correlation function is calculated, as described below in section 5(c). 
(b) Path Matching Between the Sequence of Previous Vehicle Headings and the 
Sequence of Connected Segment Headings 
As will be shown by the two examples I and II of FIG. 6E, and described 
more fully below, path matching is used when the vehicle V has been 
determined not to be turning. In each example I and II, the solid lines 
having the current dead reckoned position DRP.sub.c show a recent dead 
reckoned path used for matching and the dashed lines show an older dead 
reckoned path not used for matching. The other solid lines of examples I 
and II show respective sequences of connected line segments S. After 
computer 12 determines, for example, line segment S.sub.2 to be the most 
likely to correspond to the street St on which the vehicle V is probably 
moving, then this path match parameter will compare the dead reckoned path 
of the vehicle V with the path of the segment S.sub.2 and connected 
segments (if needed), such as segment S.sub.1, to determine if the 
respective paths match. Example I of FIG. 6E shows paths that do match, 
whereby segment S.sub.2 would be used for updating the current dead 
reckoned position DRP.sub.c to the DRP.sub.cu. Example II shows paths that 
do not match, so that segment S.sub.2 would not be used for updating the 
currrent dead reckoned position DRP.sub.c. 
(c) Correlation Function Between the Sequence of Previous Vehicle Headings 
and the Sequence of Connected Segment Headings 
A correlation function, described more fully below, is used when it has 
been determined that the vehicle V has been turning. After computer 12 
determines a given line segment S to be the most likely to correspond to 
the street St on which the vehicle V is probably moving, the correlation 
function is derived to determine if the segment S is sufficiently 
correlated to warrant updating the current dead reckoned position 
DRP.sub.c. The computer 12 does this by calculating the best point BP of 
the correlation function and testing its value as well as certain shape 
factors. If it passes these tests, this best point BP is stored for later 
use in updating the DRP.sub.c to DRP.sub.cu. 
V. Use of the Parameters Derived by the Computer 12 to Improve the Accuracy 
of Tracking the Vehicle V 
A. Parameter Use--Generally 
In the present invention, the parameters of Section IV. discussed above are 
used as logical tests in conjunction with other processing and logical 
tests to determine if a point along a selected segment S, i.e., the most 
probable segment, is a more probable position of the vehicle V than the 
current dead reckoned position DRP.sub.c. If such a most probable segment 
S is selected, then an update of the DRP.sub.c to that point (the 
DRP.sub.cu) will be made as outlined in Section VI. below and detailed 
more fully in Section IX. 
The parameters are generally used to sequentially test and eliminate the 
set of segments {S} in the navigation neighborhood from further 
consideration as candidate segments S for the most probable segment S. As 
will be described in detail in Section IX., the navigation algorithm uses 
these parameters and other processing and logic to eliminate all but one 
or two segments S as candidate segments. The algorithm then makes a final 
determination if one segment S fully qualifies as having the highest 
probability of representing the street St where the vehicle V is moving 
and that the probability is sufficiently high to qualify for updating the 
current dead reckoned position DRP.sub.c to the DRP.sub.cu as the 
above-mentioned point on such one segment S. 
B. Parameter Use--Other Embodiments 
The use of these parameters for determining if and how to update the 
current dead reckoned position DRP.sub.c can take other embodiments. For 
example, rather than a logical sequence of eliminating segments S, they 
may be used in a weighted score algorithm. In such an algorithm the 
parameters described in Section IV. above may be numerically computed for 
each segment S in the navigation neighborhood. Each parameter could be 
weighted by numerical values representing the average error bounds 
estimated for that parameter and representing the significance assigned to 
that parameter. In this way a weighted sum of scores could be computed for 
each segment S and the segment S with the best weighted sum determined. If 
that sum was sufficiently good the decision would be made to update. 
In another embodiment a combination of the elimination method of the 
present invention and the scoring method discussed above, could be used. 
VI. Update of the DRP.sub.c, the CEP and Sensor Calibration Data to Improve 
the Accuracy of Tracking the Vehicle V 
A. Update--Generally 
Once a segment S, i.e., the most probable segment S, has been determined to 
be sufficiently probable of containing the actual location of the vehicle 
V to justify updating the current dead reckoned position DRP.sub.c, the 
computer 12 processes the segment, parameter and DRP.sub.c data to 
determine the most probable DRP.sub.cu, the updated CEP.sub.u and, if 
appropriate, updated distance and heading sensor calibration coefficients. 
The method of calculating DRP.sub.cu depends on whether the computer 12 
determines that the vehicle V has been turning or has been moving in a 
straight line. 
As will be described in detail later, if the vehicle V has been moving in a 
straight line, DRP.sub.cu is computed directly using the selected segment 
S, the DRP.sub.c, the angle and distance between them and the CEP. If the 
vehicle V is turning, the DRP.sub.cu is determined by calculating a 
correlation function obtained by comparing the sequence of recent vehicle 
headings to the segment S (and if necessary connected segments S). The 
best point BP of the correlation computation becomes the selected 
DRP.sub.cu if it passes certain quality tests. 
The CEP is updated to CEP.sub.u differently in accordance with the two 
methods of updating the DRP.sub.c. Also, when the update is judged to 
provide added information about the calibration of the sensors 18 and 28, 
the calibration coefficients are updated. 
B. Update--Other Embodiments 
The method of updating DRP.sub.c to DRP.sub.cu can take other embodiments. 
For example, the past DRP positions, the most probable position along the 
selected segment S, the score of the segment S if a score was computed, as 
well as other parameter information could be input into a linear filter 
(not shown) for computing an optimum or least mean square position based 
on some assignment of values of the different inputs. The optimum or most 
probable position may or may not fall on a segment S. 
VII. Summary 
Thus far, there has been described a variety of information that is 
inputted to, stored and processed by the computer 12 to improve the 
accuracy of tracking the vehicle V. This information includes, for 
example, the distance and heading data inputted to the computer 12, the 
map data base stored on medium 14 and the estimate of the accuracy of the 
dead reckoned positions DRP. As was also described, the computer 12 may 
use this information to derive one or more parameters, each of which and 
all of which, are useful for determining if a most probable segment S 
exists and if such segment S contains a more probable current dead 
reckoned position DRP.sub.cu than the current DRP.sub.c. If it is 
determined that such a segment S exists, the computer 12 computes a more 
probable position and then updates the DRP.sub.c to a DRP.sub.cu, the 
estimate of the accuracy of the DRP and the calibration coefficients. The 
computer 12 may selectively process the information described and other 
information to be described, and derive the parameters, and perform the 
updates in accordance with a vehicle navigational algorithm of the present 
invention, one embodiment of which will now be described. 
VIII. Overall Computer Program Structure 
FIGS. 7A-7C show three block diagrams which, together, constitute an 
overall computer program structure that is utilized by the system 10. FIG. 
7A references a main program, with FIGS. 7B-7C referencing interrupt 
programs. The interrupt program of FIG. 7B is used to refresh the monitor 
38 and to provide an operator interface via the console means 46. The 
interrupt program of FIG. 7C is the program performing the vehicle 
navigational algorithm of the present invention. 
Generally, in the operation of the overall computer program structure, in 
response to all information that is processed by the computer 12, as 
described above and as will be further described below, the main program 
computes and formats data necessary to select and display the selected map 
M and the vehicle symbol S.sub.v shown on the monitor 38 and provide the 
segments S in the navigation neighborhood for the vehicle navigational 
algorithm. The execution of this main program can be interrupted by the 
two additional programs of FIG. 7B and FIG. 7C. The refresh display 
program of FIG. 7B resets the commands necessary to maintain the visual 
images shown on the monitor 38 and reads in any operator command data via 
the console means 44 needed for the main program to select and format the 
display presentation. The interrupt program of FIG. 7B can interrupt 
either the main program of FIG. 7A or the navigational program of FIG. 7C. 
The latter can only interrupt the main program and does so approximately 
every 1 second, as will be further described. 
IX. The Vehicle Navigational Program and Algorithm 
FIG. 8 is a flow chart illustrating an embodiment of the overall vehicle 
navigational algorithm of the present invention performed by the computer 
12. As previously mentioned, every second the vehicle navigational program 
interrupts the main program. First, the computer 12 advances an old dead 
reckoned position DRP.sub.o to a current dead reckoned position DRP.sub.c 
by dead reckoning (see also FIG. 1B) and expands an estimate of the 
accuracy of the DRP.sub.c (see also FIG. 5C-1) and (block 8A), as 
described further below in relation to FIG. 9. Next, a decision is made if 
it is time to test for an update of the DRP.sub.c, the estimate and other 
information (block 8B), as described below in relation to FIG. 12. If not, 
the remaining program is bypassed and control is returned to the main 
program. 
If it is time to test for an update (block 8B), then a multi-parameter 
evaluation is performed by computer 12 to determine if a segment S in the 
navigation neighborhood contains a point which is more likely than the 
current dead reckoned position DRP.sub.c (block 8C), as will be described 
in relation to FIG. 13. If the multi-parameter evaluation does not result 
in the determination of such a segment S (block 8D), then the remaining 
program is bypassed and control is passed to the main program. If the 
multi-parameter evaluation indicates that such a more likely segment S 
does exist, then a position along this segment S is determined and an 
update is performed (block 8E), as will be described in connection with 
FIG. 28, and thereafter control is returned to the main program. This 
update not only includes an update of the current dead reckoned position 
DRP.sub.c to the DRP.sub.cu (see FIG. 1C), and an update of the estimate 
(see FIG. 5C-2), but also, if appropriate, an update of calibration data 
relating to the distance sensor means 16 and the heading sensor means 26 
(see FIG. 2). 
FIG. 9 shows a flow chart of the subroutine for advancing the DRP.sub.o to 
DRP.sub.c and expanding the estimate of the accuracy of the DRP.sub.c (see 
block 8A). First, the DRP.sub.o is advanced by dead reckoning to the 
DRP.sub.c (block 9A), as will be described in relation to FIG. 10. Next, 
the estimate of the accuracy of the DRP.sub.c is enlarged or expanded 
(block 9B), as will be described in connection with FIG. 11. 
FIG. 10 illustrates the flow chart of the subroutine for advancing a given 
DRP.sub.o to the DRP.sub.c (see block 9A). Reference will be made to the 
equations shown on FIG. 10. First, the heading H of the vehicle V is 
measured by computer 12 (block 10A), which receives the heading data from 
the sensor means 26. The measured heading H is then corrected for certain 
errors (block 10B). That is, and as will be described in relation to FIG. 
35-1, the computer 12 maintains a sensor deviation table by storing 
heading sensor deviation vs. sensor reading, which heading deviation is 
added to the output of the heading sensor means 26 to arrive at a more 
precise magnetic bearing. Additionally, the local magnetic variation from 
the map data base (see Section III.A.2.e) is added to the output of the 
heading sensor means 26 to arrive at a more accurate heading H of the 
vehicle V. 
Then, a distance .DELTA.d traveled since the calculation of the DRP.sub.o 
is measured by the computer 12 using the distance data from sensor means 
18 (block 10C). Next, the computer 12 calculates the distance .DELTA.D 
(see FIG. 1B) (block 10D), in which the calibration coefficient C.sub.D is 
described more fully in relation to FIG. 35-2. Next, the DRP.sub.c is 
calculated using equations 1' and 2' (block 10E), and this subroutine is 
then completed. 
FIG. 11 discloses a flow chart of the subroutine for expanding the contour 
CEP (see block 9B). Reference also will be made to FIG. 11A which is a 
simplification of FIG. 5C-1 and which shows the enlarged CEP having area 
A' after the vehicle V has traveled from one location to another and the 
distance .DELTA.D has been calculated. 
First, the X and Y distance components of the calculated .DELTA.D are 
determined by the computer 12, as follows (block 11A): 
EQU .DELTA.D.sub.x =.DELTA.D cos H (3) 
EQU .DELTA.D.sub.y =.DELTA.D sin H (4) 
Next, the computer 12 calculates certain variable heading and distance 
errors E.sub.H and E.sub.D, respectively, to be described in detail below. 
Generally, these errors E.sub.H and E.sub.D relate to sensor accuracies 
and overall system performance. 
Thereafter, new XY coordinate data are calculated by the computer 12, for 
each corner R'S'T'U' of the CEP as follows (block 11C): 
EQU R'.sub.x =R.sub.x -E.sub.D..DELTA.D.sub.x -E.sub.H..DELTA.D.sub.y (5) 
EQU R'.sub.y =R.sub.y -E.sub.D..DELTA.D.sub.y +E.sub.H..DELTA.D.sub.x (6) 
EQU S'.sub.x =S.sub.x +E.sub.D..DELTA.D.sub.x -E.sub.H..DELTA.D.sub.y (7) 
EQU S'.sub.y =S.sub.y +E.sub.D..DELTA.D.sub.y -E.sub.H..DELTA.D.sub.x (8) 
EQU T'.sub.x =T.sub.x +E.sub.D..DELTA.D.sub.x +E.sub.H..DELTA.D.sub.y (9) 
EQU T'.sub.y =T.sub.y +E.sub.D..DELTA.D.sub.y -E.sub.H..DELTA.D.sub.x (10) 
EQU U'.sub.x =U.sub.x -E.sub.D..DELTA.D.sub.x +E.sub.H..DELTA.D.sub.y (11) 
EQU U'.sub.y =U.sub.y -E.sub.D..DELTA.D.sub.y -E.sub.H..DELTA.D.sub.x (12) 
As indicated above, E.sub.H and E.sub.D are variables, as are 
.DELTA.D.sub.x and .DELTA.D.sub.y since these data depend on the distance 
traveled by vehicle V from one location to the other when it is time to 
advance the DRP.sub.o and expand the CEP. Consequently, the rate at which 
the CEP expands will vary. For example, the higher the values for E.sub.H 
or E.sub.D, the faster the CEP will grow, reflecting the decreased 
accuracy of the DRP.sub.c and certainty of knowing the actual location of 
the vehicle V. 
With the DRP.sub.o now being advanced to the DRP.sub.c and the CEP being 
expanded, FIG. 12 illustrates the flow chart of the subroutine for 
determining if it is time to test for an update (see block 8B). First, the 
computer 12 determines if 2 seconds have elapsed since a previous update 
was considered (not necessarily made) (block 12A). If not, it is not time 
for testing for an update (block 12B) and the remaining program is 
bypassed with control being returned to the main program. 
If the 2 seconds have elapsed, computer 12 determines if the vehicle V has 
traveled a threshold distance since the previous update was considered 
(block 12C). If not, it is not time for testing for an update (block 12B). 
If yes, then it is time to determine if an update should be made (block 
12D). 
FIG. 13 is a flow chart of the subroutine for performing the 
multi-parameter evaluation by the computer 12 (see blocks 8C and 8D). 
First, the computer 12 determines a most probable line segment S, if any, 
based on the parameters (1)-(4) listed above (block 13A), as will be 
further described in relation to FIG. 14. If a most probable line segment 
S has been found (block 13B), then a determination is made (block 13C) as 
to whether this most probable segment S passes the correlation tests of 
the correlation parameter, as will be described in relation to FIG. 23. If 
not, a flag is set to bypass the update subroutine (block 13D). If yes, a 
flag is set (block 13E), so that control proceeds to the update 
subroutines. 
FIG. 14 shows the flow chart of the subroutine for determining the most 
probable line segment S and if this line segment S is sufficiently 
probable to proceed with the update subroutines (see block 13A). First, 
the XY coordinate data of a line segment S are fetched by computer 12 from 
the navigation neighborhood of the map data base stored on medium 14 
(block 14A). Then, the computer 12 determines if this line segment S is 
parallel to the heading H of the vehicle within a threshold (see the 
heading parameter, Section IV B1.) (block 14B), as will be described in 
relation to FIG. 15. If not, then the computer 12 determines if this line 
segment S is the last segment S in the navigation neighborhood to fetch 
(block 14C). If not, then the subroutine returns to block 14A, whereby the 
computer 12 fetches another segment S. 
If the line segment S that is fetched is parallel to the heading H of the 
vehicle V within a threshold (block 14B), then the computer 12 determines 
if this line segment S intersects the CEP (block 14D) (see the closeness 
parameter relative to the estimate of the accuracy of the DRP.sub.c ; 
Section IV B2). An example of a procedure for determining whether a line 
segment S intersects the CEP is disclosed in a book entitled, "Algorithms 
for Graphics and Image Processing," by Theodosios Pavlidis, Computer 
Science Press, Inc., 1982 at .sctn.15.2 entitled, "Clipping a Line Segment 
by a Convex Polygon", and .sctn.15.3 entitled, "Clipping a Line Segment by 
a Regular Rectangle". If this line segment S does not intersect the CEP 
(block 14D), and if this line segment S is not the last segment S in the 
navigation neighborhood that is fetched (block 14C), then the subroutine 
returns to block 14A, whereby the computer 12 fetches another line segment 
S. If this line segment S does intersect the CEP (block 14D), then this 
line segment S is added by the computer 12 to a list stored in memory of 
lines-of-position L-O-P (block 14E) which qualify as probable segments S 
for further consideration. 
Next, the computer 12 tests this line segment S which was added to the list 
for the parameters of connectivity (see Section IV B3) and the closeness 
of two line segments S (see Section IV B4) (block 14F), as will be further 
described in relation to FIG. 16. If this line segment S fails a 
particular combination of these two tests, it is removed from the L-O-P 
list. The subroutine then continues to block 14C. 
When the segment test of block 14C passes, then a most probable line 
segment S, if any, is selected by the computer 12 from the remaining 
entries in the L-O-P list (block 14G), as will be further described in 
relation to FIG. 20. It is this selected most probable line segment S 
which is the segment to which the DRP.sub.c is updated to the DRP.sub.cu 
if it passes the tests of the correlation parameter. 
FIG. 15 shows the flow chart of the subroutine for determining if a segment 
S is parallel to the heading H of the vehicle V, i.e., the heading 
parameter (see block 14B). Initially, an angle .theta. of the line segment 
S is calculated (block 15A) in accordance with the following equation: 
EQU .theta.=arc tangent {(Y.sub.2 -Y.sub.1)/(X.sub.2 -X.sub.1)}(13) 
where X.sub.1, X.sub.2, Y.sub.1, Y.sub.2 are the XY coordinate data of the 
end points EP of the line segment S currently being processed by the 
computer 12. 
Then, the current heading H of the vehicle V is determined, i.e., the angle 
.alpha. (block 15B) from the heading data received from the sensor means 
26. Next, the computer 12 determines if 
.vertline..theta.-.alpha..vertline. or 
.vertline..theta.-.alpha.+180.degree..vertline. is less than a threshold 
number of degrees (block 15C). If this difference is not less than the 
threshold (block 15D), then the computer 12 determines that this line 
segment S is not parallel to the heading H of the vehicle (block 15E). If 
this difference is less than the threshold (block 15D), then the computer 
12 determines that this segment S is parallel to the heading H of the 
vehicle V (block 15F). 
FIG. 16 shows the flow chart of the subroutine for testing for the 
parameters of connectivity and closeness of two line segment S (see block 
14F). First, the computer 12 calculates the distance from the current dead 
reckoned position DRP.sub.c to the line segment S (now a line-of-position 
L-O-P via block 14E) being processed (block 16A), as will be described 
further in relation to FIG. 17. Then, the computer 12 accesses the 
navigation neighborhood of the map data base to compute if this line 
segment S is connected to the "old street", which, as previously 
mentioned, corresponds to the line segment S to which the next preceding 
DRP.sub.cu was calculated to be on (block 16B). This line segment S and 
the old street segment S are or are not connected, as was described 
previously in relation to FIG. 6C. 
Then, if this is the first line segment S being processed (block 16C), the 
XY coordinate data of this segment S are saved as "side 1" (block 16D). 
This "side 1" means that this line segment S is on one side of the 
DRP.sub.c, as mentioned above in relation to FIG. 6D. Also, the result of 
the distance calculation (block 16A) is saved (block 16E), as well as the 
result of the segment connection calculation (block 16B) (block 16F). 
If this line segment S currently being processed is not the first segment S 
(block 16C), then the computer 12 determines if this segment S is on the 
same side of the DRP.sub.c as the side 1 segment S (block 16G). If it is 
on the same side as the side 1 segment S, then the computer 12 selects the 
most probable segment S on side 1 (block 16H), as will be described in 
relation to the subroutine of FIG. 18. 
If this line segment S is not on side 1 (block 16G), then it is on "side 
2", i.e., the other side of the DRP.sub.c. Accordingly, the most probable 
segment S on side 2 is selected (block 16I), as will be described for the 
subroutine of FIG. 19. Thus, at the end of this subroutine of FIG. 16, a 
most probable line segment S if any on side 1 and a most probable line 
segment S if any on side 2 of the DRP.sub.c have been selected, and these 
will be further tested for closeness or ambiguity, as will be described in 
relation to FIG. 20. All other L-O-P's on the list (see block 14E) have 
been eliminated from further consideration. 
FIG. 17 is a flow chart showing the subroutine for calculating a distance d 
from the DRP.sub.c to a line segment S (see block 16A). First, using the 
coordinate data X.sub.2 Y.sub.2 and X.sub.1 Y.sub.1, which define the 
segment S, and the XY coordinate data of the DRP.sub.c, the intersection I 
of a line 1, perpendicular to the segment S, and the segment S is 
calculated by the computer 12 (block 17A). The reason for the 
perpendicularity of the line 1 is that this will provide the closest 
intersection I to the DRP.sub.c. This intersection I is identified by 
coordinate data X.sub.3 Y.sub.3. Then, the distance d between the 
DRP.sub.c and the intersection I is calculated using the XY coordinate 
data of the DRP.sub.c and X.sub.3 Y.sub.3 (block 17B). 
FIG. 18 illustrates the flow chart of the subroutine for selecting the most 
probable line segment S on side 1 of the current dead reckoned position 
DRP.sub.c (see block 16H). First, the computer 12 determines if this line 
segment S being processed and the side 1 line segment S are both connected 
to the old street segment S (block 18A). If so connected, then the 
computer 12, having saved the result of the distance calculation (block 
16E), determines if this line segment S is closer to the current dead 
reckoned position DRP.sub.c than the side 1 line segment S (block 18B). If 
not, the side 1 segment S is retained as the side 1 segment S (block 18C). 
If closer, then this line segment S is saved as the new side 1 segment S 
along with its distance and connectivity data (block 18D). 
If this line segment S and the side 1 segment S are not both connected to 
the old street segment S (block 18A), then the computer 12 determines if 
this line segment S and the side 1 segment S are not both connected to the 
old street segment S (block 18E). If the answer is yes, then the 
subroutine proceeds via block 18B as above. If the answer is no, then the 
computer 12 determines if this line segment S is connected to the old 
street segment S and if the side 1 segment S is not so connected (block 
18F). If the answer is no, then the side 1 segment S is retained as the 
side 1 segment S (block 18C). Otherwise, this line segment S becomes the 
side 1 segment S (block 18D). Thus, at the end of this subroutine, only 
one line segment S on one side of the current dead reckoned position 
DRP.sub.c is saved as the side 1 segment S. 
FIG. 19 shows the flow chart of the subroutine for selecting the most 
probable line segment S on side 2, i.e., the other side from side 1 of the 
current dead reckoned position DRP.sub.c (see block 16I). If this is the 
first line segment S on side 2 being considered by the computer 12 (block 
19A), then this line segment S is saved as the "side 2" segment S along 
with its distance and connectivity data (block 19B). If not, then the 
computer 12, having saved the results of the street connection tests 
(block 16F), decides if this line segment S and the side 2 segment S are 
both connected to the old street segment S (block 19C). If yes, then the 
computer 12, having saved the results of the distance calculation (block 
16E), decides if this line segment S is closer to the current dead 
reckoned position DRP.sub.c than the side 2 segment S (block 19D). If not, 
the side 2 segment S is retained as the side 2 segment S (block 19E). If 
it is closer, then this line segment S is now saved as the side 2 segment 
S along with its distance and connectivity data (block 19F). 
If this line segment S and the side 2 segment S are not both connected to 
the old street segment S (block 19C), then the computer 12 determines if 
this line segment S and the side 2 segment S are both not connected to the 
old street segment S (block 19G). If the answer is yes, then the 
subroutine proceeds through block 19D. If not, then a decision is made by 
the computer 12 if this line segment S is connected to the old street 
segment S and the side 2 segment S is not connected to the old street 
segment S (block 19H). If not, then the side 2 segment S is retained as 
the side 2 segment S (block 19E). If yes, then this line segment S is 
retained as the new side 2 segment S along with its distance and 
connectivity data (block 19F). 
FIG. 20 shows the flow chart of the subroutine for selecting the most 
probable segment S of the remaining segments S (see block 14G). First, the 
computer 12, having made a list of segments S qualifying as a 
line-of-position L-O-P (block 14E) and eliminating all but no more than 
two, determines if only one segment S has qualified as such a 
line-of-position L-O-P (block 20A). If there is only one, then this line 
segment S is selected as the most probable segment S in the navigation 
neighborhood at this time (block 20B). The computer 12 then determines if 
this most probable segment S passes the tests of the correlation parameter 
(block 20C), as will be described in connection with the subroutine of 
FIG. 23. If this segment S does not pass these tests, no update will 
occur. If this segment S passes the correlation tests, then the subroutine 
continues accordingly towards determining the point on this line segment S 
to which the DRP.sub.cu should be positioned i.e., towards an update of 
DRP.sub.c to DRP.sub.cu. 
If more than one remaining line segment S qualifies as a line-of-position 
L-O-P (block 20A), then there is a side 1 segment S and a side 2 segment 
S, and the computer 12 determines if the side 1 segment S is connected to 
the old street segment S and if the side 2 segment S is not connected to 
the old street segment S (block 20D). If the answer is yes, then the side 
1 segment is selected as the most probable segment S in the navigation 
neighborhood (block 20E), and the subroutine continues directly to block 
20C. 
If the answer is no (block 20D), then the computer 12 determines if the 
side 2 segment S is connected to the old street segment S and the side 1 
segment S is not connected to the old street segment S (block 20F). If the 
answer is yes, then the side 2 segment S is selected as the most probable 
segment S in the navigation neighborhood (block 20G), and the subroutine 
continues directly to block 20C. If the answer is no, then the computer 12 
determines if the side 1 segment S and the side 2 segment S are too close 
together (block 20H) (see the ambiguity parameter; Section IV B4), as will 
be described more fully in relation to the flow chart of FIG. 21. If the 
side 1 segment S and the side 2 segment S are too close together, then the 
computer 12 determines that no most probable segment S exists at this time 
(block 20I) and no update will be made at this time. 
If these two line segments S are not too close together (block 20H), then 
the computer 12 determines if one segment S is closer to the DRP.sub.c 
than the other segment S within a threshold (block 20J), as will be 
further described in connection with the subroutine of FIG. 22. If not, 
then the computer 12 determines that no most probable segment S occurs at 
this time (block 20I); consequently, no update will be made at this time. 
If yes, then the one segment S is selected as the most probable segment S 
(block 20K) and the subroutine continues to block 20C. Thus, at the 
completion of this subroutine, either no most probable segment S exists at 
this time or a most probable segment S exists if it passes the test of the 
correlation parameter (see Section IV.B.5 above). 
FIG. 21 shows the flow chart of the subroutine for determining if the side 
1 and side 2 segments S are too close together (see block 20H). First, the 
distance between the two segments S is calculated by the computer 12 
(block 21A). Then, the computer 12 determines if this distance is below a 
threshold distance (block 21B). If yes, then the two segments S are too 
close together, representing an ambiguous condition (block 21C), thereby 
resulting in no updating at this time. If not, the segments S are 
determined to be not too close together (block 21D) and an update possibly 
may occur. 
FIG. 22 illustrates the flow chart of the subroutine for determining if the 
side 1 segment S or the side 2 segment S is significantly closer to the 
DRP.sub.c than the other (see block 20J). First, the computer 12 
calculates the ratio of the distance from the DRP.sub.c to the side 1 
segment S to the distance from the DRP.sub.c to the side 2 segment S 
(block 22A). Then, the computer 12 determines if this ratio is greater 
than a threshold or less than 1/threshold, (block 22B). If not, then the 
DRP.sub.c is determined to be not closer to one segment S than the other 
segment S (block 22C), thereby resulting in no updating at this time. If 
yes, then the DRP.sub.c is determined to be closer to the one segment S 
than the other (block 22D) and an update possibly may occur. 
FIG. 23 shows the subroutine for performing the correlation tests with 
respect to the most probable segment S (see block 20C). As was discussed 
in relation to the subroutine of FIG. 13, once the most probable segment S 
has been determined to exist, a determination is made by the computer 12 
as to whether or not the vehicle has been turning, as will be described 
further in relation to FIG. 25. If the computer 12 determines that the 
vehicle V has not been turning (block 23A), it performs the correlation 
test by a simple path matching computation (blocks 23B-23F), as will be 
described in conjunction with FIGS. 24A-24D (see also Section IV.B.5b 
above). Otherwise, it performs the correlation test by calculating and 
testing a correlation function (blocks 23G-23J) (see also Section IV.B.5c 
above). 
FIG. 24A to FIG. 24D are illustrations of plots of various data used by the 
computer 12 in determining if the simple path match exists. FIG. 24A is a 
plot of XY positions of a plurality of segments S of the street St on 
which the vehicle V may be actually moving, in which this street St has 
six line segments S.sub.1 -S.sub.6 defined by end points a-g, as shown, 
and one of which corresponds to the most probable segment S. FIG. 24B is a 
plot of the XY positions of a plurality of dead reckoned positions DRP 
previously calculated in accordance with the present invention and 
equations (1) or (1') and (2) or (2'), as shown at points A-K, including 
the current dead reckoned position DRP.sub.c at point K. FIG. 24B shows 
these dead reckoned positions DRP over a total calculated distance D 
traveled by the vehicle V, which is the sum of .DELTA.D.sub.1 
-.DELTA.D.sub.10. FIG. 24C shows the headings h.sub.1 -h.sub.6 
corresponding to the line segments S.sub.1 -S.sub.6, respectively, as a 
function of distance along the street St of FIG. 24A (as distinct from the 
X position). As previously mentioned, the map data base has end point data 
identifying the line segments S.sub.1 -S.sub.6 of a given street St shown 
in FIG. 24A, but the heading data of FIG. 24C are calculated by the 
computer 12, as needed in accordance with the discussion below. FIG. 24D 
shows the corresponding measured headings H.sub.1 -H.sub.10 of the vehicle 
V for .DELTA.D.sub.1 -.DELTA.D.sub.10, respectively, of FIG. 24B. 
The .DELTA.D distance data and the heading data H.sub.1 -H.sub.10 shown in 
FIG. 24B and FIG. 24D are calculated by and temporarily stored in the 
computer 12 as a heading table of entries. FIG. 24D is a plot of this 
table. Specifically, as the vehicle V travels, every second the distance 
traveled and heading of the vehicle V are measured. An entry is made into 
the heading table if the vehicle V has traveled more than a threshold 
distance since the preceding entry of the table was made. 
With reference again to FIG. 23, the computer 12 calculates the heading h 
of the street St for each entry in the heading table for a past threshold 
distance traveled by the vehicle V (block 23B). That is, this heading h of 
the street St is calculated for a threshold distance traveled by the 
vehicle V preceding the current dead reckoned position DRP.sub.c indicated 
in FIG. 24B. For example, this threshold distance may be approximately 300 
ft. 
Then, the computer 12 calculates the RMS (root mean square) heading error 
over this threshold distance (block 23C). The RMS heading error 
calculation is performed in accordance with the following equation: 
##EQU3## 
where: n=number of entries in heading table 
heading (i)=heading of vehicle V at i.sup.th entry in heading table 
street heading (i,p)=street heading for i.sup.th entry in heading table 
assuming the vehicle V is at a position p. 
The computer 12 then determines if this RMS heading error (calculated for 
one position p-- the DRP.sub.c) is less than a threshold (block 23D). If 
it is, then the computer 12 determines that the measured dead reckoning 
path of the vehicle V does match this most probable element S and the 
latter is saved (block 23E). If not, then the computer 12 determines that 
the measured dead reckoning path of the vehicle V does not match this most 
probable segment, so that there is no most probable segment S (block 23F). 
Thus, if the match exists, there is a most probable segment S to which the 
current dead reckoned position DRP.sub.c can be updated; otherwise, no 
update is performed at this time. 
If the computer 12 determines that the vehicle V has been turning (block 
23A), then it performs the correlation test by computation of a 
correlation function (blocks 23G-23J). First, the computer 12 calculates a 
correlation function between the measured path of the vehicle V and the 
headings of certain line segments S including the most probable segment S 
and line segments S connected to it (block 23G), as will be described 
further in relation to FIG. 26. The computer 12 then determines if the 
results from this correlation function passes certain threshold tests 
(block 23H), as will be described in relation to FIG. 27. If not, then no 
most probable segment is found (block 23F). If the correlation function 
does pass the threshold tests (block 23H), then XY data of a "most 
probable point", i.e., the best point BP previously mentioned, on the 
correlation function is saved corresponding to a position along the 
segment S with the best correlation (block 23I). Then, this segment S is 
saved as the most probable segment. 
FIG. 25 shows the subroutine for determining if the vehicle V is turning 
(see block 23A). The computer 12 begins by comparing the data identifying 
the heading H associated with the current dead reckoned position DRP.sub.c 
and the data identifying the preceding heading H associated with the old 
dead reckoned position DRP.sub.o (block 25A). If the current heading data 
indicate that the current heading H has changed more than a threshold 
number of degrees (block 25B), then the computer 12 decides that the 
vehicle V has been turning (block 25C). 
If the current heading H has not changed more than a threshold number of 
degrees (block 25B), then the computer 12 determines if the vehicle V has 
been on the current heading H for a threshold distance (block 25D). If 
not, the vehicle V is determined to be turning (block 25C); however, if 
the vehicle V has been on the current heading H for a threshold distance 
(block 25D), then a decision is made by the computer 12 that the vehicle V 
is not turning (block 25E). 
FIG. 26 illustrates the flow chart of the subroutine for calculating the 
correlation function between the path of the vehicle V and the selected 
line segments S mentioned above (see block 23G), while FIG. 26-1 
illustrates the calculated correlation function. The correlation function 
is calculated by first calculating a maximum dimension L of the CEP 
associated with the DRP.sub.c (block 26A). Then, with reference again to 
FIG. 24A and FIG. 24C, which are also used to explain this correlation 
test, the two end points EP.sub.1, EP.sub.2 of the interval L which are 
plus or minus L/2 respectively from a best guess (BC) position or the 
DRP.sub.cu are calculated by the computer 12 (block 26B). Next, the 
computer 12 divides this interval L into a plurality of positions which 
are, for example 40 feet apart (block 26C). Next, for each such position, 
the heading h of the street St is calculated for each .DELTA.D distance 
entry in the above-mentioned heading table (block 26D). Thereafter, the 
RMS heading error for each position (p) along the interval L is calculated 
by the computer 12, using equation (14) (block 26E). 
FIG. 27 illustrates the flow chart of the subroutine for determining if the 
correlation function passes certain thresholds (see block 23H). First, the 
computer 12 finds the position of minimum RMS error (block 27A), which is 
shown in FIG. 26-1. Then, the computer 12 determines if this RMS error is 
below a threshold (block 27B). If not, the remaining subroutine is 
bypassed and no most probable segment S is found (returning to block 23F). 
If the RMS error is below a threshold, then the curvature of the 
correlation function at the minimum position is calculated by taking a 
second order difference of the RMS error vs. position (block 27C). If this 
curvature is not above a threshold (block 27D), then the correlation test 
fails and the remaining subroutine is bypassed (block 27F). If this 
curvature is above the threshold (block 27D), then the computer 12 
determines that the correlation calculation passes the test of all 
thresholds (block 27E), whereby the position of the RMS minimum error is 
the best point BP (see block 23I) that becomes DRP.sub.cu. If the 
curvature is above the threshold, then this assures that the correlation 
parameter has peaked enough. For example, if the line segments S for the 
distances covered by the heading table are straight, then the second order 
difference would be zero and the correlation parameter would not contain 
any position information for the DRP.sub.cu. 
Consequently, and with reference again to FIG. 8, assume now that as a 
result of the multiparameter evaluation (block 8C), that a more likely 
position for the DRP.sub.c can be determined (block 8D), in that there is 
a line segment S to which the DRP.sub.c may be updated. Therefore, FIG. 28 
is a flow chart showing generally the subroutine for the update (see block 
8E). Thus, first the computer 12 updates the current dead reckoned 
position DRP.sub.c to the current updated dead reckoned position 
DRP.sub.cu (block 28A), as will be further described in relation to FIG. 
29. Next, the computer 12 updates the estimate of the accuracy of the 
DRP.sub.c (block 28B), as will be described in relation to FIG. 32. Next, 
the sensor means 16 and sensor means 26 are recalibrated (block 28C), as 
will be described in relation to FIG. 35. 
FIG. 29 illustrates the flow chart of the subroutine for updating the 
DRP.sub.c to the DRP.sub.cu. If the vehicle has been turning (block 29A), 
then the XY coordinate data of the DRP.sub.c are set to the XY coordinate 
data of the best correlation point BP previously calculated (see block 
23I), thereby updating the DRP.sub.c to the DRP.sub.cu (block 29B). Then, 
a dead reckoning performance ratio PR is calculated (block 29C), which, 
for example, is equal to the distance between the DRP.sub.c and the 
DRP.sub.cu divided by the calculated distance .DELTA.D the vehicle V has 
traveled since the last update of a DRP.sub.c to a DRP.sub.cu. This 
performance ratio PR is used to calculate a certain error in the system 10 
that, as previously mentioned and as will be further described, is used 
for determining the varying rate or rate of growth of the CEP. If the 
vehicle V has not been turning (block 29A), then the DRP.sub.c is set to 
the most probable constant course position (block 29D), as will be 
described in relation to FIG. 30, followed by the calculation of the dead 
reckoning performance ratio PR (block 29C). 
FIG. 30 illustrates the flow chart of the subroutine for updating a given 
DRP.sub.c to a given DRP.sub.cu when the vehicle V is on a constant 
heading H (see block 29D). FIG. 30-1 also will be used to describe the 
updating of the DRP.sub.c to the DRP.sub.cu and shows the DRP.sub.c, a 
given CEP associated with the DRP.sub.c and the most probable line segment 
S. 
Thus, first the computer 12 calculates the aspect ratio AR of the CEP, 
which equals .vertline.RS.vertline..div..vertline.ST.vertline. (block 
30A). Then, the computer 12 determines if this aspect ratio AR is close to 
1 within a threshold (block 30B). If it is, then the update of the 
DRP.sub.c is made to the closest point along the most probable segment S 
(block 30C). As shown in FIG. 30-1, the closest point is point P.sub.3 
which is the point at which a line l, drawn through the DRP.sub.c and 
perpendicular to the segment S.sub.1, intersects the latter. 
If the aspect ratio AR is not close to 1 within the threshold (block 30B), 
then the computer 12 calculates an angle .alpha. of the segment S shown in 
FIG. 30-1 (block 30D). Then, the computer 12 calculates an angle .beta. of 
the major axis of the CEP, as shown in FIG. 30-1, (block 30E). Next, the 
computer 12 determines if the angle (.alpha.-.beta.) is less than a 
threshold (block 30F). If it is, then the subroutine proceeds to block 
30C. If not, the DRP.sub.c is updated to a most probable point 
(approximately the most probable point) on the segment S (block 30G), as 
will now be described in relation to FIG. 31. 
FIG. 31 shows the flow chart of the subroutine for updating the DRP.sub.c 
to a most probable point on the most probable segment S (see block 30G). 
Reference again will also be made to FIG. 30-1. First, the computer 12 
determines the sides which are parallel to the major axis of the CEP, 
i.e., sides S.sub.1 and S.sub.2 in the example shown in FIG. 30-1, (block 
31A). Next, the computer 12 calculates the points P.sub.1 and P.sub.2 
where the sides S.sub.1 and S.sub.2 intersect the most probable segment S 
(block 31B). Next, the computer 12 calculates the mid-point P.sub.4 
between point P.sub.1 and P.sub.2 (block 31C). Then, the computer 12 
calculates the closest point P.sub.3 (block 31D) in the manner previously 
described. Next, a distance d between point P.sub.3 and point P.sub.4 is 
calculated by the computer 12 (block 31E). Finally, the computer 12 
calculates the XY coordinate data of the DRP.sub.cu (block 31F) in 
accordance with the following equations: 
EQU DRP.sub.cu (x)=P.sub.3 (x)+d cos (.alpha.-.beta.) cos .alpha.(15) 
EQU DRP.sub.cu (y)=P.sub.3 (y)+d cos (.alpha.-.beta.) sin .alpha.(16) 
Having now updated the DRP.sub.c to the DRP.sub.cu, the computer 12 
performs the subroutine shown in FIG. 32 for updating the CEP associated 
with the DRP.sub.c to an updated CEP.sub.u associated with the DRP.sub.cu 
(see block 28B). If the vehicle has not been turning (block 32A), then the 
CEP is updated based on the constant heading most probable position (block 
32B), as will be described in FIG. 33. If the vehicle has been turning, 
the CEP will be updated based on the calculation of the correlation 
function (block 32C), as will be described in FIG. 34. 
FIG. 33 shows the flow chart of the subroutine for updating the CEP to the 
CEP.sub.u based on the constant heading most probable position (see block 
32B). Also, reference will be made to FIG. 33-1 which is used to explain 
the flow chart of FIG. 33, in which FIG. 33-1 shows a given CEP, the 
associated DRP.sub.c, the DRP.sub.cu and the resulting CEP.sub.u. First, 
assume that the computer 12 has calculated the DRP.sub.cu as described 
previously in relation to FIG. 30. Then, an angle .alpha. of the most 
probable segment S is calculated (block 33A). Then, the computer 12 
calculates a line l.sub.1 which is parallel to the most probable segment S 
and passes through the DRP.sub.c (block 33B), i.e., line l.sub.1 also has 
the angle .alpha.. Next, points P.sub.1 and P.sub.2 along the line l.sub.1 
which intersect the CEP are calculated (block 33C). Next, the computer 12 
calculates the distance d.sub.1 between the points P.sub.1 and P.sub.2 
(block 33D). Next, for the major or longitudinal axis of the CEP.sub.u, 
the distance d.sub.2 =d.sub.1 /2 is calculated (block 33E). Then, the 
computer 12 determines the half axis or distance d.sub.3 for the CEP.sub.u 
perpendicular to the most probable segment S, in which d.sub.3 is equal to 
the half-width of the width W of the street St that is fetched from the 
navigation neighborhood of the map data base (block 33F). The calculated 
distances, d.sub.2 and d.sub.3, are compared to threshold minimum 
distances according to the map accuracy data fetched from the map data 
base (block 33G) to set the minimum size of the CEP.sub.u (see Section 
III.A.2.f). Finally, the XY coordinate data of the corners R"S"T"U" of the 
CEP.sub.u are calculated as follows (block 33H): 
EQU R"(x)=DRP.sub.cu (x)+d.sub.2 cos .alpha.-d.sub.3 sin .alpha.(17) 
EQU R"(y)=DRP.sub.cu (y)+d.sub.2 sin .alpha.+d.sub.3 cos .alpha.(18) 
EQU S"(x)=DRP.sub.cu (x)+d.sub.2 cos .alpha.-d.sub.3 sin .alpha.(19) 
EQU S"(y)=DRP.sub.cu (y)+d.sub.2 sin .alpha.-d.sub.3 cos .alpha.(20) 
EQU T"(x)=DRP.sub.cu (x)-d.sub.2 cos .alpha.+d.sub.3 sin .alpha.(21) 
EQU T"(y)=DRP.sub.cu (y)-d.sub.2 sin .alpha.-d.sub.3 cos .alpha.(22) 
EQU U"(x)=DRP.sub.cu (x)-d.sub.2 cos .alpha.-d.sub.3 sin .alpha.(23) 
EQU U"(y)=DRP.sub.cu (y)-d.sub.2 sin .alpha.+d.sub.3 cos .alpha.(24) 
FIG. 34 shows the flow chart of the subroutine for updating the CEP to the 
CEP.sub.u based on the outcome of correlation function (see block 32C). 
FIG. 34-1, which shows the most probable segment S, the DRP.sub.cu and the 
resulting CEP.sub.u, will also be used to describe the flow chart of FIG. 
34. Thus, first, the computer 12 calculates an angle .alpha. (block 34A). 
Then, an estimated uncertainty of the position of the DRP.sub.cu based on 
the curvature of the correlation function is calculated, i.e., the 
distance d.sub.2 (block 34B). Next, the computer 12 determines the 
half-width, d.sub.1, of the street St based on its width W which is 
fetched from the navigation neighborhood of the map data base (block 34C). 
As similarly described above, the calculated distances, d.sub.1 and 
d.sub.2, are compared to threshold minimum distances according to the map 
accuracy data fetched from the map data base to set the minimum size of 
the CEP.sub.u ; (see Section III.A.2f). Next, the updated CEP.sub.u is 
calculated using similar equations as shown for R" , as follows (block 
34D): 
EQU R"(x)=DRP.sub.cu (x)-d.sub.1 sin .alpha.+d.sub.2 cos .alpha.(25) 
EQU R"(y)=DRP.sub.cu (y)+d.sub.1 cos .alpha.+d.sub.2 sin .alpha.(26) 
With the DRP.sub.cu being determined (see block 28A), and the CEP.sub.u 
being determined (see block 28B), FIG. 35 now shows the flow chart of the 
subroutine for recalibrating the sensor means 16 and 26 (see block 28C). 
If the vehicle V is turning (block 35A), as may be determined in a manner 
previously described, then the remaining subroutine is bypassed and the 
sensor means 16 and 26 are not recalibrated at this time. If the vehicle V 
is not turning, then the heading sensor means 26 is recalibrated (block 
35B), as will be described more fully below in relation to FIG. 35-1. 
Next, if the vehicle V did not just finish a turn, then the remaining 
subroutine is bypassed (block 35C). If the vehicle V did just finish a 
turn, then the distance sensor means 16 is recalibrated (block 35D), as 
will be described more fully below in relation to FIG. 35-2. 
FIG. 35-1 shows a plot of the deviation of the heading sensor means 26 as a 
function of the output of the heading sensor means 26. This plot is stored 
on medium 14 as a heading deviation table mentioned previously. Upon 
updating the DRP.sub.c to the DRP.sub.cu, the measured heading H of the 
vehicle V and the actual heading h of the street St corresponding to the 
DRP.sub.cu are then known, as previously described. Consequently, with 
this heading data being available, any error or deviation between the 
measured heading H and the actual heading h of the street St is known. 
Therefore, the computer 12 can now make an appropriate correction in the 
heading deviation table corresponding to a particular output of the 
heading sensor means 26 to correct a corresponding calibration coefficient 
stored on medium 14 and, thereby, provide the more accurate advancement of 
a given DRP.sub.o to a given DRP.sub.c. 
With reference to FIG. 35-2, assume that the vehicle V is traveling on a 
street St.sub.1 and makes a right turn onto the street St.sub.2. Assume 
also that after the turn onto the street St.sub.2, the calculation of the 
DRP.sub.c places the vehicle V from position A to either position B, which 
is short of the street St.sub.2, or to position B' which is beyond the 
street St.sub.2. Also assume that as a result of the vehicle navigational 
algorithm, the DRP.sub.c at position B or position B' is updated to 
position C which happens to coincide with the actual location of the 
vehicle V. 
The calibration of the distance sensor means 16 is checked after the 
vehicle V makes the turn onto the street St.sub.2. When the vehicle 
navigational algorithm updates the DRP.sub.c to the DRP.sub.cu for the 
first time to position C after the turn is made, the calibration 
coefficient C.sub.D (see FIG. 10) of the distance sensor means 16 is 
increased or decreased, as follows. If the DRP.sub.c placed on the 
position of the vehicle V short of the street St.sub.2 within a threshold, 
as shown at point B, the calibration coefficient C.sub.D is too low and, 
therefore, increased. If, however, the DRP.sub.c placed the vehicle V 
beyond the street St.sub.2 within a threshold, as shown at B', the 
calibration coefficient C.sub.D is too high and, therefore, is decreased. 
As with other calibration data, the distance calibration coefficient 
C.sub.D is stored on the medium 14 and processed by the computer 12 to 
provide a more accurate DRP. 
As was mentioned in relation to FIG. 5C-1, and discussed in relation to 
equations (5)-(12), the CEP may be enlarged at a varying rate as the 
DRP.sub.o is advanced to the DRP.sub.c as a function of the error 
variables E.sub.H and E.sub.D. FIG. 36 is a flow chart of a subroutine for 
determining E.sub.H and E.sub.D. First, the computer 12 calculates a 
change in heading from information received from the flux gate compass 28 
shown in FIG. 2 (block 36A), as a DRP.sub.o is advanced to a DRP.sub.c. 
Then, the computer 12 calculates the change in heading from information 
received from the differential wheel sensors 18 of FIG. 2 (block 36B) as 
the DRP.sub.o is advanced to the DRP.sub.c. 
Next, the computer 12 calculates an error e.sub.1 based on the above 
calculations (block 36C), as will now be described in detail. As already 
indicated, heading measurements are obtained from two sources, one being 
the flux gate compass 28 and the other being the differential wheel 
sensors 18. The flux gate compass 28 measures the horizontal component of 
the terrestrial magnetic field and indicates the orientation of the 
vehicle V relative to magnetic north. The differential wheel sensors 18 
measure the rotation of opposing wheels on the same axis of the vehicle V 
from which an angle A of turning may be calculated, as follows: 
EQU A=(D.sub.R -D.sub.L)/T (27) 
where D.sub.4 is the distance traveled by the right wheel, D.sub.L is the 
distance traveled by the left wheel, and T is the track or distance 
between the right and left wheels. Equation 27 holds true for rear wheels 
and should be modified for front wheels. 
Both sensor 28 and differential wheel sensors 18 are subject to measurement 
errors. The flux gate compass 28 will incorrectly indicate the orientation 
of the vehicle V if the terrestrial magnetic field is distorted (e.g., 
near large steel structures). Additionally, if the vehicle V is not on a 
level surface (e.g., driving on a hill), and the compass 28 is not 
gimbled, the compass 28 will incorrectly read due to magnetic dip error. 
If the compass 28 is gimbled, it will read incorrectly when the vehicle V 
accelerates and decelerates, again due to magnetic dip error. For these 
reasons, the compass 28 is not absolutely accurate. 
The differential wheel sensors 18 are subject to errors because of wheel 
slip. If the vehicle V accelerates or decelerates too quickly, one or both 
of the wheels will slip and the measured distance will be incorrect, 
whereby the angle A will be incorrectly calculated. Additionally, if the 
vehicle V turns sharply or fast enough, the wheels will slip due to 
lateral acceleration and, thereby, incorrectly indicate the distance each 
wheel traveled. Finally, the point of contact of each wheel with the 
streets can change, making the track T different and, hence, introducing 
error. 
Consequently, the computer 12 makes comparisons between the heading 
information from the compass 28 and from the differential wheel sensors 18 
to determine how accurate the overall heading measurement is, i.e., to 
determine e.sub.1. If both agree, i.e., e.sub.1 =0, the rate of growth of 
the CEP will not be affected by this factor. If, however, they disagree, 
i.e., e.sub.1 &gt;0, then the CEP will grow at an increased rate, reflecting 
the apparently decreased accuracy of the heading measurement and, hence, 
of the knowledge of the actual location of the vehicle V. 
With reference again to FIG. 36, having calculated e.sub.1 (block 36C), the 
computer 12 now calculates an update performance error e.sub.2, as follows 
(block 36D): 
EQU e.sub.2 =K.DR Performance Ratio (28) 
where K=constant, and the DR Performance Ratio (PR) is that described above 
(see block 29C). 
Next, the computer 12 calculates E.sub.H, as follows (block 36E): 
##EQU4## 
where e.sub.1 and e.sub.2 are as defined above, and e.sub.3 is a basic 
sensor accuracy of the flux gate compass 28, e.g., sin 4.degree. 0.07. 
Then, the computer 12 calculates E.sub.D, as follows (block 36F): 
##EQU5## 
where e.sub.2 is as defined above, and e.sub.4 is the basic accuracy of 
the distance sensor means 16, e.g., 0.01. 
Thus, the rate of growth of the CEP is dependent on one or more factors, 
including (1) the characteristics of the heading sensor data that indicate 
the quality of the sensor data, i.e., e.sub.1, (2) the quality of the 
previous dead reckoning performance, i.e., e.sub.2, (3) the basic sensor 
accuracy, i.e., e.sub.3 and e.sub.4, and (4) the distance .DELTA.D 
traveled by the vehicle V, pursuant to equations (5)-(12). 
X. Summary of the Vehicle Navigational Algorithm 
As the vehicle V moves over streets St identified by the map M, a given DRP 
will be advanced and updated, and a given estimate of the accuracy of the 
DRP will change accordingly. As this updating occurs, the vehicle symbol 
S.sub.v on the monitor 38 will be moved relative to the displayed map M, 
so that the driver may see the current location of the vehicle V on or 
near a street St. Accordingly, the driver will then be able to navigate 
the vehicle V over the streets St to reach a desired destination. If, for 
example, the vehicle V were a police car or taxi cab, a communications 
network (not shown) also could be employed to send the position data of 
the vehicle V from the vehicle V to a central station for monitoring the 
current position of the vehicle V and other similar vehicles V coupled 
within such a network. 
The present invention provides a technique that allows a vehicle V to be 
reliably and accurately navigated. This is accomplished through the 
maintenance, use and derivation of a significant amount of information, 
including the position of the vehicle V, the map data base, the estimate 
of the accuracy of the position of the vehicle V and the updating of the 
calibration data. 
As a result, the present invention makes reasonable decisions as to whether 
to update a given DRP.sub.c. For example, the present invention will not 
update to a street St that is so far away from a DRP.sub.c that it is not 
more probable that the vehicle V is on that street than off all the 
streets in the navigation neighborhood of the map data base. Conversely, 
an update will occur to a distant street St if it is computed to be more 
probable that the vehicle V is on that street. Furthermore, the vehicle M 
may move on and off streets St shown in the map M, such as onto driveways, 
parking lots and new streets St (paved or unpaved) that have not been 
included in the map M; yet, the vehicle navigational algorithm will 
accurately track the vehicle V due, in part, to the updating only to 
positions which are more probable. 
XI. Program Code Listings 
Assembly language code listings of significant aspects of the vehicle 
navigation algorithm, which may be executed onthe IBM PC mentioned above, 
are included as part of this specification in the form of computer 
printout sheets. The title, operation and general content of these 
assembly language code listings are as follows: 
1. NAV--This is the main navigation function which is called to test for 
and do the update. 
2. DR--This calculates the dead reckoned positions and calls QEP CALC. 
3. QEP CALC--This expands the contour of equal probability CEP (or QEP). 
14. STRSRCH--This searches the map data base for streets and performs part 
of the multiparameter evaluation--particularly, this evaluates the heading 
parameter, called INQEP (see below), calls SFCONNECT (see below) and 
evaluates the closeness of two line segments S. 
5. INQEP--This determines the intersection of a line segment S with the 
CEP. 
6. SFCONNECT--This determines if two streets St are connected. 
7. BCORCALC--This performs a binary search correlation calculation to 
evaluate the correlation parameter, including calling NPAM; MCBUF AND 
CORRELATE (see below)--if the vehicle V is turning, this also calculates 
DRP.sub.cu. 
8. NPAM--This finds a point on a segment S that is a specified distance 
away from a given point on some segment S where distance is measured along 
a specified sequence of segments S. 
9. MCBUF--This performs map course buffering; particularly this calculates 
the DR heading and compares it with the street heading. 
10. CORRELATE--This calculates the RMS error at the particular point 
determined by NPAM. 
11. IPTDIST--This calculates the intersection of a line (extending from a 
point) perpendicular to another line and the distance from the 
intersection to the point. 
12. QEPMOD--This updates CEP to CEP.sub.u, and determines DRP.sub.cu if the 
vehicle is not turning. 
13. UPDSTCAL--This updates the calibration coefficients for the distance 
sensor means 16. 
14. DEVCORR--This updates the calibration coefficients for the heading 
sensor means 26. 
While the invention has been particularly shown and described with 
reference to preferred embodiments thereof, it will be understood by those 
skilled in the art that the foregoing and other changes in form and detail 
may be made therein without departing from the spirit and scope of the 
invention. 
##SPC1## 
PG,102