Customizable route planning using graphics processing unit

Patent metadata

Field	Value
Publication number	US-10062188-B2
Application number	US-201414296644-A
Country	US
Kind code	B2
Filing date	Jun 5, 2014
Priority date	Jun 5, 2014
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

Customizable route planning is a technique for computing point-to-point shortest paths in road networks. It includes three phases: preprocessing, metric customization, and queries. A graphics processing unit may be used, e.g., in the metric customization phase, to make customization even faster, enabling a wide range of applications including highly dynamic applications and on-line personalized cost functions.

First claim

What is claimed:

1. A method for determining a shortest path between an origin location and a destination location, comprising:
preprocessing, at a central processing unit (CPU) of a computing device, a graph comprising a plurality of vertices and a plurality of edges to generate preprocessed data comprising a partitioned graph, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost;
performing, at a graphics processing unit (GPU) of the computing device, metric customization using the partitioned graph to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph, wherein performing metric customization comprises:
copying a plurality of costs of a plurality of mapping arcs to an array;
determining a plurality of costs of a plurality of arcs of the graph from the array;
performing a search phase using the plurality of arcs and the determined plurality of costs of the plurality of arcs; and
computing the metric customization data comprising a plurality of costs of shortcuts using results of the search phase; and

computing, at the CPU, a shortest path between the origin location and the destination location using the preprocessed data and the metric customization data, wherein the method further comprises:
the CPU sending metric information to the GPU for use by the GPU during the metric customization; and
the CPU copying metric customization data from the GPU to memory of the CPU.

2. The method of claim 1 , wherein the preprocessing is metric-independent.

3. The method of claim 1 , further comprising:
receiving a query at the computing device, the query comprising the origin location and the destination location.

4. The method of claim 1 , wherein the array is a shortcut array, and wherein the plurality of arcs are inner arcs and init arcs.

5. The method of claim 1 , wherein for determining the plurality of costs of the plurality of arcs a single kernel is created with one thread for each arc.

6. The method of claim 1 , wherein performing metric customization comprises search-based metric customization using the GPU.

7. The method of claim 1 , wherein performing metric customization comprises contraction-based metric customization using the GPU.

8. The method of claim 1 , wherein performing metric customization comprises using microinstructions with the GPU.

9. The method of claim 8 , wherein using microinstructions with the GPU comprises storing a microinstruction array in a global memory and storing a memory array in a shared memory.

10. The method of claim 1 , wherein the graph represents a network of nodes.

11. The method of claim 1 , wherein the graph represents a road map.

12. A method of determining a shortest path between two locations, comprising:
obtaining in a computing device, a graph comprising a plurality of vertices and edges, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost;
executing a preprocessing stage in a central processing unit (CPU) of the computing device, the preprocessing stage comprising generating preprocessed data comprising a partitioned graph;
executing a metric customization stage, in a graphics processing unit (GPU) of the computing device, to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph, wherein executing the metric customization stage comprises:
copying a plurality of costs of a plurality of mapping arcs to an array;
determining a plurality of costs of a plurality of arcs of the graph from the array;
performing a search phase using the plurality of arcs and the determined plurality of costs of the plurality of arcs; and
computing the metric customization data comprising a plurality of costs of shortcuts using results of the search phase;

computing, at the CPU, a point-to-point shortest path using the preprocessed data and the metric customization data without re-executing the preprocessing stage; and
outputting the point-to-point shortest path, by the computing device, wherein the method further comprises:
the CPU sending metric information to the GPU for use by the GPU during the metric customization; and
the CPU copying the metric customization data from the GPU to memory of the CPU.

13. The method of claim 12 , wherein executing the metric customization stage further comprises contraction-based metric customization using the GPU.

14. A system for determining a shortest path between two locations, comprising:
a central processing unit (CPU), of a computing device, that executes a preprocessing stage to generate preprocessed data comprising a partitioned graph comprising a plurality of vertices and edges, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost; and
a graphics processing unit (GPU), of the computing device, that performs search-based metric customization using the partitioned graph to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph,
wherein the CPU is configured to:
compute the shortest path between the two locations using the preprocessed data and the metric customization data; and
output the shortest path, and

wherein the CPU sends the metric information to the GPU for use by the GPU during the metric customization, and the CPU copies metric customization data from the GPU to memory of the CPU, and wherein the GPU performing search-based metric customization comprises the GPU configured to:
copy a plurality of costs of a plurality of mapping arcs to an array;
determine a plurality of costs of a plurality of arcs of the graph from the array;
perform a search phase using the plurality of arcs and the determined plurality of costs; and
compute the metric customization data comprising a plurality of costs of shortcuts using results of the search phase.

15. The system of claim 14 , wherein the CPU is configured to set up data structures on the GPU during the preprocessing stage, for use by the GPU during the metric customization.

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Delling Daniel
• Werneck Renato F
• Kobitzsch Moritz Helge

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G06T11/206 Primary

  Physics · mapped topic