United States Patent (19J
`Behr et al.
`
`I lllll 1111111111111111 111111111111111 lllll lllll lllll lllll 111111111111111111
`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 Ill.
`
`(73) A5.5ignee: Navigation Technologies Corporation,
`Rosemont, lJl.
`
`[ *) Notice:
`
`This patent i5sued on a continued pros(cid:173)
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(aX2).
`
`(21] Appl. No.: 09/151,255
`Sep. 10, 1998
`
`[22) Filed:
`
`(63]
`
`(51]
`(52]
`
`(58)
`
`(56)
`
`Related U.S. Application Data
`
`Continuation of application No. 08/494,198, Jun. 23, 1995,
`Pal No. 5,808,566, which is a continuation-in-part of appli(cid:173)
`cation No. 08/265,094, Jun. 24, 1994, Pat. No. 5,543,789.
`Int. Cl.7
`... ....................... .. .... .. .... .. ............. G08G 1/123
`U.S. CJ. .......................... 340/995; 340/988; 701/208;
`701/209; 701/211
`Field of Search ..................................... 340/995, 990,
`340/991, 988, 905; 701/209, 211, 208,
`210
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,301,506
`4,311,876
`4,428,057
`4,466, 125
`4,481,584
`4,546,439
`4,570,227
`4,642,775
`4,733,356
`
`11/ 1981 Turco .
`1/ 1982 Endo et al. .... ... ... ... ... .... ...... ... 340/905
`1/ 1984 Setliff el al. .
`8/1984 Kanayama .............................. 340/990
`11/ 1984 Holland .
`10/1985 Esparza .
`2/ 1986 Tachi el al. .
`2/1987 Cline et al.
`3/ 1988 Haeussermann et al. .
`
`FOREIGN PATENT DOCUMENTS
`
`0 379 198 A3
`0 585 950 A2
`41 41 597 Al
`3150699
`6266997
`
`7/1990 European Pal. Off . .
`9/1993 European Pat. Off ..
`12/1991 Germany .
`6/1991
`Japan .
`9/1994
`Japan .
`
`(List continued on next page.)
`
`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.
`
`(List continued on next page.)
`
`Primary Examiner-Brent A Swarthout
`Aflorney, 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
`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-Io(cid:173)
`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 di5play. 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 coordinates. 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
`
`

`

`6,107,944
`Page 2
`
`U.S PATENT DOCUMENTS
`
`4,758,959
`4,780,717
`4,812,843
`4,819,174
`4,951,212
`4,954,958
`4,954,959
`4,974,170
`5,043,902
`5,067,081
`5,113,178
`5,126,941
`5,172,321
`5,187,810
`5,214,757
`5,243,528
`5,262,775
`5,283,575
`5,289,572
`5,291,412
`5,291,413
`5,293,163
`5,293,484
`5,359,527
`
`7/1988 Thoone el al. .
`10/1988 Takanabe et al.
`...................... 340/995
`3/1989 Champion, III el al. ............... 340/905
`4/ 1989 Fumno et al. .......................... 340/995
`8/1990 Kurihara el al. ........................ 340/395
`9/ 1990 Savage et al. .
`9/1990 .Morolo el al. .......................... 340/995
`11/ 1990 Bouve et al. ........................... 395/357
`8/ 1991 Yokoyama et al. ..................... 340/988
`11/ 1991 Pel'son ..................................... 340/995
`5/ 1992 Yasuda el al. .......................... 340/995
`6/ 1992 Gmmu e! al. .......................... 340/989
`12/ 1992 Ghaem el al. .......................... 340/995
`2/1993 Yoneyama el al. ..................... 340/905
`5/ 1993 Mauney et al. ......................... 395/ 161
`9/1993 Lefebvre ................................. 340/995
`11/ 1993 Tamai et al. ... ... ... ... ... .... ... ... ... 340/995
`2/1994 Kao et al. ............................... 340/990
`2/ 1994 Yauo et al. .... ... ... ... ... .... ... ... ... 395/ 155
`3/1994 Tamai et al. .
`3/1994 Tamai el al ..
`3/1994 Kakihara et al. ....................... 340/988
`................ 340/825.44
`3/1994 Dabbs, III el al .
`10/1994 Takanabe et al.
`...................... 340/990
`
`3/1995 Hanchett .
`5,396,429
`4/1995 Braegas ................................... 340/905
`5,406,490
`4/1995 Goto et al. .............................. 340/995
`5,406,493
`6/1995 Nobe el al..
`5,424,951
`5,465,088 11/1995 Braegas ................................... 340/905
`5,537,323
`7/1996 Schulte .
`8/1996 Behr et al. .............................. 340/995
`5,543,789
`5,559,707
`9/1996 Del orme et al. ...................... 340/995
`5,579,535 11/1996 Orlen et al. ............................. 340/995
`3/1997 Ohomori et al. ....................... 340/995
`5,614,895
`5,699,255 12/1997 Ellis e! al. .............................. 340/995
`
`FOREIGN PATENT DOCUMENTS
`
`W0 92/
`8/1992 WJPO .
`14215
`WO 92/21001 11/1992 WJPO .
`
`OTHER PUBLICATIONS
`
`PCT- Notification of Transmittal of the International
`Search Report, dated Nov. 2, 1995, in International appli(cid:173)
`cation No. PCT/US95/07859, Application Shields Enter(cid:173)
`prises, Inc.
`"Smart cars. Smart Highways." Collier, W. Clay and
`Weiland, Richard J. JEEE Spectrum, Apr. 1994, pp. 27- 33.
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 1 of 15
`
`6,107,944
`
`~8
`. - - - ----:- ,7:;;;._ - -~72 - - - r80'
`2..
`I
`MAP
`ON -LINE
`THIRD PARTY
`! INFORMATION
`TRAFFIC AND ~DATABASE~
`DATA
`I
`I\ t
`MAP UPDATER ~ -..----~
`INT£GRATOR
`·
`..... ,,___,,....,..8--____,+
`I
`I
`DISTM.JC E
`SURROUf.JDINGS
`I
`A~D TIME
`EXPLOR£RS
`I
`TRAVEL
`I
`- ESTIMATOR~
`~
`I
`.,
`I Lr ,z
`I
`~ R£~~~~rR _r c,-4
`1
`I
`.
`,21
`...----l(L....--'--.1....----- ~77
`I
`I
`EXT.~
`I/F
`I/0 INTERFAC£
`1-4--- - - - - - --k.~. CONTROL
`1-T_E_L_E_P_H_O_N_E~N---'-E-T__,;.._R_F:'-______ .....,
`1/F
`I/F
`I/F
`7C
`L---...----.--'-~--'------'~
`74!>
`75:>
`L _______ - - - - - - ___ ,.......______.
`I
`
`MAP
`DATABASE
`VENDOR(S)
`,
`.
`'B 1
`
`TRAFFIC _.__ 8"3
`INFO.
`PROVIDER
`
`,,
`
`t
`ROUTE
`CALCULATOR
`,~
`-~
`!
`
`j \
`
`2.5 ___,,..
`
`k--+-
`
`CELLULAR
`SYSTEM
`
`7
`)
`
`.. -
`
`l
`
`OTH E R
`
`PROVIDERS
`
`(70
`
`'
`
`KBD I DI s p
`5
`r
`8,
`88)
`
`I
`
`MODEM
`
`MEM
`
`KBD
`
`~
`
`DISPLAY
`
`1 1_•
`
`.r.54
`
`52..
`
`y
`
`l
`
`y
`
`SI
`
`.r 3C.
`
`~34
`
`4(
`µp IMoDEM 40 RF r/F
`,o---... DISPLAY
`MEM
`I
`rt
`f-42
`s,-.,, 1PP M
`PAGER
`
`J 2C,
`
`LAPTOP
`PC
`
`DISPLAY
`
`PO S
`K8D
`' -~ --'---~----'----'~44
`4(, s
`18)
`
`20 5 56
`
`10
`"'-
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 2 of 15
`
`6,107,944
`
`START
`
`ESTABLISH COMMUNICATION
`
`100
`
`~ORMAT A QUERY~---------.
`
`TRANSMIT QUERY
`
`104
`
`QUE:RY RESOLUTION
`
`110
`
`TRANSMIT
`ERROR
`MESSAG-£
`
`Y£S
`
`I DENT I FY QUERY TY PE
`
`112
`
`Y£S
`
`NO
`
`J 11-4
`
`QUERY FULFI LLM£NT
`
`FORMAT RESPONSE
`
`TRANSMIT RESPONSE:
`
`118
`
`END
`
`'"'---""'
`
`..f--11'- 2
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`
`!JI
`
`0
`
`~ -~
`
`~
`
`(J) :r
`
`N §
`
`► =
`
`~N
`N
`(!Q
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`+X, +Y
`
`-X +Y
`
`,;f-~ 5
`
`~
`
`------------X
`
`ORIGIN
`+X, -Y
`
`y
`
`-X, -Y
`
`J~-1-
`
`~
`
`\n
`
`MESSAGE
`
`1'30
`
`J7<S
`
`/C,2. _,,,f
`
`!t.O
`
`I MESSAGE ID I JD I TYPE
`
`MSG LEN 11 C Re I TIME STAMP I SUBSCRIBE.R ID
`
`, 17,
`
`174...,
`
`172
`
`!70
`
`1'8
`
`lC.4 c!C.S ,IC(,
`
`J,~3
`
`ORIGIN I OTYPE I DEST I OTYPE I DLIMIT IL TYPE I \Y1 ~
`
`152
`
`r 150
`
`<148
`
`< 14-C
`
`< /44
`!22 _.,,?f
`
`,,-142
`
`/40
`
`/3C (138
`
`l
`
`LONG
`
`r
`
`STAM p I s UBS~RIBER ID I MESSAGE ID
`12..B
`
`, 130
`
`r 13 2
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 4 of 15
`
`6,107,944
`
`START OUT GO ING EAST ON
`R OCKWOOD ST T OWARDS
`GLEN DALE B LVD.
`DR IVE 0.1 MILfS
`
`ROCKWOOD
`
`TURN RIGHT ONTO GL£tJDALE BLVD.
`DRIVE o.r M I LES
`
`GLENDALE
`
`7
`
`TURN SLIGHT RI GHT ONTO
`LUCAS AVE
`DRIVE O.'.<, MILES
`
`GLENDALE
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 5 of 15
`
`6,107,944
`
`TURN LEFT O NTO EMERALD DR
`0 . 1 MILES.
`DRIVE
`
`EM ERAL D
`
`LUCAS:]
`
`9
`
`TURN RIGHT ONTO E M ERALD ST.
`DRIVE A SHORT DISTANCE TO
`YOUR DE ST INATION AT 280
`£ M £RALD ST.
`
`,___,,,.
`J ~ / 0
`
`EM ERALD
`
`MAI N
`
`EL M
`
`BROAD
`
`

`

`~
`~
`\0
`._.
`-...,l
`0
`~
`._.
`0-...
`
`....
`0 ....
`~ ...
`IJ) =(cid:173)~
`
`0\
`
`Ul
`
`N §
`
`~N
`N
`
`> C qo
`
`~ = .....
`~ .....
`~
`•
`00
`0 •
`
`0.1 Turn RIGHT onto
`
`0.0 Start out going East
`
`Drive 0 .1 miles.
`
`About 0.4 miles, 3
`
`MESSAGE
`
`)
`
`_;f~./2
`
`~
`
`INFO.
`
`ROUTING
`
`TYPE
`LIMIT ALTfRNATIV£S
`\
`'-------~
`
`~ D£5T/NATION
`
`F'IE LD
`LIMIT
`
`)
`
`DESTlt-iATION
`~
`/
`
`TYPE
`
`TEXT
`
`DESTINATION
`
`J~ 11
`
`~
`
`TYPE::
`ORIGIN
`
`)
`
`{
`
`PACK ET
`WHOLE
`
`!ARM2GLE~DALE;LUCAS;l,99;17,-
`0.2 Turn SLIGHT RIGHT
`
`.Drive 0.2 miles.
`
`IARM .. ROCKWOOD;GLENDALE;l,99;90,·
`
`Drive 0.1 miles.
`
`\r
`
`\r
`
`[ARMzLUCAS;EMERALD;l,99;·98,17;-7,-
`
`Drive 0.1 miles.
`
`\r
`
`99[MOREaYI
`EMERALD OR.
`
`0.4 Turn LEFT onto
`
`4)
`
`I l2fc37396IS40620B00159377[9bc5jDUNMIR21109[Rl\r\r
`
`{
`
`5'QI MESSAGE-
`
`4!H MESSAGE-
`
`98 j • 91, -4 0; • 4 2 I• 90; 93 • 34 I
`onto LUCAS AVE.
`[2fc37396jS40620B001S9377[9bcSjDUNMIR21109IRl\r\r 3)
`42;·91,41[
`
`·j2fc37396jS40620B00159377l9bcSIDUNMIR21109[Rl\r\r 2)
`jARM:ROCKWOOD;GLENOALE;l,99;·91,4~;90,·42j
`on ROCKWOOD ST towards GLENDALE BIND.
`\r
`l2fc37396[S40620B00159377j9bcSIDUNMIR21109IRl\r\r 1)
`minutes. \r I
`PACKET HEADER-{ I oaos la~de
`
`'"'-
`l ST MESSAGE--{ I ~fc37396jS40620B00159377j 9bc5 jOUNMIR21109 IRl\r
`
`)
`
`)
`
`TYPE
`
`MSG LEN TIM£ STAMP MESSAGE ID
`
`~ C RCj SU8SCRlBER ID; US£ R ID
`
`)
`
`(
`
`38.P MESSAGE--GLENDALE BLVD.
`
`{
`
`{
`
`2.~ MES SAGE -
`
`ANGELESIADDRESSl280 EMERALD ST, LOS ANGELESIADDRESSIOIM[ARMS•YI
`j131jo4Dlj92D4580BIS4062osoo1s9377l9BcsjouNM1R211091 I 11sso ROCKWOOD sT, Los
`
`(
`
`) VSEt ID
`
`ORIGIN TEXT
`
`ID
`
`MESSAGE
`
`TIME'. STAMP
`
`MSG LEN
`
`) c~c ! SVBSCtlBER ID
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`
`!JI
`
`0
`
`~
`
`(J) :r
`
`~ ---.:a
`
`N §
`
`► =
`
`~N
`N
`(!Q
`
`~ = fl"!',
`~ fl"!',
`•
`rJ1
`0 •
`
`Thank you for using
`
`2fc3739blS4062OB00159377j9bcalDUNMIR21109jRl\r
`
`EMERALD ST.\rjARM=EM~RALD;EMERALD;l,99;96,-26;-74,-661
`
`I0039j67flj2efSd974jIDSDIVISIONl9d89jBOBDIEIOKI,
`
`i;f~!~
`
`-----./
`
`MAXPKT .. 1024j-.
`I07BIOA8Dl80DC0960IIDSDIVISIONl9D89IBOBDI I I I I I I I ISESSION=0OOOOOOOjBURST=N
`
`~ ..;f1f 15
`
`Information Technology/IDS Software version 1.2)\rjMORE=NI
`
`i--.. MESSAGE Corp. \r (Database version wsal10076_2. 3. O, SEI/EnRoute Copyright 1993-1994 SE!
`
`. SEI/EnRoute!\r\rDatabase Copyright 1992 -94 Navigation Technologies
`
`NO
`
`ll
`
`{
`
`Drive a short distance to your destination at 280
`0.4 Turn RIGHT onto
`.J~.
`
`14
`
`~
`
`j2fc3739bjS4062OB00159377j9bcajDUNMIR21109jRj\r\r 5)
`
`\r
`
`PACKET HEADER --{ I 04 95 I 9588
`
`;!~. 13
`
`~
`
`1 ~ MESSAGE~ EMERALD ST.
`
`WHOLE PACl-<.ET-{ I 073 I 2F39 j 92D45811 j S4062O800159377 I 9BCA I DµNMIR21109 I I I I I I I I I MANEUVER=NEXT IARMS•YI
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`
`!JI
`
`0
`
`~
`
`(J) :r
`
`~ -00
`
`N §
`
`► =
`
`~N
`N
`(!Q
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`I062l61D6ISODC0975IIDSDIVISIONl9D9FIBOBDI I I I I I I I IMANElNER=NEXTIARMS=YI,
`
`.;ff, 21
`
`,....____,
`
`IARM=WHITE FIR;LONE
`
`Drive 0.1 miles.
`
`0.1 Turn RIGHT onto SLONE
`
`jARM=FLINT RIDGE;WHITE FIR;l,99;
`0.0 Turn LEFT onto E WHITE
`
`Drive 0.1 miles.
`
`Drive a short distance.
`
`0.0 Start out going
`
`\r
`
`About 9.1 miles
`
`ANAHEIMIADDRESSj2043 N SACRAMENTO, ORANGEIADDRESSI0IMIARMS=YI,
`ll19IA4C8j80DC096EIIDSDIVISIONl9D98IBOBDI I 1950 S FLINT RIDGE WAY,
`
`I0039l3d8al2efSd976IIDSDIVISIONl9d8blBOBDIEIOKI,
`
`jossjaooajaooco962IIDSDIVISIONl9D8BIBOBDI I I I II I I lcONFIG=LA.CFGI,
`
`\r
`
`\r ·
`
`\r
`
`0.2 Turn LEFT onto E
`
`IARM=LONE
`
`Drive a short distance.
`
`PINE;SOMERSET;l,99;-93,-35;38,-92IMORE=YI,
`SOMERSET LN.
`l2ef5d987jIDSDIVISIONl9d98jBOBDIRl\r\r 4)
`PINE;l,99;67,-73j,
`PINE LN.
`l2ef5d987jIDSDIVISIONj9d9BjBOBDIRl\r\r 3)
`79,-61;24,-961-,
`FIR LN.
`l2efSd987jIDSDIVISIONl9d9SIBOBDIRl\r\r 2)
`IARM=FLINT RIDGE;WHITE FIR;l,99;-79,-61;24,-96j,
`Northwest on s FLINT RIDGE WAY.
`l2ef5d987\IDSDIVISIONl9d98IBOBDIRl\r\r 1)
`20 minutes .·\rl..,
`I0753l2bc6j2ef5d987IIDSDIVISIONl9d98IBOBDIRl\r
`
`J~ 20
`
`~
`
`~~
`~ Jr
`/9
`18 ~
`~ J:.
`
`J-~. /7
`
`~
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`
`!JI
`
`0
`
`~
`
`(J) :r
`
`~ -\0
`
`N §
`
`► =
`
`~N
`N
`(!Q
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`8.9 Turn RIGHT onto N
`
`Drive a short distance.
`
`\r
`
`IARM=TUSTIN;MEATS;l,99;-99,3;-4,-
`
`Drive 0.4 miles.
`
`8.6 Turn LEFT onto E MEATS
`
`IARM=TUSTIN ST;TUSTIN;l,99;-99,-
`
`Drive 1.0 miles.
`
`7.6 Turn LEFT onto N TUSTIN
`
`\r
`
`\r
`
`IARM=MEATS;BRECKENRIDGE;l,99;99,3;0,-l00IMORE=YI..,
`BRECKENRIDGE ST.
`l2ef5d98dlIDSDIVISIONl9da2IBOBDIRl\r\r 12}
`99;99-,-lll..,
`AVE.
`l2ef5d98djIDSDIVISIONj9da2jBOBDIRl\r\r 11}
`6;98,lSj-,
`ST.
`l2ef5d98dlIDSDIVISIONl9da2jBOBDIRl\r\r 10)
`MESA;TUSTIN ST;l,99;-2,-99;-21,-971~
`RANCH RD/LINCOLN AVE exit.
`I0652l6dc9j2ef5d98dlIDSDIVISIONl9da2IBOBDIRl\r\r
`
`7.4 Take the NOHL
`
`IARM=COSTA
`
`9}
`
`Drive 0. 2 miles.
`
`\r
`
`I062IF22El80DC0978IIDSDIVISIONl9DA2IBOBDI I I I I I I I IMANEUVER=NEXTjARMS=YI~
`
`IARM=RIVERSIDE;CA-55 SOUTH;l,99;0,-
`6.7 Take the CA-55 HWY SOUTH
`8}
`
`Drive 0.7 miles.
`
`\r
`
`IARM=YORBA LINDA;CA-91
`
`Drive 5.3 miles.
`
`\r
`
`1.4 Turn RIGHT onto the CA(cid:173)
`
`IARM=SERRANO;WEIR
`0.6 Turn LEFT onto S WEIR
`
`\r
`
`100;7,-99IMORE=YI..,
`exit.
`l2ef5d98alIDSDIVISIONj9d9fjBOBDIRl\r\r
`WEST;l,99;83,-55;2,-991..,
`91 WEST RAMP.
`l2ef5d98ajIDSDIVISIONl9d9flBOBDIRl\r\r 7)
`CANYON;l,99;-99,0;-26,-96;97,-211~
`Drive 0.8 miles.
`CANYON RD.
`l2ef5d98ajIDSDIVISIONl9d9flBOBDIRl\r\r 6)
`IARM=SOMERSET;SERRANO;l,99;98,-18;-97,22;-12,-991~
`onto SERRANO AVE.
`j0664j449cj2ef5d98ajIDSDIVISIONl9d9flBOBDjRl\r\r 5)
`
`0.2 Turn RIGHT
`
`D~ive 0.3 miles.
`
`\r
`
`J~ 24
`
`,,..___.,,
`
`J,· 23 ~
`
`,....__/
`
`J~ 22
`
`,.....___,
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`Q
`~
`
`~ .... Ul
`(J') =-~ ... ....
`
`N §
`
`► = ~
`
`,..N
`N
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`ANGELESIADDRESSl7530 ORANGETHORPE, BUENA PARKIADDRESSI0IMIARMS=YI~
`ll2ll7372l80DC099CIIDSDIVISIONl9DC6IBOBDJ I 11750 QUEENS RD, LOS
`
`J~2/
`
`~
`
`Drive a short distance to your destination
`
`\r
`
`9.0 Turn LEFT onto N
`
`SEI Information Technology/IDS Software version 5.48)\rlMORE=NI,
`Corp.\r(Database version lao0104_2.3.0, SEI/EnRoute Copyright 1993-1994
`SEI/EnRoute!\r\rDatabase Copyright 1992 -94 Navigation Technologies
`Thank you for using
`l2ef5d990IIDSDIVISIONj9daS!BOBDlRl\r
`at 2043 N SACRAMENTO ST.\rlARM=BRENTFORD;SACRAMENTO;l,99;-99,0I,
`SACRAMENTO ST.
`l2ef5d990IIDSDIVISIONj9daSjBOBDIRl\r\r 14)
`lARM=BRECKENRIDGE;BRENTFORD;l,99;99,-4;-4,-991,
`onto E BRENTFORD AVE.
`j0640j638bl2ef5d990IIDSDIVISIONl9daSIBOBDIRl\r\r 13)
`
`9.0 Turn RIGHT
`
`Drive 0.1 miles.
`
`\r
`
`✓~-2~
`
`,,...______,
`
`I062l159Sl80DC097BIIDSDIVISIONl9DASIBOBDI I [ [ [ I [ [ [MANEUVER=NEXT[ARMS=Yl0
`
`~ 25
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`....
`~ ... ....
`rJ) =(cid:173)~
`
`Q
`
`!.II
`
`N §
`
`► = ~
`
`,..N
`N
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`I062IEB9CIBODC09A6IIDSDIVISIONl9DDOIBOBDI I I I I I I I IMANEUVER=NEXTIARMS=YI~
`
`.,;f~ 29
`
`,,.....______,
`
`IARM=SUNSET;US-101
`
`Drive 24.5 miles.
`
`\r
`
`4.1 Turn RIGHT onto the US-
`
`IARM=QUEENS;SUNSET;l,99;-99,5;99,-
`0.5 Turn LEFT onto W SUNSET
`
`Drive 3.5 miles.
`
`\r
`
`SOUTH;l,99;92,-37;-2,-99IMORE=YI~
`101 SOUTH RAMP.
`l2ef5d9b8IIDSDIVISIONl9dc6IBOBDIRl\r\r 4)
`61~
`BLVD.
`l2ef5d9b8IIDSDIVISIONl9dc6IBOBDIRl\r\r 3)
`99;95,-301~
`QUEENS RD.
`Drive 0.5 miles.
`l2ef5d9b8IIDSDIVISIONl9dc6IBOBDIRl\r\r 2)
`distance.
`IARM=QUEENS;QUEENS;l,99;-64,761~
`Northwest on QUEENS RD towards FRANKLIN AVE.
`l2ef5d9b8IIDSDIVISIONl9dc6IBOBDl~l\r\r 1)
`miles, 51 rninutes.\rl~
`I0746.lfef212ef5d9b8IIDSDIVISIONl9dc6IBOBDIRl\r
`
`IARM=FRANKLIN;QUEENS;l,99;4,-
`0.1 Turn SLIGHT RIGHT onto
`
`Drive a short
`
`\r
`
`0.0 Start out going
`
`About 30.2
`
`\r
`
`,....__..,, J7 28
`
`

`

`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ .... Ul
`(J') =-~ ... ....
`
`Q
`N
`
`N §
`
`► = ~
`
`,..N
`N
`
`~ = fl"!',
`~ fl"!',
`•
`rJ1
`0 •
`
`28.7 Merge onto KNOTT AVE.
`
`28.6 Take the KNOTT
`
`IARM=SANTA ANA;ARTESIA
`
`.
`
`Drive 0.1 miles.
`
`\r
`
`-.ff JO
`,,...___.,,
`
`SEI Information Technology/IDS Software version 5.48)\rlMORE=NI~
`Corp.\r(Database version lao0104_2.3.0, SEI/EnRoute Copyright 1993-1994
`SEI/EnRoute!\r\rDatabase Copyright 1992 -94 Navigation Technologies
`Thank you for using
`l2ef5d9bbjIDSDIVISIONl9ddOIBOBDIRl\r
`7530 ORANGETHORPE AVE.\rjARM=KNOTT;ORANGETHORPE;l,99;-99,3;-4,-99;99,-ll~
`ORANGETHORPE AVE.
`j2ef5d9bbjIDSDIVISIONj9ddOIBOBDIRl\r\r 7) 29.7 Turn LEFT onto
`23,97;-97,-21;97,221~
`\r
`l2ef5d9bblIDSDIVISIONj9ddOIBOBDIRl\r\r 6)
`BLVD;l,99;77,-63;12,-99j~
`AVE exit.
`I0802ldb71j2ef5d9bbjIDSDIVISIONl9ddOI.BOBDIRl\r\r 5)
`
`joossj30ddl2efSd9f4jIDSDIVISIONl9eOBIBOBDIQINo of POis found:00000:
`
`IMORE=NI~
`
`:
`
`:
`
`I
`
`I
`
`-
`
`-
`
`~ J~.32
`
`ORANGEIADDRESSIHAPPYjRESTAURANTllOOIMIQUERY=POISI~
`ll04l5F3ll80DC09DFIIDSDIVISIONl9E08IBOBDI I 11855 w KATELLA AVE,
`
`J-~31
`,,...______,,
`
`Drive 0.5 miles to your destination at
`
`\r
`
`jARM=ARTESIA BLVD;KNOTT;l,99;19,-98;-
`
`Drive 1.0 miles.
`
`

`

`:
`
`I0704llc86.j2ef5daldlIDSDIVISIONl9e3llBOBDIQINo of POis found:00016:
`
`N §
`
`,..N
`N
`
`► = ~
`
`~ = fl"!'-
`~ fl"!'(cid:173)
`•
`rJ1
`0 •
`
`ORANGE I ADDRESS I BURGER I RESTAURANT 1·10 0 IM I QUERY= PO IS I ..,
`llOSjF24Sl80DCOA07IIDSDIVISIONl9E31lBOBDI I 11855 w KATELLA AVE,
`
`BLVD, FULLERTON:36:24034:0-0-459-108,4,2:38570:NIMORE=NI..,
`PARK:36:23606:0-0-223-137,4,1:46646:N;HUNGRY EEAR RESTAURANT:2219 N HARBOR
`
`;HUNGRY TIGER SEAFOOD RESTAURANT:€231 MANCHESTER BLVD, BUENA
`: -
`
`:
`
`I0269j523al2ef5daOclIDSDIVISIONl9e20IBOBDIQINo of POis found:00002:
`
`:
`
`:
`
`,
`
`,
`
`-
`
`-
`
`ORANGEIADDRESSIHUNGRYIRESTAURANTllOOIMIQUERY=PCISI,
`11oslE9C4leooco9F61IosorvrsioNl9E20IBOBDI I 11ass w KATELLA AVE,
`
`W LA HABRA BLVD, LA HABRA:36:24484:0-0-908-180,4,2:52112:NIMORE=YI~
`IMPERIAL HWY, LA HABRA:36:24435:0-0-919-268,4,-:46502:N;T ANDS BURGER:650
`BLVD, LA HABRA:36:24429:0-0-908-180,4,1:52112:N;IMPERIAL BURGERS:241 E
`LA HABRA:36:24408:0-0-229-139,4,1:50512:N;GEORGE'S BURGERS:601 W LA HABRA
`HABRA:36:24406:0-0-453-165,4,2:49052:N;C AND J BURGER:421 ELA HABRA BLVD,
`BEACH:36:24237:0-0-779-194,4,2:51444:N;BURGER KING:1236 W IMPERIAL HWY, LA
`82,4,1:43298:N;BURGER KING:19201 BROOKHURST ST, HUNTINGTON
`190,4,l:38608:N;BURGER KING:959 S COAST DR, COSTA MESA:36:23729:0-0-395-
`: ;BREA'S BEST BURGERS:707 S BREA BLVD, BREA:36:23589:0-0-230-
`: -
`
`\0 ... ...
`~ = .....:a
`
`-..
`
`-..
`e,...
`
`~ ....
`
`Ul
`
`Q
`~
`
`(J') =-~ ... ....
`
`:
`
`,
`
`,
`
`-
`
`-
`
`:JC,
`
`~·
`~ ±-.
`
`~-
`~ J. :3S
`
`J~34
`
`~
`
`~ ..:f-1J) :n
`
`

`

`.&;:.
`.&;:.
`"" \0
`......:.J
`0
`"" ~
`0"-,
`
`~ .... u,
`Q
`.,::.
`....
`~ ....
`c.,) =
`
`N §
`
`,.N
`N
`~
`► C
`
`~ = .....
`~ .....
`
`•
`'J).
`~ •
`
`WESTMINSTER: 36: 27186 :' 0-0-1197-216, 4, 2: 4 914 0: NI MORE=N 1,
`315,4,2:40114:N;IN-N-OITT BURGER:6292 WESTMINSTER BLVD,
`BURGER:13891 BEACH BLVD, WESTMINSTER:36:27177:0-0-199-
`NEWPORT AVE, TUSTIN:36:26864:0-0-871-69,4,1:28304:N;BOB'S
`SANTA ANA:36:26543:0-0-797-207,4,l:35830:N;BURGER KING:13431
`ANA:36:26542:0-0-396-lll,4,1:36418:N;BURGER KING:601 E DYER RD,
`137,4,1:24590:~;BURGER KING:2850 S BRISTOL ST, SANTA
`OUT BURGER:825 W CHAPMAN AVE, PLACENTIA:36:26314:0-0-959-
`KING:245 N CITRUS ST, ORANGE:36:26021:0-0-829-124,4,l:6189:N;IN-N(cid:173)
`VALLEY VIEW ST, LA PALMA:36:24514:0-0-1210-243,4,2:50592:N;BURGER
`I0643l833el2efSdalflIDSDIVISIONj9e34jBOBDIOIIN-N-OUT BURGER:7926
`
`I0SSIASCll80DC0A0BIIDSDIVISIONl9E34IBOBDI I I I I I II IMANEUVER=NEXTI,
`
`~ -f-UJ!-JC)
`
`J~.37
`,,___,
`
`

`

`U.S. Patent
`
`Aug. 22, 2000
`
`Sheet 15 of 15
`
`6,107,944
`
`TOKEN ENC.LISH TABLE
`MAKE A u
`TURN AT
`
`1
`
`2
`
`3
`
`SPANISH TABLE
`
`GERMAN TABLE
`
`AN DER KRE:UZUNG
`HACA UNA
`. VUELTA EN MIT
`81TTE
`u £N
`£IN£ KfHRTW£NDU~
`MACHEN •
`. .
`CAMBIA EL __ UND£RT DEN
`CHANGES
`NAMEN :zu --·
`NOMBRE A
`NAME TO
`TURN LEFT ON Di;: VUELTA A LA AUF _
`LINKS
`IZQUIERDA E:N A681EGEN UNO
`ANO DRIVE
`__ Y MAN£J£
`ME.ILEN
`MILES.
`MILLA$. WEITERFUHREN.
`
`~
`
`40
`
`5S
`
`REQUEST STRIP(cid:173)
`MAP FOR PARTS
`NOT ADf:QUATEL Y
`COVERED.
`
`RECEIVE STRIP(cid:173)
`MAP INFORMATION
`FROM 6AS£ UNIT.
`
`51
`
`52
`
`53
`
`'REQUEST ROUT£
`FROM
`BAS£ UNIT.
`
`RECEIVE ROUTE
`INFORMATION FROM
`BASE UNIT.
`
`COMPARE . RECEIVED
`ROUTE: WITH
`ONBOARD MAP
`
`54
`
`N
`RT NOT YfS
`QUATELY ____ _,
`VERED
`?
`
`NO
`
`DONE.
`
`S7
`
`

`

`6,107,944
`
`1
`ELECTRONIC NAVIGATION SYSTEM AND
`METHOD
`
`REFERENCE TO RELATED APPLIC~rIONS
`
`1l1e present application is a continuation of Ser. No.
`08/494,198, filed Jun. 23, 1995, now U.S. Pat. No. 5,808,
`S66, which was a continuation-in-part of Ser. No. 08/ 265,
`094, filed Jun. 24, 1994, now U.S. Pat. No. 5,543,789, the
`entire contents of which are incorporated by reference
`herein.
`
`REFERENCE TO MICROFICHE APPENDIX
`
`5
`
`2
`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-
`terns 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
`database on CD-ROM or other media becomes out of date.
`lo addition, when a database is compiled, it may include
`10 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(cid:173)
`rect or outdated information in the database can lead to
`errors when calculating routes. When an out-of-date data-
`15 base doe.s 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(cid:173)
`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
`30 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
`35 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
`45 beacons. The navigational information thus provided forms
`a generally inefficient routing path from origin to destina(cid:173)
`tion. In addition, such a system does not provide the capa(cid:173)
`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(cid:173)
`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,
`55 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
`60 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 wirele.ss, wire line,
`and optical channels. There is a still further need for a data
`65 communication protocol for providing accurate, reliable
`communication in such a system, independent of hardware
`configuration and in a compact form.
`
`Included with this specification is a microfiche appendix
`including 3 sheeLs 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 tbe patent document or tbe patent
`disclosure, as it appears in tbe Patent and Trademark Office 20
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`The invention relates generally to a system and method 25
`for providing route guidance and tracking information and
`other information from a base unit to a mobile unit over
`wireless, ,1/ireline, 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 40
`points of interest, directions to points of interest, and direc(cid:173)
`tions between a specified origin and a destination. An
`on-board computer calculates route guidance infom1ation
`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(cid:173)
`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, 50
`street names, navigation anributes, such as tum 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(cid:173)
`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
`
`

`

`3
`SUMMARY OF THE INVENTION
`
`6,107,944
`
`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
`5 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 flowchart used for explaining operation of a
`stripmap request feature of the invention.
`
`An object of the invention is to provide a method and
`system for transmitting route guidance and other informa(cid:173)
`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(cid:173)
`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 10
`user at the remote unit.
`Another object of the invention is to provide a method and
`system for transmitting route guidance and other informa(cid:173)
`tion from a base unit Lo a remote unit in which the amount
`of information available at a remote unit can be expanded by 15
`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(cid:173)
`ing route guidance and other information from a base unit to 20
`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(cid:173)
`lated at the base unit in response to the query, using a large 25
`up-to-date database located at the base unit. A response to
`the query is formatted at the base unit, the response includ(cid:173)
`ing route guidance information. The response is then trans(cid:173)
`mitted from the base unit to the remote unit for display.
`The transmission is made in a compact form through the 30
`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 transmis.sion 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(cid:173)
`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 50
`will be apparent from the detailed description set forth
`below.
`
`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(