(12)
`
`United States Patent
`Croyle et al.
`
`USOO6308134B1
`(10) Patent No.:
`US 6,308,134 B1
`(45) Date of Patent:
`Oct. 23, 2001
`
`(54) VEHICLE NAVIGATION SYSTEMAND
`METHOD USING MULTIPLE AXES
`ACCELEROMETER
`
`(*) Notice:
`
`(75) Inventors: Steven R. Croyle, Franklin; Larry E.
`Spencer, II, Lake Orion; Ernie R.
`Sittaro, Romero, all of MI (US)
`(73) Assignee: Magellan DIS, Inc., Rochester Hills,
`MI (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`(21) Appl. No.:
`09/091,430
`(22) PCT Filed:
`Dec. 27, 1996
`(86) PCT No.:
`PCT/US96/20848
`S371 Date:
`Nov.30, 1998
`S 102(e) Date: Nov.30, 1998
`(87) PCT Pub. No.: WO97/24582
`PCT Pub. Date:Jul. 10, 1997
`(51) Int. Cl." ................................................... G06G 7/78
`(52) U.S. Cl. .......................... 701/220; 701/213; 701/214;
`701/216; 701/221; 701/200; 340/723: 340/995;
`340/990; 343/450; 343/451
`(58) Field of Search ..................................... 701/220, 207,
`701/1; 364/454; 235/150.27
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`3,442,140
`3,492.465
`
`5/1969 Peteson.
`1/1970 Buscher et al. .
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`3242904 A1 11/1982 (DE).
`
`3912108
`
`4/1989 (DE).
`(List continued on next page.)
`OTHER PUBLICATIONS
`Brochure: Fleet-Trak: Fleet Management System.
`McLellan, et al., Applicaiton of GPS Positioning to Man
`agement of Mobile Operations, pp. 1-16; 1991.
`(List continued on next page.)
`Primary Examiner William A. Cuchlinski, Jr.
`ASSistant Examiner Tuan C To
`(74) Attorney, Agent, or Firm-Carlson, Gaskey & Olds
`(57)
`ABSTRACT
`The improved vehicle navigation System uses a multiple,
`orthogonal axes accelerometer, Such as two or three accel
`erometers which are mounted orthogonal to one another. The
`two axes whose acceleration are to be measured are the
`longitudinal (nose to rear bumper) axis and lateral (left to
`right side) axis. The tangential or longitudinal axis accel
`eration is integrated once to obtain longitudinal Speed and is
`integrated again to produce a vehicle displacement. The
`lateral accelerometer measures the centripetal force that the
`vehicle is encountering which is used to compute a centrip
`etal or lateral acceleration. The lateral acceleration is used to
`obtain a heading change derived from the lateral accelera
`tion information and the longitudinal Speed. Using the
`heading change and the longitudinal acceleration, the
`improved vehicle navigation System propagates a previous
`position to a current position. This is accomplished without
`the need for connection to the vehicle Speed Sensor and the
`heading Sensor. If a third axis acceleration measurement
`Sensor is used the improved vehicle navigation System can
`operate completely independent of vehicle Sensors, further
`increasing flexibility in mounting. The third accelerometer
`provides pitch to assist in calibrating the other accelerom
`eters or other Sensors and in altering the longitudinal and/or
`lateral acceleration information by, for example, detecting a
`banked turn.
`
`20 Claims, 10 Drawing Sheets
`
`
`
`GPS
`ANTENNA
`
`APPLICAICN
`PROCESSOR
`
`POWER
`SOURCE
`
`28
`
`NTERFACE
`HARWARE
`
`ELKATA
`(maps, etc)
`
`2CR3AXIS
`ACCEEROMETER
`
`USERINTERFACE
`(SPLAY,
`KEYBOARD, etc)
`
`IPR2020-01192
`Apple EX1015 Page 1
`
`

`

`US 6,308,134 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`10/1994 Knobbe.
`5,355,316
`11/1994 Tsuji..................................... 364/449
`5,367,463
`1/1995 Shibata ................................. 364/449
`5,383,127
`8/1995 Kau.
`5,442,560
`9/1995 Raymer et al..
`5,450,345
`12/1995 Keyes et al..
`5,479,161
`6/1996 Tanaka et al. .
`5,526.263
`7/1996 Erdley.
`5,531,115
`10/1996 Mark et al. .
`5,570,304
`2/2000 Croyle .................................. 701/207
`6,029,111
`6,038,495 * 3/2000 Schiffmann .
`FOREIGN PATENT DOCUMENTS
`
`
`
`9/1982 (EP).
`0 059 435
`10/1982 (EP).
`0 061564. 1
`1/1983 (EP).
`0 069965
`3/1984 (EP).
`O 103 847
`6/1984 (EP).
`0110171
`9/1984 (EP).
`O 118 886
`2/1992 (EP).
`O 471 405
`7/1992 (EP).
`O 496 538
`0514887 11/1992 (EP).
`0544.403
`6/1993 (EP).
`O 567 268
`10/1993 (EP).
`1 470 694
`4/1977 (GB).
`2014 309
`8/1979 (GB).
`2144 007
`2/1985 (GB).
`2 115946
`9/1993 (GB).
`59-28244
`10/1957 (JP).
`57-158875
`9/1982 (JP).
`58-27008
`2/1983 (JP).
`58-111969
`7/1983 (JP).
`58-113711
`7/1983 (JP).
`58-178213
`10/1983 (JP).
`60-135817
`7/1985 (JP).
`WO92/10824
`6/1992 (WO).
`OTHER PUBLICATIONS
`Stanley K. Honey; A Novel Approach to Automotive Navi
`gation and Map Display, pp. 40–43.
`Sienens. All-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.
`Lezniak, et. al., A Dead Reckoning/Map Correlation System
`for Automatic Vehicle Traking; pp. 47–60.
`May, 1973; Vehicular technology; Antartic Navigation; pp.
`36-41.
`
`i
`
`3,588,478 * 6/1971 Anthony .......................... 235/150.27
`3,597,598
`8/1971 McAllister.
`3,610,900
`10/1971 Talwani.
`3,702,477
`11/1972 Brown.
`3,749,893
`7/1973 Hileman .......................... 235/150.27
`3,803,387
`4/1974 Lackowski.
`3,845,289
`10/1974 French .............................. 235/151.2
`3,924,824
`12/1975 Brodie et al..
`3,984806
`10/1976 Tyler ...................................... 340/23
`4,032,758
`6/1977 Lewis ................................ 235/150.2
`4,038,527
`7/1977 Brodie et al..
`4,070,674
`1/1978 Buell et al..
`4,086,632
`4/1978 Lions ................................... 364/444
`4,107,689
`8/1978 Jellinek
`343/112 TC
`4,135,155
`1/1979 Kehl et al..
`4,173,784
`11/1979 Health et al..
`4,253,150
`2/1981 Scovill ................................. 364/449
`4,254,465
`3/1981 Land .................................... 364/453
`4,262,861
`4/1981 Goldstein.
`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
`4,369,441
`1/1983 Wohlmuth ......
`... 340/733
`4,403.291
`9/1983 Von Tomkewitsch ............... 364/424
`4.483.357
`11/1984 Evans et al..
`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 Gene Esparza
`... 364/444
`4,571,684
`2/1986 Tachi et al. ...
`... 364/444
`4,608,656
`8/1986 Tanaka et al. .
`... 364/449
`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,00s
`4,692,765
`9/1987 Politis et al..
`4,713,767
`12/1987 Sato et al..
`4,758,959
`7/1988 Thoone et al. ....................... 364/454
`SS E. R et al. ........................ 36/50
`4,814,989
`3/1989 Dobereiner et al. .................
`a
`4,819,175
`4/1989 Wuttke ................................. E.
`4,823,626
`4/1989 Hartmann et al. .
`4,847,769
`7/1989 Reeve .............................. 364/424.02
`4,870,588
`9/1989 Merhav .
`4,890,104
`12/1989 Takanabe et al. ................... 340/995
`4,899.285
`2/1990 Nakayama et al. .................. 364/453
`4,930,085
`5/1990 Kleinschmidt.
`
`2Y-- Y-2
`
`nSKy.
`
`CE RE NE".'" M.E. R. L. French: MAP Matching Origins Approaches and
`Applications, pp. 91-116.
`3/1991 Rapiejko et al..
`5,001,647
`5,014,205
`5/1991 Sindlinger et al. .................. 364449
`Sep. 1974; R. L. Fey; Automatic Vehicle Location Tech
`5,023,798
`6/1991 Neukirchner et al.
`... 364/449
`niques for Law Enforcement Use, pp. 1-22.
`5,046,011
`9/1991 Kakihara et al. .................... 364/449
`TSumura, An Experiment System for Automatic Guidance of
`5,058,023
`10/1991 Kozikaro .............................. 364/450
`Ground Vehicle Following the Commanded Guidance Route
`5,075,693
`12/1991 McMillian et al.
`3427 on Map, pp. 2425-2430.
`5,109,344
`4/1992 Kakihara et al. ............
`Totani et al.; Automotive Navigation System; pp. 469-477.
`5,111,209
`5/1992 Toriyama ............................. 342/357
`5,119,102
`6/1992 Barnard ................................ 323s,
`K. Mitamura et al.; SAE Technical Paper Series; The Friver
`5,166,882
`11/1992 Stambaugh.
`Guide System; pp. 1-9.
`5,172,323
`12/1992 Schmidt.
`Thoone, Carin, a car information and navigation System;
`5,185,610
`2/1993 Ward et al. .......................... 342/357
`Philips Technical Review; vol.43, No. 11/12, Dec. 1987; pp.
`5,233,844
`8/1993 Mansell et al. ...................... 342/357
`317-329.
`5,276,451
`1/1994 Odagawa .............................
`23S.
`T. Tsumura, et. al.; A System for Measuring Current Position
`5,278,424
`1/1994 Kagawa ............................... *''' and/or Heading of vehicles; pp. 3–8.
`5,301,114
`4/1994 Mitchell.
`5,301,130
`4/1994 Alcone et al. .
`Edward N. Skomal; Automatic Vehicle Locating System; pp.
`5,311,195
`5/1994 Mathis et al. ........................ 342.357
`1-12, 65–98, 319-320.
`5,337,243
`8/1994 Shibata et al. ....................... 364/449
`Agard; No. 176; Medium Accuracy Low Cost Navigation;
`5,339,684
`8/1994 Jircitano et al. .
`pp. 28-1 to 28–31.
`
`IPR2020-01192
`Apple EX1015 Page 2
`
`

`

`US 6,308,134 B1
`Page 3
`
`K. Tagami, et. al., New Navigaiton Technology to Advance
`Utilizationof Passenger Cars; pp. 413-422.
`Tagami et al.; SAE Technical Paper Series; “Electro Gyro
`Cator” New Inertial Navigation System etc., pp. 1-15.
`Agard; W. M. Aspin Comed- A Combined Display Includ
`ing a Full Electronic Facility etc.; pp. 30-1 to 30-11.
`Evan; Chrysler Laser Atlas Satellite System (C.L.A.S.S.).pp.
`1-31.
`R. L. French; The Evolution of Automobile Navigation in
`Japan, Jun. 21-23, 1993.
`R. L. French, et al.; A Comparison of IVHS Progress in the
`United States, Japan and Europe.etc. 3/94 pp. 17-22.
`M. Shibita; etal; Curent Status and Future Plans for Digital
`Map Databases in Japan; 10/93 pp. 29-33.
`Itoh, The Development of the Drive Guide System (japanese
`with English Summary). 1989.
`BusineSS Week Magazine, Space-age Navigation for the
`Family Car; pp. 82-84, 1984.
`Journal; Nissan Technical Review; The Develpment of a
`New Multi-AV System, 1991.
`Buxton, et al., The Travelpilot: A Second-Generation
`Automative 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., Automative 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 Mangement Trials in Western
`Canada; pp. 797-806.
`Skomal, Comparative Analysis fo Six Commercially Avail
`able System; 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.
`* cited by examiner
`
`IPR2020-01192
`Apple EX1015 Page 3
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 1 of 10
`
`US 6,308,134 B1
`
`
`
`18
`
`GPS
`ANTENNA
`W
`
`14
`
`GPS
`RECEIVER
`
`POWER
`SOURCE
`
`28
`
`not
`2OR3AXIS
`ACCELEROMETER - ODOMETER
`
`USER INTERFACE
`(DISPLAY,
`KEYBOARD, etc)
`
`A/G f
`
`IPR2020-01192
`Apple EX1015 Page 4
`
`

`

`U
`
`S”a.
`
`fin.5:8mmxmmamoEmEz
`
`ESQ,
`
`295892..mm52%4:938..a.Emsmmamfis.al0llllllllJlllllllllllb_S.,
` 20:59.W@2502:lmozmoflz528$.2,\n2:
`
`.L55<
`
`memzmm_a<8%E:Mu-mozfimadW...
`20.25.20“amzozommmoo _“<20
`
`nurlqummmhm§m<m"”mmeEOmmeoo"mzoEmmEozoflopwmmmoo_asmomzmm
`lllllllllllll
`
`
`
` _IIIIIIIIII3..11“moz<hw_o<_”552000
`
`US 6,308,134 B1
`
`NGE
`
`.1
`
`|l
`
`
`
`__.J__
`
`|PR2020-01192
`
`Apple EX1015 Page 5
`
`IPR2020-01192
`Apple EX1015 Page 5
`
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 3 of 10
`
`US 6,308,134 B1
`
`GET ACCELERATION
`
`
`
`READ ACCELEROMETER
`DATA
`
`DIFFERENCEs DATA
`ZERO OFFSET
`
`G's = OFFERENCE"
`SCALEFACTOR
`
`ACC = G's "METERS PER
`SECOND2 PER G
`
`48
`
`49
`
`50
`
`51
`
`52
`
`WELOCITY = ACC DELTA
`TIME
`
`(LONGITUDINAL ONLY)
`
`A/G 3a
`
`IPR2020-01192
`Apple EX1015 Page 6
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 4 of 10
`
`US 6,308,134 B1
`
`
`
`GET ACCELERATION DATA
`
`A - A2 & THRESHOLD
`
`A - GPSLATERALC
`A2 - GPS LATERAL
`
`A1 a LATERAL
`
`A2 = LATERAL
`
`A2 - GPS LONGUDINALK
`A1 GPS LONGITUDINAL
`
`A - GPS LONGTUDINALK
`A2 - GPS LONGITUDNAL
`
`A2 LONGITUDINAL
`
`A = LONGUDNAL
`
`IPR2020-01192
`Apple EX1015 Page 7
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 5 of 10
`
`US 6,308,134 B1
`
`?WTHTNOILOW-OHBZ
`
`IPR2020-01192
`Apple EX1015 Page 8
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 6 of 10
`
`US 6,308,134 B1
`
`7
`5
`
`NOISE = 0
`Ise 0
`
`
`
`
`
`
`
`READDATA (I)
`
`NOSE = NOSE
`DATA I - 1 - DATA (I)
`
`79
`
`8
`
`83
`
`85
`
`
`
`
`
`
`
`
`
`
`
`SNOISE >
`THESHOLD
`
`89
`
`YES
`
`91
`
`MOTION
`DETECTED
`
`SEZERO MOTION
`FLAG VELOCITY
`ZERO
`
`ZERO OFFSET
`I = n
`D DATA (I)
`as 0
`
`
`
`F/G, 4b
`
`IPR2020-01192
`Apple EX1015 Page 9
`
`

`

`U
`
`2
`
`f0
`
`US 6,308,134 B1
`
`mmwet
`
`35:08so§<in55
`
`:maooc.mozfima
`
`6255:.moo.55n55-2
`
`
`
`
`
`Emgammzowo.55-2.+:3n:3
`
`
`
`EEEmwwmomo.554w.+ozSuozS
`
`a:
`
`IN:
`
`
`
`m;
`
`6255:.25.55u5.3
`
`.mm:Scm_
`m@;wFZmzmmsmfimm_Mia.02mam>z<«2Poz9
`
`mm;
`
`3,N22.mmtoQENBEESwmmozéflsofi
`mszwn20:52
`
`
`>tood>Ham—20om2<wn029E:
`
`w._m<;=<><oumozfiwa<
`
`1N.88m50.3wm>3:$2
`
`
`
`wh88
`
`I'll;
`
`
`
`
`
`S2952EmEB£22820.52FEESE228
`
`
`
`wzmmsénmozfima$5208mzmmzém8—29595oz$55535%$528552
`
`
`|PR2020-01192
`
`Apple EX1015 Page 10
`
`IPR2020-01192
`Apple EX1015 Page 10
`
`
`
`
`
`
`
`

`

`US. Patent
`
`US 6,308,134 B1
`
`2:Eun29:80.
`
`
`
`m20:59.55000n55m.
`
`8..mozém:w20:59.mac
`
`Oz25520:50;
`
`SOIwmmI»v
`
`5.88n5.82nwmo558<"55_u55_ha:E_111111.SxozoEmEm
`w2:um:M‘LNEw@2502:"as.
`
`
`mm:
`
`
`
`20000..5500.
`
`oz
`
`NC
`
`v5
`
`
`
`
`
`02283?5.82
`
`
`
`ZOEmOmhzmmmbo><._n_m_n_Dmmmmifioolxn0<o2m2:<55u05%
`
`awmmwmoam38025<+$255:n0255:
`
`
`
`
`
`
`
`QM6E
`
`
`
`.559+623u$290Emméammmoma.55sz+:3u:3
`
`Emmémmmmwwo
`
`
`
`5255;z_m.55u551m
`
`azafiam8.55"5512
`
`|PR2020-01192
`
`Apple EX1015 Page 11
`
`IPR2020-01192
`Apple EX1015 Page 11
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 9 of 10
`
`US 6,308,134 B1
`
`
`
`
`
`-
`
`196
`
`198
`
`192
`
`A/G 6d
`
`IPR2020-01192
`Apple EX1015 Page 12
`
`

`

`U.S. Patent
`
`Oct. 23, 2001
`
`Sheet 10 of 10
`
`US 6,308,134 B1
`
`204
`
`---
`
`PREVIOUS POSITION
`
`202
`
`MAP HEADING
`
`e
`
`t
`
`l
`
`200
`
`206
`
`191
`
`210
`
`208
`
`
`
`- MAPHEADING
`
`19
`
`24
`
`IPR2020-01192
`Apple EX1015 Page 13
`
`

`

`1
`VEHICLE NAVIGATION SYSTEMAND
`METHOD USING MULTIPLE AXES
`ACCELEROMETER
`
`This application is a 371 of PCT/US96/20848, filed Dec.
`27, 1996, which claims priority to U.S. Ser. No. 08/580,177,
`filed Dec. 28, 1995, now abandoned.
`
`5
`
`FIELD OF THE INVENTION
`The present invention relates generally to vehicle navi
`gation Systems using accelerometers. More particularly, the
`present invention relates to an improved vehicle navigation
`System and method using multiple accelerometers mounted
`orthogonally to each other or an orthogonal axes acceler
`Ometer.
`
`15
`
`BACKGROUND OF THE INVENTION
`Accelerometers have been used in airborne navigation
`Systems in the past, but only in conjunction with gyros. The
`current route guidance and navigation Systems that exist for
`automobiles today use the vehicle Speed Signal, rate gyro
`and a reverse gear hookup to “dead reckon' the vehicle
`position from a previously known position. This method of
`dead 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. This reduces the installation
`flexibility, increases installation costs and reduces the port
`ability of the vehicle navigation System. Accordingly, there
`is a need for a vehicle navigation System with more freedom
`of installation which is portable and accurately determines
`vehicle position.
`
`SUMMARY OF THE INVENTION
`The improved vehicle navigation System is Smaller, more
`cost effective, potentially portable and allows for more
`freedom of installation. In certain embodiments, the Zero
`motion detection System takes advantage of the recent
`availability of low cost micro-machined accelerometers.
`The improved vehicle navigation System uses an Orthogo
`nal axes accelerometer, Such as two or three accelerometers,
`which are mounted orthogonal to one another. The System
`can measure acceleration in the longitudinal (nose to rear
`bumper) axis and lateral (left to right side) axis. The tan
`gential or longitudinal axis acceleration is integrated once to
`obtain longitudinal Speed and is integrated again to produce
`a vehicle displacement. The lateral accelerometer measures
`the centripetal force that the vehicle is encountering which
`is used to compute a centripetal or lateral acceleration. The
`lateral acceleration is used to obtain a heading change
`derived from the lateral acceleration information and the
`longitudinal Speed. Using the heading change and the lon
`gitudinal acceleration, the improved vehicle navigation SyS
`tem propagates a previous position to a current position.
`This is accomplished without the need for connection to the
`vehicle Speed Sensor and the heading Sensor. If a third axis
`acceleration measurement Sensor is used, the improved
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,308,134 B1
`
`2
`vehicle navigation System can operate completely indepen
`dent of vehicle Sensors, further increasing flexibility in
`mounting. The third accelerometer provides pitch to assist in
`calibrating the other accelerometers or other Sensors and in
`altering the longitudinal and/or lateral acceleration informa
`tion by, for example, detecting a banked turn.
`
`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 shows an improved vehicle navigation System
`according to the principles of the present invention;
`FIG. 2 shows a block/data flow diagram of the improved
`vehicle navigation system of FIG. 1;
`FIGS. 3a and 3b show flow charts for gathering accel
`eration information and orienting the multiple axis acceler
`Ometer,
`FIG. 4a shows a block diagram of a Zero motion detect
`System according to the principles of the present invention,
`and FIG. 4b shows a flow chart for the operation of the Zero
`motion detect system of FIG. 4a,
`FIGS. 5a and 5b show a general flow chart of the
`operation of the improved vehicle navigation System of FIG.
`1, and
`FIGS. 6a-6e show general diagrams illustrating how the
`improved vehicle navigation System updates the heading
`information with the map heading for position propagation.
`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 position
`determination System according to the principles of the
`present invention and methodology is described below as it
`might be implemented using orthogonally mounted accel
`erometers 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
`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.
`The improved vehicle navigation System can be used in a
`variety of configurations as would be understood by one of
`ordinary skill in the art. Such a vehicle navigation System is
`disclosed in copending patent application Ser. No. 08/580,
`150, entitled “Improved Vehicle Navigation System And
`Method” and filed concurrently with this application. Par
`ticular embodiments of the improved vehicle navigation
`System uses GPS, Such as an electromagnetic wave posi
`
`IPR2020-01192
`Apple EX1015 Page 14
`
`

`

`US 6,308,134 B1
`
`3
`tioning system. Such a GPS system is the Navigation
`Satellite Timing and Ranging (NAVSTAR) Global Position
`ing System. GPS includes NAVSTAR GPS and its
`successors, Differential GPS (DGPS), or any other electro
`magnetic wave positioning systems. NAVSTAR GPS
`receivers provide users with continuous three-dimensional
`position, Velocity, and time data.
`FIG. 1 illustrates, in block diagram form, an exemplary
`arrangement 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 again maximum
`of +6 dBiC. Patch or Helix antennas matching these speci
`fications 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 16.
`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 receiver's 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. 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.
`As shown in FIG. 1, the GPS receiver 18 provides GPS
`measurements to an application unit 22. Powered via a
`conventional power Source 20, the application unit 22 con
`Sists of application processing circuitry 24, Such as a
`processor, memory, buses, the application Software and
`related circuitry, and interface hardware 26. In certain
`embodiments of the present invention, the application unit
`22 can be incorporated into the GPS receiver 18. The
`interface hardware 26 integrates the various components of
`the vehicle navigation System 10 with the application unit
`22. In this embodiment, a 2 or 3 orthogonal axis acceler
`ometer 28 provides acceleration signals to the application
`unit 22. An odometer 29 provides information which can be
`used in place of the information derived from the
`accelerometer, but the odometer 29 is optional because it
`reduces the portability of the system. A map database 30
`Stores map information, Such as a road network, and pro
`vides map information to the application unit 22. A user
`interface 32, which includes a display and keyboard, allows
`interaction between the user and the improved vehicle
`navigation System 10.
`FIG.2 shows a more detailed block and data flow diagram
`for the improved vehicle navigation system 10 of FIG. 1.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`The GPS receiver 18 provides position information, velocity
`information, pseudoranges and delta pseudoranges to the
`sensor integrator 40. The sensor integrator 40 uses the
`Velocity information to determine a current position for the
`vehicle. In this embodiment, if GPS velocity information is
`not available, the sensor integrator 40 can calculate GPS
`Velocity using the available delta range measurements to
`determine a current position. GPS velocity information is
`derived from a set of delta range measurements, and if only
`a Subset of delta range measurements is available, the
`vehicle navigation system can derive GPS velocity infor
`mation from the Subset of delta range measurements. The
`vehicle navigation System uses the GPS position informa
`tion at Start-up as a current position and during other times
`of operation as a check against the current position. If the
`current position fails the check, then the GPS position can
`replace the current position.
`When GPS velocity information is available and reliable,
`the application processor 22 propagates the position vector
`x(t) with the GPS velocity vector v as follows: X(t)=
`x(t–1)+ v At. If the difference between the GPS heading
`and the map heading is within a threshold, the map heading
`is used as the heading. If the GPS velocity information is not
`available or unreliable (at low velocities below 1.5 m/s), the
`vehicle positioning information will propagate the position
`vector x(t) using the available velocity vector with the most
`merit as follows: X(t)= x (t–1)+ v At.
`In the particular embodiment, the improved vehicle navi
`gation System can propagate the vehicle position from the
`available information, Such as GPS delta range measurement
`(S), the GPS Velocity, or the orthogonal axes accelerometer
`using lateral and longitudinal acceleration information.
`Application processor 22 calibrates V from V when
`possible. The GPS position information is used as an overall
`check on the current position. For example, if x(t)-
`x(t)|<(18.5*PDOP), where PDOP is the “position dilution
`of precision' a common variable computed automatically in
`the GPS engine, then X(t) is left unchanged, i.e. X (t)= x(t).
`Otherwise, X(t)= x(t). In certain embodiments, all raw
`inputs could go into a Kalman filter arrangement which
`outputs the Velocity vector.
`The sensor 28 for the embodiment of FIG. 2, which is a
`multiple, orthogonal axis accelerometer, provides accelera
`tion information for at least two orthogonal axes (lateral,
`longitudinal and/or vertical). The accelerometers 28 produce
`a voltage measure. AS shown in FIG. 3a for the longitudinal
`accelerometer although a similar flow chart applies to each
`orthogonal axis, the accelerometer data is read at Step 48,
`and the Zero offset (set at the factory and constantly
`re-checked and reset by the Zero Motion Detector men
`tioned below) is subtracted from this measure at step 49 to
`produce a number of Volts displacement from Zero. This
`number of volts displaced from Zero is then multiplied by a
`Scale factor (set at the factory and continuously re-calibrated
`by the GPS) to produce a number of G's of acceleration at
`step 50. This number of G's of acceleration is then multi
`plied by the number of meters per Second Squared per G to
`produce meters per Second Squared of acceleration at Step
`51. The meters per Second Squared of acceleration is then
`multiplied by the delta time (integrated once) to produce a
`velocity at step 52. This velocity is saved for the next
`Second. This acceleration information can be used to deter
`mine change in distance information, ADIST, and change in
`turn information, A0.
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`-e
`
`IPR2020-01192
`Apple EX1015 Page 15
`
`

`

`US 6,308,134 B1
`
`S
`Initially, the improved vehicle navigation System requires
`initial conditions for various items, Such as accelerometer
`orientations, accelerometer Zero offsets and accelerometer
`scale factors. Factory defaults that will be used for each of
`these items So that no initialization will be necessary. Those
`items will also need to be maintained, but not necessarily in
`the absence of all power (i.e. battery loss, or removal from
`vehicle). An option will be available to manually initialize
`these items. This would allow immediate use of the system,
`without having to wait for GPS to be acquired for calibrating
`these items.
`Once GPS has been acquired and is determined to be
`useable, GPS can be used to calibrate all of the configurable
`items. It will first determine the accelerometer orientations
`as described in FIG. 3c. At power on, the assignment of
`accelerometers to each of the lateral, longitudinal and down
`axes (if three axis accelerometer is used) are in the same
`orientation as the last power down, which will be saved in
`Some non-volatile Storage. If three accelerometers are used,
`one will be measuring the Earth's gravity. The accelerometer
`measuring one G (Earth's Gravity) will be assigned to the
`Down Axis. For the other two axes, as shown in FIG. 3c, the
`following procedure will take place. At Step 53, the accel
`eration data is obtained as described in FIG. 4b. The
`acceleration measurements from each of the two accelerom
`eters will be compared until their difference reaches a
`pre-defined threshold at step 54. The reason for this is to
`ensure that the accelerations are uneven enough that a valid
`compare against current vehicle conditions can be made
`without ambiguity.
`As shown in steps 55-61 for this particular embodiment,
`once this situation occurs and there is acceleration data
`computed from the GPS data, the acceleration from each of
`the accelerometers will be compared to the lateral and
`longitudinal accelerations computed from the GPS and the
`accelerometers with the closest acceleration values for each
`of those axes will be assigned to those axes. Additionally, the
`initial vehicle orientation is determined because the vehicle
`heading relative to True North can be computed from the
`GPS velocities.
`With reference to FIG. 2, the sensor integrator 40 can use
`the longitudinal and lateral acceleration information as
`described below to determine a current position for the
`vehicle if GPS velocity information is not available. In any
`event, if GPS is available or not, the sensor integrator 40
`provides the current position and a velocity (Speed and
`heading) to a map matching block 42. The map matching
`block 42 provides road Segment information for the road
`Segment that the vehicle is determined to be travelling on,
`Such as heading, and a Suggested position. The Sensor
`integrator 40 can update the heading component of the
`Velocity information with the heading provided by the map
`matching block 42 to update the current position. If the map
`matching block 42 indicates a good match, then the map
`matched position can replace the current position. If not, the
`Sensor integrator 40 propagates the previous position to the
`current position using the Velocity information. AS Such, the
`Sensor integrator 40 determines the current position and
`provides the current position to a user interface and/or route
`guidance block 46.
`The map matching block