VWGoA - Ex. 1004
`Volkswagen Group of America, Inc., Petitioner
`
`1
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 1 0131
`
`US 6,707,421 B1
`
`
`
`
`
`Q;
`
`
` $9
`
`CPS SATELLITES
`
`
`
`140
`
`122
`
`'
`
`120
`
`CENTRAUZED
`seavea
`
`‘I
`
`130
`
`j
`EXTERNAL
`INFORMATION
`SYSTEM
`
`SERVER
`7 I M”
`I‘
`PROVIDER
`
`SYSTEM
`
`60
`
`T -
`
`~
`
`100
`
`A AJ’.
`I] IN VEHICLE
`'05
`SYSTEM 0
`ALL
`105
`001
`F [N VEHICLE
`1.‘ SYSTEM
`4.!
`® SYSTEM
`
`IN VEHICLE 105
`
`-:j—_———..:
`
`100
`
`2
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 2 0131
`
`US 6,707,421 B1
`
`sAraunes,140
`
`sazvax SYSTEM, 125
`
`V COMMUNICATION V
`
`svsrem
`
`
`_
`
`_
`
`260
`
`' cmuma
`TRANSCEIVER
`
`»
`
`V
`
`'
`’ ”"”°5‘T
`
`250
`
`
`
`- MAGNETIC
`commss
`
`IN-VEHICLE SYSTEM
`
`L5.
`
`3
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 3 of 31
`
`US 6,707,421 B1
`
`Turn On:
`Exit .23
`I-94 Freeway West
`‘ 0.8 _ miles
`
`'
`
`SELECT STREET
`1
`
`4
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 4 0131
`
`US 6,707,421 B1
`
`
`PUBLIC
`SWITCHED
`CELLULAR
`TELEPHONE
`
`TELEPHONE‘
`NETWORK
` cps SATELLITES,
`NETWORK
`
`(PSTN)
`140
`
`
`
`340
`
`
`
`
`
`TO VEHICLES,
`
`100
`
`TELEPHONE
`INTERFACE
`
`SEEVER COMPUTER
`
`
`
`312
`
`314
`
`P
`
`5
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 5 of 31
`
`US 6,707,421 B1
`
`CPS
`RECEIVER
`252
`
`CELLULAR
`TRANSCEIVER
`254
`
`
`
`.
`
`COMMUNICATION , INTERFACE
`
`
`
`NAVIGATION
`APPLICATION
`
`-
`
`VEHICLE INTERFACE
`
`.
`
` 410-.
`
`
`
`WORKING
`
`STORAGE
`
`SENSORS, VEHICLE
`230
`- SYSTEMS,
`270
`
`I/O
`DEVICES.
`240
`
`FIG. 4A
`
`IN-VEHICLE
`
`DATABASE
`
`STATIC sTOI2AcE
`
`6
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 6 of 31
`
`US 6,707,421 B1
`
`TO TELEPHONE
`
`TO GPS
`
`INTERFACE, 320
`
`RECEIVER, 325
`
`COMMUNICATION"
`INTERFACE
`
`; cps
`INTERFACE ‘
`
`
`
`514
`
`
`
`NAVIGATION
`I APPLICATION
`
`DATA ‘INTERFACE 4
`
`'
`
`_
`
`
`SESXER
`"'§},"é%‘s"’
`A TRAFFIC
`DATABASE
`~
`DATABASE
`A
`I
`
`
`
`
`
`
`
`
`
`
`DATABASE
`
`IN-VEHICLE '
`DATABASE
`
`
`
`
`
`MAP PROCESSOR
`
`360
`
`FROM MAP
`
`PROVIDER, 160
`
`FROM EXTERNAL
`INFORMATION
`
`SYSTEMS, 130
`
`FIG. 5
`
`7
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 7 of 31
`
`US 6,707,421 B1
`
`HIGHWAY
`
`
`
`8
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 8 of 31
`
`US 6,707,421 B1
`
`7.9.9
`
`711
`
`712
`
`713
`
`715
`
`1 716
`
`9
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 9 of 31
`
`US 6,707,421 B1
`
`692
`
`FIG. 8
`
`10
`
`10
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 10 0131
`
`US 6,707,421 B1
`
`11
`
`11
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 11 0131
`
`US 6,707,421 B1
`
`1000
`'_
`
`712
`
`715
`713
`i_I-_'—l—'fl‘—-
`
`692
`E
`
`°
`
`°
`
`718
`I,’
`
`783
`
`.
`
`F1012,‘
`
`_
`
`722
`
`I/I
`
`.
`
`735 / 785
`
`-
`
`1
`
`‘
`
`781
`
`,1,/101°
`
`/
`
`780
`, /
`/
`
`732
`
`G
`
`'Z‘
`
`//
`
`.
`
`7'33
`5 /
`/'//
`
`1:1..-—
`
`12
`
`‘ 792
`L/
`I.
`
`_
`
`742
`
`*“'"*7'
`{.4
`690
`
`1 l
`
`O
`
`‘1
`
`752
`
`752
`
`°
`
`772
`
`.
`
`12
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 12 0131
`
`US 6,707,421 B1
`
`AddressC1tyState
`
`1110
`
`Addressstreet
`
` .
`
`A
`1118. m2
`
`.
`"1116,
`
`1114
`
`1150
`
`
`-II: ==—
`_ 1119 . nu- __
`
`-
`
`1120
`County’
`'
`' _
`1153
`1122 Ii
`H ,
`_
`Addresskange 1180
`
`-.
`
`C1lyStat1e
`1
`étreetRecord
`1160
`H 1132
`1164 2
`1166
`-I
`1353’ 1162
`"40
`,
`State K
` 1142
`StreetName
`
`1.
`
`1
`
`1170
`
`1172
`
`13
`
`13
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 13 0131
`
`US 6,707,421 B1
`
`TEXT TABLE
`
`14
`
`14
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 14 0131
`
`US 6,707,421 B1
`
`15
`
`15
`
`

`
`S.U
`
`a
`
`r._m
`
`4002(091
`
`13fl.0
`
`1B124,707,6
`
`PmvoZ.8mmE
`
`M2%.
`mm—.U_u_Iv:E3__
`
`
`99
`
`99
`
`
`e..e...
`..«mm%was..
`m5%..a:2,
`
`OQS
`
`
`
`.m.:mmm...m:ut<«mm.omm—T_
`
`
`
`SU.~:_on_mQm_._mv_c_.__u._oum~__wm:mO02.
`
`
`
`
`
`
`16
`
`16
`
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 16 Of 31
`
`US 6,707,421 B1
`
`'P0|TYPe
`
`1410
`
`1414
`
`- 1415 ’
`
`.
`
`1 type
`
`offset
`
`1412
`‘
`
`1413
`
`_n-5-0\I
`
`PO|Types
`
`1420
`
`1
`
`FIG. 14
`
`PO|NameCity
`1430 ,-
`‘
`1434
`.1436 q
`1433'’
`1440
`_
`mo
`citystate
`of set a “32
`C"Y5‘“e
`1=—j=E= 1:13. -
`1 Z jI
`1-—jI;.I_"' _—
`
`—U
`“'1
`POlList 1450
`1460’ 1452
`1453
`I
`1456
`1454
`@141/Ions "
`
`1160
`
`S"°°"‘°“°"'
`
`1-
`
`17
`
`17
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 17 of 31
`
`US 6,707,421 B1
`
`1501
`
`Plan Route (|n-Vehicle)i-
`
`1502
`
`1503
`
`1504
`
`1505
`
`1505
`
`1507
`
`1508
`
`1509
`
`1510
`
`1511
`
`1512
`
`1513
`
`Accept Destination Specification from Operator
`
`Determine Current Location Data
`
`Establish Communication Session with Server
`
`Send Destination Specification and Current Location Data to Server
`
`IF Destination Specification Requires Server Interaction THEN
`
`Accept Secondary Destination Specification Data from Server
`
`Accept Secondary Destination Specification from Operator
`
`' Send Secondary Destination Specification to Server
`
`END IF
`
`Wait for Server Response
`
`Receive Planned Route, Spot Map, and Differential GPS Data from Sewer
`
`Close Communication Session with Server
`
`FIG. 15A
`
`18
`
`18
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 18 0131
`
`US 6,707,421 B1
`
`1551
`
`Plan Route (Server):
`
`1552
`
`1553
`
`-1554
`
`1555
`
`1556
`
`1557
`
`1558
`
`1559
`
`1560
`
`1561
`
`1562
`
`1563
`
`1564
`
`Acceptcornmunication Session with Vehicle
`
`Receive Destination Specification and Current Location Data from Vehicle
`
`Determine DGPS Correction Data
`
`Determine Vehicle Location
`
`IF Destination Specification Requires Further Operator lnput THEN
`
`Determine Secondary Destination Specification Data
`
`Send Secondary Destination Specification Data to Vehicle
`
`Receive Secondary Destination Specifi_cation from Vehicle
`
`END IF
`
`Determine Planned Route to Specified Destination
`
`Detennine Spot Map near Vehicle Location
`
`Send Planned Route, Spot Map, and DGPS Data to Vehicle
`
`Close Communication Session with Vehicle
`
`FIG. 15B
`
`19
`
`19
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 19 0131
`
`US 6,707,421 B1
`
`1601
`
`Startup Maneuvers:
`
`1602
`
`1603
`
`1604
`1605
`
`1606
`
`‘Initialize Estimated Location using Differential GPS Data
`
`WHlLE Estimated Location is not at a Point of the Planned Route 00
`
`Track Estimated Location using (D)GPS Data-
`Display Spot Map and Estimated Location on Display‘
`
`END WHlLE
`
`FIG. 16
`
`1301
`
`Replan Route:
`
`1802
`
`1803
`
`1804
`
`1305
`
`1806
`
`1807
`
`Estimate Vehicle Location of Main Roads Network using
`
`Dead-Reconing Location
`
`Calculate Best Route to a Maneuver or Way Point on the Previous
`
`Planned Route
`
`Replace Planned Route with Newly Calculated Route
`
`GOTO Follow Route
`
`FIG. 18
`
`20
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 20 of 31
`
`US 6,707,421 B1
`
`1701
`
`1702
`
`1703
`
`1704
`
`1705
`
`1705
`
`1707
`
`1708
`
`1709
`
`1710
`
`1711
`
`1712
`
`1713
`
`1714
`
`1715
`
`1716
`
`1717
`
`1718
`
`1719
`
`1720
`
`1721
`
`1722
`
`1723
`
`1724
`
`1725
`
`Follow Route:
`
`FOR Each Link on Planned Route DO
`
`At Initial Maneuver Initialize Off-Route Tolerance
`
`WHILE Vehicle Is Travelling to the Next Maneuver Point 00
`
`Increase Off-Route Tolerance
`
`Track Dead-Reckoning Location
`
`Track (D)GPS Location
`
`IF (Dead-Reckoning Location is more than Off-Route Tolerance
`
`from (D)GPS Location THEN
`
`GOTO Replan Route
`
`END IF
`
`IF Dead-Reckoning Location is within Maneuver
`
`Notification Vtfindow THEN
`
`Notify Operator of Next Maneuver
`
`END IF
`
`IF Dead-Reckoning Location is within Maneuver
`
`.
`
`Detection Window THEN
`
`IF Next Maneuver is Detected THEN
`
`Update Dead-Reckoning Location
`
`Update DGPS Data
`
`END IF
`
`END IF
`
`UNTIL Maneuver was Detected OR
`
`Vehicle Leaves Maneuver Detection Window
`
`UNTIL Destination is Reached
`
`FIG. 17
`
`21
`
`21
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 21 0131
`
`US 6,707,421 B1
`
`SERVER ‘SYSTEM.
`
`
`
`NAVIGATION 0
`
`APPLICATION
`
` TRAFFIC
`,
`
`DATABASE
`
`
`
` EXTERNAL
`
`INFORMATION
`SYSTEM
`
`
`
` NAVIGATION
`
`APPLICATION
`
`
`
`
`LIINK
`
`SPEED
`DATABASE
`
`‘IN-VEHICLE. “SYSTEM
`
`
`
`FIG. 19
`
`22
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 22 0131
`
`US 6,707,421 B1
`
`ONBOARD
`COMPUTER
`
`STORAGE
`
`' STATIC
`
`'
`
`
`
`STATIC
`STORAGE
`
`
`
`FIG. 20A
`
`2030
`
`
`105 EQUIPMENT
`
`
`
`
`
`SERVTCE
`
`IN-TVEHICLE SYSTEM
`
`ONBOARD
`COMPUTER
`
`
`
`
`2031
`
` PERSONAL
`COMPUTER
`2040
`
`23
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 23 0131
`
`US 6,707,421 B1
`
`105
`
`0
`
`
`
`SERVER
`SYSTE_M ,
`
`
` IN-VEHICLE SYSTEM '
`
`
`
`ONBOARD 210
`. COMPUTER .
`
`125
`
`FIG. 20C
`
`24
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 24 0131
`
`US 6,707,421 B1
`
`120
`
`
`
`SERVER
`SYSTEM
`
`2110
`TELEPHONE/
`OPERATOR
`
`VEHICLE ID, /
`LOCATlOy
`
`VOICE
`
`VEHICLE -
`
`.
`
`IN-VEHICLE
`
`SYSTEM
`
` CENTRALIZED SERVER
`
`
`OPERATOR
`
`FIG. 21A
`
`
`
`CENTRALIZED SERVER
`
`120
`FIG. 21B
`
`
`
`COMMANDS
`
`/
`
`SERVER
`SYSTEM.
`
`125
`
`2110
`TELEPHONE J
`OPERATOR
`
`340
`
`|N—VEH|CLE
`SYSTEM
`
`
`
`
`OPERATOR
`
`25
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 25 0131
`
`US 6,707,421 B1
`
`TO VEHICLES
`
`SERVER SYSTEM__
`
`2252
`
`320
`
`
`
`2210
`
`TELEPHONE
`INT
`‘
`ERFACE
`
`GATEWAY
`SYSTEM
`
`
`
`
`
`COMMUNICATION
`-SYSTEM
`'
`
`NEWS
`SYSTEM
`
`
`
`2220
`ADMINISTRATIVE
`SYSTEM
`
`2230
`REMOTE
`CONFIGURATION
`
`
`
`
`
`1)
`userz
`
`PROFILES
`
`
`
`TO INTERNET
`
`FIG. 22
`
`
`
`
`
`
`
`2250
`
`SYSTEM
`
`
`
`MAP
`PROVIDER
`
`TRAFFIC
`INFO.
`PROVIDER
`
`
`
`2252
`E MAIL
`SYSTEM
`
`
`
`2264
`
`2272
`
`NEWS
`
`SERWCE
`
`
`
`26
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 26 of 31
`
`US 6,707,421 B1
`
`232°
`
`235°
`
`HANDSET
`MODULE
`
`
`
`
`
`DATA
`
`AUDIO
`2322
`
`OUTPUT
`
`%
`
`FIG. 23A
`
`27
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 27 0131
`
`US 6,707,421 B1
`
`23 20
`
`2330
`
`'. MODULE
`
`CELLULAR PHONE
`MODULE
`
`
`' GPS RECEIVER
`
`2352
`
`2364
`
`2366
`
`
`
`
`
`HANDSET ’
`MODULE
`-
`
`
`
`.254
`CELLULAR
`TRANSCHVER
`
`DATA
`
`
`ONBOARD COMPUTER‘
`
`OUTPUT
`
`
`
`FIG. 23B
`
`DISPLAY
`
`28
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 28 0131
`
`US 6,707,421 B1
`
`
`
`
`_ DISPLAY
`FUNCTION
`
`MENU A
`
`
`2370
`
`
`
`SELECT
`"TRAFFlC'
`
`,
`
`-
`SELECT
`‘ROADSIDE ASS'T"
`
`I
`
`
`
`SELECT
`‘NAVIGATION’
`
`2376
`
`_ INPUT
`DESTINATION
`
`
`
`2378
`
`
`
`DISPLAY
`TRIP MENU
`
`
`
`
`
`
`PREVIEVV
`ROUTE
`
`
`
`
`
`
`
`
`
`
`
`DlSPLAY/
`PROMPT
`MANEUVER
`
`SELECT
`"TRIPS"
`
`_
`
`-
`
`' SELECT
`‘NEW TRIP"
`
`-
`
`
`
`"SELECT
`DISPLAY
`CROSS 1st
`
`TRIP NAMES
`STREETS
`AND TIMES
`
`
`SELECT
`ROAD
`SEGMENT
`
`SELECT
`' CROSS LAST
`STREET
`
`FIG. 23C
`
`29
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 29 0131
`
`US 6,707,421 B1
`
`
`
`
` I60
`
`0
`MAP.
`INFORMATION
`
`- MAP '
`PROVIDER
`
`
`
`FIG. 24
`
`wumsss
`
`
`
`C?¢Asb_rri;Jh|A~l|CAT|ON
`
`125
`
`
`3533
`
`.
`
`F — — -I. —-L — .— _- —‘
`I 2410 I
`I';;gg~AL
`°
`1
`
`L
`
`30
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 30 of 31
`
`US 6,707,421 B1
`
`
`
`DESTINATION
`COORDINATES
`
`
`
`' KEYPAD
`
`‘TURN RIGHT
`IN 0.1 MILES
`ONTO MAPLE
`ROAD‘
`
`FIG. 25
`
`OVERLAY
`
`2550
`
`31
`
`

`
`U.S. Patent
`
`Mar. 16, 2004
`
`Sheet 31 0131
`
`US 6,707,421 B1
`
`
`
` 2525
`
`5”
`
`.WM
`1NPUT/OUTPUT
`
`‘
`
`V
`
`—-—c— _u- -:3.
`
`240
`
`2515
`
`-_
`
`saecroa
`swnaws
`
`
`
`
`
`
`
`%wP**‘“*'
`‘-1
`PACER
`'
`
`-—.-—-.——.;.
`
`2600
`
`FIG. 26A
`
`2620
`
`2622
`
`2600
`
`32
`
`

`
`US 6,707,421 B1
`
`1
`DRIVER INFORMATION SYSTEM
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of U.S. Appli-
`cation No. 09/136,868, filed Aug. 19, 1998, which claimed
`the benefit of U.S. Provisional Application No. 60/056,150,
`filed Aug. 19, 1997, and also claims the benefit of U.S.
`Provisional Application No. 60/104,275, filed Oct. 14, 1998.
`
`BACKGROUND
`
`This invention relates to an information system for motor
`vehicles.
`
`Vehicle information systems have been developed that
`provide various types of information to operators of those
`vehicles. In particular, navigation systems have been devel-
`oped. One type of navigation system, an autonomous navi-
`gation system, uses an on-board map, typically stored on a
`removable medium such as a compact optical disk (e.g.,
`CD-ROM). The navigation system uses the on-board map to
`plan a route from a starting point to a destination, which is
`specified by the operator of the vehicle. Updating an autono-
`mous system’s map,
`for example to add or correct
`information,
`typically involves replacing the removable
`medium.
`
`inputs the
`In some navigation systems the operator
`desired destination (and the current location, if required by
`the system) by entering a spelling of the destination. Some
`systems also allow an operator to select from a stored list of
`“points of interest,” such as a list of gas stations or restau-
`rants. Once the operator inputs the destination, the system
`plans a route along the road network to the destination. The
`route is typically planned to provide a shortest distance or to
`try to provide the shortest travel time. Once the route is
`planned, the operator is guided by the system along the
`route.
`
`Various approaches to route guidance have been used. A
`particularly simple approach is to provide the operator with
`a sequence of discrete instructions, for instance, at intersec-
`tions where the operator must turn from one street onto
`another. The operator indicates when he or she is ready for
`the next instruction. For example, the instructions are pro-
`vided as an audio output, and the operator says “next” when
`ready for another instruction.
`Another approach to route guidance uses a displayed map
`on which the planned route and the vehicle’s location are
`dynamically displayed. The operator uses the map to decide
`when and where to turn in order to follow the planned route.
`Some guidance approaches are aided by in-vehicle sen-
`sors that are used to estimate the location of the vehicle. For
`
`instance, a magnetic compass is used to estimate the direc-
`tion of travel, and a velocity sensor is used to estimate the
`distance traveled. In addition, the location of the vehicle can
`be estimated using the Global Positioning System (GPS). In
`GPS, multiple satellites emit signals that allow an in-vehicle
`GPS receiver to estimate its absolute location.
`
`Other types of vehicle information systems have also been
`developed. In some systems, traffic related information, such
`as traffic advisories,
`is broadcast
`to specially equipped
`in-vehicle radio receivers.
`
`SUMMARY
`
`In one aspect, in general, the invention is a driver infor-
`mation system that includes a handset module, and a com-
`munication module, for example, a handset module and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`communication module that make up a modular wireless
`telephone. The information system also includes a computer
`coupled between the handset module and the communica-
`tion module. The handset module includes a display, for
`example, a small alphanumeric display, a keyboard, for
`example a numeric telephone keyboard with function keys,
`and an audio device for receiving and playing acoustic
`information, such as a microphone and a speaker. The
`communication module includes a wireless communication
`
`interface for accepting data signals from a server. The
`computer that is coupled to the handset module and to the
`communication module is programmed to perform the func-
`tions of (a) coupling the handset module to the communi-
`cation module to provide telephone communication services
`to a user of the handset module, including accepting tele-
`phone dialing commands entered by the user on the key-
`board and coupling the audio device to a telephone com-
`munication channel through the communication module, (b)
`accepting driver information commands entered by the user
`through the handset module, for example using the keypad
`or speaking a command that is interpreted by a speech
`recognition system, (c) retrieving information through the
`wireless communication interface from the server in
`
`response to the driver information commands, and (d) pre-
`senting the retrieved information on the handset module, for
`example by presenting the information on the display of the
`handset, or by playing the information on the audio device
`of the handset. The information system can additionally
`include a positioning system coupled to the computer, and
`then the computer is further programmed to perform the
`functions of (e) accepting a geographic position of the
`system from the positioning system, and
`providing the
`position to the server through the communication interface.
`The computer may be additionally coupled to a display for
`presenting graphical information to the user, and to other
`devices, for example over an in-vehicle data bus.
`In another aspect, in general, the invention is a portable
`information system that includes multiple switches for ini-
`tiating access to a remote server in one of a corresponding
`plurality of operating modes. For instance the system can
`include switches, or other types of input devices, for initi-
`ating traffic information,
`roadside assistance, personal
`information, or emergency modes. The system includes a
`positioning system for generating position data related to a
`geographic location of the system, and a wireless commu-
`nication device, such as a cellular telephone transceiver,
`coupled to the switches and to the positioning system for
`passing the generated position data to a remote server in
`response to a signal from the switches. The wireless com-
`munication device then receives information from the
`
`server. The system also includes an audio output device,
`such as a speaker, coupled to the wireless communication
`device for presenting the received information. The system
`can also include a storage for a unique identification of the
`information system. This identification is passed to the
`remote server through the wireless communication device.
`In another aspect, the invention is an in-vehicle naviga-
`tion system for providing route information through a road
`network. The system includes a first stored database, which
`may be provided on a removable storage medium such as a
`CD-ROM, includes information related to roads in the road
`network within a first geographic area. The system option-
`ally includes a second stored database that includes infor-
`mation related to major roads in the road network within a
`second geographic area. The first geographic area includes a
`common area within the second geographic area, and the
`first stored database includes information about roads in the
`
`33
`
`

`
`US 6,707,421 B1
`
`common area that
`
`is not
`
`3
`included in the second stored
`
`database. The system also includes an onboard computer
`programmed to perform the functions of (a) accepting a
`specification of a starting and an ending location in the road
`network, (b) if the starting and the ending locations are
`within the first geographic area, planning a route through the
`road network from the starting to the ending locations, and
`(c) if the starting or the ending locations are not within the
`first geographic area, communicating with a remote server
`computer to retrieve information related to a route through
`the road network from the starting to the ending locations.
`This system has the advantage that it can function autono-
`mously within the first geographic area without necessarily
`requiring the assistance of the remote server. The system can
`also provide navigation functions outside the first
`geographic, for example, by retrieving route information
`from the remote server for portions of a route outside the
`first geographic area.
`In another aspect, in general, the invention is a navigation
`system. The system includes a printed map illustrating a
`geographic area, including a representation of a roadway
`network in the geographic area. The map includes
`annotations, such as coordinates or codes, identifying geo-
`graphic features, such as points of interest or road segments,
`in the geographic area. The system also includes an input
`device, such as a keypad on a telephone device, for accept-
`ing an annotation from the printed map identifying a chosen
`geographic feature, an onboard computer for receiving the
`accepted annotation and providing a planned route to the
`chosen geographic feature through the roadway network,
`and an output device, such as the display on a telephone
`handset, for presenting the planned route information. This
`system has an advantage of allowing simplified user input by
`having the user determine short encodings of locations from
`the printed map. Also, simplified output can also refer to the
`annotations on the printed map, thereby allowing use of a
`limited output device.
`the system is a vehicle
`in general,
`In another aspect,
`information system that includes a translucent overlay, for
`example including a printed map illustrating a roadway
`network or other geographic markers, and a display for
`accepting the translucent overlay. The display includes mul-
`tiple controlled light sources that when activated are visible
`through the accepted overlay. An onboard computer is
`programmed to provide route information by activating one
`or more of the controlled light sources.
`Other features and advantages of the invention will be
`apparent from the following description, and from the
`claims.
`
`DESCRIPTION OF DRAWINGS
`
`FIG. 1 is a block diagram of a vehicle navigation system;
`FIG. 2 is a block diagram of in-vehicle components of the
`system;
`FIGS. 2A—C show an integrated input/output device;
`FIG. 3 is a block diagram including components of a
`server system;
`FIGS. 4A—B show an in-vehicle system software archi-
`tecture;
`FIG. 5 is a block diagram of a server system software
`architecture;
`FIG. 6 is a schematic map showing the road network in an
`exemplary region;
`FIG. 7 is a graph representation of the road network in the
`exemplary region;
`
`is
`
`4
`FIG. 8 illustrates an exemplary planned route that
`downloaded from a server system to a vehicle;
`FIG. 9 is an exemplary spot map that is downloaded from
`a server system to a vehicle;
`FIG. 10 is a main roads map that is preloaded in a vehicle;
`FIG. 11 shows data structures of an in-vehicle database;
`FIG. 12 shows the structure of text tables in the in-vehicle
`database;
`FIG. 13A shows a representative link of a main roads
`network;
`FIG. 13B shows data structures of an in-vehicle database
`
`encoding a main roads network;
`FIG. 14 shows elements of an in-vehicle database which
`encode Points of Interest information;
`FIG. 15A is a pseudocode listing of an in-vehicle route
`planning procedure;
`FIG. 15B is a pseudocode listing of a server route
`planning procedure;
`FIG. 16 is a pseudocode listing of a startup maneuver
`procedure;
`FIG. 17 is a pseudocode listing of a route following
`procedure;
`FIG. 18 is a pseudocode listing of a route replanning
`procedure;
`FIG. 19 illustrates a extensible server architecture;
`FIGS. 20A—20C illustrate approaches to updating an
`in-vehicle system;
`FIGS. 21A—21B illustrate additional information services
`
`provided by a server system;
`FIG. 22 is a block diagram of an extensible server system;
`and
`
`FIG. 23A is block diagram of a standard module cellular
`telephone architecture;
`FIG. 23B is a block diagram in which an onboard com-
`puter is coupled between a handset module and a cellular
`phone module;
`FIG. 23C is a flow chart illustrating a menu-based user
`interface presented using the handset module;
`FIG. 24 illustrates a hybrid driver information system;
`FIG. 25 illustrates use of printed maps in a user interface;
`FIG. 26A shows the logical blocks of an information pod;
`and
`
`FIG. 26B illustrates the physical arrangement of an infor-
`mation pod.
`
`DESCRIPTION
`
`1 OVERVIEW (FIGS. 1. 6-10)
`1.1 Architecture (FIG. 1)
`Referring to FIG. 1, a vehicle information system pro-
`vides services, including a route planning and guidance (i.e.,
`a “navigation”) service, to the operators of multiple vehicles
`100, which are free to drive throughout a wide geographic
`area. To provide these services to the operators of the
`vehicles,
`the vehicle information system performs some
`functions in a server system 125 at a centralized server 120
`that is at a fixed location, and other functions in in-vehicle
`systems 105 installed in each of the vehicles 100. The
`vehicle information system also includes a positioning sys-
`tem that provides a reference for estimating the locations of
`vehicles 100 in absolute terms (i.e., in terms of their latitudes
`and longitudes). In particular, Global Positioning System
`(GPS) satellites 140 provide signals that when received at
`the vehicles enable the in-vehicle systems to estimate their
`locations.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`34
`
`

`
`US 6,707,421 B1
`
`5
`The navigation service of the vehicle information system
`as a whole, which are provided through a combination of
`functions that are performed by server system 125 and by an
`in-vehicle system 105, enable an operator of a vehicle to
`specify a desired destination, and then to be guided by the
`system to that destination while driving the vehicle.
`In-vehicle system 105 tracks (i.e., repeatedly estimates) the
`position of the vehicle as it travels to the desired destination,
`and provides instructions to the operator to guide the opera-
`tor to the desired destination. For instance, in-vehicle system
`105 provides an instruction to make a turn at an upcoming
`intersection while the vehicle is approaching the intersec-
`tion. Also, in-vehicle system 105 typically determines when
`the operator has made an error and the vehicle is off a
`planned route. If the vehicle is off route, in-vehicle system
`105 provides the operator with instructions to continue to
`guide the vehicle to the destination despite the error.
`Server system 125 provides various services to in-vehicle
`system 105,
`in a “client-server” arrangement
`in which
`in-vehicle systems 105 request services from server system
`125. For instance, a route planning function is performed by
`server system 125 at the request of in-vehicle system 105
`while route guidance functions are performed by in-vehicle
`system 105.
`In-vehicle systems 105 are coupled to server system 125
`by wireless communication links. In particular, in-vehicle
`systems 105 at times communicate with server system 125
`over signal paths 110 using modulated data signals that are
`passed over a standard analog cellular telephone system (i.e.,
`using the Advanced Mobile Phone Service (AMPS)
`standard). An in-vehicle system 105 typically operates in an
`autonomous mode after an initial exchange with server
`system 125. During the initial exchange, a starting location
`(or other location-related data), speed and heading, and a
`desired destination are uploaded from the in-vehicle system
`to the server system and then a planned route is downloaded
`from the server system to the in-vehicle system. After
`planned route information is downloaded to the vehicle from
`the server system, the in-vehicle system does not require
`further interaction with the server system to operate in its
`autonomous route guidance mode. While in the autonomous
`route guidance mode the in-vehicle system can recover from
`an operator going off the planned route without necessarily
`requiring further communication with the server system.
`In-vehicle systems 105 receive signals from GPS satel-
`lites 140 over radio frequency communication paths 112.
`Server system 125 also receives signals from GPS satellites
`140 over radio frequency communication path 122. As is
`described more fully below (see Section 2.4), data derived
`from signals received by server system 125 from GPS
`satellites 140 is used at times by both server system 125 and
`in-vehicle systems 105 to improve the location estimates of
`vehicles 100, for instance, using “differential” GPS calcu-
`lations.
`
`Referring still to FIG. 1, server system 125 relies on a map
`provider 160,
`for
`instance,
`a vendor of map-related
`information,
`to provide information related to the road
`network, including the locations and types of road segments
`that interconnect to form the road network. Map provider
`160, or some other external
`information provider, also
`provides other map-related information such as the locations
`of typical points of interest such as city centers, restaurants,
`and gas stations.
`In some versions of the system, server system 125 also
`serves as a gateway to external information systems 130.
`These external systems provide information used by server
`system 125, or provide information that is passed directly to
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`in-vehicle systems 105. For instance, an external informa-
`tion system 130 can provide traffic-related information that
`is used by server system 125 to determine a fastest route
`from a starting to a destination location. In another instance,
`an external information system 130 can provide communi-
`cation services to vehicle operators, such as a paging ser-
`vice.
`Alternative communication approaches between
`in-vehicle systems 105 and server system 125 can be used.
`Use of standard analog cellular telephone links is useful due
`to the broad geographic coverage in North America of the
`infrastructure needed to support such links. In other parts of
`the world, digital cellular telephone links may be more
`appropriate if the necessary infrastructure is available. Such
`a digital-based infrastructure is expected to be available in
`North America in the future. A satellite-based communica-
`tion system can alternatively be used to link the in-vehicle
`systems to the server system. Also, other wireless data
`communication systems can be equivalently used to couple
`in-vehicle systems 105 and server system 125. Such systems
`are currently being deployed in North America (e.g.,
`ARDIS, RAM, CDPD, GSM), although the geographic
`coverage is not yet adequate to support this system and
`provide broad geographic availability to vehicle operators.
`Many wireless communication systems also include a “short
`message” capability with which short messages can be
`transferred. Such short message services can alternatively be
`used for some types of communication between the
`in-vehicle systems and the server system, for instance for
`notification of exception conditions.
`Also, alternative positioning systems can be used rather
`than relying on signals from GPS satellites 140. For
`instance, a roadside optical or radio frequency beacon sys-
`tems can be used to provide location information to vehicles.
`Such a roadside beacon system is not broadly available in
`North America. On the other hand, the GPS-based approach
`provides broad geographic coverage today.
`Centralized server 120 is “centralized” in that it provides
`services at one location for vehicles that are distributed
`throughout a geographic area. The centralized server’s loca-
`tion does not have to be “central” or even located in the same
`
`geographic area as the vehicles it services. Also, although
`the system is described in terms of a single centralized server
`120, multiple servers can alternatively be used. When mul-
`tiple servers are used, in-vehicle systems 105 can be con-
`figured to access particular servers for all, or for particular
`types of, service requests.
`1.2 Operation (FIGS. 6-10)
`General operation of the navigation service of the vehicle
`information system can be understood with reference to
`FIGS. 6-10, which illustrate various representations of
`exemplary maps and routes that are used in the system.
`These drawings correspond to a common geographic area
`that is shown schematically in FIG. 6. The geographic area
`shown is only a very small portion of the area that
`is
`typically supported by the navigation service, which may be
`as large as the United States or multiple countries in Europe.
`Referring to FIG. 6, a map 600 is illustrated with three
`classes of roads shown in different line widths. In general,
`roads are classified according to their size or typical vehicle
`speed, for example, highways, limited access roads, main
`roads, and side streets. In FIG. 6, a highway 610 is shown
`as a thick line running along the vertical orientation of the
`drawing. Aset of main roads 620, 622, 624, and 626, which
`is shown in medium thickness lines, form an intersecting
`network. Main roads 620 and 622 are connected to highway
`610 at two on-ramps, 612 and 614, respectively. A set of
`residential roads (side streets) 630-636 completes the road
`network.
`
`35
`
`

`
`US 6,707,421 B1
`
`7
`In this example, an operator and vehicle are initially at the
`point marked ‘X’ 690. The operator wants to get to a desired
`destination 692 that is not shown in the drawings, but that is
`best accessed by following highway 610 as indicated in the
`drawings.
`As the first step, the operator enters a specification of
`desired destination 692 into in-vehicle system 105. For
`instance,
`the operator enters the city, street, and street
`number of a destination address. The destination is validated
`
`by the in-vehicle system, for instance validating that the
`street address is in an allowable range for the specified
`street.
`
`After in-vehicle system 105 has accepted and validated
`the destination specification, it establishes a communication
`session with server system 125 over cellular telephone link
`110 and sends the destination specification to the server
`system. The in-vehicle system also sends information to the
`server system that allows the server system to determine the
`vehicle’s starting location 690. For instance, the in-vehicle
`system sends the estimated latitude and longitude output
`obtained from a GPS receiver in the vehicle, or sends other
`raw output from its GPS receiver.
`Referring to FIG. 7, the server system includes a stored
`detailed representation of the road network 700. The net-
`work is represented as a graph with a set of nodes, indicated
`in the drawing by open circles, that are interconnected by
`links (arcs) that correspond to road segments. Links in the
`graph have associated stored data which includes the class of
`the road represented by the links. Each node in the graph has
`associated data including its latitude and longitude (or
`equivalently its relative location to another node that is at a
`known location), as well as other information, such as which
`turns from one link to another link joined at the node are
`valid. Many link