ROUTE PLANNING WITH CONTINGENCIES

• US 20080004802A1
• Filed: 06/30/2006
• Published: 01/03/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J.
• Granted Patent: US 8,126,641 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

A route planning system comprises a receiver component that receives a request for directions between two points. A route generator component outputs directions between the two points, the directions include a contingency such that an alternate route is provided, a selected route between the two points is dependent upon a user perception at a geographic location that corresponds to the contingency.

Claims

1. A route planning system comprising the following computer-executable components:

a receiver component that receives a request for directions between two or more points; and

a route generator component that outputs directions between the two or more points, the directions include a contingency such that an alternate route is provided, the alternate route determined based at least in part upon information about a flow of traffic with respect to at least one road segment within the directions.

2. The route planning system of claim 1, the information about the flow of traffic is in a form of at least one of a probability distribution of observed velocity statistics, a variance of observed velocity statistics, a standard deviation of observed velocity statistics, an upper bound on observed velocity statistics, and a lower bound on observed velocity statistics.

3. The route planning system of claim 1, the route generator component comprises a branching component that determines where to place the contingency based at least in part upon the information about the flow of traffic.

4. The route planning system of claim 3, the branching component determines where to place one or more contingencies by performing multiple searches over one of a database and a predictive model that describes flows within a traffic system with respect to at least one of a particular context and a combination of contexts.

5. The route planning system of claim 4, the database comprises a weighted graph, where nodes represent intersections, edges represent road segments, and weights associated therewith are a function of a probability distribution of one of observed and inferred speed of road segments and intersections represented within the database, the weights alter as time of day alters.

6. The route planning system of claim 3, the branching component generates one or more candidate contingent routes based upon an average flow for one or more specified contexts.

7. The route planning system of claim 6, the branching component determines a candidate contingent route based upon risk preferences provided by a user.

8. The route planning system of claim 1, further comprising a profile matching component that assigns an initiator of the request for directions with a driving profile, the directions are output based at least in part upon the assigned profile.

9. The route planning system of claim 1, further comprising a branching component that places multiple contingencies within the directions to provide multiple alternate routes, a selected route is dependent upon user perceptions at one or more geographic location that corresponds to at least one of the contingencies.

10. The route planning system of claim 1, the route generator component utilizes search methods to generate one or more contingent route constellations that provide assistance with travel between the two or more points based upon a consideration of overall expected duration of the one or more contingent route constellations.

11. The route planning system of claim 1, further comprising a branching component that determines where to place one or more contingencies based at least in part upon one or more of cost, difficulty, and reliability of evaluating an observation point at a possible contingency point.

12. The route planning system of claim 1, the route generator component utilizes one of a Dykstra search algorithm, an A* search algorithm, a Dykstra variant search algorithm, and an A* variant search algorithm in connection with outputting the directions and selecting the alternate route.

13. The system of claim 1, the route generator component determines a first route given a first context and a second route given a second context, location of the contingency within the directions results from a comparison of the first and second routes.

14. A method for outputting directions between two locations comprising the following computer-executable acts:

receiving a request for directions between a beginning point and a destination point;

determining a first route between the two points;

determining where to place a branch point within the first route, the branch point is a beginning of an alternate route to the destination point; and

outputting directions that include the branch point.

15. The method of claim 14, further comprising:

determining the first route by analyzing one of a context provided by a user and an assumed context.

16. The method of claim 14, the output directions include instructions on which route to select based upon user observations near the branch point.

17. The method of claim 14, determining where to place the branch point within the first route comprises detecting road segments within the first route that are associated with a variance of traffic flow that is above variances of traffic flow of other road segments.

18. The method of claim 14, further comprising:

assigning a driving profile to an initiator of the received request; and

determining where to place the branch point based at least in part upon the assigned driving profile.

19. The method of claim 14, further comprising generating a contingency plan within the directions and outputting the contingency plan to a user.

20. A route planning system, comprising:

computer-implemented means for receiving a request for directions between a beginning point and a destination point; and

computer-implemented means for providing directions to an initiator of the request, the directions comprise multiple alternate routes and instructions regarding which of the routes to take based at least in part upon user perceptions where the multiple alternate routes diverge.