US005808566A
`5,808,566
`(114) Patent Number:
`United States Patent 55
`Behretal.
`[45] Date of Patent:
`Sep. 15, 1998
`
`
`[54] ELECTRONIC NAVIGATION SYSTEM AND
`METHOD
`Inventors: David A. Behr, Roselle; Ramesh
`Ramakrishnan, MountProspect, both
`of
`Til.
`
`[75]
`
`FOREIGN PATENT DOCUMENTS
`0 379 198 A3
`7/1990 European Pat. Off.
`.
`wo oniaots
`1009 eer
`WO 92/21001
`11/1992 WIPO.
`
`OTHER PUBLICATIONS
`
`[73] Assignee: NavigationTechnologies Corporation,
`oo
`
`[21] Appl. No.: 494,198
`:
`22]
`Filed:
`. 23, 1995
`[22]
`File
`Jun.
`23,
`Related U.S. Application Data
`
`Hoffman, Steve and Stewart, Charles, “Text-based Routing:
`An Affordable Way Ahead?”, Proceedings of the IEEE-IEE
`Vehicle
`Navigation
`& Inf
`ion
`S
`Conf
`ehicle
`Navigation
`niormation
`System
`Conterence,
`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
`[63] Continuation-in-part of Ser. No. 265,094, Jun. 24, 1994,Pat.
`Weiland, Richard J., IEEE Spectrum, Apr. 1994, pp. 27-33.
`No. 5,543,789.
`;
`;
`,
`Primary Examiner—Brent A. Swarthout
`Tint, C1.e cece ccecsceceseseeeseneeesesesesees G08G 1/123
`Attorney, Agent, or Firm—Brinks Hofer Gilson & Lione
`[51]
`[52] U.S. Ch. eeeeeeeceees 340/995; 340/988; Lon [57]
`ABSTRACT
`[58] Field of Search occ 340/988, 990,
`The invention provides a method and system for providing
`340/995, 991; 364/444, 449; 701/200, 208,
`route guidance and other information from a base unit to a
`209, 211
`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
`query is formatted at the base unit, the response including
`4,301,506 L1/1981 TUrco ooeeeeeeeceeeeeeecneeee 364/436
`
`: aa route guidance information. The responseis then transmitted
`teow i)fond ae oa
`”
`oes
`eT EE ao
`from the base unit
`to the remote unit for display. The
`
`tevees toes panayama ov
`™ Sena
`transmission is made in a compact form through the use of
`
`364i444
`4,546,439
`10/1985 Esparza _
`maneuver arms and combined maneuver arms and through
`4,570,227
`2/1986 Tachiet al.
`.
`.. 364/444
`the use of tokenized forms. A maneuver arm represents a
`
`4,642,775
`2/1987 Cline et al. ccc.
`.. 364/443
`road at an intersection, for depiction on a display, by one or
`4,733,356
`3/1988 Haeussermannet al
`.. 364/424
`two endpoint coordinates. The tokenized forms are
`4,758,959
`7/1988 Thooneetal. .........
`.. 364/454
`expanded at the remote unit into textual driving instructions
`4,780,717 10/1988 Takanabeet al.
`.....
`340/995
`for each of one or more languages.In addition, the amount
`
`4,812,843
`3/1989 Champion,III et al.
`340/905
`of information available at a remote unit can be increased by
`ne oy1000 qumtharaetal. ”
`seit
`providing the remote unit with information from the base
`5.043902
`81991 Yokoyamaet al
`340/988
`unit which is not adequately covered by any databases
`5,172,321
`12/1992 Ghaem et al. esnsnsnsnnenene 364/444
`on-board the remote unit.
`
`[56]
`
`References Cited
`
`US. PATENT DOCUMENTS
`
`(List continued on next page.)
`
`11 Claims, 15 Drawing Sheets
`
`
`
`Jactthes|
`("sea ~9
`
`
`[VENDOR(S)|
`[PROVIDER
`- —2-f.5 Tr Ppe Ts ca % ON-LINE
`
`|
`MAP
`THIRD PARTY
`!
`THE
`aT.
`
`‘a
`INFORMATION
`[TRAFFIC AND bot DATABASE Lem
`|
`
`[MAP _LPDATER
`
`Ii
`
`
`
`
`
`INTEGRATOR
`[||
`PROVIDERS
`1.
`II
`YO —
`SURROUNDINGS
`I|
`CALCULATOR
`G
`
` -XPLORERS RAVELeae |
`||\
`
`
`
`
`|||I|
`g
`||
`
`
`plestlton
`Ce
`|
`UERY
`RESOLVER
`fer?
`Lea,
`cot
`|
`Qt
`r
`oe
`|
`
`
`II
`
`1
`>
`ExT.
`CONTROL
`
`YERF
`KBD] DISP
`
`‘1/0 INTERFACE ]
`TELEPHONE|
`Ni
`
`
`1/F
`1/e|I/F
`
`
`
`oie
`CELLULAR
`
`
`28
`SYSTEM
`C38
`240
`
`(7?
`B25
`LAPTOP
` MEM
`Pc [mp] MooEM ‘
`26)
`PC
`
`om| KBD |
`
`DISPLAY
`
`
`a
`
`
`
`
`
`
`wo?
`
`ed 28
`
`46?
`
`0
`
`FORDEX.1012, p. 1
`
`FORD EX. 1012, p. 1
`
`

`

`5,808,566
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,243,528
`5,262,775
`5,283,575
`
`9/1993 Lefebvre ..eeeecsssescssseeessseessseeee 340/995
`.
`11/1993) Tamaiet al. sesseereeen 340/995
`2/1994 Kao et al. eceeeecsscseeeeeeneeee 340/990
`
`5,291,412
`5,291,413
`5,293,163
`5,293,484
`5,306,429
`5,559,707
`
`3/1994 Tamaiet al. viessscsesssssessseens 364/449
`3/1994 Tamaietal. ....
`ws. 364/449
`..
`3/1994 Kakihara et al.
`w. 340/988
`3/1994 Dabbs,III etal.
`340/825.44
`3/1995 Hanchett wccesesesssssssssseseeeeeee 364/436
`9/1996 DeLormeet al. one 340/995
`
`
`
`FORDEX. 1012, p. 2
`
`FORD EX. 1012, p. 2
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 1 of 15
`
`5,808,566
`
`MAP
`DATABASE
`VENDOR (S)
`
`TRAFFIC
`INFO,
`
`PROVIDER 82
`DATA BASE PROVIDERS
`
`Bo |
`72
`72U
`
`
`
`ON-LINE
`THIRD PARTY
`
`TRAFFIC AND
`
`
`DATA
`
`
`
`MAP UPDATER
`INTEGRATOR
`
`
`
`OTHER
`INFORMATION
`
` DISTANCE
`
`
`
`
`AND TIME
`TRAVEL
`ESTIMATOR
`
`SURROUNDINGS
`
`EXPLORERS
`
`
`SYSTEM JO
`
`8-4
`
`CELLULAR
`
`
`
`
`1G
`
`FORDEX.1012, p. 3
`
`FORD EX. 1012, p. 3
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 2 of 15
`
`5,808,566
`
`
`
`TRANSMIT
`ERROR
`
` UNRESOLVED
`QUERY
`°
`
`
`IDENTIFY QUERY TYPE
`
`
` 110
`
`MESSAGE
`
`
`
`
`
`
` UNIDENTIFIED
`QUERY
`
`°
`
`NO
`
`QUERY FULFILLMENT
`
`S 114
`
`FORMAT RESPONSE
`
`TRANSMIT RESPONSE
`
`116
`
`116
`
`aa2
`END
`FLY).
`
`FORDEX.1012, p. 4
`
`FORD EX. 1012, p. 4
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`PL/SI?IL2besaaanCHefCL
`
`
`PEL21GOl-Pol
`
`KcolOC!
`
`Sheet 3 of 15
`
`5,808,566
`
`FORDEX. 1012, p. 5
`
`FORD EX. 1012, p. 5
`
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 4 of 15
`
`5,808,566
`
`GLENDALE
`
`ROCKWOOD
`
`START OUT GOING EAST ON
`ROCKWOOD ST TOWARDS
`GLENDALE BLVD.
`DRIVE O.1 MILES
`
`GLENDALE
`
`TURN RIGHT ONTO GLENDALE BLVD
`DRIVE O.1 MILES
`
`GLENDALE
`
`ROCKWOOD
`
`TURN SLIGHT RIGHT ONTO
`LUCAS AVE
`DRIVE O.2 MILES
`
`FORDEX.1012, p. 6
`
`FORD EX. 1012, p. 6
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 5 of 15
`
`5,808,566
`
`EMERALD
`
`TURN RIGHT ONTO EMERALD ST.
`DRIVE A SHORT DISTANCE TO
`YOUR DESTINATION AT 280
`EMERALD ST.
`
`TURN LEFT ONTO EMERALD DR
`DRIVE
`0.1 MILES.
`
`EMERALD
`
`EMERALD
`
`FORDEX.1012, p. 7
`
`FORD EX. 1012, p. 7
`
`

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 6 of 15
`
`5,808,566
`
`A
`
`clbrig
`
`-'06/66'T!AIVGNATID!dOOMNDON=WuY,|“SatTtw1°OeaTtagI\“datasrvanato|30¥SS3au’
`
`
`
`
`
`-'L-!LT'86-66'TiaIvusWa‘SvoOnT=wuw|‘“seTtw1°0eatagZ\“udaTwuaWa}—F9OYSSAWmS
`
`
`0°90(IT2\4\]u]6oTtzyIWNna]soq6{eLeestoowoz90PS|96ELEDSZ|T6-!66'T/ATYAONATO‘COOMNDOU=WUY|‘“SaTtwT°Qsataqda\‘dATdAIVGNAIDspzemco7LSGOOMHDOYuo|~govssanON©asegBuroByno3zeqg
`
`
`
`-'LT!66‘TL!SYONT'SIVONSIO=Wuv|“S@TTwZ‘oaaTaga\‘dawswontcue|goyseanmat
`
`
`
`
`
`
`
`130Vd)AOvVssawgd!yasndlYsglyosEnsou5AdALGI}~-YSGVAH€‘SeTTwpoynoqy4\[uf6oTTZyIWNAG|S$°q6|LLE6STOOgOz9NFS|96ELEDZZ|}—s0vssa4s}§§(epse|soso|
`
`
`
`
`
`
`
`LHDINLHDITSurnLZo(€2\4\{uleottzyrwnna]|soqe6|LceeStoosoz90brs|96ELEDZZ||Th‘
`
`
`
`
`SSAILVWNYADVLIWITAIWITNOILYNILS3AdLxX34AdAL
`oJUOLHDIYUzANnLT'0(22\a\/uleotreyrIwNnd|soqe|zzeestoosozgors|96ezeorz||Zb-
`
`
`
`OjUOL3IaTurn,Po(bA\A\{a]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|SSTSONWYoegz|ssaudav|_AdmMovVdSOT‘LSalvugwasa1g9Nv
`
`
`
`
`JOVSSAWdWVLSAWILNATSSW
`‘06Tb’
`
`Ja\°seqnutw~
`
`|pe'€6!06-‘2p-'0b-'T6-'86
`
`T6-!tp
`
`|A=AUOW|66
`
`FORDEX.1012, p. 8
`
`FORD EX. 1012, p. 8
`
`

`

`Sep. 15, 1998
`
`U.S. Patent
`
`
`
`
`
`|A=sway|IxEN=uaananww||||||{||6ottzatwna|was|eeestoogoz90rs|ttesbace|6eaz|€L0|}~LAOVdJIOHM
`
`BYCrp
`
`£!(org
`
`~~
`
`
`
`
`
`ges6é|sebo|}~-YAGVSH1aMdvd
`
`
`
`
`
`ButsntoxnoAyueyLA\[a]6OTTZHIWNaG|e9q6|LLE6STOOMOZ90bS|q6ELEOTZ|
`
`
`
`O8@3BuoTJeUuTASepANOAOF|dueISTPRACUSesaTIGa\'LSAIWHEWE}>~FDVSSAWfel
`
`
`
`
`OqUOLHDIYun,po(¢2\4\|uleoTTzurwnna|eoq6|iLe6stoosoz90rs|q6EeLeozz|
`
`
`
`
`
`[99-‘bL-!9%-'96/66'T/GIVYEWE/CTIVUAWA=Wuv|2\'LSATWuaWa
`
`IdSp66T-€66TJYStzaAdoDajnoyug/Igs‘0°€°S9LOOTTESMUuoTSIaAaseqejed)1\'di0p-ADVSSINox
`
`
`
`
`
`
`
`
`
`
`
`SeTBoTouyoaLuotAebTaeNb6-7661AYSTIAdODsseqeqeqsz\1\;aqnoyuy/IgsSon
`
`
`
`
`
`|N=SYOW|I\azemqjossar/ABoTouyoayuotyewAoJU](ZTuoTsraa
`
`
`
`
`
`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
`
`FORDEX. 1012, p. 9
`
`FORD EX. 1012, 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
`
`
`
`
`
`
`
`
`
`
`
`'66’/TiadldBLIBM‘GOGINLNITd=Wav|“seTtwT°osaTzga\‘NTIUla
`
`
`
`
`
`
`
`ANOTS$OQUOJHOTYurNLT°0(€a2\2z\|ulagoag]eg6pe|NOISIAIGSAI|Le86pszez|-|96-'PZ!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
`
`
`
`
`
`Sheet 8 of 15
`
`
`
`LNITA=Wey|"eoueISTpPAAOUSeBsATIGI\‘°RYMADSCIYINIT$uo4semMyqI0N
`
`
`
`
`
`ButohAno4zeASs=«0'”0(tT2\2a\|ulaqoa]sepe|NoIsTArasdl|Le6psszeaz|-|2\'saqnutw0z
`
`Lyx6
`
`eyO26
`
`BCE
`
`FORD EX.1012, p. 10
`
`FORD EX. 1012, 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
`
`FORD EX.1012, p. 11
`
`FORD EX. 1012, p. 11
`
`

`

`Sheet 10 of 15
`
`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!
`
`
`
`
`
`
`
`Butsnz0FnoAyueyL41\|ul|dagoa|sepée|NorsIaArasar|]o6epsseaz|
`
`
`
`
`
`SatboTouydsayuot3ebtaen76-Z66TWYHTAAdODaeseqejeqr\z\jeqnoyug/IgsS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`P66T-€66LJUHTAAdODaeyjnoyu_/IgS‘0°€°%POTOOSTuoTSTeAeseqeqeq)a\'d1z0p
`
`
`
`
`
`-|N=HYOW|2\(8h'°S/AboTouyos]uotyewzoJZuLUCTSisAazTeMATJOSSqrIIgs
`
`
`
`
`
`
`
`5,808,566
`
`“|A=SWaw|W|O|SSHUGaW|WAvdWNENd‘AdNOHLSONWHOO€SL|ssHudav|sataonyLCorp
`
`
`
`
`
`SOT‘CaSNEHNOoszt|||agoa|90d6|NOISIAIdSaI|D6600a08|zzez|T2T|
`
`Ps
`
`FORD EX.1012, p. 12
`
`FORD EX. 1012, 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|
`
`
`
`
`
`
`
`Sep. 15, 1998
`
`
`
`‘soueqsTpoqUOLHDIYLHDSIISuznLtT’o(Z2\2\|ulagoa|9°pe6|NoISIaArasar|sqepsseaz|-|92'79-/66‘T/SNEENO‘SNaaNO=Wuv|
`
`
`
`-'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
`
`
`
`
`
`
`
`-SNeyQO4UOLHOTYUANLT's(p2\2\|uladoa|9°pe6|NoISTarasat|sqepszez|-|9
`
`
`
`
`
`TOT-SN/LESNAS=Waw|“SeTtus'Pzaatagda\‘dWWuHLNOSTOT
`
`
`
`
`
`
`
`Sheet 11 of 15
`
`
`
`.|A=HNOW|66-‘2-/LE-'7%6'66'T!/HINOS
`
`5,808,566
`
`
`
`
`
`
`
`-|A=SWay|LXEN=uzAnENwW]|}|1||||aaoa|oaae|Norstarasar|9ve0oaos|D6aa|Z90|
`
`ax(ers
`
`Pe
`
`FORD EX.1012, p. 13
`
`FORD EX. 1012, 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\"qTxX®FAW
`
`
`
`
`
`
`
`‘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
`
`
`Butsn2oFnoAYyueyL2\|u|ado]opps|NoIstarasar
`
`
`
`
`
`
`
`
`
`|qqepszez|u|T-'66/66-'b-'€'66-'66'T!FdYOHLAONWUO!|2\"SAVAdYOHLADNWYOO€SLLLONM=Wuv
`
`
`
`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=HHOW]+2'4--
`
`FORD EX. 1012, p. 14
`
`FORD EX. 1012, 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|
`
`
`
`
`
`
`
`YWNaNd‘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
`
`FORD EX. 1012, p. 15
`
`FORD EX. 1012, p. 15
`
`

`

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

`

`U.S. Patent
`
`Sep. 15, 1998
`
`Sheet 15 of 15
`
`5,808,566
`
`AN DER KREUZUNG
`HAGA UNA
`[MIT
`BITTE
`VUELTA EN
`U EN. _JEINE KEHRTWENDUNG
`MACHEN.
`
`
`
`CHANGES CAMBIA EL|___UNDERT DEN
`
`NAME TO __W_.|NOMBRE A ____.|NAMEN ZU
`
`TURN LEFT ON |DE VUELTA A LA AUF __ LINKS
`—___ AND DRIVE|IZQUIERDA EN |ABBIEGEN UND
`
`MILES.|__- Y MANEVE MEILEN
`
`MILLAS. WEITERFUHREN.
`
`
`
`REQUEST STRIP-
`
`MAP FOR PARTS
`
`
`NOT ADEQUATELY
`RECEIVE ROUTE
`COVERED.
`
`
`
`INFORMATION FROM
`BASE UNIT.
`
`
`
`RECEIVE STRIP-
`
`MAP INFORMATION
`
`COMPARE RECEIVED
`
`FROM BASE UNIT.
`
`ROUTE WITH
`
`ONBOARD MAP
`
`REQUEST ROUTE
`FROM
`BASE UNIT.
`
`SE
`
`
`1s
`
`
`ANY
`PART NOT
`
`
`ADE QUATELY
`
`COVERED
`
`?
`
`
`Siig. 41
`
`FORD EX. 1012, p. 17
`
`FORD EX. 1012, p. 17
`
`

`

`5,808,566
`
`1
`ELECTRONIC NAVIGATION SYSTEM AND
`METHOD
`
`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 anyoneof the patent documentor 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 methodfor providing
`to a mobile unit route guidance and tracking information and
`other information which has been calculated and/orstored 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
`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 independentand 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-waystreets, 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`database on CD-ROMorother media becomesoutofdate.
`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
`roadwayis 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-ROMorfloppy 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 autonomousroute 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.
`Anothertype of route guidance system has beentested 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 becauseof 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,
`convenienttransportation 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.
`SUMMARYOF 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 inventionis to provide a method and
`system for transmitting route guidance and other informa-
`
`FORD EX.1012, p. 18
`
`FORD EX. 1012, p. 18
`
`

`

`5,808,566
`
`3
`in a language
`to a remote unit
`tion from a base unit
`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.
`
`Anotherobject 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 responseis 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 tokemized 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 secondset 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 commondisplay.
`The tokenized forms are expandedat 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;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`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 armsdisplay;
`FIG. 40 illustrates some examples of tokens and corre-
`sponding expanded English, Spanish, and Germantext; 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 meansat the mobile unit
`for providing an origin and a destination. The system further
`comprises a calculating meansat 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 pointsofinterest
`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 inventionstill 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 meansfor providing at least a route destination
`and an output meansfor providing an indication of the route
`guidance information. The system further comprisesa 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
`
`FORD EX.1012, p. 19
`
`FORD EX. 1012, p. 19
`
`

`

`5,808,566
`
`5
`the origin data being indicative of a route origin. The system
`still further comprises a base unit at the central location. The
`base unit includesa 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
`meansfor 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 meansfor 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-
`fied protocol. The base unit communicates responses to
`queries, the responses also being formatted in a specified
`protocol. The responses may include, for example, textual
`navigational directions and/or maneuver arms showing
`graphical representations of street
`intersections and the
`c