Inferring road speeds for context-sensitive routing

• US 7,706,964 B2
• Filed: 06/30/2006
• Issued: 04/27/2010
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Koch, Paul B., Horvitz, Eric J., Srinivasan, Sridhar, Subramani, Murugesan S.
• Primary Examiner(s): Tran; Dalena
• Application Number:
  US11/428,175
• Publication Number:
  US 20080004789A1
• Time in Patent Office: 1,397 Days
• Field of Search: 701117-119, 701/201, 701/202, 701207-209, 701/211, 342/357.13, 340/990, 340/995
• US Class Current: 701/117
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0141 for traffic information dissemination
• CPC Class Codes: G08G 1/096811 where the route is computed offboard

Abstract

Sensing, learning, inference, and route analysis methods are described that center on the development and use of models that predict road speeds. In use, the system includes a receiver component that receives a traffic system representation, the traffic system representation includes velocities for a plurality of road segments over different contexts. A predictive component analyzes the traffic system representation and automatically assigns velocities to road segments within the traffic system representation, thereby providing more realistic velocities for different contexts where only statistics and/or posted speed limits were available before. The predictive component makes predictions about velocities for road segments at a current time or at specified times in the future by considering available velocity information as well as such information as the properties of roads, geometric relationships among roads of different types, proximal terrain and businesses, and other resources near road segments, and/or contextual information.

Claims

1. A system that facilitates predicting road speeds or probability distributions over speeds for road segments not associated with sensed data for all desired contexts, comprising:

a receiver component that receives a traffic system representation, the traffic system representation includes sensed velocities for at least a portion of a plurality of road segments over different contexts; and

a predictive component that

determines that a sensed velocity is not available for a first road segment of the plurality of road segments; and

analyzes the traffic system representation and automatically assigns at least one of an average velocity and a probability distribution over velocities to the first road segment within the traffic system representation, by;

identifying at least one similar road segment that is similar to the first road segment and for which sensed velocities are available in a context, and

predicting, for the context, at least one of the average velocity and the probability distribution over velocities for the first road segment based on the sensed velocities available for the identified at least one similar road segment.

2. The system of claim 1, the predictive component comprises a machine learning component that utilizes machine learning techniques to determine patterns and trends within the traffic system representation between road segments, the predictive component assigns the at least one of the average velocity and the probability distribution over velocities based at least in part upon the determined patterns and trends.

3. The system of claim 1, the predictive component comprises a context analyzer component that determines a sensed velocity with respect to the road segment given a different context, the predictive component assigns the at least one of the average velocity and the probability distribution over velocities as a function of the sensed velocity given the different context.

4. The system of claim 1, the predictive component comprises a road type analyzer component that locates sensed velocities associated with road segments that are labeled with a similar road type as the road segment, the predictive component assigns the at least one of the average velocity and the probability distribution over velocities as a function of the sensed velocities associated with the road segments of similar type as the road segment.

5. The system of claim 1, the traffic system representation includes a weighted graph, where nodes represent intersections, edges represent road segments of the plurality of road segments between the intersections, and weights are based at least in part upon statistics representing road velocities of the road segments.

6. The system of claim 5, the weights within the traffic system representation alter as context alters.

7. The system of claim 5, the traffic system representation includes context-dependent road speeds, data indicating road types of road segments, data indicating relationships to other roads, roads associated with traffic flow problems, data indicating posted speed limits, data indicating type of terrain, data indicating businesses and services, and types of buildings that are associated with road segments.

8. The system of claim 5, the predictive component analyzes real-time sensed parameters and automatically assigns at least one of the average velocity and the probability distribution over velocities to the road segment based at least in part upon spatial relationships between road segments and the real-time sensed parameters, the real-time sensed parameters include at least one of location of accidents, weather, and sensed traffic flows.

9. The system of claim 1, further comprising a second traffic system representation, the predictive component assigns one or more velocity statistics to a road segment within the second traffic system representation based at least in part upon the analysis of the traffic system representation.

10. The system of claim 1 being a route planning system, the route planning system utilizes at least one of a Dykstra, A*, variant of Dykstra, and variant of A* search algorithm together with at least one of the average velocity and the probability distribution over velocities to output a route between points to a user.

11. The system of claim 10, the output route is for one of a current time and a time in the future, the route planning system outputs the route based at least in part upon predictions of contextual data, wherein the predictions are based upon evidence collected at a previous point in time.

12. The methodology of claim 11, further comprising:

receiving a request for driving directions; and

outputting driving directions based at least in part upon the request and the automatically predicted travel velocity statistics.

13. The methodology of claim 12, further comprising outputting the driving directions for a future time of travel, wherein at least one currently sensed parameter is ignored when outputting the driving directions.

14. The methodology of claim 13, further comprising utilizing at least one of a Dykstra, A*, variant of Dykstra, and variant of A* search algorithm for outputting the directions.

15. A methodology for predicting statistics relating to velocities on road segments within a traffic system representation comprises:

with at least one processor;

analyzing sensed data associated with a traffic system, the sensed data includes travel velocity statistics over at least a portion of the road segments given different contexts;

determining that travel velocity statistics are not available for a first road segment of the road segments; and

automatically predicting a travel velocity statistic for the first road segment based at least in part upon the analysis, by;

identifying at least one similar road segment that is similar to the first road segment and for which sensed data is available in a context, and

predicting, for the context, the travel velocity statistic for the first road segment based on the sensed data available for the identified at least one similar road segment.

16. The methodology of claim 15, analyzing the sensed data comprises reasoning over the sensed data to determine correlations between road segment types and average travel velocities.

17. The methodology of claim 15, further comprising utilizing at least one of ad hoc and structured sensing for obtaining travel velocity statistics with respect to road segments within the traffic system.

18. The methodology of claim 15, further comprising analyzing the traffic system representation to locate representations of road segments that are not assigned one or more statistics representing travel velocities for each desired context.

19. The method of claim 15, further comprising analyzing at least one of context-dependent road speeds, data indicating road types of road segments, data indicating relationships to other roads, roads associated with traffic flow problems, data indicating posted speed limits, data indicating type of terrain, data indicating businesses and services, and types of buildings that are associated with road segments in connection with automatically predicting travel velocity statistics with respect to road segments.

20. A system comprising computer-implemented means that, when executed by a processor, create a robust traffic system representation, the computer-implemented means comprising:

computer-implemented means for receiving sensed travel velocity statistics with respect to at least a portion of road segments in a travel system;

computer-implemented means for analyzing, by the processor, the sensed travel velocity statistics;

computer-implemented means for determining that travel velocity statistics are not available for a first road segment of the road segments; and

computer-implemented means for predicting a travel velocity statistic over a plurality of contexts for the first road segment based at least in part upon the analysis, by;

identifying at least one similar road segment that is similar to the first road segment and for which sensed data is available in the plurality of contexts, and

predicting, for the plurality of contexts, the travel velocity statistic for the first road segment based on the sensed data available for the identified at least one similar road segment.