Vehicle information system Number:6,784,832 from the United States Patent and Trademark Office (PTO) owispatent

Title: Vehicle information system

Abstract: A vehicle information system which includes an in-vehicle system 105 and a centralized server system 120. The in-vehicle system communicates with the server system using a wireless communication link 110, such as over a cellular telephone system. A position system, such as a set of GPS satellites 140, provides positioning signals that are used by the in-vehicle systems, and optionally by the centralized server system to increase the accuracy of position estimates. In one version of the system, an operator specifies a destination to an in-vehicle system which validates the destination. The in-vehicle system transmits specification of the destination to a server system 125 at the centralized server. The server system computes a route to the destination and transmits the computed route to the in-vehicle system. The in-vehicle system guides the operator along the route. If the in-vehicle system detects that the vehicle has deviated from the planned route, it replans a new route to the destination using an in-vehicle map database.

Patent Number: 6,784,832 Issued on 08/31/2004 to Knockeart,   et al.

---

Inventors:	Knockeart; Ronald P. (Clarkston, MI), Drury; Bob (Novi, MI), Rode; Melvin A. (Orion, MI), Brown; Steven (Sterling Heights, MI), Asher; Harry (Garden City, MI), Jozefowicz; Paul A. (Roseville, MI)
Assignee:	Siemens VDO Automotive Corporation (Auburn Hills, MI)
Appl. No.:	10/656,361
Filed:	September 5, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	136868	Aug., 1998	6680694

---

Current U.S. Class:	342/357.13 ; 342/357.07; 701/208; 701/210
Field of Search:	342/357.13,357.07 701/208,210

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5072395		December 1991		Bliss et al.
	5243528		September 1993		Lefebvre
	5334986		August 1994		Fernhout
	5364093		November 1994		Huston et al.
	5394333		February 1995		Kao
	5539645		July 1996		Mandhyan et al.
	5563607		October 1996		Loomis et al.
	5598534		January 1997		Haas
	5604676		February 1997		Penzias
	5802492		September 1998		DeLorme et al.
	5955973		September 1999		Anderson
	5987381		November 1999		Oshizawa
	6028537		February 2000		Suman et al.
	6073075		June 2000		Kondou et al.
	6104338		August 2000		Krasner
	6169515		January 2001		Mannings et al.
	6324472		November 2001		O'Shea
	6614363		September 2003		Behr et al.

Foreign Patent Documents

	4139581		Jun., 1993		DE
	4300927		Jul., 1994		DE
	0349652		Jan., 1990		EP
	0354684		Feb., 1990		EP
	0786646		Jul., 1997		EP
	96/00373		Jan., 1996		WO
	96/21193		Jul., 1996		WO

Primary Examiner: Blum; Theodore M.

---

Parent Case Text

---

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a divisional of U.S. application Ser. No. 09/136,868, filed Aug. 19, 1998, now U.S. Pat. No. 6,680,694 which claims the benefit of U.S. Provisional Application No. 60/056,150, filed Aug. 19, 1997.

---

Claims

---

What is claimed is:

1. A method for tracking a vehicle comprising: storing data characterizing a series of maneuvers to be carried out by the vehicle, said series of maneuvers including a first maneuver to be carried out by the vehicle at a first location; determining when the vehicle is at the first location, including detecting when the vehicle performs the first maneuver using the stored data characterizing the series of maneuvers; computing first position data using a reference signal at the vehicle from a positioning system at the time at which the vehicle was determined to be at the first location; computing position correction data using the first position data and coordinates of the first location; computing second position data using a reference signal received at the vehicle 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 determining coordinates of the vehicle at the second time including combining at the vehicle the correction data and the second position data.

2. Software recorded on a computer readable medium for causing an in-vehicle computer to perform the functions of: storing data characterizing a series of maneuvers to be carried out by the vehicle, said series of maneuvers including a first maneuver to be carded out by the vehicle at a first location; determining when the vehicle is at the first location, including detecting when the vehicle performs the first maneuver using the stored data characterizing the series of maneuvers; computing first position data using a reference signal received at the vehicle from a positioning system at the time at which the vehicle was determined to be at the first location; computing position correction data using the first position data and coordinates of the first location; computing second position data using a reference signal received at the vehicle from a positioning system at a second time subsequent to the time at which that the vehicle was determined to be at the first location; and determining coordinates of the vehicle at the second time including combining at the vehicle the correction data and the second position data.

3. An in-vehicle navigation system comprising: a positioning system receiver for receiving reference signals from a positioning system; a first storage for holding data characterizing a series of maneuvers to be carded out by a vehicle, said data including coordinate of a first location and data characterizing a first maneuver to be carried out by the vehicle at the first location; a second storage for holding position correction data; a vehicle sensor for sensing motion of the vehicle; and a processor coupled to the positioning system receiver, to the first and the second storage, and to the vehicle sensor, and programmed to perform the functions of determining when the vehicle is at the first location using signals from the vehicle sensor, including detecting when the vehicle performs the first maneuver using the data from the first storage characterizing the first maneuver, accepting first reference data related to the location of the vehicle at the time at which the vehicle was determined to be at the first location from the positioning system receiver, computing position correction data using the first reference data and the coordinates of the first location, and determining coordinates of the vehicle at a second time subsequent to the time at which that the vehicle was determined to be at the first location using the computed position correction data.

---

Description

---

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 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 autonomous system's map, for example to add or correct information, typically involves replacing the removable medium.

In some navigation systems the operator inputs the 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 restaurants. 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 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 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 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.

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 general, in one aspect, the invention is a vehicle information system. The vehicle information system features an in-vehicle system and a centralized server system. The in-vehicle system communicates with the server system using a wireless communication link.

In general, in another aspect, the invention is a 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 particular 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 tracking the location of the vehicle. The method can also feature displaying the received map in conjunction with a representation of the planned route, and a location of the vehicle.

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.

In general, in another aspect, the invention is a method for tracking a vehicle. The method features receiving a reference signal from a positioning system, for example receiving signals from GPS satellites, and computing 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 transmitting 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 estimated coordinates of the vehicle including combining data computed from the received reference signal and the position correction data.

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.

In general, in another aspect, the invention is a method for tracking a vehicle. The method features receiving a specification of a first location which includes coordinates, 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 computing 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 measurements 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 location. 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 signals 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.

The method can feature including in the specification 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 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.

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.

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.

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.

In general, in another aspect, the invention is a 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.

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 specification. 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.

In general, in another aspect, the invention is 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.

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.

In general, in another aspect, the invention is a 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 maneuvers along the route. The method includes tracking a location 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 accessing a map database stored in the vehicle.

The method can also include establishing a wireless 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.

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.

In general, in another aspect, the invention is a method for collecting traffic information. The method includes tracking the location of a vehicle, including detecting when the vehicle traverses each of a plurality of segments of a road network. For each detected segment, the method includes logging traffic-related data, including logging data related to the vehicle's speed on the detected segment. The method then includes transmitting the logged data to a server 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 method for collecting traffic information. The method includes tracking the location of a vehicle, including detecting 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 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.

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 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 selection 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 destinations 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.

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 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 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.

In general, in another aspect, the invention is 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.

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.

In general, in another aspect, the invention is a 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 instructions to the operator through the input/output device.

In general, in another aspect, the invention is a 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 information 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 instructions.

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.

In general, in another aspect, the invention is a 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 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.

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 architecture;

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;

FIG. 8 illustrates an exemplary planned route that is 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; and

FIG. 22 is a block diagram of an extensible server system.

DESCRIPTION

1 Overview (FIGS. 1, 6-10)

1.1 Architecture (FIG. 1)

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 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 system 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.

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 operator 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 intersection. 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 satellites 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 calculations.

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 in-vehicle systems 105. For instance, an external information 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 communication services to vehicle operators, such as a paging service.

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 communication 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 systems 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 location 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 multiple servers are used, in-vehicle systems 105 can be configured 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. A set 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.

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 network 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 links are approximated by straight line segments joining the nodes at each end of the link. Some links, such as the links joining nodes 733 and 735 or nodes 716 and 725, represent curved road segments. To represent such curved road segments, links can include one or more "shape points," represented as hatched circles 780-785 in the drawing. Each shape point has location data associated with it. The segments between adjacent shape points, or between nodes and adjacent shape points, are approximated by straight line segments.

Server system 125 uses the information provided by the in-vehicle system related to the location of the vehicle 690 to determine the starting latitude and longitude of the vehicle. Based on the vehicle's latitude and longitude, speed, and heading, the server system finds the vehicle's starting link in its graph representation of road network 700. In this example, this first point on the road network is on the link joining nodes 753 and 763.

The server system next computes a best path to destination 692. "Best" can be based on a variety of criteria such as the smallest total distance, or the shortest expected travel time using information related to the expected speed of travel along links of the roadway graph. In this example, this planned route is illustrated by the dotted line 792. Referring back to FIG. 6, this planned route has the vehicle starting on residential road 635 and first making a left on residential road 632. The vehicle then is to make a right turn onto main road 628, and a right onto main road 620. Main road 620 merges onto highway 610. The vehicle then is to continue along highway 610 toward destination 692.

Referring to FIG. 8, planned route 800 is downloaded from the server system to the in-vehicle system in the form of a sequence of links joined by nodes. Each node along the route (other than necessarily the start node) corresponds to a node in the server's road network 700 (FIG. 7). Nodes along planned route 800 correspond to "maneuvers" that must be carried out by the operator. For example, the maneuver at node 790 is "turn left onto road 635" (See FIG. 6). Each link along the route can have one or more "way points." Way points correspond to shape points in the server's road network 700, or to nodes which are intersections at which the operator does not have to make a maneuver, that is, nodes of the server's road network 700 at which the operator simply continues without turning or making some other maneuver. In FIG. 8, nodes 733, 780, and 781 are way points on the link joining maneuver points 732 and 735.

In principle, if the operator could always be expected to follow directions exactly, then the operator will drive to the desired destination. However, various factors may result in the operator not reaching the desired destination without further planning. These factors include:

Inaccuracy in the estimate of the vehicle's initial location, for example due to closely spaced side streets,

The operator's inability to follow directions, particularly during the initial startup portion of a route where the directions may be complicated,

Errors in the system's map of the road network, for instance, due to unexpected road construction, and

Inaccuracy in estimating the distance traveled by the vehicle.

In order to account for errors associated with the startup portion of the route, the server system downloads to the in-vehicle system a detailed map 900, known as a "spot map," around initial location 690. Referring to FIG. 9, map information related to nodes and links in the vicinity of starting location 690 are downloaded. Spot map 900 has as high a level of detail as does the server's road network 700, but is limited geographically, for instance including all nodes within two links of the starting location.

The server system can also download a spot map around one, or more, maneuver points, or around the destination. For instance, if a maneuver is particularly complex, the server system would download a spot map around that maneuver point.

After planned route 800 and spot map 900 are downloaded to the vehicle, communication between in-vehicle system 105 and server system 125 is typically completed. At this point, the operator can preview the route, or can start traveling to the destination. The operator can also start traveling before the planned route is downloaded. The in-vehicle system begins providing initial guidance commands and displaying the spot map around the starting location to the operator as soon as it is downloaded without necessarily waiting for the complete route to be downloaded.

While traveling to the destination, the in-vehicle system attempts to track the location of the vehicle. As the in-vehicle system determines that the vehicle is approaching each maneuver point, it provides aural and graphical instructions to the operator regarding the action to take at that maneuver point. If a spot map has been downloaded for the maneuver, the in-vehicle system displays the spot map in addition to, or instead of, the graphical instructions.

During the initial portion of the trip or near a maneuver for which the server system has provided a spot map, while the vehicle is in the region of a spot map 900, the spot map is used by the in-vehicle system to guide the operator onto the planned route. In particular, the in-vehicle system displays the spot map and the initial portion of the planned route to the operator. In addition, the in-vehicle system displays the tracked location of the vehicle in conjunction with the spot map. This allows the operator to recover from errors during the initial portion of the trip by seeing that the tracked location is not following the planned route, and using the roads shown on the spot map to determine what turns to make to get back to the planned route.

The in-vehicle system also has a preloaded main roads network 1000, which is a stored version of the map that includes only main and larger roadways (i.e., it does not include residential roads). A portion of the main roads network 1000 is shown in FIG. 10. Main roads network 1000 has a similar form as the server's road network 700 shown in FIG. 7, except that fewer links are included. For reference, the planned route 792 is illustrated by a dotted line.

While traveling toward the destination, the in-vehicle system tracks an estimated location of the vehicle. If the operator does not properly follow the directions, the in-vehicle system will typically detect when the vehicle has diverged too far from the planned route. When it detects that the vehicle is off-route, it plans a corrected route based on the main roads map shown in FIG. 10 which get the vehicle back onto the originally planned route.

Referring back to FIG. 6, in this example, the operator fails to make the right turn from main road 628 onto main road 620, continuing instead on main road 628. Referring back to FIG. 10, the in-vehicle system determines that the vehicle is off-route at a point 1010, which corresponds to a point on a main road segment between nodes 732 and 722 when it should have been at a point on the link joining points 732 and 735. Using its main road network 1000, the in-vehicle system plans a corrected route indicated by the dashed line 1012. This re-planned route joins the originally planned route at point 725. Note that in replanning a route after an off-route condition occurs, the in-vehicle system does not necessarily have to contact the server system, relying instead on its main roads network 1000.

The in-vehicle system therefore uses a combination of main roads network 1000 that is preloaded into the vehicle and spot maps 900 that are downloaded to the vehicle along with planned route 800 to replan the route when the vehicle is detected to not be following the planned route.

In an alternative version of the system, spot maps 900 can be used to augment main roads network 1000 to re-plan the route if the operator fails to follow the planned route during the initial portion of the trip.

In the system operation described above, a vehicle operator receives instructions in the form of

Graphically presented maneuver instructions,

Aural maneuver instructions, and

Spot map based instructions.

Alternative versions of the system use subsets of these forms of instructions. For instance, a version of the system can use aural instructions alone. Another version of the system can use graphically presented maneuver instructions without any map based or aural instructions. Other combinations or instruction modes can be used as well. Furthermore, alternative versions of the system can give the vehicle operator control over which instruction modes are used, for instance, allowing the operator to switch between map based and graphical instruction based modes.

2 Harware and Software Architecture (FIGS. 2-5)

2.1 In-Vehicle System Components (FIG. 2)

Referring to FIG. 2, each in-vehicle system 105 includes an onboard computer 210 which is used to coordinate the operation of other components, including sensors 230, which provide information related to the motion of the vehicle, input/output (I/O) devices 240, which provide an interface between the operator of the vehicle and the navigation system, and communication system 250, which provides communication links from GPS satellites 140 and to and from server system 125. Onboard computer 210 is also coupled to vehicle systems 270, which include door locking system 272 and airbag system 274.

Onboard computer 210 has limited storage and processing capabilities. In this version of the in-vehicle system, onboard computer 210 includes a processor 212 coupled to other components of the onboard computer over a data bus 214. The other components includes dynamic random access memory (DRAM) 220, which provides 2 MB of working storage for processor 212, erasable programmable read-only memory (EPROM) 218, which provides 4 MB of non-volatile storage, and universal asynchronous receiver-transmitter (UART) 216, which provides serial communication capabilities to other system components. Alternative hardware configurations, for instance, with more or less memory, can be used.

Processor 212 is also coupled to a static storage 222 which is a non-volatile storage used to store code and data for operation of the system. In particular, as is described further below, static storage 222 is used to store map-related information, such as main roads network 1000 (FIG. 10), which is used during route planning and guidance procedures executed on onboard computer 210. Static storage 222 is a removable 40 MB flash memory system which emulates a disk storage device. Alternative static storage devices can be used, including removable and non-removable disk storage devices and semiconductor memories.

Sensors 230 include a velocity sensor 232 which provides a velocity signal to onboard computer 210. The velocity signal encodes the distance traveled by the vehicle by providing a constant number of pulses per revolution of the output of the vehicle's transmission, and which therefore provides a relative constant number of pulses per mile traveled. Sensors 230 also includes a magnetic compass 234 which provides a signal to onboard computer 210 encoding the orientation of the vehicle. Alternative versions of the system do not necessarily include magnetic compass 234, relying only on the velocity signal. Also, alternative versions may include other sensors of the state of the vehicle, including a gyroscope or accelerometers for determining the rate of rotation of the vehicle, or a differential velocity sensor, which provides the relative speed of the wheels on either side of the vehicle thereby encoding a turning radius of the vehicle as it goes through a turn.

I/O devices 240 includes a display 242. In versions of the in-vehicle system in which only graphical commands are displayed, display 242 is a small (e.g., 4-5 lines of text high, 64.times.240 pixels) monochrome liquid crystal display (LCD) which is used to provide text and schematic image instructions to the operator of the vehicle. In versions of the in-vehicle system in which spot maps are displayed to the operator, display 242 is 4 to 5 inch diagonal display with approximately 200.times.200 pixels, which is large enough and has a high enough resolution to provide a detailed map display to the operator that can be used to provide map-based directions to the operator. Also, in alternative versions of the system, visual feedback is not necessarily used, relying instead solely on audio instructions from the system to the operator.

I/O devices 240 also includes an input device 244. Input device 244 includes multiple push buttons associated with display 242. The operator uses these buttons to select alternatives shown on display 242, or to scroll the list of displayed alternatives. Alternative versions of the system can include an alphanumeric keyboard coupled to the onboard computer.

Referring to FIGS. 2A-C, an integrated I/O device 241 includes display 242 and a set of four rocker switches that are part of input device 244. One rocker switch is dedicated to "menu" and "cancel" inputs while the other three are reconfigurable. Referring to FIG. 2A, display 242 is at times used to display both text commands and graphical representations of commands. Referring to FIGS. 2B-C, display 242 is used at times to provide visual feedback to the operator when inputting information. FIG. 2B illustrates selection from a list and FIG. 2C illustrates spelled input in which the operator uses the rotary switch to select letters to spell an input word.

Referring back to FIG. 2, I/O devices 240 also include a voice output device 246. Voice output device 246 provides audio output of speech commands that are stored or formed on onboard computer, for example, using compressed or concatenated waveforms or a speech synthesizer.

I/O devices 240 can be dedicated to onboard computer 210, or can alternatively be part of another vehicle component such as a radio. In the latter case, display 242 and input device 244 are the display and input buttons of the other component, respectively. Many audio components include standard control interfaces, such as the ACP (Audio Control Protocol) interface used in vehicles manufactured by the Ford Motor Company. In such a case, onboard computer 210 can communicate with the audio component using a standard communication interface. Voice output can be provided to the operator by passing it through the audio system, or alternatively, onboard computer 210 can mute or attenuate the audio system while voice output is provided through a dedicated audio path.

Referring still to FIG. 2, communication system 250 includes a GPS receiver 252 coupled to a GPS antenna 253 for receiving signals from GPS satellites 140. GPS receiver 252 repeatedly provides location-related information to onboard computer 210, for example, at one-second intervals. The location related information can be an estimated location, in terms of latitude and longitude, or other raw measurements that can be used to compute an estimated location. GPS receiver 252 can also receive correction data from onboard computer 210, which it uses to compute increased accuracy location estimates from its raw measurements. As is described further below, the correction data can be provided by server system 125 and is used at times to increase the accuracy of the location information provided by GPS receiver 252.

Communication system 250 also includes a cellular transceiver 254 coupled to a cellular telephone antenna 255. Cellular transceiver 254 provides voice and data communication capabilities to the vehicle. A modem 256 is coupled between onboard computer 210 and cellular transceiver 254. Data sent to and received from server system 125 over a cellular telephone line passes through modem 256. Cellular transceiver 254 is also coupled to a handset 260. The operator can place standard telephone calls using handset 260 when cellular transceiver 254 is not being used to communicate with server system 125.

2.2 Server System Components (FIG. 3)

Referring to FIG. 3, server system 125 includes a server computer 310, which communicates with in-vehicle systems 105. Server system 125 includes a telephone interface 320 for receiving and placing telephone calls to establish data communication sessions with individual in-vehicle systems 105.

An in-vehicle system 105 initiates a communication session with server system 125 by placing a cellular telephone call to a telephone number associated with the server system. The call is routed through a cellular telephone network 350 to public switched telephone network (PSTN) 340 and then to telephone interface 320. Telephone interface 320 answers the call. Telephone interface includes a modem function which is used to establish a data connection with modem 256 (FIG. 2) in the calling vehicle. In alternative