Methods and systems for providing geotemporal graphs

• US 9,341,486 B2
• Filed: 04/24/2014
• Issued: 05/17/2016
• Est. Priority Date: 04/24/2013
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Aragon, Cecilia, Hong, Sungsoo, Yoon, Jong-Chul
• Primary Examiner(s): Beaulieu, Yonel
• Assistant Examiner(s): Ramesh, Krishnan
• Application Number:
  US14/261,055
• Publication Number:
  US 20140324327A1
• Time in Patent Office: 754 Days
• Field of Search: None
• US Class Current: 1/1
• 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 non-transitory computer readable memory, the 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 at an original location for that node in the area represented by the graph, wherein the infrastructure is a transportation infrastructure including a representation of one or more of;

roadways, walkways, railways, shipping lanes, air traffic, or any combination thereof;

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; and

updating a visual representation of the graph by;

calculating, for each node of the multiple nodes 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 selected node of the multiple nodes added to the graph, a warp vector identifying a distance to move the selected node from the selected node'"'"'s original location and a direction to move the selected node from the selected node'"'"'s original location;

wherein the direction to move the selected node corresponds to a direction defined by a location emanating line connecting the selected location with the selected node'"'"'s original location; and

wherein the distance to move the selected node is defined such that a final distance between the selected location and the selected node, after the selected node is moved the distance to move the selected node in the direction to move the selected node, is a representation of the calculated travel time between the selected node and the selected location; and

applying a warping algorithm to the graph, using the defined warp vectors, such that each node of the multiple nodes added to the graph 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 roadway infrastructure and the travel conditions comprise current vehicular traffic conditions.

3. 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.

4. 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.

5. The computer readable memory of claim 1 wherein, for at least one node of the multiple nodes:

the original location for the at least one node on the graph is at a point along the infrastructure that, based on the infrastructure usage data, is at a specified travel time interval from the selected location; and

the distance to move the at least one node corresponds to the distance from the original location of the at least one node to an isochronous contour defined for the specified travel time interval that was used in determining the original location for the at least one node.

6. 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, wherein each point has an original location,

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, wherein the infrastructure is a transportation infrastructure including a representation of one or more of;

roadways, walkways, railways, shipping lanes, air traffic, or any combination thereof; and

updating a visual representation of the graph by;

calculating, for each point of the multiple points 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 selected point of the multiple points added to the graph, a warp vector identifying a distance to move the selected point from the selected point'"'"'s original location and a direction to move the selected point from the selected point'"'"'s original location,

wherein the direction to move the selected point corresponds to a direction defined by a location emanating line connecting the selected location with the selected point'"'"'s original location; and

wherein the distance to move the selected point is defined such that a resulting distance between the selected location and the selected point, after the selected point is moved the distance to move the selected point in the direction to move the selected point, is a representation of the calculated travel time between the selected point and the selected location; and

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

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

8. The method of claim 6 wherein the at least one of the travel times is calculated as a shortest travel time.

9. The method of claim 6 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.

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

a memory; and

one or more processors;

wherein the memory stores instructions that, when executed by the one or more processors, cause the visual display system to perform operations comprising;

displaying a visual representation of a geographic area comprising an infrastructure, wherein the infrastructure is a transportation infrastructure including a representation of one or more of;

roadways, walkways, railways, shipping lanes, air traffic, or any combination thereof;

receiving input specifying a location and a time; and

upon receiving the location, updating the visual representation of the geographic area by;

defining, for each selected point of multiple points on the geotemporal graph, a warp vector identifying a distance to move the selected point from an original location of the selected point and a direction to move the selected point from the selected point'"'"'s original location,

wherein the direction to move the selected point corresponds to a direction defined by a location emanating line connecting the selected location with the selected point'"'"'s original location, and

wherein the distance to move the selected point is defined such that a resulting distance between the selected location and the selected point, after the selected point is moved the distance to move the selected point in the direction to move the selected point, is a representation of an expected travel time between the selected point and the selected location, accounting for traffic conditions at the specified time; and

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

11. The visual display system of claim 10 wherein:

receiving the input includes receiving a location signal indicating a current location of a computing device; and

the operations further comprise periodically modifying the visual representation of the geographic area with a new location corresponding to the current location such that displayed spatial distances between the new location and the multiple points of the geographic area represent new expected travel times between the new location and the multiple points, wherein the new expected travel times account for traffic conditions.

12. The visual display system of claim 10 wherein:

receiving the input includes receiving user input indicating a desired category of destination; and

the operations further comprise, upon receiving the desired category of destination, displaying on the visual representation of the geographic area multiple identifiers, wherein each of the multiple identifiers correspond to the desired category.

13. The visual display system of claim 10 wherein:

the specified location is a first location; and

the operations further comprise;

receiving a second location; and

upon receiving the second location, updating the visual representation of the geographic area such that a route is displayed between the first location and the second location.

14. The visual display system of claim 10 wherein the operations further comprise:

receiving an end location and a reverse direction user input; and

upon receiving the reverse direction user input, updating the visual representation of the geographic area such that displayed spatial distances between the end point and the multiple points of the geographic area represent an expected travel time from the end location to the multiple points, wherein the expected travel times account for traffic conditions at the specified time.

15. The visual display system of claim 10 wherein:

each expected travel time between the specified location and each of the multiple 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.

16. The visual display system of claim 10 wherein:

the specified location is a destination; and

the operations further comprise;

receiving, as at least some of the multiple points, indications of multiple start points; and

updating the visual representation of the geographic area by displaying a spatial distance between each of the multiple start points and the destination 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.

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

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

19. The visual display system of claim 10 wherein the visual representation of the geographic area is further updated such that the visual representation of the geographic area is overlaid with a series of concentric equally spaced circles centered at the specified location.