United States Patent (19)
`Behr et al.
`
`USOO58O8566A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,808,566
`Sep. 15, 1998
`
`54 ELECTRONICNAVIGATION SYSTEMAND
`METHOD
`75 Inventors: David A. Behr, Roselle; Ramesh
`Ramakrishnan, Mount Prospect, both
`O.
`
`73 ASSignee: Navigation technologies Corporation,
`s rule 8
`
`Appl. No.: 494,198
`21
`22 Filled:
`. 23, 1995
`22 File
`Jun. 23,
`Related U.S. Application Data
`
`63 Continuation-in-part of Ser. No. 265,094, Jun. 24, 1994, Pat.
`No. 5,543,789.
`6
`51 Int. Cl. ..................................................... G08G 1/123
`52 U.S. Cl. .......................... 340/995; 340/988; '92.
`58 Field of Search ..................................... 340/988, 990,
`340/995, 991; 364/444, 449; 701/200, 208,
`209, 211
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`FOREIGN PATENT DOCUMENTS
`0379 198 A3 7/1990 European Pat. Off..
`WO 5.
`6/1991 Japan.
`/14215 8/1992 WIPO.
`WO 92/21001 11/1992 WIPO.
`OTHER PUBLICATIONS
`Hoffman, Steve and Stewart, Charles, “Text-based Routing:
`An Affordable Way Ahead?", Proceedings of the IEEE-IEE
`Vehicle Navigation & Information System Conference,
`Ottawa, Canada -VNIS 1993.
`PCT-Notification of Transmittal of the International Search
`Report, dated Nov. 2, 1995, in International application No.
`PCT/US95/07859, Applicant Shields Enterprises, Inc.
`“Smart cars, Smart Highways,” Collier, W. Clay and
`Weiland, Richard J., IEEE Spectrum, Apr. 1994, pp. 27-33.
`Primary Examiner Brent A. Swarthout
`Attorney, Agent, or Firm-Brinks Hofer Gilson & Lione
`57
`ABSTRACT
`The invention provides a method and System for providing
`route guidance and other information from a base unit to a
`remote unit in response to a request from the remote unit. A
`query is formatted at the remote unit, the query including the
`request, and is transmitted from the remote unit to the base
`unit. Requested route guidance information is calculated at
`the base unit in response to the query, using a large up-to
`date database located at the base unit. A response to the
`4,301,506 11/1981 Turco ...................................... 364/436
`query is formatted at the base unit, the response including
`3. tE. SE - - -
`.
`route guidance information. The response is then transmitted
`2 : 1 Y-2
`C. C. a.
`from the base unit to the remote unit for display. The
`- - -
`2.
`...E. iyya - - - -
`- - - - is: transmission is made in a compact form through the use of
`4,546.439 10/1985 Esparza r
`... 364f444
`maneuver arms and combined maneuver arms and through
`4570.227 2/1986 Tachi et al. ...
`... 364/444
`the use of tokenized forms. A maneuver arm represents a
`4,642,775 2/1987 Cline et al. ..............
`... 364/443
`road at an interSection, for depiction on a display, by one or
`4,733,356 3/1988 Haeussermann et al.
`... 364/424
`two endpoint coordinates. The tokenized forms are
`4,758,959 7/1988 Thoone et al............
`... 364/454
`expanded at the remote unit into textual driving instructions
`4,812,843 3/1989 Champion, III et al........... 340/905
`of information available at a remote unit can be increased by
`3.5 8. Still - - - - - -
`- - - SE providing the remote unit with information from the base
`5,043.902 8/1991 SNE al.
`... 340A988
`unit which is not adequately covered by any databases
`5,172,321 12/1992 Ghaem et al. .......................... 3.4444
`on-board the remote unit.
`(List continued on next page.)
`11 Claims, 15 Drawing Sheets
`
`4,780,717 10/1988 Takanabe et al. - - - - - - - - - - - - - - - - - - - - - - 340/995
`
`for each of OC, OOC languages. In addition, the amount
`
`
`
`...t.c -- as
`EVENSORs privijek
`A
`it..'.
`FFARYDATABAS. He
`ata
`MAP UPDATER
`!NTEsRATOR
`Bourg
`CALC&LATOR
`2.
`
`Distice
`AND ME
`Estimators
`
`SURROUNENS
`EXPRERS
`
`-82.
`eleinfortation
`PROVIDERs
`
`(3x
`
`Que Ry
`RESOLWER
`
`a-3
`
`|I/O INTERFACE |
`Af
`telephone set Trf
`/F/F/F Y--
`
`:
`z.:
`;... 3
`- - - - - - - - - - - - - -
`
`33---
`33
`
`(Eily A &
`SySM
`
`- 2
`2
`control
`KBE DSP
`
`8&-
`
`8
`
`&
`
`-54
`
`3-i-
`33-
`2.
`-
`.2
`.
`PepMobs v.
`Me M
`...
`K3C
`M
`28
`
`DISPLAY
`
`32 is
`
`52
`- 38.
`°ss
`s
`(3-
`48,
`RFI/F
`|LAEOPLup|MoDEM -
`33
`PC
`MEM (YDisplay
`42
`POS 3-up M
`K3
`A&ER
`3
`20 a /
`
`-
`iSPLAyi
`
`-
`&
`
`i8
`
`X:-
`
`Google Ex. 1004, p. 1
`
`

`

`5,808,566
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,243,528 9/1993 Lefebvre ................................. 340/995
`5,262,775 11/1993 Tamai et al. ............................ 340/995
`5,283,575 2/1994 Kao et al. ...
`340/990
`
`5,291,412 3/1994 Tamai et al. ............................ 364/449
`5,291,413
`3/1994 Tamai et al. ...
`... 364/449
`5,293,163 3/1994 Kakihara et al. ....................... 340/988
`5,293,484 3/1994 Dabbs, III et al. ................ 340/825.44
`5,396,429 3/1995 Hanchett ................................. 364/436
`5,559,707 9/1996 DeLorime et al.
`340/995
`
`
`
`Google Ex. 1004, p. 2
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 1 of 15
`
`5,808,566
`
`TRAFFIC
`MAP
`NFO.
`DATABASE
`VENDOR(S) PROVIDER
`
`83
`
`-71
`J: -
`
`/
`
`r
`
`- - - -a -- ru- mor- mm - rur- am
`
`72U
`MAP
`DATA BASE
`
`36
`72
`THIRD PART y
`DATA
`INTEGRATOR
`
`82
`
`
`
`OTHER
`INFORMATION
`PROVIDERS
`
`
`
`TRAFFIC AND
`MAP UPDATER
`
`
`
`
`
`
`
`
`
`D STANCE
`AND T ME
`TRAVEL
`
`
`
`
`
`at EST MATOR
`A
`
`
`
`SURROUNDINGS
`EXPLORERS
`
`QUERY
`
`6-4-
`
`72
`
`?
`
`I/O INTERFACE
`
`
`
`77
`
`CONTROL
`KBDDSP
`KBD DSP
`
`8%
`
`(58
`
`Google Ex. 1004, p. 3
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 2 of 15
`
`5,808,566
`
`START
`
`ESABL SH COMMUNI CATION
`
`1OO
`
`
`
`TRANSMT QUERY
`
`
`
`
`
`
`
`QUERY RESOLUTION
`
`1 O
`
`TRANSMT
`ERROR
`MESSAGE
`
`
`
`
`
`UN FRESOLVED
`QUERY
`p
`NO
`
`DEN FY QUERY TYPE
`
`| 12
`
`
`
`
`
`
`
`UN DENT FED
`QUERY
`2
`
`NO
`
`u? 1 11
`QUERY FULFILLMENT
`
`FORMAT RESPONSE
`
`TRANS M T RESPONSE
`
`1 16
`
`f 18
`
`END
`
`~f 2/.
`
`Google Ex. 1004, p. 4
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 3 0f 15
`
`5,808,566
`
`NSEWu:
`
`
`mvh\ VA\w3\03VoN888II'III'
`
`mo<mmm§
`
`
`
`\NwkOWN
`
`YDwN~hN\V83
`
`Google EX. 1004, p. 5
`
`Google Ex. 1004, p. 5
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 4 of 15
`
`5,808,566
`
`
`
`START OUT GONG EAST ON
`ROCKWOOD ST TOWARDS
`GLEN DALE BLVD.
`DRIVE O.1 MLS
`
`GLEN DALE
`
`ROC-(WOOD
`
`TURN RGHT ON TO GEN DALE BLVD.
`DRV. O. MILES
`
`GLEN DALE
`
`TURN SLCHT RIGHT ON TO
`LUCAS AVE
`DRIVE O.2 MLS
`
`ROCKWOOD
`
`GLEN DALE
`
`Google Ex. 1004, p. 6
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 5 of 15
`
`5,808,566
`
`
`
`TURN LEFT ON TO EMERALD DR
`DRIVE O. 1 MLE S.
`
`EMERALD
`
`TURN RIGHT ONTO EMERALD ST.
`DRIVE A SHORT DISTANCE TO
`YOUR DESTINATION AT 23O
`EMERALD St.
`
`EMERALD
`
`Google Ex. 1004, p. 7
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 15, 1998
`Sep. 15, 1998
`
`Sheet 6 of 15
`Sheet 6 0f 15
`
`5,808,566
`5,808,566
`
`
`
`
`
`
`
`02.5me20.22Emmq\zoF<szmozGEo
`
`mo;.pmocozxoOm0mm:_In:REzzafimumm_Emmmfioomomogflmommvamm_52:3:m4013vAAXD.mmmjo.mmmEummDmUmu\FXmC.
`
`
`ZGEOm:mo<mmm§u§<km”:2;2m:092
`
`
`
`
`
`ZumzmiioEmmmooimmqmoimo;émmimmzmwomm_mmmmaoimmgmoz¢(Fmvfiqd
`
`
`
`
`
`
`
`wm>rr<2mmb<EEZ.523ZO_._.<2_meQFXmE.mniF
`
`0.47:mai‘raim;moi/L.\2
`
`_2K33
`
`
`
`3fig\/
`
`
`
`
`
`mfikp:m:m0<mmm§022<F®NEE:ZNJOWE
`
`ummmmcfiomuse33m0.0:Euiw:SENEESEmonm_EmmmgomONmovflmmmnmowm.
`
`.mmZETo@3228/.QSmmqqozmqomvumzouemooozxoomcoW3m0<mmm§94d
`
`
`
`KT.omKSJmme8135250500258"sz
`
`
`mmmEummbmUmom )\m63?To3928/E.moflmEzzao.mBm_8882088382@3231w§m0<mmm2EHMvW251mg:wl\mmo<m1meoéJm0<mmm§n:KNWDm:
`
`
`
`
`_M/.mmu::flE
`
`
`-88.8mmA“mqamzmfiukooozxuomuzmi.mmZeH.o933i,.EEmmquwquwemolxmmmvémam
`3:05:05museH6Am81/7:mofimmszaflmonm_memgomogovflmmmnmomfl.
`
`
`
`
`
`_H¢.Hm-«mv
`
`ESE583m5:9m5Amfiniimofimmggflmunm_EmmmsomoSowflmmfllmowfl
`
`-Kimm.Humfiafimémzmfiouzmi.835«.09L88/.mimagmaScowemo<mmm231V
`
`
`
`_fi£fi§i$L$L$me
`
`-KLSdmme‘ioqmmmzfimmusqflzmi.835H59:8H/.maoqfimzm(mo<mmm§firm
`
`
`
`EcoEma55v.03(SH/7:moSmmszDE321823888882mmmnmoufi
`
`_yummoz_mm
`
`Google EX. 1004, p. 8
`
`Google Ex. 1004, p. 8
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 7 0f 15
`
`5,808,566
`
`
`
`9:3Now30>xcmfi5_Emoflmfizéflmunm_Emmmsomogovmfimmnmuwm_
`
`
`
`Emlifdm-63mm4Noqémzmmoqfimzmuzmin/.emQq§mzm
`
`
`
`
`
`0mmumcoflmcflummv30>3853mguuonmm935M}.9maqgmzmemw<mmm§UHBuo$on53;8.0Gu/uifimoflmgzzaflmonm_EmmmaoomONmS‘mEmmnmuwm_
`
`
`
`_»umzmiexm2umm>bmz§________Foflmfizzafldomm:SmmfioomoSovfl233$KEEROSJEVCE30:3
`
`88mm
`
`MNAwfim)
`
`I
`
`2mm_mmvo_wz\39$:ESE
`
`Hmm$3-33ӣ9538musomcmEmm~o.m.m:m:.8:mm3c0335mmmnmumovu/dyou
`
`
`
`
`
`mmflwoflocnomhcoflummT/mzvmummmaucmfluxuouwwmnmquM/p/Mmusomcm\Hmm-m0<mmm§QZN
`
`
`
`
`
`
`
`
`
`
`
`
`
`gummozi/ANAcoflmumSmum3uwommQH\>m0HoczomBcoflumEMOMEH
`
`
`
`
`
`
`
`r§o_m_omom~mmwm_onmH>HomB_32833733303W\\WQWN)
`
`\2
`
`
`
`
`
`Zuemmam:oooooooouonmmmfl_______Emoflmmom505533103898_Qm«o_mno_
`
`
`
`r3moan§mx§MN\WWWW
`
`Google EX. 1004, p. 9
`
`Google Ex. 1004, p. 9
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 8 0f 15
`
`5,808,566
`
`
`
`“mm8HNmHmmHHmszoaHmHqumHZM¢_.mmHHeH.om>fluo8/.zqmHm
`
`
`
`
`
`mzoqmoucoHmempageH.oAmM/u/_m_omom_mmwm_onmH>HQmQH_>mmvmmwm_
`
`r_mm-.wmwamu.m>
`
`
`
`
`
`mzoquHmmeHmzuzm¢_.mmflfleH.om>HHQ8/.2;msz
`
`r.>umzmm_9xm2umm>bmz¢z__,_fl._*,omom_mmnm_onmH>HomoH_mwmoumow_moam_mmo_
`
`r_wummoz_mm-.mmwmm-.mm-“mm\a“emmmm20m“msz
`
`moucoHmmgmusem.oAwu/u/_m_omom_mmvm_onmH>HamaH_nmmwmmwm_
`
`r_mb-.>wkmm.flkmsz
`
`
`
`
`
`m209uzmm_.wucmumfluuuonmmm>Hno8/.zqHmmmmSOm
`
`
`
`
`
`mHHmzmoucoEmmacgse0.0AmH/H/_m_mmom_mmwm_onmH>HmmnH_nmmvmumm_
`
`
`
`
`
`r_wm-\«mkaw-\mp-wmm.H“mHmmBHmzwmoQHmHqumuzm¢_
`
`
`
`mmafleH.musogdH/_m_omom_mem.onmH>HomoH_>mmUmmmm_monm_mmno_
`
`
`
`r_H/.wwudcfleow
`
`
`
`.moumumHUugonmmm>fluoH/.w¢zmonmHqummnoummznuuoz
`
`msflomuseugmum0.0AHM/u/_m_omom_mmvm_onmH>HomoH_>mmvmmmm_
`
`r_wmu.mqumezou___fi_____omom_mmam_onmH>HmmoH_mmmouoow_moom_mmo_
`
`\wdzmoonHqummomm___omom_mmam_onmH>HmmaH_mmmouoom_wu«¢_mfia_
`
`
`
`r_wumzm4_2_o_mmmmoq<_moz«mo~092mz¢5¢mzmvom_mmmmoa¢_szm«2¢
`
`r_mo_m_om0m_nmvm_onmH>HomoH_mbmummmm_mmUm_mmoo_
`
`:$88
`
`88mm
`
`:$8
`
`Google EX. 1004, p. 10
`
`Google Ex. 1004, p. 10
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 9 0f 15
`
`5,808,566
`
`-«omapounoHmonmusew.Hanu/u/_m_mmom_wmvm_onmH>HomnH_mmmUmwmm_
`
`
`
`mHmzmOusoEmmamazem.oAwH/u/_m_omom_wmwm_onmH>Haon_mmmvmumm_
`
`
`
`mHmzwoz¢mmmmnzm¢_.mmHHEm.om>fluo8/.omzowz¢u
`
`r_mm-~ma-flmm~nm-“ma-8mmumm.Hwoz<mmmmNHmmmmzomuzm¢_
`
`r_Hm-_>mkmm-8mm-mo~mm-umm~amzowz¢u
`
`
`
`
`
`Hm-<u“¢oqu4mmownzm4_.mmaflem.mm>flue8/.mz¢m9mm:Hm
`
`mebomyammm-¢umapmxmeb.mAwH/~/_m_amom_vam_onmH>HmmnH_mmmwmwmm_
`
`r_mm-~mumm-~mm“mm.auammz
`
`ememcanem.oAmu/M/_m_mmom_wmvm_onmH>HomoH_mmmvmwwm_omw¢_¢mmo_
`
`
`
`
`
`.mmflflem.om>Humu/.m>«oz¢mMmmouao
`
`
`
`-808mm.HKmHDommm-¢u“monmm>Hmuzm<_.mmHHE8.0m>flgoH/.uflxm
`
`
`
`
`
`r_»umzm<_exm2umm>bmz¢z_________omom_mmam_onmH>HomoH_w>mouaom_mmmm_mmo_
`
`qmozmgumxme8.»AmH/u/_m_omom_vam_onmH>HomoH_meUmmmm_munm_mmmo_
`
`r_wummoz_mm-.>Nooa
`
`
`
`49m00u2m4_.mwafle«.0m>fiuoH/.uflxmm>mzqooqu\ommuz¢m
`
`
`
`
`
`
`
`
`
`zHHmDHzOucoEmmamusem.nAoau/u/_m_omom_mmvm_onmH>HomaH_vmmvmmmm_
`
`
`
`r_nm-.fim-8mm-.m-8mm\HNemszmphmmmmz
`
`
`
`
`
`-8mm-8mm‘H“zHHmsauBmzHemDHuzm¢_.mmafleo.Hm>flgo8/.Bm
`
`r_ma.mmmm
`
`
`
`memmzmOuco9mm;cpsem.mAHHu/H/_m_omom_mmvm_onmH>HamoH_UmmUmwwm_
`
`
`
`
`
`
`
`-88-“m8mm-8mm.HumemmzmzHembenzm4_.mmHHE¢.om>fluoH/.m><
`
`r_HH-‘mm“mm
`
`Bmemmusem.mANHH/u/_m_mmom_mmwm_onmH>HomaH_Ummvmmwmw.mocmumHUuuonmmm>fluoH/.emmoon2mxummmzouuo
`
`
`
`
`
`
`
`r_wummoz_ooa-.okm_mmumm.H“monm2mmummmkme¢m2nzm<_
`
`GOOgIe EX. 1004, p. 11
`
`Google Ex. 1004, p. 11
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 10 0f 15
`
`5,808,566
`
`
`
`
`
`8mma-mmmaunmfluumoumunomsm\Hmm‘o.m.mI¢OHoomHcoflmgm>mmmgwumovn/.mnoo
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`memOHocflomHcofiummfi/mz«m-mmmaunmflflaovmmmnmuwQH/H/mmusomnm\Hmm
`
`
`
`mnflmsgo“so»xcmgap/_m_omom_mmvm_onmH>HomQH_ommnmwmm_
`
`
`
`
`
`r_»nmzm¢_axm2umm>omz<z_________omom_mmam_ZOHwH>HomaH_m>mouoom_mmma_mmo~
`
`EOflumcflumeH59”Oumoflmfimflvuhogmmw>HHQu/.HmOBZMEU/Nmzouco
`
`
`pumamuseo.mhwaH/H/_m_omom_mmwflonmHBommiommvmwmfl
`
`
`
`r_08mm-8mm8H“OHZmzmmummNamomezwmmnzm¢_H/.ew092mz¢mvmmzmvomum
`
`
`
`emonmuseo.mAmau/H/_m_omom_mm©m_onmH>HommH_ommnmmmm_nmmm_owmo_
`
`
`
`.mmHHEH.om>flgmu/.m>«mmomHmemmouuo
`
`r_mm-\w-N¢-\mmem8HNomomBmem“moonzmmummmuzm¢_
`
`3R883
`
`\\|/\
`
`8wSwag»
`
`J
`
`\Y/K
`
`
`
`
`
`r_2nmmoz_u/Aw¢.m:oflmpm>mumzuwommoH\>moHocnomhcOflumenowcHHmm
`
`
`
`
`
`
`
`r_wumzm4_z_o_mmmmom<_mm<mommn_mmmmao¢_qumwzmmeW\&WWYMMJ«zmbm.mmmomemozmmo
`
`moq.Qmmzmmboompfl___mmom_muom_onmH>HomoH_Ummouoow_mbmn_ama_
`
`
`
`
`
`\‘/\
`
`Google EX. 1004, p. 12
`
`Google Ex. 1004, p. 12
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 11 0f 15
`
`5,808,566
`
`
`
`
`
`uuonmmm>fluou/.m>«quxzammmvumzouommmeDonoummsnugoz
`
`
`
`m.om“scam~/_m_omom_mUUm_onmH>HamaH_mgmUmmmm_mwmw_mv>o_
`
`mcflom“sougmum0.0AHH/H/_m_am0m_movm_onmH>HammH_mnmUmmmm_
`
`
`
`rT?.mmudnfleHm.mmHHE
`
`
`
`
`
`BmmZDmzOucoHmmqnudem.oAmH/H/_m_omom_wovm_onmH>HomnH_mnmUmumm_
`
`
`
`
`
`oucoemonemqummuseH.oAmH/H/_m_omom_muum_onmH>HomnH_mnmwmmmm_
`
`
`
`-8¢Kmm.Hkammboquqmz4mmuzm¢_.mmHHEm.om>fluoH/.ommzmmbo
`
`r_om-~mmumm
`
`
`
`r_m888m-umm.HNmmesoanmm50nzm¢_.monmuwflw
`
`
`
`-momapoucoBmemmuseH.¢Awg/H/_m_omom_muwm_onmH>HomaH_mnmvmmmm_
`
`
`
`Hoa-moNemmZDmuzm¢_.mwaflem.¢mm>flgo8/.mz¢mmebomHOH
`
`r_wummoz_mm-\N-N>m-~mmmmm\akmebom
`
`
`
`-8mm8m.mm-“mm.HuemmZDmumzmm50uzm<_.mmflflsm.mm>flyoH/.o>am
`
`r_m
`
`r_wumzm4_exm2umm>bmzmz_________omom_ooom_onmH>HomoH_m¢moooom_0mmm_wmo_
`
`8w"$83
`
`\‘I/k
`
`Google EX. 1004, p. 13
`
`Google Ex. 1004, p. 13
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 12 0f 15
`
`5,808,566
`
`
`
`-u”"000006958“mHommooz_o_amom_mowm_ZOHmH>HQmDH_wmm©mwmm_wvom_mwoo_
`
`r_2ummoz_”u--
`
`~~
`
`
`
`8m>4dqqm9«x3mmma___amom_momm_onmH>HomQH_9Qmouoow_ammm_woa_
`
`r.mHomuwmmDO_z_ooa_92¢m9¢9mmm_9mm<m_mmmmoo4_moz¢mo
`
`W 2
`
`?
`
`i“a
`
`?
`
`GOOgIe EX. 1004, p. 14
`
`
`
`
`
`r~2nmmoz_u/fimw.mcoflmMm>mHmBumommQH\>onOGSUmBcofiumEHowcHHmm
`
`
`
`
`
`99022mnumxm9m.mmAmH/u/_m_omom_ouwm_onmH>HomQH_nnmUmwmm_H9nw_momo_
`
`
`
`
`
`«Hmm9m<“¢z¢«92¢mnzm¢_.meHeH.om>fluo9/.uflxwm>¢
`
`r_mm-~mHNmm-.99umm8Huo>qm
`
`
`
`.m>¢99023cucommgmz9.mmAmH/M/_m_omom_ovum_onmH>HomoH_nnmvmwmm_
`
`
`
`
`
`
`
`
`
`rifi-8mm8mm-88-8m.mm-“mm8H«mmmom9mmz¢mow99ozxuzm<;9/.m>4mmmom9mwz<moomm9
`
`
`
`umcofiumcflummv930%Onmmaflem.ow>9uoH/.m><mmmOmBmUdeO
`
`
`
`ouco99mg29:99.mmA9p/p/_m_omom_oUUm_onmH>HomQH_nnmwmmmm_
`
`r_mm.9m“am-~9m-u9m~m~
`
`
`
`
`
`mcflm:809:09xcmz9u/_m_omom.ovum_onmH>HomQH_nnmwmmmm_
`
`
`
`
`
`-Nmm-\mflkmm.flu99ozx“m>qm«Hmm9mauzm<_.mmHHEo.Hw>flum8/
`
`
`
`mwflmOHosaowHsoflumm9>mzwmINmmausmfluxmouwmwnmquH/H/mmuSOMfiM\Hmm
`
`
`
`
`
`
`
`
`
`«mmfi-mmmausmfluxmouwusomsm\Hmm~o.m.mlwoaoomacoflmum>mmmnmumaVH/.muoo
`
`
`
`
`
`
`
`Google Ex. 1004, p. 14
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 13 0f 15
`
`5,808,566
`
`
`
`-u”uNooooécsowmHomwooz_o_omom_ommm_onmH>HamoH_oomUmwmm_mmmm_mmmo_
`
`
`
`.m>¢¢game¢z3mmmH___omom.ommm_onmH>HomoH_mmmouoom_80mm_moa_
`
`r_mHomuwmmDo_z_ooa_Bz<momemmm_wmw29m_mmmman¢_mwzmmo
`
`
`
`
`
`\~azmpm80>gmmmemmmuzmzHmmwnezmmsmemmmaoom¢mmmmeeEmzsmN"n--
`
`
`
`
`
`mom;ZmHNNuHZQNdeBmm/mEm.NMOZDENZ"wwwmvua.¢.hmanmmmuouo”mommmummnmmdm
`
`
`
`r_ZummOE_zu0bmwm"N.¢~woaumm¢uo-ouvmowmanHZOHmmAgm~nfiwflm
`
`
`
`-N”umfloooan:0wmHommooz_o_omom_Hmmm_onmH>HomaH“vamwmmmmfmmofl_wobo_
`
`
`
`.m>4mqqmemxzmmmfi___Qmom_Hmmm_onmH>HmmoH_>omouoom.mwmm_moa_
`
`r_mHomuwmmDo_z_ooa_ez¢mb¢9mmm_mmombm_mmmmom¢_mwz¢mo
`
`
`
`
`
`-omm-o;ommmmmmm«mmm.o>qm«mmmmpopmmmwmomHmmmmkmmmN"n..--
`
`
`
`
`
`
`
`«a\wzmqummmzH3wmmanwszmmwmbmkz“wwwfim"m.¢‘wma-mnn-o-oubmmwmnmmumudmm
`
`
`
`\m>qm«mmdm¢qmHmwnmmwmbm692¢ouz“mmomvnm_¢‘mma-mmwlo-onmo¢¢mnmmu¢mm<m
`
`
`
`mmmmm442Howmmmwmomm.mumomoflzumamomufi\¢.mma-mmm-o-oumo¢¢mummu¢mmmm«a
`
`
`
`ommnmmwmbmmaz¢eflzumommwn-~¢8mmm-mam-o-oumm¢¢mummu¢mmmm«a\wzmqummmzHmHmmmmombmqummmzHzNHHmH.w.omfi-mom-o-ommwwmnmm<mm¢md4.o>qm
`
`
`
`
`
`
`
`r_wummoz_znmfiammum8880mfi-wom-o-ouww¢¢mummummm¢m«a80>qm«mm¢mma3
`
`
`
`-mmm-o-ommnmmmm«mm:«pmou8mmBm4oummmmuoszmmompmuzumomwmua.¢.omfi
`
`
`
`
`
`
`
`zoewzHHZDm.emHmmbmmoommHommauoszmmwmbmuzummmm¢ufi.«~wm
`
`
`
`
`
`Google EX. 1004, p. 15
`
`Google Ex. 1004, p. 15
`
`

`

`US. Patent
`
`Sep. 15, 1998
`
`Sheet 14 0f 15
`
`5,808,566
`
`r_9xm2umm>bmz¢z_________mmom_«mmm_onmH>HomQH.momoooom_HUmm_mmo_
`
`
`
`mmwmbmkz"mmmom"m‘8‘m¢m-oama-o-on¢Hm¢mummnmzq¢m«aNewzmH>wmqq¢>
`
`
`
`mmmbnmmombm950-2-2H_o_omom_¢mmm.onmH>HammH_MHmUmmmm_mmmw_mwmo_
`
`
`
`-z-zH“z"mmamua88.wma-mmw-o-oufimommummnmwz¢mo.HmmomeHuzmwmuwzHM
`
`
`.ommmwomHowwszmmwmbmkzuma¢mmnfl_¢NHHH-wmm-o-onm¢mmmummu<za
`«92¢m89mqoemHmmmommmnozHMmmombmflzuommwmna~¢~bma
`
`
`
`
`
`-mmm-o-ou¢HmmmnmmN<H92mu¢qm.m>mzmzmamu3mmwummombmBbo
`
`
`
`
`
`Hm¢mfiuwszmmmemKZUOmmmmna.¢.nom->mh-oloum¢mmmummu«z¢mezmm
`
`
`
`
`
`m.m0muzu¢ommmuH888mm-H>w-o-ou8mmmmummquHmDe.m>4Hmongmz
`
`
`
`-mma-o-onbanmmmmmemszpmmz80>qmmummmHmmmaummoMDm
`
`
`
`
`
`r_2ummoz_zuo¢am¢"m.¢.mflm-bmfia-o-onmmabmummnmmemzHZBmmz
`~0.5mmmHmszemmzNmmmummwmbmeso-z‘zHNz"¢HHowum.w.mHm
`
`
`
`
`
`Google EX. 1004, p. 16
`
`Google Ex. 1004, p. 16
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 15 0f 15
`
`5,808,566
`
`
`
`2.
`
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MAKE A U
`TURN AT
`
`ANDER KRUZUNG
`HA CA UNA
`VUE LTA EN M
`BIT
`U EN .
`.
`ElNE KEHRTWENDUNG
`MACHEN.
`CAMBIA EL -
`CHANGES
`UNDERT DEN
`NAME TO -- . NOMBRE A
`. NAMEN ZU
`.
`TURN LEFT ON Dá VUELTA A LA AUF
`LINKS
`AND DRIVE Z QUIERDA EN A BB EGEN UND
`MILE S.
`Y MANEu E
`MELEN
`- MILL AS. WE TERFU REN.
`
`
`
`REQUEST ROUTE
`PROM
`E3ASE UN.
`
`RECEIVE ROU
`NFORMATION FROM
`3ASE UN. T.
`
`
`
`COMPARE RECEIVE)
`RO U
`W -
`ONEO ARO MAP
`
`
`
`
`
`
`
`
`
`S
`A NY
`PART NOT
`A DE QUATELY
`COVERED
`2
`
`
`
`55
`
`RECQUEST STRP
`MAP OR PARTS
`NOT ADCCPUATELY
`COVEREO.
`
`RECEVE STR P
`MAP NFORMATION
`FROM 3ASE UNT,
`
`54
`
`of 2. “
`
`Google Ex. 1004, p. 17
`
`

`

`1
`ELECTRONIC NAVIGATION SYSTEMAND
`METHOD
`
`5,808,566
`
`15
`
`2
`database on CD-ROM or other media becomes out of date.
`In addition, when a database is compiled, it may include
`errors which are then replicated in the many copies provided
`to users. These errors may require correction in the user
`copies by replacing those database copies. Moreover, incor
`rect or outdated information in the database can lead to
`errors when calculating routes. When an out-of-date data
`base does not include the information that a particular
`roadway is closed, the System may be unable to calculate an
`alternate route.
`Autonomous route guidance System providers may
`improve the accuracy of the System by providing occasional
`database updates to users. However, distribution of the
`database, in a medium such as CD-ROM or floppy disk, to
`remotely located mobile users may be difficult. In addition,
`the media themselves are expensive Since they may gener
`ally be used only a Single time.
`Other aspects of Such prior art autonomous route guidance
`Systems add to their cost and inconvenience. Because the
`Systems are autonomous, they must include all components,
`including the computer, the database and the position Sensor.
`Using present technology, Such a System is too heavy and
`too large to be readily transported by an individual. In
`addition, the complete System has power requirements
`which make battery operation impractical. As a result,
`autonomous route guidance Systems have been limited to
`installation in automobiles or other vehicles which can
`accommodate the size and power requirements of Such a
`System. The current best price for a complete autonomous
`route guidance System is Substantial. This includes only the
`cost for a Single, dedicated autonomous route guidance
`System.
`Another type of route guidance System has been tested in
`Europe using beacons to provide a guidance Signal to
`on-board equipment. The System directs the user to travel
`from beacon to beacon, creating a stepwise path between an
`origin and a destination because of the fixed locations of the
`beacons. The navigational information thus provided forms
`a generally inefficient routing path from origin to destina
`tion. In addition, Such a System does not provide the capa
`bility to query a database for information about nearby
`points of interest and other geographical information.
`Therefore, there is a need for a routing and information
`System that continually provides access to up-to-date, cor
`rect geographic information by a remote user. There is a
`further need for a routing and information System which can
`be implemented on lightweight, portable devices for easy,
`convenient transportation and use. There is a further need for
`a routing and information System which is independent of
`any particular hardware configuration and which may be
`implemented on any Suitably equipped data processing
`apparatus, Such as a desktop personal computer, a laptop
`computer, a personal digital assistant or even a pager. There
`is a further need for a routing and information System which
`provides communication between mobile units and a base
`unit over any available channel, including wireleSS, wireline,
`and optical channels. There is a still further need for a data
`communication protocol for providing accurate, reliable
`communication in Such a System, independent of hardware
`configuration and in a compact form.
`SUMMARY OF THE INVENTION
`An object of the invention is to provide a method and
`System for transmitting route guidance and other informa
`tion from a base unit to a remote unit in a compact form.
`Another object of the invention is to provide a method and
`System for transmitting route guidance and other informa
`
`25
`
`This application is a continuation-in-part of U.S. patent
`application Ser. No. 08/265,094 filed on Jun. 24, 1994 by
`David A. Behr and Randall B. Jones, now U.S. Pat. No.
`5,543,789, entitled “Computerized Navigation System.” The
`entire contents of the Ser. No. 08/265,094 application is
`incorporated herein by reference.
`A portion of the disclosure of this patent document
`contains material which is Subject to copyright protection.
`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 otherwise reserves all copyright
`rights whatsoever.
`BACKGROUND OF THE INVENTION
`The invention relates generally to a System and method
`for providing route guidance and tracking information and
`other information from a base unit to a mobile unit over
`wireless, wireline, or optical devices. The invention more
`particularly relates to an apparatus and method for providing
`to a mobile unit route guidance and tracking information and
`other information which has been calculated and/or Stored at
`a base unit in response to a query from the mobile unit.
`Systems have already been developed which provide
`geographical or position-dependent information to a mobile
`user. Such Systems are generally installed in an automobile
`or other vehicle. These Systems generally include an
`on-board geographic database which may be accessed to
`determine geographic information, Such as locations of
`points of interest, directions to points of interest, and direc
`tions between a Specified origin and a destination. An
`35
`on-board computer calculates route guidance information
`using data from the database in response to user inputs.
`Such Systems are known as autonomous route guidance
`Systems Since they are independent and Self-contained. The
`Systems generally include a geographic database, position
`ing Sensors, and a computer including a keyboard and
`display. The geographic database is a representation of a
`region or metropolitan area and may include, for example,
`Street names, navigation attributes, Such as turn restrictions
`and one-way Streets, Street addresses, and points of interest,
`Such as airports, restaurants and museums. The positioning
`Sensors may determine geographic position from RF (Radio
`Frequency) triangulation or in response to signals from, for
`example, GPS (Global Positioning System), LORAN C or
`other similar positioning Systems, and from motion and
`direction detectors. The computer calculates route guidance
`information in response to inputs from the other System
`components as well as from operator input. The route
`guidance information is provided to the user in the form of
`navigational text or map graphics.
`Autonomous route guidance Systems have many
`drawbacks, however, which have prevented their wide
`Spread use. Because the System is autonomous and has an
`on-board database, the System must include large Storage
`capabilities for storing all of the data which form the
`database. Technologies such as CD-ROM have allowed
`Storage of an entire database but require Still a tradeoff
`between cost and fast, efficient data access.
`Another problem with autonomous route guidance SyS
`tems is maintenance and currency of the database. AS new
`Streets are built, or as old Streets are reconfigured, as
`businesses and other points of interest open and close, the
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Google Ex. 1004, p. 18
`
`

`

`5,808,566
`
`3
`tion from a base unit to a remote unit in a language
`independent form Such that the remote unit can provide the
`information to a user in any language or form desired by the
`user at the remote unit.
`Another object of the invention is to provide a method and
`System for transmitting route guidance and other informa
`tion from a base unit to a remote unit in which the amount
`of information available at a remote unit can be expanded by
`providing the remote unit with information from the base
`unit which is not adequately covered by any databases
`on-board the remote unit.
`The invention provides a method and system for provid
`ing route guidance and other information from a base unit to
`a remote unit in response to a request from the remote unit.
`A query is formatted at the remote unit, the query including
`the request, and is transmitted from the remote unit to the
`base unit. Requested route guidance information is calcu
`lated at the base unit in response to the query, using a large
`up-to-date database located at the base unit. A response to
`the query is formatted at the base unit, the response includ
`ing route guidance information. The response is then trans
`mitted from the base unit to the remote unit for display.
`The transmission is made in a compact form through the
`use of maneuver arms and combined maneuver arms and
`through the use of tokenized forms. These tokenized forms
`represent a large amount of textual information by one or
`Several alphanumeric characters.
`A maneuver arm represents a road at an interSection, for
`depiction on a display, by one or two endpoint coordinates.
`If two interSections are Sufficiently close together, a first Set
`of maneuver arms for one interSection and a Second Set of
`maneuver arms for the other interSection are combined to
`produce a combined set of endpoints for transmission in a
`compact form to depict the first Set of maneuver arms and
`the Second Set of maneuver arms on a common display.
`The tokenized forms are expanded at the remote unit into
`textual driving instructions for each of one or more lan
`guages. In addition, the amount of information available at
`a remote unit can be increased by providing the remote unit
`with information from the base unit which is not adequately
`covered by any databases on-board the remote unit.
`Other objects, features, and advantages of the invention
`will be apparent from the detailed description set forth
`below.
`BRIEF DESCRIPITON OF THE DRAWINGS
`The features of the invention are set forth with particu
`larity in the appended claims. The invention, together with
`further objects and advantages thereof, may be further
`understood by making reference to the following description
`taken in conjunction with the accompanying drawings,
`wherein:
`FIG. 1 is a functional block diagram illustrating a System
`of the invention;
`FIG. 2 is a flow diagram illustrating a method of the
`invention;
`FIG. 3 is a diagram illustrating a data communication
`protocol for communicating data from a mobile, or remote,
`unit to a base unit in accordance with the invention and
`which is used in conjunction with the system of FIG. 1 and
`the method of FIG. 2;
`FIG. 4 is a diagram illustrating a data communication
`protocol for communicating data from a base unit to a
`mobile unit in accordance with the invention and which is
`used in conjunction with the system of FIG. 1 and the
`method of FIG. 2;
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 5 is a diagram illustrating a Suitable sign convention
`for maneuver arm endpoint coordinates,
`FIGS. 6 to 10 show examples of maneuver arms displays
`in a remote unit;
`FIGS. 11 to 14 illustrate data that is transferred between
`a remote unit and a base unit in the example of FIGS. 6 to
`10;
`FIGS. 15 to 38 illustrate additional examples of data
`transferred between a remote unit and a base unit;
`FIG. 39 illustrates a combined maneuver arms display;
`FIG. 40 illustrates some examples of tokens and corre
`sponding expanded English, Spanish, and German text, and
`FIG. 41 is a flowchart used for explaining operation of a
`Stripmap request feature of the invention.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`Overview
`The invention provides a method of providing route
`guidance information and other information from a base unit
`to a mobile unit in response to a request from the mobile
`unit. The method comprises the Steps of formatting a query
`at the mobile unit, the query including the request, commu
`nicating the query from the mobile unit to the base unit, and
`calculating route guidance information at the base unit in
`response to the query. The method further comprises the
`Steps of formatting a response to the query at the base unit,
`the response including route guidance information, and
`communicating the response from the base unit to the
`mobile unit. The guidance information may include naviga
`tion instructions from an origin to a destination, information
`about one or more points of interest within a particular
`region, or other geographically referenced information.
`The invention further provides a System for communicat
`ing routing information between a base unit and a mobile
`unit. The System comprises an input means at the mobile unit
`for providing an origin and a destination. The System further
`comprises a calculating means at the base unit for calculat
`ing a route between the origin and the destination. The
`System Still further comprises communication means for
`communicating the origin and the destination from the
`mobile unit to the base unit and for communicating the route
`from the base unit to the mobile unit. The routing informa
`tion may include navigation instructions from an origin to a
`destination, information about one or more points of interest
`within a particular region, or other geographically refer
`enced information.
`The invention still further provides a method of providing
`routing information to a mobile unit. The method comprises
`the Steps of providing an origin and a destination from the
`mobile unit to a base unit, the base unit located remotely
`from the mobile unit. The method further comprises the
`Steps of calculating at the base unit a route between the
`origin and the destination, and providing the route to the
`mobile unit.
`The invention still further provides a system for providing
`route guidance information to a remote location from a
`central location. The System comprises a mobile unit includ
`ing an input means for providing at least a route destination
`and an output means for providing an indication of the route
`guidance information. The System further comprises a first
`transmission means at the mobile unit for transmitting
`destination data and origin data from the mobile unit, the
`destination data being indicative of a route destination and
`
`Google Ex. 1004, p. 19
`
`

`

`5,808,566
`
`15
`
`25
`
`35
`
`40
`
`S
`the origin data being indicative of a route origin. The System
`Still further comprises a base unit at the central location. The
`base unit includes a first receiving means for receiving the
`destination data and the origin data from the first transmis
`Sion means, a calculating means coupled with the receiving
`means for calculating a route to the route destination from a
`route origin responsive to the destination data and the origin
`data, and a Second transmission means for transmitting
`routing data, the routing data being indicative of the route.
`The System still further comprises a Second receiving means
`at the mobile unit for receiving the routing data from the
`Second transmission means, the Second receiving means
`being coupled with the output means for providing the route
`guidance information to the input means responsive to the
`routing data.
`The invention also provides a System and method for
`providing geographically referenced information from a
`base unit or server to a mobile unit. The mobile unit may be
`a transportable device Such as a laptop computer or personal
`digital assistant (PDA), or may be a desktop personal
`computer or any other device permitting data entry and
`display, printing, or Sounding of the provided information.
`The mobile unit communicates with the base unit using
`any available communication System, Such as land line
`telephone link, cellular telephone or radio frequency trans
`mission. Queries are communicated from the mobile unit to
`the base unit. The query requests route guidance
`information, information about a point of interest or other
`geographical information. The query is formatted in a speci