United States Patent
`Croyle et al.
`
`19
`
`54) VEHICLE NAVIGATION SYSTEMAND
`METHOD
`
`75 Inventors: Steven R. Croyle, Franklin; Larry E.
`Spencer, II, Lake Orion; Ernie R.
`Sittaro, Romeo, all of Mich.
`73 Assignee: Magellan DIS, Inc., Rochester Hills,
`Mich.
`
`21 Appl. No.: 580,150
`22 Filed:
`Dec. 28, 1995
`(51) Int. Cl." ....................................................... G06G 7/48
`52 U.S. Cl. .......................... 701/213; 701/214; 701/215;
`701/208; 73/178 R
`58 Field of Search ..................................... 364/460, 461,
`364/444.1, 449.1, 450, 447, 449.7, 449.3,
`454, 453, 448, 440, 443; 340/988, 990,
`995; 73/178 R; 342/357, 457, 352, 451;
`701/207, 208, 213, 214, 215, 221, 220,
`216
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`... 235/150.27
`7/1973 Hileman ........
`3,749,893
`... 235/150.27
`1/1974 Henson et al.
`3,789,198
`3,845,289 10/1974 French ................................. 235/151.2
`3,984.806 10/1976 Tyler ......................................... 340/23
`4,032,758 6/1977 Lewis ................................... 235/150.2
`4,086,632 4/1978 Lions ...................................... 364/444
`4,107,689 8/1978 Jellinek ............................. 343/112 TC
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`0 059 435 9/1982 European Pat. Off..
`0 061564 1. 10/1982 European Pat. Off..
`0 069965 1/1983 European Pat. Off..
`0 103 847 3/1984 European Pat. Off..
`0110171 6/1984 European Pat. Off..
`O 118 886 9/1984 European Pat. Off..
`0181012 5/1986 European Pat. Off..
`O 471 405 2/1992 European Pat. Off..
`(List continued on next page.)
`
`USOO586251 1A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,862,511
`Jan. 19, 1999
`
`OTHER PUBLICATIONS
`Integration of GPS and Dead Reckoning Navigation Sys
`tems by Wei-Wen Kao published Jan. 10, 1991 in the
`Institute of Electrical and Electronics Engineers.
`Brochure: Fleet-Trak: Fleet Management System.
`McLellan, et al., Application of GPS Positioning to Man
`agement of Mobile Operations, pp. 1-16; 1991.
`Stanley K. Honey; A Novel Approach to Automotive Navi
`gation and Map Display, pp. 40–43.
`Siemens, Ali-Scout System;.
`G. C. Larson; Evaluation of an AVM System Implemented
`City-Wide in St. Louis, pp. 378-383.
`Brochure: NavTrax 1000 Fleet Management System.
`(List continued on next page.)
`Primary Examiner Jacques H. Louis-Jacques
`Attorney, Agent, or Firm-Howard & Howard
`57
`ABSTRACT
`The improved vehicle navigation System and method uses
`information from a Global Positioning System (GPS) to
`obtain Velocity vectors, which include Speed and heading
`components, for “dead reckoning the vehicle position from
`a previous position. If information from the GPS is not
`available, then the improved vehicle navigation System uses
`information from an Orthogonal axes accelerometer, Such as
`two or three orthogonally positioned accelerometers, to
`propagate vehicle position. Because the GPS information
`should almost always be available, the improved vehicle
`navigation System relies leSS on its accelerometers, thereby
`allowing the use of less expensive accelerometers. The
`improved vehicle navigation System retains the accuracy of
`the accelerometers by repeatedly calibrating them with the
`velocity data obtained from the GPS information. The
`improved vehicle navigation System calibrates the Sensors
`whenever GPS data is available (for example, once a second
`at relatively high speeds). Furthermore, the improved
`vehicle navigation System does not need to rely on map
`matching to calibrate Sensors. System flexibility is improved
`because map matching is oblivious to the hardware, and the
`System hardware can be updated without affecting map
`matching or a change in the map database.
`
`17 Claims, 13 Drawing Sheets
`
`GPS
`ANNA
`
`8
`
`22 sy
`
`
`
`22
`
`24
`
`26
`
`28
`
`N
`
`-
`
`GPS
`RECEIVER
`2.
`APP:ICATIONLIT
`-------4---
`APPLICATICK
`POESSR
`
`HARAARE
`
`He---
`
`i8UK)ATA
`mas, etc.)
`
`|
`
`20R3AX:S
`
`AccELEROMETER
`
`..
`
`USaRINTERFACE
`(DISPLAY,
`KEYBOARD, etc)
`
`
`
`Exhibit 2008
`
`

`

`5,862,511
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,253,150 2/1981 Scovill .................................... 364/449
`4,254,465
`3/1981 Land ....................................... 364/453
`4,301,506 11/1981 Turco ......
`... 364/436
`4,312,577
`1/1982 Fitzgerald .
`... 353/12
`4,351,027 9/1982 Gay et al. ...
`... 364/432
`
`1/1997 Rodal et al. ............................ 342/357
`5,594,453
`1/1997 Sprague et al.
`... 701/213
`5,596,500
`5,629,708 5/1997 Rodal et al. ............................ 342/357
`
`
`
`FOREIGN PATENT DOCUMENTS
`0488594 6/1992 European Pat. Off..
`O 496 538 7/1992 European Pat. Off..
`
`4,369,441
`
`1/1983 Wohlmuth r - - - - - - - - - - - - - - - - - - - - - - - - - - - 340/733
`
`4,403.291 9/1983 Von Tomkewitsch .................. 364/424
`4,504,913 3/1985 Miura et al. ......
`... 364/449
`4.513,377 4/1985 Hasebe et al. ...
`... 364/449
`4,528,552 7/1985 Moriyama et al.
`... 340/525
`4,543,572 9/1985 Tanaka et al. .......................... 340/723
`4,546,439 10/1985 Esparza ................................... 364/444
`4,570.227 2/1986 Tachi et al. ...
`... 364/444
`4,571,684 2/1986 Takanabe et al. ...................... 364/449
`4,608,656 8/1986 Tanaka et al. .......................... 364/449
`4,639,773
`1/1987 Hurst..............
`... 358/105
`4,646,089 2/1987 Takanabe et al. ...................... 340/995
`4,660,037 4/1987 Nakamura ............................... 340/990
`4,675,676
`6/1987 Takanabe et al.
`... 340/995
`4,711,125 12/1987 Morrison ............................... 73/178 R
`4,758,959 7/1988 Thoone et al. .......................... 364/454
`4,796,191
`1/1989 Honey et al. .....
`... 364/450
`4,814,989 3/1989 Dobereiner et al. .................... 364/444
`4,819,175 4/1989 Wuttke .................................... 364/449
`4,847,769 7/1989 Reeve.............
`364/424.02
`4,890,104 12/1989 Takanabe et al. ...................... 340/995
`
`O 514 887 11/1992 European Pat. Off.
`
`0527558 2/1993 European Pat. Off..
`0.544 403 6/1993 European Pat. Off..
`O 567 268 10/1993 European Pat. Off..
`3242904 A1 11/1982 Germany.
`3912108 4/1989 Germany.
`57-158875 9/1982 Japan.
`58009017 1/1983 Japan.
`58-27008 2/1983 Japan.
`58-113711
`7/1983 Japan.
`58-11969
`7/1983 Japan.
`58-78213 10/1983 Japan.
`60-135817 7/1985 Japan.
`59-28244 3/1995 Japan.
`1 470 694 4/1977 United Kingdom.
`2014 309 8/1979 United Kingdom.
`2144 007 2/1985 United Kingdom.
`2 115946 9/1993 United Kingdom.
`WO 92/10824 6/1992 WIPO.
`
`OTHER PUBLICATIONS
`
`o: 3. Ny.
`- - - - - - - - - - - - - - - - - - - : Lezniak, et al.; A Dead Reckoning/Map Correlation System
`4,930,085 5/1990 Kleinschmidt .......................... 323ss
`for Automatic Vehicle Tracking; pp. 47–60.
`4,949,268 8/1990 Nishikawa et al. ..................... 364/449
`May, 1973; Vehicular Technology; Antartic Navigation; pp.
`4,954,833 9/1990 Evans et al. ...
`... 342/357
`36-41.
`4,989,151
`1/1991 Nuimura ................................. 364/449
`R. L. French; MAP Matching Origins Approaches and
`5,014,205
`5/1991 Sindlinger et al. ..................... 364/449
`Applications; pp. 91-116.
`5,023,798
`6/1991 Neukirchner et al.
`... 364/449
`Sep. 1974; R. L. Fey; Automatic Vehicle Location Tech
`5,046,011 9/1991 Kakihara et al. .............
`niques for Law Enforcement Use; pp. 1-22.
`E. 1919: SA, et al. - - - - - - - - - - - - - - - - - - - - - - 3. TSumura, An Experimental System for Automatic Guidance
`5.109344 4/1992 Kakihara et al... 364/449
`of Ground Vehicle Following the Commanded Guidance
`5,111,209 5/1992 Toriyama ................................ 342.357
`Route on Map, pp. 24252430.
`5,119,102 6/1992 Barnard ......
`... 342/357
`Totani et al.; Automotive Navigation System; pp. 469-477.
`5,166,882 11/1992 Stambaugh.
`... 701/220
`K. Mitamura et al.; SAE Technical Paper Series; The Driver
`5,179,519
`1/1993 Adachi et al. .
`... 701/216
`Guide System; pp. 1-9.
`5,185,610 2/1993 Ward et al. .......
`... 342/357
`Thoone; CARIN, a car information and navigation System;
`5,220,509 6/1993 Takemura et al.
`... 701/216
`Philips Technical Review; vol.43, No. 11/12, Dec. 1987; pp.
`5,233,844 8/1993 Mansell et al.
`342/357
`317-329.
`3. 1919: saw - - - - -
`E. T. Tsumura, et al., A System for Measuring Current Position
`5,278,424
`1/1994 Kagawa.
`... 250/561
`and/or Heading of Vehicles; pp.3-8.
`5,311,195 5/1994 Mathis et al.
`... 342/357
`Edward N. Skomal; Automatic Vehicle Locating Systems;
`5,317,515 5/1994 Matsuzaki ..
`... 364/454
`pp. 1-12, 65–98, 319-320.
`5,331,563
`7/1994 Masumoto et al.
`... 342/457
`AGARD; No. 176; Medium Accuracy Low Cost Naviga
`5,334,986 8/1994 Fernhout ........
`... 342/357
`tion; pp. 28-1 to 28-31.
`5,337,243 8/1994 Shibata et al. .
`... 364/449
`K. Tagami, et al., New Navigation Technology to Advance
`5,361,212 11/1994 Class et al. .
`... 364/460
`Utilization of Passenger Cars; pp. 413-422.
`5,367,463 11/1994 Tsuji.
`... 701/216
`Tagami et al.; SAE Technical Paper Series; “Electro Gyro
`5,383,127
`1/1995 Shibata ...
`... 364/449
`Cator' New Inertial Navigation Svstem etc:
`1-15
`5,416,712 5/1995 Geier et al. .
`... 701/216
`1g
`y
`pp.
`5,422,814 6/1995 Sprage et al. ..
`... 364/460
`AGARD, W. M. Aspin Comed-A Combined Display
`5.434,788 7/1995 Seymour et al. .
`... 701/207
`Including a Full Electronic Facility etc.; pp. 30-1 to 30-11.
`5,469,158 11/1995 Morita ............
`... 364/460
`Evans; Chrysler Laser Atlas Satellite System (C.L.A.S.S.).
`5,483,457
`1/1996 Shibata et al
`... 364/449.7
`pp. 1-31.
`5,485,161
`1/1996 Vaughn ......
`... 364/449.7
`R. L. French; The Evolution of Automobile Navigation,
`5,488.559
`1/1996 Seymour .
`... 364/450
`1992, Arlington, Virginia.
`5,508,931
`4/1996 Snider - - - - - - - -
`... 364/450
`R. L. French, et al.; A Comparison of IVHS Progress in the
`5.512.903 4/1996 Schmidtke .
`... 701/221
`United States, Japan and Europe.etc. Mar. 1994 pp. 17-22.
`5,523,765
`6/1996 Ichikawa ...
`... 364/449.7
`-
`0
`5,525,998 6/1996 Geier ..........
`... 364/449.7
`M. Shibita; et al; Current Status and Future Plans for Digital
`5,539,647 7/1996 Shibata et al. .
`70,221
`Map Databases in Japan; Oct. 1993 pp. 29–33.
`5,563,607 10/1996 Loomis et al. .
`... 701/213
`Itoh, The Development of the Drive Guide System (japanese
`5,583,776 12/1996 Levi et al. .............................. 364/450
`with English summary). 1989.
`
`Exhibit 2008
`
`

`

`5,862,511
`Page 3
`
`BusineSS Week Magazine, Space-Age Navigation for the
`Family Car; pp. 82-84, 1984.
`Journal: Nissan Technical Review; The Development of a
`New Multi-AV System, 1991.
`Buxton, et al., The Travelpilot: A Second-Generation Auto
`motive Navigation System, 1991.
`Pilsak, Eva-An Electronic Traffic Pilot for Motorists, 1986.
`French, The Evolving Roles of Vehicular Navigation, 1987,
`pp. 212, 216.
`Claussen, et al.; Status and Directions of Digital Map
`Databases in Europe; 1993, pp. 25-28.
`Jarvis, et al., Cathode-Ray Tube Information Center with
`Automotive Navigation, pp. 123-137.
`Dork, Satellite Navigation Systems for Land Vehicles; 1987,
`pp. 2-5.
`French, Automobile Navigation: Where is it Going? 1987,
`pp. 6-12.
`LaHaije, et al., Efficient Road-Map Management for a Car
`Navigation System, pp. 477-491.
`
`French, et al., Automatic Route Control System; 1973, pp.
`36-41.
`TSumura, et al., Automatic Vehicle Guidance-Commanded
`Map Routing, pp. 62-67.
`Sugie, et al., CARGuide-on board computer for automo
`bile route guidance, pp. 695–706.
`McLellan, et al., Fleet Management Trials in Western
`Canada; pp. 797-806.
`Skomal, Comparative Analysis of Six Commercially Avail
`able Systems; pp. 34-45.
`Krause, et al. Veloc-A Vehicle Location and Fleet Man
`agement System.
`Dittloff, et al., Veloc-A New Kind of Information System;
`pp. 181-187; 1992.
`Article: Vehicle Positioning High Level Map Matching
`Design Document; pp. 1-25; 195.
`Brown, Low Cost Vehicle Location and Tracking using
`GPS; 1992.
`
`Exhibit 2008
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 19, 1999
`Jan. 19,1999
`
`Sheet 1 of 13
`Sheet 1 0f 13
`
`5,862,511
`5,862,511
`
`
`
`
`
`Exhibit 2008
`Exhibit 2008
`
`.1}—
`H
`OZ
`O 2.
`'—
`”“23
`-
`2 as SB
`33Oct)
`O CO
`
`Z0
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 2 of 13
`
`5,862,511
`
`
`
`GPS
`ANTENNA
`
`2 OR 3 AXIS
`ACCELEROMETER
`
`ODOMETER
`
`USER INTERFACE
`(DISPLAY,
`KEYBOARD, etc)
`
`|Fig - 2a
`
`Exhibit 2008
`
`

`

`US. Patent
`
`Jan. 19, 1999
`
`Sheet 3 0f 13
`
`5,862,511
`
`3$2050I
`
`mm
`
`8
`
`moEmEzcum::2:2922?:
`
`
`
`__.llllllllllllll.I_\\mo<¢mmpz__r
`
`5:199
`
`as.0553?
`
`memmmooE820:55”:
`IIIIIII.nlEamomm_Iwas_Q2<mmm
`
`mm<m<b<o
`
`_IIIIIIIIII.
`
`Omaha,IIIIIIIII_$353?355%;;
`
`IIIIII_.memzmaEmmy
`
`_.I
`
`a
`
`mm30m
`
`momDOm
`
`ON
`
`__llllllL_.I.||||.I.IIIII.|.||w
`mmpmzomm4moo<Hm2<mmom“
`
`mm
`
`mm
`
`IINIJlllll\fl:33:momzo“
`
`.x2:<55
`
`IIIIWIII__llllllllllllll
`
`“Ammhmgooov"woz<Hgo
`
`or
`
`vm
`
`mm
`
`xxzop<gzaggoo
`w_(zzwkz<
`
`mac
`
`3
`
`or
`
`Exhibit 2008
`Exhibit 2008
`
`
`
`

`

`US. Patent
`
`Jan. 19, 1999
`
`Sheet 4 0f 13
`
`5,862,511
`
`8-9;
`
`
`3.
`
`QR
`
`0220::ln32ZOEwOm
`.92.0mm
`
`
`
`>tood>20:60;
`
`mv
`
`ov
`
`mmmz
`
`mogmmfiz
`
`EDGE
`
`moz<o50
`
`I
`
`mOmzmw
`
`mob/E0E2
`
`mmmm
`
`Hzmzmm3m<m2
`
`...go
`..Ezwowm
`
`2.
`
`ZOfiommmoo
`
`<55
`
`mOmzmm
`
`20:55:46
`
`mOmme
`
`zo_.r<mm:<o
`
`mmmwm§<m<a
`
`zofiowmmoo
`
`<56
`
`moz<._.m_oQ”mmhmEOwEdoox‘
`
`.04WEE2mm;
`
`HmmEEOQO
`
`moz<._.m_n_AV
`
`mm
`
`Exhibit 2008
`Exhibit 2008
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 5 of 13
`
`5,862,511
`
`18
`
`
`
`gyro
`
`Odo
`
`TT
`
`28
`
`|Fig-3b
`
`Exhibit 2008
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 6 of 13
`
`5,862,511
`
`GET ACCELERATION
`
`
`
`READ ACCELEROMETER
`DATA
`
`DIFFERENCE = DATA
`ZERO OFFSET
`
`G'S = DIFFERENCE
`SCALEFACTOR
`
`ACC G's "METERS PER
`SECOND2 PER G
`
`48
`
`49
`
`50
`
`51
`
`52
`
`VELOCITY ACC DELA
`TME
`
`(LONGITUDINALONLY)
`
`|Fig - 4a
`
`Exhibit 2008
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 7 of 13
`
`5,862,511
`
`
`
`GET ACCELERATION DATA
`
`A - A2C THRESHOLD
`
`A - GPSLATERAL &
`A2 - GPS LATERAL
`
`A1 = LATERAL
`
`A2 = LATERAL
`
`A2. GPSLONGITUDINALK
`A - GPSLONGTUDNAL
`
`A - GPS LONGTUDINALK
`A2. GPS LONGITUDINAL
`
`A2 = LONGTUDINAL
`
`A = LONGTUDINAL
`
`Exhibit 2008
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 8 of 13
`
`5,862,511
`
`0\/THTNOILOW-OBEZ
`
`
`
`WIWO 13S-1-10
`
`og –61 ||
`
`
`
`
`
`
`
`
`
`Exhibit 2008
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`75
`
`Sheet 9 of 13
`
`5,862,511
`
`NOISE = 0
`I = 0
`
`READ DATA (I)
`
`READDATA (I)
`
`
`
`
`
`NOISE = NOISE+/
`DATAI-1 - DATAI
`
`77
`
`79
`
`81
`
`83
`
`85
`
`
`
`
`
`
`
`
`
`89
`
`YES
`
`9
`
`MOTION
`DETECTED
`
`SNOISE >
`THESHOLD
`
`SETZEROMOTION
`FLAG VELOCITY
`ZERO
`
`
`
`ZERO OFFSET
`I = n
`D DATA (I)
`I = 0
`
`n
`
`Exhibit 2008
`
`

`

`US. Patent
`
`Jan. 19, 1999
`
`Sheet 10 0f 13
`
`5,862,511
`
`ozmac>z<
`
`20:38Oumozfimadmmo
`593232%u025$:
`
`
`
`$3.55£21mn83
`
`we0
`
`259%£2282%n2958
`Ezw2mmam<m82
`
`
`
`mmoz<m<EOE...—HmwnEOOmmNwh<mm3<o
`
`2212.55-$212uoo<-zEmmémwmmomo.55qu+:3n:3
`
`$2.59:-m:u83E253.02.3N:+m2;<.5222n552
`
`mm:
`
`32
`
`
`
`3-922.6
`
`$528020.206a?55
`
`
`
`25589mozfima
`
`625$;25.55u55d
`
`825$;moo.55n55-2
`
`
`
`EEEmmmmomo.$5.22+:3u:3
`
`
`
`Emm2ammmowo.559+ozSu029
`
`
`20.22925oz2ooooEmmémmmmumo.559+623nqu
`
`
`02552$525358.$5.22+:3u:3mozfima$5280mzmmzé
`
`
`32:3.822-22«2+m2:4.$2-22n5512$55:35m$528352Eémzé
`
`
`
`322$.8432N:+a2:4.mi:N55dEmmémmmmmmo.559+ozSu@202
`
`Exhibit 2008
`Exhibit 2008
`
`$2.55.m>lzn022
`
`52:3.823.N:+m2:4.divn523
`
`
`
`

`

`US. Patent
`
`Jan. 19, 1999
`
`Sheet 11 0f 13
`
`5,862,511
`
`.2:
`
`mm:
`
`95uzoEwOm
`
`zoEmon.
`
`oz=._o._.<§n22
`
`
`
`
`
`zo_._._won_Emmmzo>5mw5
`
`o3
`
`a-a:
`
`
`
`02
`
`m3
`
`
`
`z_\>>zoEmon.
`
`zoEmOammo
`
`mwz<m
`
`x0zo_._._mon_
`
`«2
`
`0238,5‘n582
`
`SozmmmEvfloz___En__
`
`m:IIIIIIm_n5580u55fl._at.__
`5.88_582amo55Hzu55wu55L.
`
`ammmmmjogua<m2:4.55u895
`ammmomoam938254+0255:u025$:
`Emmzawmmwmo.55d+023nozS
`Ammmsammmomo.55%+:3u:3
`6255158.55"55-2
`625$;25.55u55d
`
`om:
`
`_LE.»
`
`Exhibit 2008
`Exhibit 2008
`
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 19, 1999
`Jan. 19,1999
`
`Sheet 12 of 13
`Sheet 12 0f 13
`
`5,862,511
`5,862,511
`
`
`
`196
`
`196
`
`
`
`
`
`198
`98
`
`’,’
`- 1
`
`192
`192
`
`[Fig — 7d
`
`Exhibit 2008
`Exhibit 2008
`
`

`

`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 13 of 13
`
`5,862,511
`
`202
`
`e
`
`V
`
`le l
`
`204
`
`-- 1
`
`200
`
`MAPHEADING
`
`206
`
`PREVIOUS POSITION
`
`19
`
`N
`
`208
`
`210
`
`
`
`- MAPHEADING
`
`19
`
`24
`
`Exhibit 2008
`
`

`

`5,862,511
`
`1
`VEHICLE NAVIGATION SYSTEMAND
`METHOD
`
`FIELD OF THE INVENTION
`The present invention relates generally to vehicle navi
`gation Systems. More particularly, the present invention
`relates to an improved vehicle navigation System and
`method using information from a Global Positioning System
`(GPS) to obtain velocity vectors for vehicle position
`propagation, and if information from the GPS is not
`available, then using information from a multiple axis accel
`erometer to propagate vehicle position.
`
`BACKGROUND OF THE INVENTION
`Current vehicle navigation Systems use GPS, Such as an
`electromagnetic wave positioning System, to determine a
`vehicle's position. Such a GPS system is the Navigation
`Satellite Timing and Ranging (NAVSTAR) Global Position
`ing System, which is a Space-based Satellite radio navigation
`system developed by the U.S. Department of Defense
`(DoD). GPS includes NAVSTAR GPS and its successors,
`Differential GPS (DGPS), or any other electromagnetic
`wave positioning systems. NAVSTAR GPS receivers pro
`vide users with continuous three-dimensional position,
`Velocity, and time data.
`NAVSTAR GPS consists of three major segments: Space,
`Control, and User as illustrated in FIG.1. The space segment
`2 consists of a nominal constellation of 24 operational
`satellites which have been placed in 6 orbital planes above
`the Earth's Surface. The Satellites are in circular orbits in an
`orientation which normally provides a GPS user with a
`minimum of five satellites in view from any point on Earth
`at any one time. The Satellites broadcast an RF signal which
`is modulated by a precise ranging Signal and a coarse
`acquisition code ranging Signal to provide navigation data.
`This navigation data, which is computed and controlled
`by the GPS control segment 4, includes the satellite's time,
`its clock correction and ephemeris parameters, almanacs,
`and health status for all GPS satellites. From this
`information, the user computes the Satellite's precise posi
`tion and clock offset.
`The control segment consists of a Master Control Station
`and a number of monitor Stations at various locations around
`the world. Each monitor station tracks all the GPS satellites
`in View and passes the Signal measurement data back to the
`master control Station. There, computations are performed to
`determine precise Satellite ephemeriS and Satellite clock
`errors. The master control Station generates the upload of
`user navigation data from each Satellite. This data is Subse
`quently rebroadcast by the Satellite as part of its navigation
`data message.
`The user segment 6 is the collection of all GPS receivers
`and their application Support equipment Such as antennas
`and processors. This equipment allows users to receive,
`decode, and process the information necessary to obtain
`accurate position, Velocity and timing measurements. This
`data is used by the receiver's Support equipment for Specific
`application requirements. GPS Supports a wide variety of
`applications including navigation, Surveying, and time trans
`fer.
`GPS receivers may be used in a standalone mode or
`integrated with other Systems. Currently, land-based navi
`gation Systems use vehicle Speed Sensor, rate gyro and a
`reverse gear hookup to “dead reckon' the vehicle position
`from a previously known position. This method of dead
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`reckoning, however, is Susceptible to Sensor error, and
`therefore requires more expensive Sensors for accuracy and
`dependability.
`The Systems that use odometers, gyros and reverse gear
`hookups also lack portability due to the required connections
`to odometers and the frailty of gyros. Moreover, these
`Systems are hard to install in different cars due to differing
`odometer configurations which can have different connec
`tions and pulse counts in the transmission. Odometer data
`also varies with temp, load weight, tire pressure, Speed.
`Alternative connections to cruise control or ABS Sensors
`bring up Safety concerns.
`Prior Systems use a road network Stored in a map database
`to calculate current vehicle positions. These Systems Send
`distance and heading information to perform map matching,
`and map matching calculates the current position based on
`the road network and the inputted data. These Systems also
`use map matching to calibrate Sensors. Map matching,
`however, has inherent inaccuracies because map matching
`must look back in time and match data to a location. AS Such,
`map matching can only calibrate the Sensors when an
`absolute position is identified on the map, but on a long,
`Straight Stretch of highway, Sensor calibration using map
`matching may not occur for a significant period of time.
`Accordingly, there is a need for a potentially portable,
`vehicle navigation System which is flexible, accurate, effi
`cient and cost-effective in determining a current position
`from a previous position.
`
`SUMMARY OF THE INVENTION
`The improved vehicle navigation System and method uses
`information from a Global Positioning System (GPS) to
`obtain Velocity vectors, which include Speed and heading
`components, for propagating or “dead reckoning the
`vehicle position from a previous position. If information
`from the GPS is not available, then the improved vehicle
`navigation System uses information from an orthogonal axes
`accelerometer, Such as two or three orthogonally positioned
`accelerometers, to propagate vehicle position. Because the
`GPS information should almost always be available, the
`improved vehicle navigation System relies leSS on its
`accelerometers, thereby allowing the use of less expensive
`accelerometers. The improved vehicle navigation System
`retains the accuracy of the accelerometers by repeatedly
`calibrating them with the velocity data obtained from the
`GPS information. The improved vehicle navigation system
`calibrates the sensors whenever GPS data is available (for
`example, once a second at relatively high speeds).
`Furthermore, the improved vehicle navigation System does
`not need to rely on map matching to calibrate Sensors.
`System flexibility is improved because map matching is
`oblivious to the hardware, and the System hardware can be
`updated without affecting map matching or a change in the
`map database.
`The use of accelerometers in the improved vehicle navi
`gation System eliminates the need for connections to a
`heading Sensor, Speed Sensors or a reverse gear, making the
`improved vehicle navigation System cheaper to install and
`potentially portable. The improved vehicle navigation SyS
`tem has Sensors which are effectively calibrated because the
`Scale factors for the accelerometers vary in a known manner
`dependent on temperature but fairly independent of other
`vehicle characteristics. In contrast, for example, an odom
`eter loses accuracy if tire diameter changes due to falling tire
`preSSure. If a third axis acceleration measurement Sensor is
`added, the improved vehicle navigation System can operate
`
`Exhibit 2008
`
`

`

`5,862,511
`
`3
`completely independent of vehicle Sensors, further increas
`ing flexibility in mounting. The third accelerometer provides
`pitch to assist in calibrating the other accelerometers and in
`providing more accurate information by, for example,
`detecting a banked turn.
`In accordance with another aspect of the present
`invention, the improved vehicle navigation System interro
`gates a map database to obtain heading information for the
`mapped path Segment which the vehicle is moving on. The
`improved vehicle navigation System updates the heading
`component for the Velocity with the heading information
`from the map database. The updated Velocity is used to
`propagate the vehicle position.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Other aspects and advantages of the present invention
`may become apparent upon reading the following detailed
`description and upon reference to the drawings in which:
`FIG. 1 is a general illustration of the various Segments in
`the NAVSTAR GPS system;
`FIG. 2a shows an improved vehicle navigation System
`using the improved position determination System according
`to the principles of the present invention, and FIGS.2b show
`various hardware configurations for Systems using aspects of
`the improved vehicle navigation System according to the
`principles of the present invention;
`FIG.3a shows a block/data flow diagram of the improved
`vehicle navigation system of FIG. 2a, and FIG. 3b shows a
`block data flow diagram of alternative improved vehicle
`navigation Systems according to aspects of the present
`invention;
`FIGS. 4a and 4b show flow charts for gathering accel
`eration information and orienting the multiple axis acceler
`Ometer,
`FIG. 5a shows a block diagram of a Zero motion detect
`System according to the principles of the present invention,
`and FIG. 5b shows a flow chart for the operation of the Zero
`motion detect system of FIG. 5a,
`FIGS. 6a and 6b show a general flow chart of the
`operation of the improved vehicle navigation System of FIG.
`2a, and
`FIGS. 7a-7e show general diagrams illustrating how the
`improved vehicle navigation System updates the heading
`information with the map heading for position propagations.
`While the invention is susceptible to various modifica
`tions and alterative forms, specifics thereofhave been shown
`by way of example in the drawings and will be described in
`detail. It should be understood, however, that the intention is
`not to limit the invention to the particular embodiment
`described. On the contrary, the intention is to cover all
`modifications, equivalents, and alternatives falling within
`the Spirit and Scope of the invention as defined by the
`appended claims.
`DETAILED DESCRIPTION OF THE DRAWINGS
`An illustrative embodiment of the improved vehicle navi
`gation System according to the principles of the present
`invention and methodology is described below as it might be
`implemented to determine a current position from a previous
`position. In the interest of clarity, not all features of an actual
`implementation are described in this specification. It will of
`course be appreciated that in the development of any Such
`actual implementation (as in any development project),
`numerous implementation-specific decisions must be made
`to achieve the developerS Specific goals and Subgoals, Such
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`as compliance with System- and busineSS-related constraints,
`which will vary from one implementation to another.
`Moreover, it will be appreciated that Such a development
`effort might be complex and time-consuming, but would
`nevertheless be a routine undertaking of device engineering
`for those of ordinary skill having the benefit of this disclo
`SUC.
`Aspects of the improved vehicle navigation System can be
`used in connection with a variety of System configurations in
`which GPS Signals are used for position propagation. FIG.
`2a illustrates, in block diagram form, an exemplary arrange
`ment and use of an improved vehicle navigation System 10
`for an automobile 12. In this embodiment, the improved
`vehicle navigation system 10 uses a GPS antenna 14 to
`receive the GPS signals. The antenna 14 is preferably of
`right-hand circular polarization, has a gain minimum of -3
`dBiC above 5 degree elevation, and has a gain maximum of
`+6 dBiC. Patch or Helix antennas matching these specifi
`cations can be used. The GPS antenna 14 can be connected
`to a preamplifier 16 to amplify the GPS signals received by
`the antenna 14. The pre-amplifier 16 is optional, and the
`GPS antenna can be directly connected to a GPS receiver 18,
`which is powered by a power source 20 for the vehicle
`navigation System 10.
`The GPS receiver 18 continuously determines geographic
`position by measuring the ranges (the distance between a
`Satellite with known coordinates in Space and the receiver's
`antenna) of Several satellites and computing the geometric
`interSection of these ranges. To determine a range, the
`receiver 18 measures the time required for the GPS signal to
`travel from the Satellite to the receiver antenna. The timing
`code generated by each Satellite is compared to an identical
`code generated by the receiver 18. The receivers code is
`shifted until it matches the satellite's code. The resulting
`time shift is multiplied by the speed of light to arrive at the
`apparent range measurement.
`Since the resulting range measurement contains propaga
`tion delays due to atmospheric effects, and Satellite and
`receiver clock errors, it is referred to as a “pseudorange.”
`Changes in each of these pseudoranges over a short period
`of time are also measured and processed by the receiver 18.
`These measurements, referred to as "delta-pseudoranges,”
`are used to compute velocity. Delta ranges are in meters per
`Second which are calculated by the receiver from
`pseudoranges, and the GPS receiver 18 can track the carrier
`phase of the GPS Signals to Smooth out the pSuedoranges.
`The Velocity and time data is generally computed once a
`Second. If one of the position components is known, Such as
`altitude, only three Satellite pseudorange measurements are
`needed for the receiver 16 to determine its velocity and time.
`In this case, only three Satellites need to be tracked.
`GPS accuracy has a statistical distribution which is depen
`dent on two important factors. The accuracy which can be
`expected will vary with the error in the range measurements
`as well as the geometry or relative positions of the Satellites
`and the user. The Geometric Dilution of Precision (GDOP)
`indicates how much the geometric relationship of the
`tracked Satellites affects the estimate of the receiver's
`position, velocity, and time. There are four other DOP
`components which indicate how the geometry Specifically
`affects errors in horizontal position (DOP), vertical position
`(VDOP), position (PDOP), and time (TDOP).
`DOPs are computed based on the spatial relationships of
`the lines of sight between the satellites and the user. The
`motion of the Satellites relative to each other and the user
`causes the DOPs to vary constantly. For the same range
`
`Exhibit 2008
`
`

`

`25
`
`S
`measurement errors, lower DOPS relate to more accurate
`estimates. The errors in the range measurements which are
`used to Solve for position may be magnified by poor geom
`etry. The least amount of error results when the lines of sight
`have the greatest angular Separation between them.
`For example, if two lines of Sight are necessary to
`establish a user position, the least amount of error is present
`when the lines croSS at right angles. The error in the range
`measurement is dependent on one of two levels of GPS
`accuracy to which the user has access. PPS is the most
`accurate, but is reserved for use by the DoD and certain
`authorized users. SPS is less accurate and intended for
`general public use. The SPS Signal is intentionally degraded
`to a certain extent by a process known as Selective Avail
`ability (SA). SA is used to limit access to the full accuracy
`of SPS in the interest of U.S. national security. Differential
`GPS (DGPS) may be used to correct certain bias-like errors
`in the GPS signals. A Reference Station receiver measures
`ranges from all visible Satellites to its Surveyed position.
`Differences between the measured and estimated ranges are
`computed and transmitted via radio or other Signals to
`differential equipped receiverS/hosts in a local area. Incor
`poration of these corrections into the range measurements
`can improve their position accuracy.
`As shown in FIG. 2a, the GPS receiver 18 provides GPS
`measurements to an application unit 22. The application unit
`22 consists of application processing circuitry 24, Such as a
`processor, memory, buSSes, the application Software and
`related circuitry, and interface hardware 26. In one embodi
`ment of the present invention, the application unit 22 can be
`incorporated into the GPS receiver 18. The interface hard
`ware 26 integrates the various components of the vehicle
`navigation system 10 with the application unit 22. In this
`embodiment, a 2 or 3 axis accelerometer 28 provides accel
`eration Signals to the application unit 22. The accelerometer
`28 can include recently available and low cost, micro
`machined accelerometers. An odometer 29 provides infor
`mation which can be used in place of the information
`derived from the accelerometers, but the odometer 29 is
`optional because it reduces the portability of the System. A
`40
`map database 30 Stores map information, Such as a road
`network, and provides map info