United States Patent [19]
`Behr et al.
`
`US006107944A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,107,944
`*Aug. 22, 2000
`
`[54] ELECTRONIC NAVIGATION SYSTEM AND
`METHOD
`
`[75] Inventors: DavId A. Behr, Roselle; Ramesh
`Ramakrishnan, Mount Prospect, both
`of 111-
`
`[73] Assignee: Navigation Technologies Corporation,
`Rosemont 111'
`
`FOREIGN PATENT DOCUMENTS
`
`0 379 198 A3 7/1990 European Pat. Off. .
`O 585 950 A2 9/1993 European Pat. Off. .
`41 41 597 A1 12/1991 Germany‘
`3150699 6/1991 Japan _
`6266997 9/1994 Japan .
`
`(List Continued on next page.)
`OTHER PUBLICATIONS
`
`[ * ]
`
`Notice:
`
`This patent issued on a continued pros-
`eClltiOIl application ?led under 37 CFR
`15301), and 1S subleet t0 the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`[21] APPT- NO? 09/ 151,255
`[22] Filed:
`Sep. 10, 1998
`
`Related US. Application Data
`
`[63] Continuagion o2 appliiatilen No- 08/494,198, J11I1~ 23% 19915,
`Pat. No. ,808, 66, W ic is a continuation-in-part o app i-
`cation NO. 08/265,094, Jun. 24, 1994, Pat. NO. 5,543,789.
`
`Int. Cl.7 ................................................... .. G08G 1/123
`[51]
`[52] US. Cl. ........................ .. 340/995; 340/988; 701/208;
`701/209; 701/211
`[58] Field of Search ................................... .. 340/995, 990,
`340/991, 988, 905; 701/209, 211, 208,
`210
`
`[56]
`
`References Cited
`
`us PATENT DOCUMENTS
`4 301 506 11/1981 Turco _
`41311876
`1/1982 Endo et al. ........................... .. 340/905
`4,428,057
`1/1984 setliff e] a]_ _
`4,466,125
`8/1984 Kanayama ............................ .. 340/990
`4,481,584 11/1984 Holland .
`4,546,439 10/1985 ESparZa -
`4:570:27 2/1986 Taehieta1~~
`4,642,775
`2/1987 Cline et al. .
`4,733,356
`3/1988 Haeussermann et al. .
`
`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,
`
`(List continued on next page.)
`
`Primary Examiner—Brent A. SWarthout
`Attorney, Agent, or Firm—Frank J. KoZak; LaWrence M.
`Kaplan
`[57]
`
`ABSTRACT
`
`The invention provides a method and system for providing
`route guidance and other information from a base unit to a
`t
`'t '
`t
`t f
`th
`t
`'t A
`remo ‘QT um m response 0 a reques. mm 6 “Dime e [m1 '
`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
`route guidance information. The response is then transmitted
`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. A maneuver arm represents a
`road at an intersection, for depiction on a display, by one or
`tWO endpoint Coordinatee The tokenized forms are
`expanded at the remote unit into textual driving instructions
`for each of one or more languages. 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.
`
`(List continued on next page.)
`
`18 Claims, 15 Drawing Sheets
`
`ELLULAR
`SYSTEM
`
`3;
`
`.22
`
`24
`
`Apple, Exhibit 1040, Page 1
`
`

`

`6,107,944
`Page 2
`
`US. PATENT DOCUMENTS
`
`7/1988 T119999 9491--
`4,758,959
`4,780,717 10/1988 Takanabe et a1. .................... .. 340/995
`4,812,843
`3/1989 Champion, III 91 a1-
`- 340/905
`4,819,174
`4/1989 Furuno et a1. ...... ..
`.. 340/995
`4,951,212
`8/1990 Kurihara e191- ---------------------- -- 340/395
`4,954,958
`9/1990 Savage 9491--
`4,954,959
`9/1990 Moroto et a1. ........................ .. 340/995
`4,974,170 11/1990 Bouve et a1.
`.. 395/357
`5,043,902
`8/1991 Yokoyama er a1-
`-- 340/988
`5,067,081 11/1991 PCISOII ............. ..
`.. 340/995
`5,113,178
`5/1992 Yasuda et a1.
`.. 340/995
`5,126,941
`6/1992 Gurmu et a1.
`.. 340/989
`5,172,321 12/1992 61166111 6161.
`.. 340/995
`5,187,810
`2/1993 Y6116y61116 6161.
`.340/905
`5,214,757
`5/1993 M611116y 6161.
`395/161
`5,243,528
`9/1993 LefebVIe ...... ..
`340/995
`5,262,775 11/1993 T6111616161.
`340/995
`5’283’575
`2/1994 Kao et a1‘
`" 340/990
`5,289,572
`2/1994 Y61166161. ........................... .. 395/155
`5,291,412
`3/1994 Tamar et a1. .
`572917413
`3/1994 Tamai et a1__
`5,293,163
`3/1994 Kakihafa 6161. ..................... .. 340/988
`5,293,484
`3/1994 D6bbs,1116161.
`340/825.44
`5,359,527 10/1994 Takanabe et a1. .................... .. 340/990
`
`3/1995 Hanchett .
`5,396,429
`4/1995 Braegas ................................. .. 340/905
`5,406,490
`4/1995 6616 6161. ............................ .. 340/995
`5,406,493
`6/1995 Nobe et aL _
`574247951
`5,465,088 11/1995 13166g66 ................................. .. 340/905
`5537323 7/1996 Schulte _
`5,543,789
`8/1996 1361116161. ............................ .. 340/995
`5,559,707
`9/1996 D6L611116 6161. .
`340/995
`5579535 11/1996 Orlen et a1_
`340/995
`576147895
`3/1997 Ohomori et a1_
`340/995
`5,699,255 12/1997 Ellis 6161. ............................ .. 340/995
`
`FOREIGN PATENT DOCUMENTS
`
`W0 92/
`14215 8/1992 WIPO
`WO 92/21001 11/1992 W1PO~
`
`OTHER PUBLICATIONS
`PCT—N0ti?cati0n 0f Transmittal of the International
`Search Report, dated NW 2, 1995, in International apph_
`.
`.
`.
`.
`cation N0. PCT/US95/07859, Application Shields Enter
`Pnses> Inc
`“Smart Cars- Smart Highways” Collier, W- Clay and
`Weiland, Richard J. IEEE Spectrum, Apr. 1994, pp. 27—33.
`
`Apple, Exhibit 1040, Page 2
`
`

`

`U.S. Patent
`
`Aug. 22,2000
`
`Sheet 1 0f 15
`
`6,107,944
`
`TRAFFIC
`MAP
`INFO. ~83
`DATABASE
`vENDOR(s) PROVIDER
`c
`82
`_IL-__£T__IL_______ ____ __
`g
`I“ ,
`, f72u
`[-72
`{507
`OTHER
`l'
`oN-LINE
`MAP
`THIRD PARTY :
`‘ TRAFFIC AND ~>-DATABASE 4r DATA
`4>-|NFORMATION
`I MAp UpDA-I'ER
`I
`INTEGRATOR I
`PROVIDERS
`l
`)
`
`M
`J: '
`/
`
`'
`
`Z“ ‘
`
`r
`
`‘('1
`
`64
`QUERY
`" REsOLvER f
`J77
`4
`
`If
`:
`ROUTE
`I
`l CALCULATOR
`I
`I
`|
`I
`'
`I
`62
`i
`2 ‘
`I
`: I/O INTERFACE
`: TELEPHONE NET RF
`I F
`I F I F
`I
`/
`/
`/ “.76
`I 745
`“ 755
`_;l\
`
`I
`I
`(~48
`I
`DIsTANcE
`SURROUNDINGS l
`AND TIME
`EXPLORERS I
`TRAVEL
`(
`J
`I
`___ EsTIMATOR
`70
`I
`I
`I
`I
`64
`r,“
`f
`:
`,<, CONTROL
`KBD 015*’
`865 685
`
`I2
`
`L________
`r54
`
`L___________ ‘(___ _ _ _ _ _ _ w ___ ‘I
`
`25,“,
`
`‘ '
`
`CELLULAR
`SYSTEM
`
`24”’
`22
`32 P ‘I
`g
`PC ,up MODEM
`4
`MEM f2
`
`DISPLAY
`
`K80
`30; 76) 228
`
`f
`
`LAM,
`52
`¢
`W5
`f3
`50
`34
`48
`/
`g
`/
`LAPTOP ,up MODEM J40 RF I/F
`Pc
`MEM 40'” DISPLAY
`Pos I42 I‘
`M
`5¢T *UP
`I
`4 PAGER)
`,205 56
`
`838
`
`DISPLAY
`
`‘MS
`
`f
`
`18>
`
`K80
`
`\ 4
`
`Apple, Exhibit 1040, Page 3
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 2 0f 15
`
`6,107,944
`
`(START I
`
`I
`ESTABLISH COMMUNICATION
`
`N100
`
`FORMAT A QUERY
`I 102,
`I /
`\ 104L
`TRANSM IT QUERY
`
`I
`QUE RY RESOLUTION
`
`W100
`
`110
`g
`TRANSMIT
`ERROR
`MESSAGE
`I
`
`UNRESOLVED
`QUERY
`'9
`
`I05
`
`IDENTIFY QUERY TY PE
`
`Z112,
`
`UNIDENTIFIED
`QUERY
`9
`
`YES
`
`QUERY FULFILLMENT
`I
`FORMAT RESPONSE
`I
`TRANS M IT RESPONSE
`
`JHAL
`
`1
`
`16,
`
`118
`
`Apple, Exhibit 1040, Page 4
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 3 0f 15
`
`6,107,944
`
`mewmaE:2.:HE§504E230
`«YEwSb3V3
`NbwkN4:
`
`
`muMEEEn:afimwimm2;5-2m:02;mo<mwm§DHmmmEUmmzm
`
`“mv.2v.04MNNVS
`
`\N303
`
`
`
`
`
`waxFIm:mo<mmm2m:mum—mommsmgig—um92.1wE—E
`
`
`
`
`
`x
`
` Zfiimo
`%IAX+\AlnXI%gJ
`
`
`
`\W.N303
`
`
`
`Apple, Exhibit 1040, Page 5
`
`Apple, Exhibit 1040, Page 5
`
`
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 4 0f 15
`
`6,107,944
`
`START OUT GOING EAST ON
`ROCKWOOD ST TOWARDS
`GLENDALE BLVD.
`DRIVE 0.1 MILES
`
`GLENDALE
`
`ROCKWOOD
`
`6
`
`TURN RIGHT ONTO GLENDALE BLVD.
`DRIVE 0.1 MILES
`
`GLENDALE
`
`F’ <5
`
`TURN SLIGHT RIGHT ONTO
`LUCAS AVE
`DRIVE 0.2. MILES
`
`ROCKWOOD
`
`J/g/7
`
`LUCAS
`
`GLENDALE
`
`Apple, Exhibit 1040, Page 6
`
`

`

`U.S. Patent
`
`Aug. 22,2000
`
`Sheet 5 0f 15
`
`6,107,944
`
`TURN LEFT ONTO EMERALD‘ DR
`DRIVE 01 MILES.
`
`EMERALD
`
`LUCAS
`
`’\-/
`
`W 9
`
`TURN RIGHT ONTO EMERALD ST.
`DRIVE A SHORT DISTANCE TO
`YOUR DESTINATION AT 2.60
`EMERALD ST
`
`EMERALD
`
`EMERALD
`
`Apple, Exhibit 1040, Page 7
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 6 0f 15
`
`6,107,944
`
`
`
`
`
`wm>_.r<2mmb<.52:.25:ZO_._.<2_meQFXmFunilr
`
`
`
`
`02.458gfi<25ma\20.225828:6
`
`S\qumy
`
`\I/
`
`_:.0300::mat,QJmEmntC:
`\n/L
`
`
`
`mo;0m000250“0mm:_~00._S..2202mumifimmmsomommwvm30030018572_m;.OI>>vA\9Emman:xmmEummbm
`
`
`
`FXE.ZGEOn:mo<mmm§u§<km92:.2m:092
`0mm
`
`
`Iumzmiiimmmmaoimmqmofim3.emaimmzm0338081030024{wagmu
`
`
`
`
`
`99:.m:mw<mmm§ufifbmEC.2m:092
`
`
`
`
`
`
`
`m.mde0.0Song“/7:00222203320_04.230000000533230_M“w281mg:Txmmofix[5onJm©<mmm§n:mum:n:mmmEUmmsmomom
`
`“mam050026000000.0S01:”;00305220208100230008033002.0002
`
`
`
`.00350.03T55.05mmiozmqo00:33km80qu00W?mo<mmm294d
`
`
`
`
`-.0009....1300230582500"sz.0035H03C0u/.930mqaazuqowamod‘mmm:mmm
`3:0.5025:0.H08finiESSSEZpEmoniimmmsomonovfl03232,
`.3-6030.33.00.fimiozmaokaoozxuomuzmi
`
`
`
`0&onEwSm93.00.02“/01”:mofimfizzsflmonm_00mmmsomo~000m_002.031
`
`
`-0:“mméafiaééozmaouzmi.33:0.0NEED04/.m:2833:03mo<mmmEa?
`
`
`
`
`10-02.00-000.Haqémzmflmfifiuzmi.825H03200/.00355E<m0<mmm2an
`38ES5:00.0:0/5,7:00222203000102030000300fl002802
`
`_0m.mm..0m-.$-.~00.40-000
`
`_»umm02_mm
`
`_H0.Hm-km0
`
`Apple, Exhibit 1040, Page 8
`
`_n/.mmuncme
`wfimoimmgW”
`
`Apple, Exhibit 1040, Page 8
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 7 0f 15
`
`6,107,944
`
`
`
`mcflm:nowso»xcmzeH/_m_moaflmmszbo_monm_pummmfioomo~m0¢m_nmmpmomm_
`
`
`
`
`Hmmvmmfiémmauzmfluxmoomusomcmiam.o.m.mlmnoo:mm3:oflmugwmmnmumDE/duou
`
`
`
`
`
`
`mmfimoHorfiumHcoflummflimzvm-mmmauxmfifiaoummmnmumou/u/mmusomcm\Hmm-m0<mmm§02.0
`
`
`
`
`
`
`
`
`
`oa¢mm2m‘_mm-.wh‘www-4mmumm.H“aqammzmkoqmmmZmuzm4_u/.em
`
`
`
`_»nmzm<_exm2umm>smz¢2________.mOHHNmszuo_«omm_nnmmmaoomommon_Hammvamm_mmmm_MFO_W.«Hmv;u<Qm4mvrx>
`
`
`
`cucoemoncusp4.0Amu/H/_m~m0HHmmszoo_monm_ppmmmfioomonowm_nmm0muwm_
`ommum.coflumcflumwwH20»Cumucmumfluuuogmmw>flunu/.Hmqumzm2mo<mmm§HWH
`
`
`
`
`
`3\QEWW
`
`2«mm,
`
`3mm_3::w;\EOE:55$
`
`
`
`
`
`_z”mmoz_p:m.acoflmum>wumzuuommQHEmoHoccowe5039585
`
`
`
`
`
`
`
`r_mo_m_omom_mmvm_onmH>HamoH_¢nmvmumm_am>w~mmoo_uwN“\mmumwmy
`
`\ll/\
`
`ZHBmmDm_oooooooouonmmmm~___*____omommmwam.onmH>HomaH_ommoooom_ommo_mwo_
`
`r_¢m0Hanmx¢zwaw\
`
`,3.00P
`
`Apple, Exhibit 1040, Page 9
`
`Apple, Exhibit 1040, Page 9
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`SheetS 0f15
`
`6,107,944
`
`
`
`.musmumflmuunogmmw>HHOH/.WflgWUQHWH9.2qumSOumw3£uHOZ
`
`
`
`
`
`
`
`mwafigH.musondu/flm_omom_mmwm_onmH>HmmoH_nwmwmwwm_monm*mmno_
`
`mcflomusepumum0.0AHH/u/_m_omom_mm©m_onmH>HomnH.hmmvmu0~_
`
`
`
`r_H/umwu5nfieom
`
`r_omo.¢quonzou_~______.omom_mmom_onmH>HomoH_«mmouoom_mOOm_mmo_
`
`
`
`.w¢zmoQHmBqummomm___omom_mmmm_onmH>HamoH_mmmouoom_m04¢_maa_
`
`
`
`r_wnmzm¢_z_o_mmmmoo<_moz<mo.092m24mugmzmwow_mmmmon¢_szm¢z¢
`
`r_mo_m_omom_amvm_onmH>HomnH_wmemmmm_mwvm_mmoo~
`
`,2$4
`
`E4m»
`
`:4W»
`
`
`
`“mm.aumHmmHHmzflmonmazHamuzm<_.mwafieH.oo>fluou/.za«Hm
`
`
`
`
`
`
`
`
`
`meHmsmoucoemmgcase0.0”Nu/u/_m_omom_mmUm_onmH>HamaH_>mmUmwwm_
`
`
`
`
`
`r_wm-~¢mwflm-.mh-kmm.HNmHmmeHm24monmezHamuzm<_
`
`
`
`mzoqmoucoBmuHmmuseH.oAmH/p/_m_mmom_mmwm.onmH>HowaH_pmmnmmmm_
`
`r_wm-.emkamu.mn
`
`
`
`
`
`.mzoqmemmeHmzuzm<_.mmafieH.om>fluo.u/.24msz
`
`
`
`moucoHum;gushm.oA4u/u/_x_omom_mmwm_onmH>HomoH_bmmomumm_
`
`r_mp-_nm“mm.fl“msz
`
`
`
`
`
`mzoauzm¢_.wucmumfluuuosmmm>flunu/.ZAammmmxow
`
`r_wnmzm¢_exmz“mm>bmz¢z_________omom_mmam_onmH>HomoH_mpmouoom_moam_mmo_
`
`r_»ummo:_mml.mmkmm-_mm-“mm\auemmmmzomumsz
`
`Apple, Exhibit 1040, Page 10
`
`Apple, Exhibit 1040, Page 10
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 9 0f 15
`
`6,107,944
`
`
`
`
`
`mHmzmcucopumacasem.oAmu/p/_m_amom_mmwm_onmH>HomoH_mmmumu0m_
`
`
`
`-¢uozuouaoememcase«.HfinM/g/_m_mmomwmmom_onmH>HomoH_Mmmummmm_
`
`
`
`«Hmz“02¢mmmmuzm¢_.mmaflem.o0>Hnnu/.omzowzmu
`
`r_Hm-.hmflmm-.mm-ko.mm-umm.fikzo>z¢u
`
`r_mm-~ma-flmm‘pm-umfl-‘mmumm.Huozammmm“emmmuzomnzm¢~
`
`
`
`
`
`Hm-<u“<oqu¢mmowuzm«_.mwafism.mw>fiuau/.mz¢m9mm:Hm
`
`
`
`
`
`-.oumm\flumpsommm-¢uumaHmmm>Hmuzm<_.mmafle5.0m>fluou/.uflxw
`
`mebomwzmmm-4uan»mxmeb.mhmu/H/_m_amom_umnm_onmH>HomnH_mmmvmuum_
`
`r_mm-.mkmm-.mm“mm~a“emmz
`
`r_wnmzmm_pxm2umm>bmz¢:_________omom_maom_onmH>HomaH_wbmoooom_m~mm_mmo_
`
`amozoauoxmpv.5hmu/u/_m_omom_wam_onmH>HomoH_vmmwmumm_munm_mmmo_
`
`r_wnmmoz_mm-.>uooa
`
`ememcusp«.0AmH/u/_m_omomw“mam_onmH>HnmoH_mmmvmwwm_0m¢«_¢mmo_
`
`
`
`
`
`.mmHHEm.om>Huau/.m><ozmmmmmouuo
`
`
`
`
`
`mam00u2m¢_.moaflem.om>fluoH/.uflxmm><zqooqu\ommuz¢m
`
`
`
`
`
`
`
`zHemopzcusoEmmamusem.>.OHH/H/_m_omom#mmvmvonmH>HnmaH_wmmvmumm_
`
`
`
`r_>m-~flm-“mm-~m-Nmm.HkamzHBmspummm:
`
`
`
`
`
`-xmm-“mm.H«zHemsauHmzHamnBuzm¢_.meHeo.Hw>fluou/.em
`
`r_ma.mmmm
`
`
`
`ma¢mzmOucoEmmacuspm.mAHHu/u/_m_omom_mmvm_onmH>HomnH_wmmvmwmm_
`
`
`
`
`
`
`
`-_¢-Nm.mm-“mm‘awme¢mzwzHemoeuzmm_.mmfifie¢.oo>fluog/.m>¢
`
`r_HH-~mmumm
`
`
`
`emmHmmusem.w“NHu/u/_m_omom_mmnm_onmH>HmmoH_vmmvmumN_.mommumflnuuonwm0>Hueu/.HmmwnHmzmxummmzouno
`
`
`
`r_wummoz_OOH-‘ORM.mmumm‘fl“moonzmxummmuma¢mznzm¢_
`
`Apme,Exmbfl1040,Page11
`
`Apple, Exhibit 1040, Page 11
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheeth 0f15
`
`6,107,944
`
`r_»umxm<_exm2umm>bmz¢z____#___,Qmom_m¢om_onmH>HamoH_mnmouaow_mmma_mmow
`
`cofiumcfiumwvH50>Oumunmumfivunonmmw>fluoH/.BmOBZmEmMUfimzouuo
`
`
`Emmamuse0.0AvaH/u/_m_amom_mmom_onmH>HomoH_ommwmwmm_
`
`
`
`r.02mm-mmm2H“092mzdmudmNomomezmmmuzm¢_u/.emOHZmzmmudmzmwomum
`
`
`
`emongazeo.mAmap/M/_m_mmom_mmvm_onmH>HommH_ommwmwmm_nmmw_o¢mo_
`
`
`
`.meflEa.om>fluo0/.m>¢omomBmemmOuco
`
`r_mm-2¢-N¢-2mm2mm.HuomOmezmmm“moaHmzmMommmuzmd_
`
`
`
`mcfim:00w50>xumneH/fim_omom_mmvm.onmH>HomoH_ommmmwmm#
`
`
`
`
`
`
`
`
`
`mmHmOHOCQUwHCOwummfi>mz¢mImamausmflpxmoummmnmqun/H/mwudomcm\me
`
`
`
`
`
`
`
`
`
`
`
`wmma-mmmaunmfluhmoumusomcm\Hmm‘o.m.m«oaoomasofimum>mmmnmumavu/.muou
`
`
`
`
`
`
`
`
`
`
`
`r_z“mmoz_u/Amv.muofimnm>wxmauwommoH\>moHosnowHcofluMEHOwcHHmm
`
`
`
`
`
`
`
`r_»nmzm4_z_o.mmmmoa¢_xm<m«zmam.mmmomemoz¢moommp_mmmmoa<_mmqmoz<
`
`
`
`
`
`
`
`mog2ammzmmbocmhfi___amom_muom_20HmH>HQmoH_ommouoom_~bmn_ama_
`
`Apme,Exmbfl1040,Page12
`
`Apple, Exhibit 1040, Page 12
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheetll 0f15
`
`6,107,944
`
`
`
`uponmmwbfluoH/.mkRzHflwzfimmmezouommzmmDOc0ummzfiuhoz
`
`mcflomusouumum0.0”Hu/u/_w_nm0m_moum_onmH>HomoH_mamUmwmm_
`
`
`
`oucoHmonemeqmcussH.oAmH/»/_m_omom_movm*onmH>HomoH_mnmwmwmm_
`
`
`
`-~«umm~Hum2mmDOKZquzmmmuzm¢_.mmfifiem.ow>Huop/.ommzmmpo
`
`
`
`r4mh.¢w-kmm.H4mzmmooummeDOuzm¢_.wuumumflv
`
`
`
`m.omuson<H/_m_omom_muwm_onmH>HamoH_mnmnmmmm_«wow—m¢ho_
`
`r_u/.mmudcfleHm.meHE
`
`r_0m-4mm“mm
`
`
`
`ammzsm3cameEmma20:9m.oAmu/H/_m_omom_monm#onmH>HomoH_wnmwmuwm.
`
`
`
`-.mmwm4mm-“mm.fiwemm22mwmzwm50uzm¢_.meflEm.mm>flpou/.o>am
`
`
`
`-momguouuoBmemcase4.4A4u/H/_m_omom_mowm.onmH>Homonmnmwmmmm_
`
`
`
`Hoa-mouemmZDmuzm4_.meHEm.¢m0>HnaH/.mzmmmesomHoa
`
`r_wnmmoz_mm-.N-4>m-\mmumm‘akm930m
`
`r_m
`
`r_»umzmm_axm2umm>bmz¢z_________omom_ooam_onmH>HomaH_mdmoumow_0mmm_mmo_Awmw\Amwwmhy
`
`2
`
`Apple, Exhibit 1040, Page 13
`
`Apple, Exhibit 1040, Page 13
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet12 0f15
`
`6,107,944
`
`Heozxmagmxmem.mmAmu/u/_m_omomgowwm_onmH>HomoH_nnmUmmmN_anw‘momo_
`
`
`
`
`
`«Hmmem42<z¢«52mmn2m¢_.mmfifleH.om>fiuon/.Uflxmw>m
`
`r_mm-2maumm-2hh2mm2aha>qm
`
`
`
`.m><59022oucommumzn.mmAmu/u/_m_amom_ownm_onmH>HamaH_nnmummmm_
`
`
`
`
`
`
`
`
`
`-Nwm-2makmm2aweeozmwm>gm«Hmmem4uzm¢_.mwafieo.Hm>fluau/
`
`
`
`r_Nmpm.Hm-2hm-2nm2mm
`
`
`
`OucoEmmacasen.mmAuu/u/_m_omom_owum.onmH>HomQH_nnmnmuwm_
`
`
`
`
`
`
`
`
`
`r_H-2mm2mm-2¢-2m2mm-2mm2H“mmmomemw24momeeozxuzm<_n/.m><mmmoxamoz¢moommp
`
`umcofluMCHummvH50»OumefiEm.ow>apaH/.m>mmmmomBmOdeo
`
`
`
`mcflm:“Owso»xcwneH/_m_omom_ovum_onmH>HomnH_nnawmuwmw
`
`
`
`
`
`
`
`mmflmoHOCgowHaofiummfl>mzwm-mmmaunmflhhmoumeQmquH/u/mmudomcm\me
`
`
`
`
`
`
`
`
`
`wmmfl-mmmaugmfluxmoomusoxcm\Hmm2o.m.m|¢oaoomficofimmm>mmmnmumovu/.muoo
`
`
`
`
`
`
`
`
`
`
`
`r_z"mmOE_H/Aw¢.mCOfimuwbmHm3uwowmoH\>boHocnuwHcoaumEHOwcHme
`
`
`
`
`
`
`
`-nu”ooooonuc:0wmHommooz_O_Qmom_momm_onmH>HomoH_wwmvmmmm_UUom_mmoo_
`
`r_2nmmoz_“n22--
`
`
`
`2m><¢que¢mzmmmH__#omom’womm_onmH>HomaH_mamouoom_Hmmm_woa_
`
`r_mH0muwmmbo_z_OOH_ez¢mb<emmm_wmm¢m_mmmmanm_moz¢mo
`
`Apme,Exmbfl1040,Page14
`
`Apple, Exhibit 1040, Page 14
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 13 0f 15
`
`6,107,944
`
`
`
`-u".moooo.vnsoumHommooz_o_amom_omwm_onmH>HomoH.uOmwmumm_mmmm_mmmo_
`
`
`
`.m>¢«gamedxzmmma___omom_ommm_onmH>HomaH_mmmouoom_¢omm_moa_
`
`r_mHomuwmm:o_z_OOH_Bz¢mD¢ammm_>m025m_mmmmaa<_mwz¢mo
`
`
`
`¢zmbmo>4mmmemmmuz¢zHme.Bz¢mo<emmm000m¢mmmmeewmoZDm."u_--
`
`
`
`
`
`
`
`MOEZmHNN.HzgdhmmmEmMMDZDZ.Z.m¢mw¢.H¢FwdMNNoo.mommm.mm.Mmdm
`
`
`
`r_Zumdoz_z.0bmwm.N.«1woanmm¢u040.wmovmummuZOBmmawHPw~.Efium
`
`
`
`-u”"mHoOouwcsowmHommooz_o_omom_amom_onmH>HamaH_vflmvmmmm—mmoa_«o>o_
`
`
`
`2m>4«gamemxzmmwfl___amom_Hmmm_onmH>HomnH_no«ouaom_mwmm_moa_
`
`r_mHomuwmmbo_z_coa_yz¢mp¢ammm_mmombm_mummoo<_mozmmo
`
`
`
`
`
`-omm-o-ommmmmmm«mam_o>qm«mummpopummmompmmemm_<mmmu"u..--
`
`
`
`«a.wzmqummmzH3mmmauwzHgmmwmumflz“¢«¢Hm"m.v.«ma-mhu-o-ounmmvmummumommm
`
`.o>qmdummm4gmHm«ummwmbmh92¢u“zummom¢"m.¢.mma-mmw-o-onmowvmummu¢mm¢m
`
`
`
`mmmmmma3Howmmmombmm.momomouznNflmomua.¢.mmd-mmm-o-oumow¢mummummm<mmg
`
`
`ademmzH22”maHNmHH.42omfl-mom-o-oumm«¢~“mmndxmmm«q~o>qmr_mnwmoz_znNaHNmNm.w.owfl-mom-o-ou¢m4vmummudmmam<4.o>amammgm«axommnmmwMDmm92¢emz"momww"-.¢.wmm-mam-o-oumm¢¢mummu¢mm¢m4A.wzmg¢HmmmzHmawmummmwmom
`
`
`
`
`zoequazam.emammomxoommHommanwszmwwmomuzuwmwmwufl.¢.mm
`
`
`
`
`
`
`
`
`
`-mmm-o-ommnmmmm4mm:¢HmOU‘moemdoummmmnwzHMmmumsmflzumommmua.v.oma
`
`
`
`
`
`Apple, Exhibit 1040, Page 15
`
`Apple, Exhibit 1040, Page 15
`
`

`

`US. Patent
`
`Aug. 22, 2000
`
`Sheet 14 0f 15
`
`6,107,944
`
`
`
`-mma-o-obpahmmmmmemszpmmz.m>qmmo4mmHmmmaummwmam
`
`
`
`
`
`r_zummoz_zuo¢flm¢um~w~mam-nmfia-o-onmmanmnmmnmmemszhmwz
`2o>qmmmemszemmzmammummompmBao-z‘zHuzuwHHo«um.w.mHm
`
`
`
`
`
`
`
`
`
`
`
`Hm¢mauwszmmomomuznommmmua2¢.>om‘>m>-o-onm¢mmmnmmumz¢dezmm
`
`
`
`
`
`m.momRZ“4cmmm"H24.mw-Hnw-o-ouwmmmmummquempe_m><emOszz
`
`r_exmzumm>bmzmz_________mmom.4mmm.onmH>HamoH_mo¢oumow_aom«,mmo_
`
`EM,
`
`
`
`
`
`mam»mmombmBoo-z-zH_o.omom_«mmm_onmH>HomoH_wamwmumm_mmmm_mwmo_
`
`.QmmwwomHowoszmmompmwzumawmmufl.¢.HHH-mmm-o-oumvmmmummumzd
`
`
`
`
`-z-zH“z"mmamna.¢.¢~H-mmm-o-o"Hmommuwmumozamo.ammDmBHuzmwmnwszmumW..uh»
`
`
`mmomsmkz”Nmmomum.¢.m¢m-oama-o-ou4amwmummuazqmmd4.HmzmH>wwqa¢>\)/(
`-mmm-o-o“¢Hmm~mm«HBZmuaqm.m>¢zmzmdmuzmwwummomsm950\meV
`
`
`
`
`492<m.emJOBmHmmmommmuoszmmwmbmuzuomm¢mua.¢.bmfl
`
`Apple, Exhibit 1040, Page 16
`
`Apple, Exhibit 1040, Page 16
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 15 0f 15
`
`6,107,944
`
`TOKEN ENGLISH TABLE SPANISH TABLE
`
`GERMAN TABLE’
`
`MAKE A U
`TURN AT
`
`1
`
`AN DER KREUZUNG
`HAGA UNA
`VUELTA EN MIT
`BITTE
`0 EN______. EINE KEHRTWENDUNG
`MACHEN.
`
`2
`
`(ZAMBIA EL ____UI\IDERT DEN
`CHANGES
`NAME TO
`. NOMBRE A
`. NAMEN zu _._.
`
`TURN LEFT 0N DE VUELTA A LA AUF_____ LINKS
`3 _AND DRIVE IzQuIERDA EN ABBIEGEN UND
`MILES. _ Y MANEIJE
`MEILEN
`__ MILLAS. WEITERFUHREN.
`
`M
`
`4O
`
`REQUEST STRIP
`MAP FOR PARTS
`NOT ADEQUATELY
`
`covERED. _
`
`I
`RECEIVE STRIP"
`MAP INFORMATION
`FROM BASE UNIT.
`
`Z 54
`
`; 5!
`‘REQUEST ROUTE
`FROM
`BASE UNIT.
`
`{52.
`
`RECEIVE ROUTE
`INFORMATION FROM
`BASE UNIT.
`
`55
`COMPARE .REcEIvED I
`ROUTE WITH
`oNBoARD MAR
`
`54
`
`ANY
`PART NOT
`A DE Q UAT ELY
`COVERED
`
`YES
`
`DONE. f5?
`
`0712?. w
`
`Apple, Exhibit 1040, Page 17
`
`

`

`1
`ELECTRONIC NAVIGATION SYSTEM AND
`METHOD
`
`REFERENCE TO RELATED APPLICATIONS
`
`The present application is a continuation of Ser. No.
`08/494,198, ?led Jun. 23, 1995, now US. Pat. No. 5,808,
`566, Which Was a continuation-in-part of Ser. No. 08/265,
`094, ?led Jun. 24, 1994, now US. Pat. No. 5,543,789, the
`entire contents of Which are incorporated by reference
`herein.
`
`REFERENCE TO MICROFICHE APPENDIX
`
`Included With this speci?cation is a micro?che appendix
`including 3 sheets of 283 total frames.
`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 Of?ce
`patent ?le 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 speci?ed 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 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
`
`10
`
`15
`
`20
`
`25
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6,107,944
`
`2
`database. Technologies such as CD-ROM have alloWed
`storage of an entire database but require still a tradeoff
`betWeen cost and fast, ef?cient 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 recon?gured, as
`businesses and other points of interest open and close, the
`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 ?oppy disk, to
`remotely located mobile users may be dif?cult. 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 ?Xed 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 con?guration 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
`con?guration and in a compact form.
`
`Apple, Exhibit 1040, Page 18
`
`

`

`6,107,944
`
`3
`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 obj ect 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 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 ?rst 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 ?rst 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 DESCRIPTION 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,
`
`4
`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;
`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 ?oWchart used for explaining operation of a
`stripmap request feature of the invention.
`
`15
`
`25
`
`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
`
`35
`
`45
`
`55
`
`65
`
`Apple, Exhibit 1040, Page 19
`
`

`

`6,107,944
`
`5
`ing an input means for providing at least a route destination
`and an output means for providing an i