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
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`PLiSIPFIL2besaaanCHefCL
`
`
`PEL21GOl-Pol
`
`KcolOC!
`
`Sheet 3 of 15
`
`5,808,566
`
`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
`U.S. Patent
`
`Sep. 15, 1998
`Sep. 15, 1998
`
`Sheet 6 of 15
`Sheet 6 of 15
`
`5,808,566
`5,808,566
`
`c/orpA
`
`-'06/66'T!AIVGNATID!dOOMNDON=WuY,|“SatTtw1°OeaTtagI\“datasrvanato|30¥SS3au’
`
`
`
`
`-'L-!L0'86-!66'TidIvasWwa‘SwonT=wWuy|‘“SseTtIwtoeatigZ\“YdGIWuaWE»-FOVSSAW7G03UOL4aTuanLF'0(bA\A\{a]
`
`
`
`
`soq6{eLeestoowoz90PS|96ELEDSZ|T6-!66'T/ATYAONATO‘COOMNDOU=WUY|‘“SaTtwT°Qsataqda\‘dATdAIVGNAIDspzemco7LSGOOMHDOYuo|~govssanON©qseqButoB3no3azeqs0°0(IT2\4\]u]6oTtzyIWNna]
`
`
`
`-'LT!66‘TL!SYONT'SIVONSIO=Wuv|“S@TTwZ‘oaaTaga\"SAWswonTcue|goyseana+LHDIN
`
`
`
`
`
`
`YaqIYOSENS|DYD\SAdALGi130Vd)ADVYSSAWGg!yasnGQ!}~-YSGVAH€‘SeTTwpoynoqy4\[uf6oTTZyIWNAG|S$°q6|LLE6STOOgOz9NFS|96ELEDZZ|}—s0vssa4s}§{(epse|soso|
`
`
`
`
`LHDITSurnLZo(€2\4\{uleottzyrwnna]|soqe6|LceeStoosoz90brs|96ELEDZZ||Ur‘
`
`
`
`SSAILVWNYADVLIWITAWITNOILYNILS3dLxX34AdAL
`
`oJUOLHDIYUzANnLT'0(22\a\/uleotreyrIwNnd|soqe|zzeestoosozgors|96ezeorz||Zb-
`
`6oTTZHIWNna|soq6|zee6Stoosoz90FS|96ELEDIT]
`|lfbre
`ON|AdALQ1slaAdALAo
`SOT‘LSGoomMyDO¥osst||[6011zalwNnG|[soa6|Lee6sroosoza0rs|aossraze|tara|tet|JIOHM)(((6alyasnaq!
`
`
`
`
`ONILAOYNoliyvitsadNOLLVYNILSSG=NIDIYO
`
`
`
`
`
`
`
`HyagiwosansJY(LXgLNIDIYOqd!32vssawdWVWLSAWILN31OSW
`
`
`
`
`|A=SWav|W|o|Ssaudav|SSTSONWYSOT‘LSalvugwaoegz|ssaudav|sa1g9Nv_AdmMovVd
`
`
`22VSSAWdWvilSSaWILN3aTOSW
`‘06Tb’
`
`|pe'€6!06-‘2p-'0b-'T6-'86
`
`té6-!tP
`
`|A=AUOW|66
`
`Ja\°seqnutw~
`
`Google Ex. 1004, p. 8
`
`Google Ex. 1004, p. 8
`
`

`

`Sep. 15, 1998
`
`U.S. Patent
`
`
`
`|A=SWuy|LXAN=ugAnaNwW|||||||||6OTTZYIWNAG|vous|LLEGSTOOHOZ90bS|TIesPaze|6eaz|eco|}~LAIVdJIOHM
`
`
`
`
`
`opOxf
`
`£!(org
`
`~~
`
`
`
`
`
`ges6é|sebo|}~-YAGVSH1aMdvd
`
`
`
`O8@3BuoTJeUuTASepANOAOF|dueISTPRACUSesaTIGa\'LSAIWHEWE}>~FDVSSAWfel
`
`
`oqUuOLHDIYUAnNLpo(¢2\4\|uleoTTzurwnna|eoq6|iLe6stoosoz90rs|q6EeLeozz|
`
`
`
`
`
`
`
`
`
`
`
`[99-‘bL-!9%-'96/66'T/GIVYEWE/CTIVUAWA=Wuv|2\'LSATWuaWa
`
`
`
`IaSp66T-€66TJYHtzAdODaynoyug/IgS‘O°€°SSLOOTTeSMuoTSteA|seqeyeq)1\*dz09
`
`
`
`
`
`
`
`
`
`
`toxnoAyueyLA\[a]6OTTZHIWNaG|e9q6|LLE6STOOMOZ90bS|q6ELEOTZ|SatTboTouyoaL,uotAeHTAeNF6-ZE6TAYUHTAAdoDsseqeyjegsz\a\jijaynoyuy/TaSFTIVSSANON©Butsn
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`|N=ayOW|2z\(7°TUOTSIBAaTeMQzJOSsqr/ABoTouyoay,uotqewazojul
`
`5,808,566
`
`
`
`-|40]a]aoa]6s8p6|NOISIAIasalI|pL6Epssez|TIL9|6¢E00|alOxf
`
`ow
`
`Sheet 7 of 15
`
`
`
`N=Lsuna|oooo0000=norssas|||]|||||agoa|ésa6|Norsrarasal|0960Da08|aswo|szo|
`
`-|pZOT=LNaXWWCo(org
`
`Google Ex. 1004, p. 9
`
`Google Ex. 1004, p. 9
`
`

`

`U.S. Patent
`
`
`
`
`
`
`
`
`
`+[540°WI=DI4Nod|||}||||aaoa]aeaé|Norsrarasaz|z9600a08|ao008|sso|
`
`
`
`‘AWMZOCIYLINITAS0g6|||aaoa]s6aé|NOISIAIdSdI|ga960Da08|sdb]6TT|
`
`
`
`
`
`
`
`-|A=SWuy|W]o|SSauddv|SZONVYO‘OLNEWWuOWSN€p0z|ssauddw|WISHWNW
`
`
`
`-|¥o|a|aadog|aspé6|NOISTAIAaSaI|9L6PSFET|SBPE|6E00|
`
`
`
`
`
`settT’°634noqya\|u|aaod|s6pé6|NOISTATaSaI|ze86pszez|90qz|¢eszo|
`
`Sep. 15, 1998
`
`
`
`
`
`GLIHMqO3UO[aqIun,0°0(z2Z\z\{ul|adod|sepe|NOISIAIASAI|L86pS3ez|-|96-'pe'T9-'6L-'66'TIMIA
`
`ALIHM‘AOCIY
`
`
`
`
`
`LNITA=Wey|“eoueqsTpaTOUSeBeaTIgI\‘AWMSADSGINLNITAS$uOAsomyzI0N
`
`
`
`Sutobh3jno34zeIs0'0(tT2\2\|ulagoa|seps|NoISTATAsal|L86pszez|-|2\'saqnutw0z
`
`Sheet 8 of 15
`
`
`
`
`
`
`
`'66’T!MIdALIHM‘SOdIYLNITd=wav|‘“seTtwT°oeaTidI\‘NTUla
`
`
`
`
`
`
`
`ANOTS$OQUOJHOTYurNLT°0(€a2\2z\|ulagoag]eg6pe|NOISIAIGSAI|Le86pszez|-|96-'b7'T9-'6L
`
`5,808,566
`
`
`
`L|A=SWaW|LXSN=uaAnganun|||||||||aaod|a6a6|NOTSTAIaSaI|Sz60D5a08|9aT9|z90]
`
`
`
`-|A=HNOW|76-‘BE'SE-'€6-/66'T*LASUBWOS‘ANId
`
`
`
`
`
`qO4UOLAATuzanLZ'0(p2\2z\|ulagoa]gepe|NOISTAICSAI|Le6pszez|
`
`
`
`-|¢2-'29'66‘T!ANIA
`
`
`
`ANOT=Wuy|‘“eoueqstp4zouseeATACa\‘NILaSYaWOS
`
`
`
`
`
`
`
`ANOTUIAALIHM=Wev|“SeTTZT'O0eAtada\‘NTSNId
`
`
`
`
`
`Lyx6
`
`eyO26
`
`BCE
`
`Google Ex. 1004, p. 10
`
`Google Ex. 1004, p. 10
`
`

`

`Sheet 9 of 15
`
`
`
`
`
`MIGMSO3UOLAATuzan,9°0(92\2\|ua|adoa|sepe|NOISTATaSaT|esépszez|
`
`
`
`
`
`-|66-'CT-!%2'L6-‘/8t-'86'66'T/ONWUNRS!LHSUAWOS=NUV|"saTTW€°0eATICI\“SAWONWaYeSoOjuOC
`
`
`
`
`
`
`
`MISM/ONVUNES=Wav|“SseTtTwg°o0aatada\‘ddNOANWO
`
`
`
`-¥YOey}OQUOLHOIYwuzanLPt(L2\2\|u|agoa|Jere|NOISIAIASATI|e86Pszeaz|-|1T@-'46/96-'92-/0'66-'66'T!NOANWO
`
`
`
`
`
`
`
`
`
`
`
`
`
`T6-VYO‘WONITWHYOA=WaW|‘“SeTTw€°SeATada\‘dWWuLSaMTé6
`
`Sep. 15, 1998
`
`
`
`HLONOSAMHSS-WOeuexXeLL°9(g2\2\|ulagoa|yJ6p6|NOISIAIaSaI|esépszez|-|66-‘c'ss-'e8!66'T!LSaM
`
`
`
`
`
`-'0'66'T‘HLNOSSS-WO'SQISUSAIN=Wav|“SeTT™4°OeatadZ\ ‘31Txe
`
`
`
`
`
`-|A=SWuw|LXAN=usananww]|||||||||aaoa|ewas|NoISIAIGSaI|sz600a08|]azza|Z90]
`
`
`
`-|A=HYOW|66-‘L500T
`
`
`
`THON843SHCLPL(62\2\|ua}|adoa|zepe|NOISIAIAaSdI|ps6pssez|6op9|zs90|
`
`
`
`
`
`WLSOD=Wav|‘“SseTtTwz°0eaTagZ\°4tX®JAWNIOONIT/GYHONWY
`
`U.S. Patent
`
`
`
`
`
`
`
`
`
`LHDIYuzanL72°O(¢2\2\|ulagoa|sepe|NOISIAIasal|esepssez|o677]7990]
`
`NILSOL‘WSN
`
`
`
`
`
`
`
`
`
`NILSALN©OUOLASTuzanL9°24(OT2\2\|u|aaoa|zepe|NOISTAIASAI|PEé6éPSzez|-|L6-‘T@-'66-'2-!66’'TILS
`
`5,808,566
`
`
`
`
`
`SLVEZN3O4UOLagatuzanL3°8(TT2\2\|a|agoa|zeps|NOISTAIASAI|psépszeaz|-|ST’s6/9
`
`
`
`-'66-/66'T/NILSOL‘LSNILSOL=Wav|“SeTTmo'TeatagI\cs
`
`
`
`
`
`-'p-'¢'66-'66'T/SLVEW/NILSOL=Wuv|‘Settmp70eaTtagI\‘SAW
`
`
`
`
`
`
`
`LHDIYuznL6°8(ZT2\2\|u|agoa|zeps|NOISIAIASAI|P8éPSFeET|u|Tt-SDCIUNANOWUE‘SLVEW=WUW|"s0ueqSTpJrOYUSeeATIGI\‘LSADSCIUNaNDgyENOQUO
`
`
`|A=HYOW|O0OT-'0'€'66/66‘T!
`
`
`
`‘66/66
`
`Google Ex. 1004, p. 11
`
`Google Ex. 1004, p. 11
`
`

`

`U.S. Patent
`
`
`
`-|A=SWaw|LXAN=usaAngNwW|||||||||aaoa|swae|Norstarasar|azseoodaos|s6est]z90|
`
`Sep. 15, 1998
`
`uoTReUTASEepANOAOfSoOUeASTPJ4AOUSeSATIGA\‘LSOLNSWWuOvVSsNO9UO
`
`
`L4R1TuanL0°6(#141\2\|ul|agoa|sepe|NoIsratasal|o6é6pszez|
`
`
`
`
`
`
`
`-|0'66-!66’T!OLNENWYOVS‘CHOALLNSYE=WaW|I\'LSOLNEKWYOWSN€POz3e
`
`
`
`
`
`LHOIWYUANL0°6(€T2\2\|ulagod|sepe|NoIsTAIasal|o66pssez|aqgse9|orgo]
`
`CNOALNAUG/SOCIUNANORAE=WaL|‘seTTWwT°OeatigI\“SAWGYOdLNTYAFZojuo
`-|66-'b-!b-'66/66'T!
`
`
`
`
`
`Sutsnz0ynodyueuy41\|ul|dagoa|sepée|NorsIaArasar|]o6epsseaz|
`
`
`
`
`
`
`
`
`
`SatboTouydsayuot3ebtaen76-Z66TWYHTAAdODaeseqejeqr\z\jeqnoyug/IgsS
`
`
`
`
`
`
`
`
`
`
`
`
`
`P66T-€66LJUHTAAdODaeyjnoyu_/IgS‘0°€°%POTOOSTuoTSTeAeseqeqeq)a\'d1z0p
`
`Sheet 10 of 15
`
`
`
`
`
`
`
`-|N=SYOW|2\(8b°SUOTSTeAeTePMQITJOSSsqI/AboTouyos]vuoTtyewzrOJuLIS
`
`
`
`
`
`5,808,566
`
`|A=SWaW|W|O|SSTUdGW|NYwdVNENd‘HdNOHLAONWHOoesLissaudav|saigonyLCOrg
`
`SOT‘CaSNEHNOoszt|||agoa|90d6|NOISIAIdSaI|D6600a08|zzez|T2T|
`
`
`
`
`
`
`
`Ps
`
`Google Ex. 1004, p. 12
`
`Google Ex. 1004, p. 12
`
`

`

`U.S. Patent
`
`
`
`qzoyusesATigdZ\‘HAWNITYNWYAspzemoqquSNEENOUOAseMyAION
`
`
`
`HutoByno3azeASs0'0(T2\2\|u|agoa|9°p6|NoITSIAIasalI|sq6pszec|
`
`-{2\"seanutwTS‘’SoTtTw
`
`
`
`
`
`
`
`Z°O€Jnoqy1\|a|agoa|9°p6|NoISIAIasai|sqspssez|zsez|9pL0|
`
`
`
`
`
`
`
`‘soueqsTpoqUOLHDIYLHDSIISuznLtT’o(Z2\2\|ulagoa|9°pe6|NoISIaArasar|sqepsseaz|-|92'79-/66‘T/SNEENO‘SNaaNO=Wuv|
`
`Sep. 15, 1998
`
`
`
`-'b!66'T‘SNSENO/NITMNWVUS=Wav|“seTtws°oaaTtaga\‘daSNEENO
`
`
`
`
`
`
`
`LASNASM©3U0LaeTtuzanLs°0(€2\1\|ulagog|9°op6|NorsIatasal|sqepszez|-|oc-'S6!66
`
`
`
`
`
`~'66/S’'66-‘66‘T!LESNOS/SNASNO=Wuv|“seTTws°¢eataga\"daAlg
`
`
`
`
`
`-SQ8yqoqUOJHOIMuANLTF(pv2\2\{uladoa|90pe6|NoISTAzrasal|sqepsyzez|-|9
`
`Sheet 11 of 15
`
`
`
`.|A=HNOW|66-‘2-/LE-'7%6'66'T!/HINOS
`
`
`
`
`
`
`
`TOT-SN‘LESNNS=Waw|‘“seTtws°Pzeatada\‘dWWaHLNOSTOT
`
`5,808,566
`
`
`
`
`
`
`
`-|A=SWay|LXEN=uzAnENwW]|}|1||||aaoa|oaae|Norstarasar|9ve0oaos|D6aa|Z90|
`
`Levbr
`
`Pe
`
`Google Ex. 1004, p. 13
`
`
`
`Google Ex. 1004, p. 13
`
`

`

`Sep. 15, 1998
`
`U.S. Patent
`
`
`
`LLONYey.eyeL9°82(§2\2\]u|agod|oppé|NOISIAIasar|qqepszez|tzqp|zoso}
`
`
`
`
`
`WISHLYV‘VNVYWINVS=Wav|‘SseTTwT°oeatigI\°31xX®AW
`
`
`
`
`
`
`
`‘HAWLLONMOju0ebrzew4°92(94\2\|x|adod|oppe|NOISIAIasal|qqépszez|-|66-‘eT!e9-'24'66'Taalg
`
`
`
`
`
`
`
`-/96-'6T!66'T!LLONY‘GATGWISALYW=Wev|“SeTTWo'Teatag2\
`
`
`
`
`
`
`
`
`
`OqUOLAATUNLL462(£14\2\|u|aaoag|opps|NOISIAIasaI|aqéepssez|“|22'L6‘T2-'L6-*26'E2
`
`
`
`
`
`qeuotjeuTAsepanoAofSaTtug‘oOaaTtig1\“SAVYAdNYOHLEADNYVYO
`
`
`5utsnz0jynodyueyy2\|u|ado]opps|NoIstarasar
`
`
`
`
`
`
`
`
`
`
`
`|qqepszez|u|T-'66/66-'b-'€'66-'66'T!|2\"SAVAdYOHLADNWYOFdYOHLAONWUO!LLONM=WuvO€SL
`
`
`
`SeTHoOTOUYyoSaLUOTREHTARNPE-Z66TJYHTAAdODseseqejeqrz\1z\je3noyug_/1gsS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PE6T-€66TBYBTAAdODSrAnoyU_/IES‘0°€°2POTOOSTuoTsaaaaseqejeq)1\"dz09
`
`
`
`
`
`
`
`
`
`
`
`-|N=SYOW|4\(8%°SUOTSZBA|atTeMAZOSSaI/AboTouyseluotjewrzojulrays
`
`Sheet 12 of 15
`
`
`
`‘SAWWITSLWNM§Set|||aqaog|sog6|NOISIAIGSaI|Aiaq6o00ao8|teas|oT]
`
`
`
`-|SIOd=AUENO|W]OOT|LNWUNW.LSaH|AddWH|SSsauaaw|ZONWwAO
`
`5,808,566
`
`
`
`
`
`
`
`-=?:90000:puNnoyZSsIOdJoon|5|agog|g0e6|NOISIAIaSAI|y¥6PSFez|PPOE|S800|
`
`-|N=HuOW]¢*:->
`
`‘a
`
`Google Ex. 1004, p. 14
`
`Google Ex. 1004, p. 14
`
`

`

`U.S. Patent
`
`
`
`
`
`-:?!Z70000:punozstodjoon|O|agoa|0ze6|NOISIAIASaI|Ooepssez|eEezs|69zo0|
`
`L|SIOd=ANHNO|W|OOT|LNVAAWLSSY|ANONOH|SSauady|JONWAO
`
`
`
`
`
`
`
`‘SAWWIISLWNmMsceT]||agoa|oza6|NOISIATASAI|94600d08|PD6a|SOT|
`
`
`
`
`
`
`
`iiYWNaNd‘CAT@UALSHHONYWTE79'LNWUNWLSHYGOOAVHSUHDILAYONNH!¢::--
`
`
`
`
`
`
`
`
`
`Sheet 13 of 15
`
`Sep. 15, 1998
`
`
`
`
`
`MYOMUWHN6127:LNVUNWLSHYYVIGAMONOH‘N:9P99b-?T‘D'LET-€77-0-0*909€7?9E:WaWd
`
`
`
`
`
`
`
`L|N=SMOW|N:O0LS8E:7'P’BOT-6SP-0-0:PEOPT*9E*NOLYATING‘CATA
`
`
`
`‘SAWWITSLWHmM$S8T|||aaoa|texe|NOISIAIasaI|zowodao08|srea|sot|
`
`
`
`
`
`
`
`
`
`
`
`-++!9T000!punozZsTOdJoOn|O|aadoa|TEe6|NOISIAICSAI|PpTepszez|9soT|7OL0|
`
`
`
`
`
`-O€T-O-O'68SET:9E'WHUd'CATAWHUGSLOL:SURDUNALSHASivweuq!::44--
`
`
`
`
`
`
`
`|STOd=AuNaNo|W]OOT|LNVUNVLSY|waounad|SSauaaw|JONWAO
`
`
`
`
`
`
`
`-S6€-O0-O'6ZLETI9E'WSEWWLSOD‘YdLSVOOS6S6:ONINWHOUNG‘N:809B8E!T'b’O6T
`
`
`
`NOLONILNOH‘LSLSUMHNYOOUTTOZ6T:ONINUAOUNA‘N:SETEPIT’HZ
`
`
`
`
`
`
`
`
`
`
`
`
`
`W1’AMHIVINHdWIM9ETT:ONINYAOUNG/N:PHPTS:7‘PET-6LL-O0-O°LETH?9E:HOWNE
`
`
`
`
`
`
`
`
`
`‘CAT@WHAWHWI@T@p:ugoundCcGNYO/N!7S06b'2‘H'S9T-ESP-0-0:9007:9E:VHAWH
`
`
`
`
`
`
`
`WHGWHWIMTO9'SUSDUNASi:FUOUD‘/N:ZTSOS:T'P’6ET-6Z-0-0:BOPPT?SEWHEWHWT
`
`
`
`
`
`@lpZ:SUBOUNdTWIUAMWI‘N:ZTIZS'T’b‘O8T-806-0-0:62PP2:9E:WYEWHWI‘CATa
`
`5,808,566
`
`
`
`o¢9:usOUNGSANYL‘/N'Z0S9¥'~''897-6T6-0-0:SEPPT:9E'VHAWHWI‘AMHIVIUNSdWI
`
`
`
`
`
`
`
`
`
`
`
`
`
`-|A=SMOW|N:ZTTZS?2'F‘O08T-806-0-0:P8PHT'OEWHAWHWI‘GATWHEvHWIM
`
`Google Ex. 1004, p. 15
`
`Google Ex. 1004, p. 15
`
`

`

`5,808,566
`
`
`
`‘CATAUFLSNIWLSAM7679:aanLOO-N-NI‘N!PTTOD:2‘P'STE
`
`L|N=SUuOW|N:OPT6:7'b'9TZ-LETT-0-0*98TLZ*9E*AALSNIWLSAM
`
`
`
`
`
`
`
`
`
`
`
`LEPETIONIYNHOUNA/N:O€8SE:T’P'LOZ-L6L-0-0°ECFS9T*QENYWINWS
`
`
`
`
`
`
`
`
`
`S,adOd!N:POESTITP’69-TL8-0-07$9897?9EPNILSOL‘AAVLYOdMAN
`
`
`
`
`
`-~66T-O0-O:LLILZ:9€:USLSNIWLSEM‘CATAHOWHATeset:dawns
`
`
`
`
`
`
`
`
`
`9Z6L:NSOUNALAO-N-NI|O|agoa|vee6|NOISIAIASAI|FJTepssez|eces|ergo]
`
`
`
`
`
`Sep. 15, 1998
`
`U.S. Patent
`
`
`
`L|LXEN=uaangnyw|}]||||||agoa|rex6|NOTSIAIGSGI|dowoDd08|tosw|ss0|
`
`LeCE
`
`
`
`
`
`T2097‘9E*HONWAO‘LSSNULIONSbZ:ONINOL7-656-O0-O:PIE9T:SE‘VILNEOWId‘FAYNWWdWHOMS78:usDuNndLNOby-N-NI/N:681T9:T'b'PZT-678-0-O0:
`MHOUNG!/N:Z6SO0S:Z2'P'EPC-OTZT-0-O'PISS*9E*WWIVdWI‘LSMHIAAGTIVAPw
`
`
`
`
`
`
`
`‘duYdAd4TO9*DONINYUADUNG!N:STPIE:TP’TTT-96€-0-0°CPS9T*IE?UNV
`
`
`
`WLNWS‘LSIOLSIUGSOS8Z*ONINYROUNA'N:O6SPT:T'D'LET
`
`
`
`Sheet 14 of 15
`
`
`
`
`
`
`
`
`
`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 mobi