METHODS AND SYSTEMS FOR PROVIDING GEOTEMPORAL GRAPHS

• US 20140324327A1
• Filed: 04/24/2014
• Published: 10/30/2014
• Est. Priority Date: 04/24/2013
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Aragon, Cecilia, Hong, Sungsoo, Samples, Benjamin, Yoon, Jong-Chul
• Granted Patent: US 9,341,486 B2
• Time in Patent Office: Days
• US Class Current: 701/117
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

Technology for generating geotemporal graphs is disclosed where geotemporal graphs provide representations of areas based on an expected travel time between points, instead of the geographical distance between points. Travel times may vary based on travel conditions, and geotemporal maps may be generated that show travel times that account for travel conditions. Generating geotemporal maps may include obtaining a graph, determining for several points a warp vector indicating graph how each point should be moved to represent a travel time to that point, and warping the graph according to the determined warp vectors.

Claims

1. A computer readable memory storing instructions that, in response to being executed by a computing device, cause the computing device to perform operations for providing a geotemporal graph using travel conditions, the operations comprising:

obtaining a graph, wherein the graph is a spatial representation of an area;

adding multiple nodes to the graph, wherein each node corresponds to a point in an infrastructure in the area represented by the graph;

adding at least two edges to the graph, wherein the edges represent sections of the infrastructure and connect nodes added to the graph;

receiving a selection of a location within the graph;

receiving infrastructure usage data indicating travel conditions on the infrastructure at a particular time;

calculating, for each node added to the graph, a travel time between that node and the selected location within the graph, wherein each travel time accounts for the received usage data indicating travel conditions;

defining, for each node added to the graph, a warp vector identifying a distance and direction to move that node such that the distance between the selected location and that node is a representation of the calculated travel time for that node; and

applying a warping algorithm to the graph, using the defined warp vectors, such that each node is moved according the distance and direction identified in that node'"'"'s corresponding warp vector.

2. The computer readable memory of claim 1 wherein the infrastructure is a transportation infrastructure representing one or more of the following:

roadways, walkways, and railways.

3. The computer readable memory of claim 1 wherein the infrastructure is a roadway infrastructure and the travel conditions comprise current vehicular traffic conditions.

4. The computer readable memory of claim 1 wherein the operations further comprise:

determining that the selected location within the graph does not correspond to a node, and in response;

adding a new node to the graph corresponding to the selected location within the graph; and

adding at least one edge to the graph connecting the new node with at least one other node.

5. The computer readable memory of claim 1 wherein:

the multiple nodes are added to the graph such that a greater concentration of nodes are located on the graph in areas determined to have more congestion; and

areas are determined to have more congestion based on one or more of current congestion conditions and historical congestion conditions.

6. The computer readable memory of claim 1 wherein the warping algorithm is a thin-plate spline-based warping algorithm.

7. A method for providing a geotemporal mapping using traffic data, the method comprising:

obtaining a graph, wherein the graph is a spatial representation of an area;

adding multiple points to the graph, receiving a selection of a location within the graph;

receiving infrastructure usage data indicating travel conditions on an infrastructure in the area of the graph at a particular time;

calculating, for each point added to the graph, a travel time between that point and the selected location within the graph, wherein each travel time accounts for the received usage data indicating travel conditions;

defining, for each point added to the graph, a warp vector identifying a distance and direction to move each point such that the distance between the selected location and that point is a representation of the calculated travel time for that point; and

applying a warping algorithm to the graph, using the defined warp vectors, such that each point is moved according the distance and direction identified in that point'"'"'s corresponding vector.

8. The method of claim 7 wherein (a) the location of at least one of the multiple points or (b) at least one edge that connect two points, was previously specified by a user of the system.

9. The method of claim 7 wherein travel time is calculated as a shortest travel time.

10. The method of claim 7 wherein adding multiple points to the graph comprises selecting from a specified set of nodes, a subset of nodes corresponding to a current zoom level or focus area.

11. A visual display system for presenting a geotemporal graph using traffic condition data, the system comprising:

a memory;

one or more processors;

a graph portion, implemented with the one or more processors, configured to display a visual representation of a geographic area comprising an infrastructure; and

an input portion configured to receive input specifying a location and a time;

wherein, upon receiving the location, the graph portion is updated such that a displayed spatial distance between the specified location and multiple other points of the geographic area represent an expected travel time between the specified location and the other points, wherein the expected travel times account for traffic conditions at the specified time.

12. The visual display system of claim 11 wherein:

the input portion is further configured to receive a location signal indicating a current location of a computing device; and

the graph portion is periodically updated with a new location corresponding to the current location such that the displayed spatial distance between the new location and the multiple other points of the geographic area represent new expected travel times between the new location and the multiple other points, wherein the new expected travel times account for traffic conditions.

13. The visual display system of claim 11 wherein:

the input portion is further configured to receive user input indicating a desired category of destination; and

upon receiving the desired category of destination, multiple identifiers are displayed on the graph portion, wherein each of the multiple identifiers correspond to the desired category.

14. The visual display system of claim 11 wherein:

the specified location is a first location;

the input portion is further configured to receive a second location; and

upon receiving the second location, the graph portion is updated such that a route is displayed between the first location and the second location.

15. The visual display system of claim 11 wherein:

the input portion is further configured to receive an end location and a reverse direction user input; and

upon receiving the reverse direction user input, the graph portion is updated such that the displayed spatial distance between the end point and the multiple other points of the geographic area represent an expected travel time from the end location to the other points, wherein the expected travel times account for traffic conditions at the specified time.

16. The visual display system of claim 11 wherein:

each expected travel time between the specified location and each of the other points is a round-trip travel time; and

the expected travel times account for traffic conditions both (a) going from the specified location to each other point and (b) going from each other point to the specified location.

17. The visual display system of claim 11 wherein:

the specified location is a destination;

the input portion is further configured to receive, as at least some of the multiple other points, indications of multiple start points; and

updating the graph portion comprises displaying a spatial distance between each of the multiple start points the destination location such that, for each of the multiple start points, the displayed spatial distance between that start point and the destination represents an expected travel time from that start point to the destination.

18. The visual display system of claim 17 wherein each of the multiple start points correspond to a location of an emergency response person or vehicle.

19. The visual display system of claim 11 wherein the specified time comprises one of now and a specified future time.

20. The visual display system of claim 11 wherein the graph portion is further updated such that the graph portion is overlaid with a series of concentric equally spaced circles centered at the specified location.