Ultrafast Euclidean Shortest Path Computation Using Hub Labeling

Jinchun Du, Bojie Shen, Muhammad Aamir CheemaAAAI 2023 · DOI

TL;DR

This paper introduces Euclidean Hub Labeling (EHL), a novel algorithm for computing shortest paths in environments with polygonal obstacles. EHL significantly outperforms existing state-of-the-art methods, achieving 1-2 orders of magnitude speedup in query time by adapting the hub labeling technique, traditionally used for road networks, to the geometric domain.

What Problem Does This Paper Address?

Finding the shortest path between two points in a 2D plane containing obstacles is a fundamental problem with applications in robotics, game development, and indoor navigation. Existing methods, like End Point Search (EPS), often rely on identifying all obstacle vertices visible from the start and end points, which can lead to a large number of candidate paths and slow query times. While EPS is efficient, it still requires significant computation to determine visibility and explore potential paths. This paper aims to bridge this gap by developing a faster query processing method for this problem.

Methods

The core innovation of EHL lies in adapting the "hub labeling" technique, a successful approach for shortest path queries in road networks, to the Euclidean plane with obstacles. The process involves two main phases:

  • Offline Preprocessing:
    1. Visibility Graph Construction: A graph is built where nodes are the convex vertices of obstacles, and edges connect co-visible vertices.
  • Hub Labeling on Visibility Graph: Standard hub labeling is applied to this graph, creating labels for each vertex that store "hub" vertices and distances.
  • Grid Superimposition: The Euclidean plane is divided into a uniform grid.
  • Visibility List Creation: For each grid cell, a "visibility list" is created, containing convex vertices visible from that cell.
  • Via Label Generation: For each cell, "via labels" are generated. These labels link grid cells to hub labels of visible vertices, effectively transferring the shortest path information from the graph to the grid. Several pruning rules (PR1-PR4) and an optimization (OP) are introduced to significantly reduce the number of labels stored, making the preprocessing more efficient and the query phase faster.
  • Online Query Processing:
    1. Cell Identification: The grid cells containing the source (s) and target (t) points are identified.
  • Co-visibility Check: If s and t are directly visible, the Euclidean distance is returned.
  • Label Merging: If not co-visible, the algorithm efficiently merges the "via labels" from the source and target cells, looking for common hub nodes. The shortest path distance is then computed using these merged labels.

Datasets

The authors evaluated EHL on widely used grid map benchmarks, specifically mentioning "Dragon Age Origins (DAO)", "Dragon Age II (DA)", "Baldur's Gate II (BG)", and "StarCraft (SC)". These benchmarks are described as having underlying grids, and the experiments used a total of 373 game maps.

Key Insights and Ideas

  • Adapting Graph Techniques to Geometry: The paper demonstrates that successful graph algorithms like hub labeling can be adapted to solve geometric problems, offering significant performance gains.
  • Grid as an Intermediate Layer: Using a uniform grid to store and propagate hub labels from vertices to cells is a key insight. This allows for efficient query processing by reducing the problem to operations on a smaller set of grid cells rather than individual vertices.
  • Pruning is Crucial: The effectiveness of EHL heavily relies on the introduced pruning rules (PR1-PR4) and optimization (OP). These techniques are essential for managing the complexity and size of the labels, preventing them from becoming prohibitively large.
  • Trade-off Between Grid Size and Performance: The size of the grid cells impacts both preprocessing cost and query performance. Larger cells reduce the number of cells to process but can increase query time for simpler cases, while smaller cells increase preprocessing but can be faster for complex queries.

Key Results

  • Significant Speedup: EHL achieved 1-2 orders of magnitude faster query performance compared to state-of-the-art algorithms like EPS-CPD and Polyanya.
  • Preprocessing and Memory: EHL has larger preprocessing time and memory requirements than EPS-CPD and EPS-HL, especially for smaller grid cells. However, these costs decrease significantly as grid cell sizes increase.
  • Pruning Effectiveness: Ablation studies showed that pruning rules and the optimization significantly reduce build time, memory usage, and query performance. The optimization (OP) was found to be the most important enhancement for query performance.

Limitations and Future Work

  • Preprocessing Cost: The paper acknowledges that the preprocessing time and memory for EHL are larger than some competitors, particularly for smaller grid cells.
  • Future Work: The authors suggest investigating whether other techniques specifically designed for Euclidean plane labeling could further improve performance. They also plan to focus on reducing the preprocessing cost of EHL.

Summary updated

BibTeX
@inproceedings{du2023ultrafast,
  author = {Jinchun Du and Bojie Shen and Muhammad Aamir Cheema},
  title = {{Ultrafast Euclidean Shortest Path Computation Using Hub Labeling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26463},
}
Figure