TRAVEL PATH IDENTIFICATION BASED UPON STATISTICAL RELATIONSHIPS BETWEEN PATH COSTS

• US 20160003620A1
• Filed: 07/07/2014
• Published: 01/07/2016
• Est. Priority Date: 07/07/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kapoor, Ashish, Eden, Semiha Ece Kamar, Horvitz, Eric, Dey, Debadeepta, Kolobov, Andrey, Caruana, Richard
• Granted Patent: US 9,714,831 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 5/0008 with other aircraft
• CPC Class Codes: G08G 5/0021 located in the aircraft
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0078 for monitoring traffic from the aircraft radar or analogous systems specially adapted for traffic control G01S13/91
• CPC Class Codes: G08G 5/0091 for monitoring atmospheric conditions radar or analogous systems specially adapted for meteorological use G01S13/95; meteorology G01W

Abstract

Various technologies pertaining to dynamically identifying travel segments to be taken by a traveler traveling in a region are described herein, where observations about travel segments in the region are sparse and subject to alteration. A computer-implemented graph can be loaded into a memory, where the computer-implemented graph is representative of the region. The computer-implemented graph includes nodes that represent locations in the region and edges that represent travel segments of the region, where the edges have costs assigned thereto, and further where there is a defined statistical relationship between the costs. When an observation about a travel path is received, using the computer-implemented graph, inferences can be made about costs of traversing other travel paths in the region.

Claims

1. A method executed by a processor of a computing device, the method comprising:

receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a traveler can travel, the nodes representative or respective locations in the region, the edges representative of travel segments between locations, wherein each edge in the edges connects a respective pair of nodes in the nodes, each node in the nodes connected to at least one other node by a respective edge in the edges, the edges have respective distributions over costs assigned thereto, and the respective costs have a statistical relationship therebetween;

receiving an observation about a travel segment in the travel segments;

responsive to receiving the observation, updating the respective distributions over the costs of the edges in the computer-implemented graph based upon the observation and the statistical relationship;

identifying a particular travel segment in the travel segments over which the traveler is to travel, the identifying based upon the updating of the respective distributions over the costs of the edges and a destination location of the traveler; and

outputting a signal that causes the traveler to travel along the particular travel segment in the travel segments.

2. The method of claim 1, the traveler generates the observation about the travel segment.

3. The method of claim 2, wherein the respective distributions over the costs of the edges are updated in the computer-implemented graph as the traveler travels in the region.

4. The method of claim 1, the traveler being one of an airplane, a water vessel, a spacecraft, a drone, a robot, an automobile, a human, or a data packet.

5. The method of claim 1, the observation generated by an entity in the region other than the traveler.

6. The method of claim 5, the entity in the region being another traveler in the region.

7. The method of claim 1, statistical relationship being a joint probability distribution over the costs.

8. The method of claim 7, the joint probability distribution being a Gaussian distribution.

9. The method of claim 7, wherein identifying the particular travel segment in the travel segments over which the traveler is to travel comprises:

sampling from the joint probability distribution to acquire respective discrete cost values for the edges;

identifying a travel route from a current location of the traveler to the destination location that has a lowest aggregate cost from amongst possible travel routes from the current location of the traveler to the destination location, the travel route being over multiple travel segments, a first travel segment in the travel route being the particular travel segment; and

identifying the particular travel segment based upon the identifying of the travel route.

10. The method of claim 9, wherein identifying the particular travel segment in the travel segments over which the traveler is to travel further comprises:

sampling from the joint probability distribution multiple times to acquire multiple discrete cost values for each edge in the edges;

for each edge in the edges, computing a respective average cost value; and

identifying the travel route based upon respective average cost values for the edges.

11. The method of claim 1, further comprising repeating the acts of:

receiving an observation;

updating the respective costs of the edges;

identifying a particular travel segment in the travel segments; and

outputting a signal that causes the traveler to travel along the particular travel segment in the travel segments until the traveler reaches the destination location.

12. The method of claim 1, the statistical relationship is a function of time.

13. A computing system comprising:

a processor; and

a memory that comprises;

a computer-implemented graph, the computer-implemented graph represents a region that includes a traveler, the computer-implemented graph comprises;

nodes that represent locations in the region;

edges that represent travel segments in the region, each node in the nodes is connected to at least one other node in the nodes by a respective edge in the edges; and

cost distributions that are respectively assigned to the edges, the cost distributions having a statistical relationship therebetween; and

a plurality of components that are executed by the processor, the plurality of components comprising;

a graph updater component that receives an observation for a travel segment in the region, the travel segment in the region represented by a first edge in the edges, the graph updater component updates a cost distribution assigned to the first edge based upon the observation, the graph updater component updates respective cost distributions assigned to other edges of the graph based upon the cost distribution assigned to the first edge and the statistical relationship; and

an edge selector component that selects an edge in the edges based upon;

the cost distribution assigned to the first edge;

the respective cost distributions assigned to the other edges; and

a destination location in the region for the traveler, the edge representative of a travel segment that is to be taken by the traveler to reach the destination location.

14. The computing apparatus of claim 13, the statistical relationship being a joint probability distribution over the edges.

15. The computing apparatus of claim 14, the graph updater component comprises a constraint updater component that updates a smoothness constraint for the cost distributions based upon the observation, the smoothness constraint included in the statistical relationship.

16. The computing apparatus of claim 13, the edge selector component transmits a signal to the traveler that causes the traveler to travel the travel segment.

17. The computing apparatus of claim 13, the graph updater component dynamically updates the graph as observations for travel segments are received, the edge selector component updates selections of edges dynamically as the graph is updated.

18. The computing apparatus of claim 13, the observation received from a sensor of the traveler, the graph updater component dynamically updates the graph as further observations are received from the sensor, the edge selector component dynamically selects travel segments based upon location of the traveler in the region and the respective cost distributions of the edges.

19. The computing apparatus of claim 13, the observation received from a sensor of a second traveler in the region.

20. A computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

updating a first cost distribution over a first edge in a computer-implemented graph based upon an observation about a first travel segment in a region, the first edge representative of the first travel segment;

updating a second cost distribution over a second edge in the computer-implemented graph based upon the cost distribution over the first edge and a statistical relationship between the first edge and the second edge, the second edge representative of a second travel segment in the region; and

outputting an indication that a traveler is to travel over the second edge in the computer-implemented graph based upon the second cost distribution.