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

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 1 of 25
`
`US 2004/0064245 A1
`
`
`
`
`
`Gm»
`
`
`cps SATELLITES
`
`
`
`‘I40
`
`122
`
`.
`
`'
`
`‘
`
`_
`
`1
`
`130 I
`
`_
`
`.
`
`120
`
`
`
`
`EXTERNAL
`INFORMATION
`SYSTEM
`
`CENTRALIZED
`SERVER
`
`
`
`SYSTEM
`
`K SERVER ‘
`I I M”
`I‘
`PROVIDER
`
`150
`
`‘°°
`
`105
`
`100
`
`IN VEHICLE
`
`j__..T_j_
`
`7/ -'
`I.‘ SYSTEM
`D.
`105
`’, IN VEHICLE
`"- SY-STEM 0
`._
`0 SYSTEM Q ‘O0
`
`‘IN VEHICLE 105
`
`'
`
`2
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 2 of 25
`
`US 2004/0064245 A1
`
`sAnaLLnes,1‘4O
`
`SERVER SYSTEM,125
`
`‘V COMMUNICATION ‘
`
`V
`
`CELLULAR
`TRANSCEIVER
`
`'
`
`HANDS“
`
`_
`
` STATIC
`
`STORAGE
`
`MAGNETIC
`
`LOCKING
`SYSTEM
`
`COMPASS
`
`‘IN-VEHICLE SYSTEM
`
`U1
`__n
`.-
`
`3
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 3 of 25
`
`US 2004/0064245 A1
`
`Turn On:
`Exit 23
`I-94 Freeway West
`. 0.8 miles
`
`SELECT STREET
`
`4
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 4 of 25
`
`US 2004/0064245 A1
`
`
`
`
`350 '
`
`//
`
` PUBLIC
`SWITCHED
`CELLULAR
`TELEPHONE
`TELEPHONE
`NETWORK
`NETWORK
` cps SATELLITES,
`(PSTN)
`
`140
`
`340
`
`TO VEHICLES,
`
`100
`
`
`
`A
`GPS
`RECEIVER
`
`SERVER COMPUTER
`
`312
`
`PROCESSOR
`
`
`
`FIG. 3
`
`
`
`
`
`5
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 5 of 25
`
`US 2004/0064245 A1
`
`CPS
`RECE|VER
`252
`
`CELLULAR
`TRANSCEIVER
`254
`
`
`
`COMMUNICATION INTERFACE
`
`
`
`NAVIGATION
`APPLICATION
`
`VEHICLE INTERFACE
`
`SENSORS, VEHICLE
`230
`SYSTEMS.
`270
`
`I/O
`DEVICES.
`240
`
`FIG. 4A
`
`IN-VEHICLE
`
`DATABASE
`
`STATIC STORAGE ‘
`
`6
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 6 of 25
`
`US 2004/0064245 A1
`
`TO TELEPHONE
`INTERFACE, 320
`
`TO GPS
`RECEIVER, 325
`
`
`
`SERVER
`
`516
`
`SYSTEM
`
`
`
`I25
`
`CPS
`INTERFACE
`
`
`
`514
`
`COMMUNICATION
`INTERFACE
`
`
`
`
`
`'
`
`NAVIGATION
`APPLICATION
`
`DATA INTERFACE I
`
`SERVER
`MAP
` DATABASE
`DATABASE
`
`TRAFFIC
`DATABASE
`
`
`
`IN-VEHICLE
`DATABASE
`
`
`
`SYSTEMS, 130
`
`FIG. 5
`
`FROM MAP
`
`PROVIDER, 160
`
`
`
`FROM EXTERNAL
`INFORMATION
`
`7
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 7 of 25
`
`US 2004/0064245 A1
`
`RESIDENTIAL
`ROADS
`
`8
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 8 of 25
`
`US 2004/0064245 A1
`
` 7.02
`
`713
`
`712
`
`711
`
`9
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 9 of 25
`
`US 2004/0064245 A1
`
`+
`
`692
`
`10
`
`10
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 10 of 25
`
`US 2004/0064245 A1
`
`E62
`
`/J I
`
`/
`
`11
`
`11
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 11 of 25
`
`US 2004/0064245 A1
`
`12
`
`12
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 12 of 25
`
`US 2004/0064245 A1
`
`AddressCityState
`
`1110
`
`Addressstreet
`
`"58
`
`1154
`
`"1156 "50
`1
`
`Street ntlme
`I-- 1152
`I--
`
`-I
`
`I—
`
`1
`
`1114
`
`1116
`city state
`
`.1118 m2
`address
`street
`
`"19
`
`- H841 AddressRange 1180
`K
`4 1186
`CityState ’
`1130
`V
`1182
`'°W high
`“34 -
`- “36 -
`H32
`StreetRecord
`-I 1
`1154
`street name affixl
`type
`‘M0 I-
`StreetName
`
`1160
`, 1166
`
`1162
`
`- 1‘ 1172
`-
`
`13
`
`13
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 13 of 25
`
`US 2004/0064245 A1
`
`TEXT "TABLE
`
`FIG. 12
`
`14
`
`14
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 14 of 25
`
`US 2004/0064245 A1
`
`15
`
`15
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 15 of 25
`
`US 2004/0064245 A1
`
`39.23.22;g35E3%
`_2.0:3..co:_who:3..oc._m5wm:m6
`
`mm?39E9
`
`.IBcmfiwmmxcfi
`
`ow:
`
`&s&§.%<Nmfl
`
`one
`
`mu
`N...
`0
`‘Eu.
`:3:
`
`
`
`:__o,,._2§§._:.8:_:ou3_§Em
`
`mm.U_u_
`
`E2.”_
`
`mvoZ._Bmm<4
`
`99
`
`$9
`
`16
`
`16
`
`
`
`
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 16 of 25
`
`US 2004/0064245 A1
`
`P0|TYPe
`
`1414
`
`1410
`
`.
`
`PO|Types
`
`1420
`
`FIG; 14
`
`POINameCity
`
`1430
`
`‘
`
`1434
`
`1436
`
`1438
`
`1440
`
`CityState
`
`"30
`
`1160
`
`- -
`
`country
`
`citystate
`
`3
`
`POI name H 111.2123
`nu: 1
`II --
`-
`I I 1----
`--
`PO|List 1450
`H1
`1452
`1458’
`1456
`1454
`1460
`--‘ S"°etRe°°'d
`
`-
`-
`E----1466 3_
`
`17
`
`17
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 17 of 25
`
`US 2004/0064245 A1
`
`1501
`
`1502
`
`1503
`1504
`1505
`
`1505
`
`1507
`
`1500
`1509
`1510
`
`1511
`
`1512
`
`1513
`
`Plan Route (ln-Vehicle):
`
`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
`R
`
`Wait for Server_ Response
`
`Receive Planned Route, Spot Map, and Differential GPS Data from Server
`
`Close Communication Session with Server
`
`FIG. 15A
`
`18
`
`18
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 18 of 25
`
`US 2004/0064245 A1
`
`1551
`
`1552
`1553
`
`1554
`
`1555
`1555
`
`1557
`
`1553
`1559
`1550
`
`1561
`1552
`1563
`1554
`
`Plan Route (Server):
`
`.
`Accept Communication 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 Input THEN
`
`Determine Secondary Destination Specification Data
`
`Send Secondary Destination Specification Data to Vehicle
`Receive Secondary Destination Specification from Vehicle
`END IF
`
`in
`
`Determine Planned Route to Specified Destination
`I Determine Spot l\/lap near Vehicle Location
`Send Planned Route, Spot Map, and DGPS Data to Vehicle
`Close Communication Session with Vehicle
`FIG. 1513
`
`19
`
`19
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 19 of 25
`
`US 2004/0064245 A1
`
`1601
`
`'
`
`Startup Maneuvers:
`
`1502
`
`1603
`
`1604
`1605
`
`1606
`
`1301
`
`1302
`
`1803
`
`1804
`
`1805
`
`1305
`
`1807
`
`initialize Estimated Location using Differential cps Data
`
`WHILE Estimated Location is not at a Point of the Planned Route DO
`
`1 Track Estimated Location using (D)GPS Data
`Display Spot Map and Estimated Location on Display
`
`END WHILE ’
`
`FIG. 16
`
`Reolan Route:
`
`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
`
`F|C.18
`
`20
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 20 of 25
`
`US 2004/0064245 A1
`
`1701 ’
`
`Follow Route:
`
`1702
`
`FOR Each Link on Planned Route DO
`
`1703
`
`1704
`
`1705
`
`1706
`
`1707
`
`17oa
`
`1709
`
`1710
`1711
`
`1712
`1713
`
`1714
`
`1715
`
`1716
`
`1717
`
`1718
`
`1719
`
`1720
`
`1721
`
`1722
`
`1723
`1724
`
`At Initial Maneuver Initialize Off-Route Tolerance
`
`_ WHILE Vehicle Is Travelling to the Next Maneuver Point DO
`
`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 Window THEN
`
`Notify Operator of Next Maneuver
`
`END IF
`
`1
`
`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
`
`1725'
`
`UNTIL Destination is Reached
`
`FIG. 17
`
`21
`
`21
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 21 of 25
`
`US 2004/0064245 A1
`
` SERVER SYSTEM
`
`
`
`
`
`TRAFFIC
`
`DATABASE
`
`NAVIGATION
`
`APPLICATION
`
` EXTERNAL
`
`
`INFORMATION
`
`SYSTEM
`
`FIG I9
`
`NAVIGATION
`
`APPLICATION
`
`
`
`IN—VEHICLE SYSTEM
`
`22
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 22 of 25
`
`US 2004/0064245 A1
`
`ONBOARD
`COMPUTER
`
`STORAGE
`
`STATIC
`
`2030
`
`
`
`EQUIPMENT ’
`
`
`
`SERVICE
`
`IN-VEHICLE SYSTEM
`
`
`
`2031
`
`
` PERSONAL _
`COMPUTER
`2040
`
`
`
`23
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 23 of 25
`
`US 2004/0064245 A1
`
`105
`
`
`
`ONBOARD 210
`
`COMPUTER
`
`
`
`IN-VEHICLE SYSTEM
`
`340
`
`125
`
`SERVER
`
`SYSTEM
`
`
`
`FIG. 20c
`
`24
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 24 of 25
`
`US 2004/0064245 A1
`
`CENTRALIZED SERVER
`
`120
`
`
`
`
` VEHICLE ID. /
`2110
`
`
`LQCAT'Oy
`TELEPHONE/
`VOICE
`OPERATOR
`~
`
`
`SERVER
`SYSTEM
`
`125
`
`
`
`IN-VEHICLE
`
`SYSTEM
`
`FIG. 21A
`
`
`
`
`OPERATOR
`
`CENTRALIZED SERVER
`
`120
`
`FIG. 21B
`
`SERVER
`SYSTEM
`
`125
`
`
`
`2110
`TELEPHONE/
`OPERATOR
`
`COMMANDS
`
`/
`
`
`
`
`340
`
`OPERATOR
`
`
`
`IN-VEHICLE
`
`SYSTEM
`
`
`
`25
`
`

`
`Patent Application Publication
`
`Apr. 1, 2004 Sheet 25 of 25
`
`US 2004/0064245 A1
`
`TO VEHICLES
`
`SERVER SYSTEM
`
`2252
`
`
`PROVIDER
`
`2250
`
`NAVIGATION
`SYSTEM
`'
`
`
`
`TRAFFIC
`INFO.
`
`PROVIDER
`
`
`
`PROFILES
`
`
`M U
`
`SER
`
`_
`
`TO INTERNET
`
`22
`
`
`
`
`
`COMMUNICATION
`SYSTEM
`
`NEWS
`SYSTEM
`
`'NT'5RF’.‘CE
`
`GATEWAY
`
`
`
`2210
`
`_ SYSTEM
`
`2220
`
`ADMINISTRATIVE
`SYSTEM
`
`
`
`
`2230
`
`
`
`REMOTE
`CONFIGURATION
`SYSTEM
`
`
`
`2262
`
`E-MAIL -
`SYSTEM
`
`
`
`A2264
`
`PAGING
`SYSTEM
`
`2272
`
`NEWS _
`SERVICE
`
`26
`
`

`
`US 2004/0064245 A1
`
`Apr. 1, 2004
`
`VEHICLE INFORMATION SYSTEM
`
`SUMMARY
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`[0001] This application is a continuation of U.S. applica-
`tion Ser. No. 09/136,868, filed Aug. 19, 1998, which claims
`the benefit of U.S. Provisional Application No. 60/056,150,
`filed Aug. 19, 1997.
`
`BACKGROUND
`
`[0002] This invention relates to an information system for
`motor vehicles.
`
`[0003] Vehicle information systems have been developed
`that provide various types of information to operators of
`those vehicles. In particular, navigation systems have been
`developed. One type of navigation system, an autonomous
`navigation 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 informa-
`tion, typically involves replacing the removable medium.
`
`In some navigation systems the operator inputs the
`[0004]
`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.
`
`[0005] 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 intersections 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 provided as an audio output, and the opera-
`tor says “next” when ready for another instruction.
`
`[0006] Another approach to route guidance uses a dis-
`played 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.
`
`[0007] Some guidance approaches are aided by in-vehicle
`sensors that are used to estimate the location of the vehicle.
`
`For instance, a magnetic compass is used to estimate the
`direction 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.
`
`[0008] Other types of vehicle information systems have
`also been developed. In some systems, traffic related infor-
`mation, such as traffic advisories, is broadcast to specially
`equipped in-vehicle radio receivers.
`
`In general, in one aspect, the invention is a vehicle
`[0009]
`information system. The vehicle information system fea-
`tures an in-vehicle system and a centralized server system.
`The in-vehicle system communicates with the server system
`using a wireless communication link.
`the invention is a
`[0010]
`In general, in another aspect,
`method for guiding a vehicle through a road network from
`a starting location to a destination. The method features
`transmitting a specification of the destination to a server, for
`example by transmitting a street address or an identifier of
`a point of interest. The server determines a route to the
`specified destination and transmits a specification of the
`route to the vehicle. The method also includes receiving
`from the server a specification of a planned route through the
`road network to the destination as well as receiving from the
`server a map that
`includes a specification of the road
`network in the vicinity of the planned route. For instance, the
`map can correspond to one or more regions around particu-
`lar points on the planned route, correspond to a “corridor”
`around the planned route, or be a complex shaped region in
`the vicinity of the route. The planned route can include
`specifications of a multiple maneuvers to be carried out by
`the vehicle, and the specification of each maneuver then
`includes a location of the maneuver. The map can be in the
`vicinity of the starting location, or in the vicinity of one of
`the specified maneuvers. The method can also feature track-
`ing the location of the vehicle. The method can also feature
`displaying the received map in conjunction with a represen-
`tation of the planned route, and a location of the vehicle.
`[0011] An advantage of the invention is that the vehicle
`does not have to have a prestored map to plan a route to a
`destination. Also, the invention provides a way of displaying
`a map of the vicinity of the starting point or of intermediate
`maneuver points of a planned route without requiring that
`the map be prestored in the vehicle. The displayed map can
`provide useful information to an operator of a vehicle during
`difficult maneuvers where turn-by-turn instructions.
`[0012]
`In general, in another aspect,
`the invention is a
`method for tracking a vehicle. The method features receiv-
`ing a reference signal
`from a positioning system,
`for
`example receiving signals from GPS satellites, and comput-
`ing position data related to the location of the vehicle using
`the received reference signal. For example, the position data
`can be latitude and longitude estimates, or can be GPS
`pseudorange measurements. The method also features trans-
`mitting the position data to a server and receiving from the
`server position correction data. For example, the position
`correction can be a deviation in latitude and longitude, or
`can be correction terms to be applied to GPS pseudorange
`measurements. The method also features determining esti-
`mated coordinates of the vehicle including combining data
`computed from the received reference signal and the posi-
`tion correction data.
`
`[0013] The method can feature repeatedly computing the
`position data, and determining the estimated coordinates,
`including combining the position data and the position
`correction data. The method can also feature, subsequent to
`the interval of time, repeatedly computing the position data
`and determining estimated coordinates of the vehicle using
`the position data without using the correction data.
`[0014]
`In general, in another aspect,
`the invention is a
`method for tracking a vehicle. The method features receiv-
`
`27
`
`

`
`US 2004/0064245 A1
`
`Apr. 1, 2004
`
`ing a specification of a first location which includes coor-
`dinates, such as latitude and longitude, of the first location.
`The method includes determining when the vehicle is at or
`passes near the first location. The method includes comput-
`ing first position data using a reference signal received from
`a positioning system at the time at which the vehicle was
`determined to be at
`the first location. For instance,
`the
`positioning system can be a GPS positioning system, and the
`computed first position data can include pseudorange mea-
`surements derived from GPS satellite signals received when
`the vehicle was at or near the first location. The method
`
`further includes computing position correction data using
`the first position data and the coordinates of the first loca-
`tion. For instance, computing the position correction data
`can include computing pseudorange correction data based
`on the latitude and longitude of the first location and on the
`pseudorange measurements derived from GPS satellite sig-
`nals received when the vehicle was at or near the first
`
`location. The method further includes computing second
`position data using a reference signal received from the
`positioning system at a second time subsequent to the time
`at which that the vehicle was determined to be at the first
`
`location, and then determining coordinates of the vehicle at
`the second time including combining the correction data and
`the second position data.
`
`[0015] The method can feature including in the specifica-
`tion of the first location a specification of a maneuver to be
`carried out by the vehicle at the first location. Determining
`when the vehicle is at
`the first
`location then includes
`
`detecting when the vehicle performs the specified maneuver,
`for
`instance using vehicle sensors such as a compass,
`accelerometers, or a gyroscope.
`
`In general, in another aspect, the invention is a
`[0016]
`method for detecting when a vehicle deviates from a planned
`route. The method features tracking a first estimated position
`of the vehicle using signals from a positioning system that
`are received at
`the vehicle, for example, using a GPS
`positioning system. The method also features tracking a
`second estimated position of the vehicle using an estimate of
`the distance traveled along the planned route. The vehicle is
`detected to has deviated from the planned route when the
`first estimated position and the second estimated position
`differ by at least a tolerance distance.
`[0017] The method can feature detecting when the vehicle
`is at a first point on the planned route, such as a maneuver
`point, and estimating the distance traveled along the path
`following the first point.
`[0018] The method can also feature adjusting the tolerance
`distance, including reducing the tolerance distance when the
`vehicle is detected to be at the first point on the planned
`route, and increasing the tolerance distance as the vehicle
`travels along the path following the first point.
`[0019]
`In general, in another aspect, the invention is a
`method for providing guidance instructions to a vehicle
`operator following a planned route that includes a sequence
`of maneuver points. The method includes detecting when the
`vehicle is at a first maneuver point, and tracking the distance
`traveled by the vehicle from the first maneuver point along
`the planned route. When the tracked distance is within a
`predetermined notification distance of the distance between
`the first maneuver point and a subsequent maneuver point
`along the planned route the operator is notified of the
`subsequent maneuver.
`
`the invention is a
`In general, in another aspect,
`[0020]
`method for specifying a location in a vehicle navigation
`system. The method features providing an in-vehicle map
`database to an in-vehicle system. The in-vehicle database
`includes data related to valid location specifications for
`accessing a server map database at a server system. The
`method also features accepting a location specification, for
`instance, for an operator using a user interface in the vehicle.
`The system validates the location specification using the
`in-vehicle map database and then transmits the validated
`location specification to the server system.
`
`[0021] The method can also feature providing the server
`map database to the server system and accessing the server
`map database using the received validated location specifi-
`cation. In addition the method can also include determining
`a route to the specified location using the server map
`database, and transmitting the determined route to the in-
`vehicle system.
`
`the invention is
`in another aspect,
`In general,
`[0022]
`method for estimating a location of a vehicle. The method
`includes determining a series of vehicle position estimates
`using a positioning system, and recording each of the vehicle
`position estimates in the series. For example, the position
`estimates are recorded in a non-volatile memory as the
`vehicle reaches a destination. The method further includes
`
`estimating the location of the vehicle including retrieving
`the most recently recorded in the series of location estimates,
`for instance after the vehicle is started after a period of being
`parked at the destination.
`
`[0023] The invention has the advantage that a location
`estimate may be obtained, even if a positioning system, such
`as a GPS satellite system, is out of range, or prior to the
`positioning system being initialized.
`
`the invention is a
`In general, in another aspect,
`[0024]
`method for vehicle guidance. The method features receiving
`at the vehicle a planned route to a destination location from
`a server, and storing the planned route at the vehicle. The
`method also includes providing instructions to an operator of
`the vehicle according to the stored planned route,
`for
`example, providing instructions at each of a series of maneu-
`vers along the route. The method includes tracking a loca-
`tion of the vehicle and detecting whether the vehicle has
`deviated from the planned route. If the vehicle is detected to
`have deviated from the planned route,
`the method then
`includes planning a new route to the destination location.
`Planning the new route does not necessarily require further
`communication with the server. Planning the new route can
`include determining the location of the vehicle and access-
`ing a map database stored in the vehicle.
`
`[0025] The method can also include establishing a wire-
`less communication channel with the server, transmitting a
`specification of the destination location over the wireless
`communication channel, and then terminating the wireless
`communication channel after receiving the planned route.
`
`[0026] Advantages of this method include providing a
`server based route planning service to a vehicle, without
`requiring ongoing communication with the server to carry
`out guidance and route replanning functions.
`
`the invention is a
`In general, in another aspect,
`[0027]
`method for collecting traffic information. The method
`includes tracking the location of a vehicle, including detect-
`
`28
`
`

`
`US 2004/0064245 A1
`
`Apr. 1, 2004
`
`ing when the vehicle traverses each of a plurality of seg-
`ments of a road network. For each detected segment, the
`method includes logging traffic-related data, including log-
`ging data related to the vehicle’s speed on the detected
`segment. The method then includes transmitting the logged
`data to a server
`
`[0028] The method can feature receiving a command from
`the server to enable logging of the traffic-related data at a
`vehicle. The method can also feature receiving at a vehicle
`a request to transmit the logged data to the server.
`
`In general, in another aspect, the invention is a
`[0029]
`method for collecting traffic information. The method
`includes tracking the location of a vehicle, including detect-
`ing when the vehicle traverses each of a set of segments of
`a road-network. For each detected segment,
`the method
`features comparing the vehicle’s speed on the segment to a
`stored speed for that segment, and if the vehicle’s speed on
`the segment deviates from the stored speed, transmitting a
`traffic notification identifying that segment to a server.
`
`In general, in another aspect, the invention is a
`[0030]
`method for collecting traffic information. The method
`includes receiving traffic related data from a set of vehicles
`and updating a traffic database using the received traffic
`related data. Updating the database includes updating speed
`information associated with multiple road segments in a
`road network. The method also features planning a route
`through the road network from a starting to a destination
`location using the speed information associated with the
`road segments.
`
`[0031] The method can also feature enabling a subset of an
`available set of probe vehicles to provide the traffic related
`data, and can, in addition, feature determining a part of the
`traffic database to target for updating, for instance, according
`to a the part of the database corresponding to a geographic
`area. Enabling the subset of probe vehicles then includes
`enabling probe vehicles according to the part of the database
`that is targeted.
`
`In general, in another aspect, the invention is a
`[0032]
`method for specifying a destination to a vehicle navigation
`system. The method includes accessing a list of categories of
`destinations, and accepting a selection from the list of
`categories, for example, from an operator making the selec-
`tion on a in-vehicle user interface. The method includes
`
`transmitting the selection from the list of categories to a
`server system, and subsequently receiving a list of destina-
`tions from the selected category from the server system. The
`method then includes accepting a selection from the list of
`destinations and transmitting the selected destination to the
`server system.
`
`[0033] The method can also feature transmitting data
`related to the location of the vehicle to the server system.
`The received list of destinations then includes destinations
`
`that are in the vicinity of the vehicle.
`
`In general, in another aspect, the invention is a
`[0034]
`method for configuring a vehicle navigation system. The
`method includes providing a server map database to a server.
`The server map database includes data related to a plurality
`of road segments in a road network. The method also
`includes providing a vehicle map database to an in-vehicle
`system. The vehicle map database includes data related to a
`subset of the plurality of road segments in the server map
`
`database which satisfy a common criterion, for instance
`related to the road class of the road segments.
`
`In general, in another aspect, the invention is an
`[0035]
`in-vehicle map database. The database includes a first stored
`table and a second stored table. The first stored table
`
`includes multiple records each including a field containing a
`reference to a record containing a base name of a street in the
`second stored table, and a second field which identifies a
`prefix, a suffix, or a street type. The second stored table
`includes multiple records, each including a base name of a
`street stored in a compressed format.
`
`the invention is
`in another aspect,
`In general,
`[0036]
`method for transmitting a route to a vehicle navigation
`system. The route includes multiple intermediate points
`joined by road segments. The method includes transmitting
`a specification of the location of a first of the intermediate
`points, and transmitting a specification of a difference
`between the location of a second of the intermediate points
`and the first of the intermediate points. The specification of
`the difference can use fewer than an allocated number of
`bits.
`
`[0037] The method can also feature planning an initial
`route. The initial route includes an initial set of multiple
`intermediate points coupled by road segments. The planned
`route is formed from the initial route. For any of the road
`segments in the initial route for which the difference in
`locations of the intermediate points bounding that segment
`is greater than can be specified in the allocated number of
`bits, the method includes inserting additional intermediate
`points on that road segment so that the differences between
`the locations of the adjacent intermediate points can each be
`specified in the allocated number of bits.
`
`the invention is a
`In general, in another aspect,
`[0038]
`vehicle navigation system. The system includes an onboard
`computer, including storage for a map database, a wireless
`communication system for passing data between the
`onboard computer and a remote server, an input/output
`device for providing a user interface between the onboard
`computer and an operator of the vehicle, and a vehicle
`sensor for providing motion-related signals to the onboard
`computer. The onboard computer is programmed to perform
`the functions of accepting a planned, route from the server
`over the wireless communication system, maintaining a first
`location estimate of the vehicle using the motion-related
`signals from the vehicle sensor, and, using the planned route
`and the first location estimate, providing guidance instruc-
`tions to the operator through the input/output device.
`
`the invention is a
`In general, in another aspect,
`[0039]
`method for updating an in-vehicle navigation system. The
`method includes receiving a version number associated with
`information stored in the in-vehicle system. If the informa-
`tion stored in the in-vehicle system has a version number
`prior to the version of information a server,
`the method
`includes transmitting update information from the server to
`the in-vehicle system. The information stored in the in-
`vehicle system can include map data or computer instruc-
`tions.
`
`[0040] The method can feature prioritizing the update
`information, for instance, according to the geographic area
`represented by the update information and transmitting the
`update information in order of the priority.
`
`29
`
`

`
`US 2004/0064245 A1
`
`Apr. 1, 2004
`
`In general, in another aspect, the invention is a
`[0041]
`vehicle information server system. The system includes a
`vehicle communication interface for providing wireless data
`communication between multiple vehicles and a set of
`information system. The set of information systems includes
`a navigation system for accepting route planning request
`from the vehicles and providing planned routes through the
`communication interface, and a communication system
`coupled to an external information system for delivering
`information from the external information system to the
`vehicles.
`
`In general, in another aspect, the invention is a
`[0042]
`method for providing traffic related information to a user.
`The method features accepting from the user a specification
`of a path made up of one or more road segments in a road
`network and receiving traffic data related to road segments
`in the road network. If the received traffic data indicates an
`
`exceptional traffic condition on the specified path, the user is
`notified of the traffic condition.
`
`[0043] Other features and advantages of the invention will
`be apparent from the following description, and from the
`claims.
`
`DESCRIPTION OF DRAWINGS
`
`[0044]
`system;
`
`FIG. 1 is a block diagram of a vehicle navigation
`
`[0045] FIG. 2 is a block diagram of in-vehicle compo-
`nents of the system;
`
`[0046] FIGS. 2A-C show an integrated input/output
`device;
`
`[0047] FIG. 3 is a block diagram including components of
`a server system;
`
`[0048] FIGS. 4A-B show an in-vehicle system software
`architecture;
`
`[0049] FIG. 5 is a block diagram of a server system
`software architecture;
`
`[0050] FIG. 6 is a schematic map showing the road
`network in an exemplary region;
`
`[0051] FIG. 7 is a graph representation of the road net-
`work in the exemplary region;
`
`[0052] FIG. 8 illustrates an exemplary planned route that
`is downloaded from a server system to a vehicle;
`
`[0053] FIG. 9 is an exemplary spot map that is down-
`loaded from a server system to a vehicle;
`
`[0054]
`vehicle;
`
`FIG. 10 is a main roads map that is preloaded in a
`
`[0055] FIG. 11 shows data structures of an in-vehicle
`database;
`
`[0056] FIG. 12 shows the structure of text tables in the
`in-vehicle database;
`
`[0057] FIG. 13A shows a representative link of a main
`roads network;
`
`[0058] FIG. 13B shows data structures of an in-vehicle
`database encoding a main roads network;
`
`[0059] FIG. 14 shows elements of an in-vehicle database
`which encode Points of Interest information;
`
`[0060] FIG. 15A is a pseudocode listing of an in-vehicle
`route planning procedure;
`
`[0061] FIG. 15B is a pseudocode listing of a server route
`planning procedure;
`
`[0062] FIG. 16 is a pseudocode listing of a startup maneu-
`ver procedure;
`
`[0063] FIG. 17 is a pseudocode listing of a route follow-
`ing procedure;
`
`[0064] FIG. 18 is a pseudocode listing of a route replan-
`ning procedure;
`
`[0065] FIG. 19 illustrates a extensible server architecture;
`
`[0066] FIGS. 20A-20C illustrate approaches to updating
`an in-vehicle system;
`
`[0067] FIGS. 21A-21B illustrate additional information
`services provided by a server system; and
`
`[0068]
`system.
`
`FIG. 22 is a block diagram of an extensible server
`
`DESCRIPTION
`
`[0069]
`
`1 Overview (FIGS. 1, 6-10)
`
`[0070]
`
`1.1 Architecture (FIG. 1)
`
`[0071] Referring to FIG. 1, a vehicle information system
`provides 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 perform