# Patent

## Title
Wireless client-server navigator traffic methods

## Abstract

A wireless client-server (WCS) navigator provides routes optimized for travel time based on traffic flow rate and incident data, inexpensively and in a timely manner. A server, having a database of geographical information including road segments at a server, receives information representing traffic flow rates or traffic incidents along the road segments. This allows a route to be generated that is optimized to minimize travel time along the road segments based upon the traffic flow rates or traffic incidents. The route is then transmitted to a mobile client. Typically, though not necessarily, the route is generated in response to a request from a mobile client. Some travel time estimates may be based on historical traffic flow rate data or speed limit data rather than current information. Traffic flow rate or traffic incident data associated with the transmitted route may be transmitted to a client along with the route. The traffic flow rate information may be used to create estimates of time of arrival at a destination or points along the route. The points along the route may include, for example, points at which a maneuver such as a turn should be performed in conjunction with the route.

## Background
REFERENCE TO RELATED APPLICATIONS
This application claims priority from U.S. Provisional Patent Application Ser. No. 60/916,142, filed May 4, 2007 and 60/916,681, filed May 8, 2007, the entire content of both being incorporated herein by reference.


FIELD OF THE INVENTION
This invention relates generally to navigation systems, and in particular to the use of traffic data to optimize routing.
BACKGROUND OF THE INVENTION
Vehicle navigation systems now provide guidance that optimizes routes as a function of travel distance. While options are sometimes given to optimize routes for travel time instead, these are generally primitive approximations based on speed limits or historical travel time data. And while a variety of traffic data sources are available, transferring the data to mobile navigation devices in a useful manner is difficult. To generate optimized routes, recent traffic flow rate data about all possible roads considered by the navigator must be available, which necessitate that transfer of large amount of data to mobile navigation devices. Traffic flow rate data can change quickly, and data that is even a few minutes out of date can cause suboptimal routes to be generated. Thus data must be transmitted frequently to keep device databases up to date.
Several approaches have been tried to optimize navigator routing for traffic information, but all have significant drawbacks. One approach taken is to transmit information via FM TMC (Traffic Message Channel through frequency modulated radio broadcasts). While this approach is inexpensive, data transmission is slow. As a result only limited information about traffic jams and traffic incidents is transmitted rather than traffic flow rate data.
Another current approach is to transmit traffic information via a wireless modem. This approach is expensive because wireless carriers must be paid for the transmission. As a result, transmitted information is often limited to information about traffic jams and traffic incidents rather than traffic flow rate data. If traffic flow rate data were to be transmitted, a significant delay would result due to the volume of data required, which is undesirable in a navigation system.
SUMMARY OF THE INVENTION
This invention uses a wireless client-server (WCS) navigator to provide routes optimized for travel time based on traffic flow rate and incident data, inexpensively and in a timely manner. A server, having a database of geographical information including road segments at a server, receives information representing traffic flow rates or traffic incidents along the road segments. This allows a route to be generated that is optimized to minimize travel time along the road segments based upon the traffic flow rates or traffic incidents. The route is then transmitted to a mobile client. Typically, though not necessarily, the route is generated in response to a request from a mobile client.
Some travel time estimates may be based on historical traffic flow rate data or speed limit data rather than current information. Traffic flow rate or traffic incident data associated with the transmitted route may be transmitted to a client along with the route.
The traffic flow rate information may be used to create estimates of time of arrival at a destination or points along the route. The points along the route may include, for example, points at which a maneuver such as a turn should be preformed in conjunction with the route. A notification may be provided in advance of the maneuver, with the timing of the notification being based upon the estimates of time of arrival at a destination or points along the route. Along with the notification, an estimate may be presented as to the time or distance before the maneuver is to be performed.
In the event that traffic flow rate data or traffic incident data arrives at the server after a route has been provided to a client, the server may recalculate a time-optimized route based on previous and new traffic flow rate data and/or traffic incident data. If the newly calculated route differs from the route previously sent to a mobile client, a newly calculated route may be sent to the client.
A method of notifying a user of a vehicle navigation system that a maneuver should be performed, comprising the steps of estimating the time of arrival to the location of the maneuver based upon speed and distance to the location, and notifying the user as a function of the estimate. The method of claim 10, wherein the maneuver is a turn of the user's vehicle.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates the method of using a WCS navigation system to optimize routed based on traffic flow rate data; and
FIG. 2 illustrates using time-to-arrival estimates to optimize the time at which guidance is provided.



DETAILED DESCRIPTION OF TEE INVENTION
A wireless client-server navigator can be described as a system to aid a user in navigating by providing guidance made up of maps, routes, and/or instructions, and

    
    
        1) which has mobile clients used for requesting and receiving guidance,
        2) which has a central server that houses databases of geographical information, and generates guidance, and
        3) in which data is transmitted between the mobile clients and central server.
    
    


The advantage of WCS navigators in generating time-optimized routes over self-contained navigators is that far less data must be transmitted. In a self-contained navigator, routing is performed on the mobile device, thus traffic flow rate information about all roads that might be used in a route must be transmitted. If the data is to be available on a timely basis, the data must be transmitted frequently. On the other hand, in a WCS navigator, while the same traffic flow rate data is used that would be used in a self-contained navigator, only the final route need be transmitted to the mobile device. This approach reduces the cost of transmitted data for the navigator and also reduces response time, since complete traffic flow rate data for an area takes a significant amount of time to transmit.
Referring to FIG. 1, the server preferably receives traffic flow rate and/or incident information on a continual basis. From this information the server creates travel time estimates for the various road segments in its map database. In the absence of current traffic flow rate information, historical data or speed limit data may be used.
As an optional second step, a request for a route is entered at the client device and transmitted to the server, which receives the request.
The server generates a route from a starting point to a destination along the road segments in its map database. This route is optimized to minimize estimated travel time according to the travel time estimates previously generated.
The route is then transmitted to the mobile client. If the server receives new information indicating that a previously transmitted route is no longer optimal, it may, with or without further input from a user, transmit a route time-optimized for current conditions to the client.
Traffic flow rate information for the road segments in the route may also be transmitted. These data can be used to generate travel time estimates at the client both for the total remaining route to be traveled and for time to arrive at locations where the route specifies a maneuver.
Estimates of travel time to a maneuver allow the navigator to optimize the time at which guidance is provided to a user regarding the maneuver. If a user is informed too early of a maneuver he may not be paying attention at the time the maneuver is to be preformed. If he is informed too late, he may not have time to execute the maneuver. Thus estimating the travel time to an anticipated maneuver allows providing superior guidance as compared to guidance provided when the navigator is a particular distance from the location of the anticipated maneuver.
As shown in FIG. 2, an automobile is following a route and must make a left turn. The navigator is programmed to give the driver a first notification of a turn 30 seconds before the estimated time of arrival (ETA) at the turn. The navigator makes a running estimate of the estimated of arrival at the turn, and when the ETA drops below 30 seconds, the driver is notified.

## Claims

1. A method of generating a route with a wireless client-server navigator, comprising the steps of:
providing a database of geographical information including road segments at a server;
receiving information on a continuous basis at the server representing traffic flow rates or traffic incidents along the road segments;
generating a route optimized to minimize travel time along the road segments based upon the traffic flow rates or traffic incidents;

transmitting the route to a mobile client; and
wherein traffic flow rate or traffic incident data associated with the transmitted route is transmitted to a client along with the route.

2. A method of generating a route with a wireless client-server navigator, comprising the steps of:
providing a database of geographical information including road segments at a server;
receiving information on a continuous basis at the server representing traffic flow rates or traffic incidents along the road segments;
generating a route optimized to minimize travel time along the road segments based upon the traffic flow rates or traffic incidents;

transmitting the route to a mobile client; and
wherein: when traffic flow rate data or traffic incident data arrives at the server after a route has been provided to a client;
the server recalculates a time-optimized route based on previous and new traffic flow rate data and/or traffic incident data; and
if the newly calculated route differs from the route previously sent to a mobile client, a newly calculated route is sent to the client.