Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding

Sabine StorandtIJCAI 2024

Introduction

In shortest-path computation, researchers have long faced a stark trade-off between query speed and storage overhead. Hub Labeling (HL) offers near-instantaneous distance queries by precomputing labels for every node, but its memory requirements are often prohibitive for large-scale graphs. Conversely, Landmark-based A* (ALT) is highly space-efficient but orders of magnitude slower.

Landmark Hub Labeling (LHL) was introduced to bridge this gap by allowing queries to be satisfied either by a precomputed hub or a "perfect landmark" that provides a tight lower bound. However, initial LHL construction algorithms were computationally expensive ($O(n^3)$) and failed to scale. This paper presents novel, scalable construction algorithms and query optimizations that make LHL practical for massive networks.

Scaling Landmark Hub Labeling

The core challenge in LHL is determining which distances can be safely delegated to landmarks rather than stored in expensive hub labels. The authors propose a "Middle vs. Ends" strategy: while Hub Labeling is efficient at covering the middle sections of paths, landmarks are exceptionally good at covering the path endpoints. By exploiting this synergy, LHL can prune redundant information from labels.

Conceptual diagram of a graph with landmarks (w1-w4) used to bound path distances between source s and target t.

Key Algorithmic Innovations

To achieve scalability, the paper introduces several techniques:

  1. TreeSelect: A construction algorithm that computes labels node-by-node using shortest-path trees, eliminating the need for all-pairs shortest path precomputation.
  2. HHL Pruning (Exhaustive & Economic): These methods take existing Hierarchical Hub Labels and remove entries if a landmark already provides the exact distance. The "Exhaustive" version minimizes label size, while the "Economic" version offers a faster heuristic alternative.
  3. Edge Oracle: A constant-time mechanism that stores the "last edge" of a path within the label. This allows the query algorithm to instantly distinguish between hubs and landmarks, significantly accelerating path extraction.
  4. Center Hub Labeling: For applications where bounded suboptimality is acceptable, $k$-center clustering is used to force nodes to share hubs, further slashing memory usage.

Experimental Results

The proposed methods were evaluated on grid maps from game AI benchmarks and large-scale European road networks. The results demonstrate that LHL is not only more space-efficient than standard HL but often faster, as smaller labels allow for quicker linear scans during queries.

Comparison of label sizes across different algorithms as the number of nodes increases. HHL-exha and HHL-eco show significant reductions in label size compared to standard HHL.

Performance Highlights

  • Query Speed: The optimized LHL (HPC-LHL) achieved query speeds over 50,000x faster than landmark-based A* (ALT).
  • Space Efficiency: On grid maps, exhaustive pruning (HHL-exha) reduced average label sizes by over 70% compared to standard Hub Labeling.
  • Scalability: The new pruning methods successfully processed road networks with 1 million nodes in approximately one hour, a task that was previously computationally infeasible.
  • Ranking Impact: The study found that using a "KC-order" (based on $k$-center clustering) for landmark selection is significantly more effective than the standard "CH-order" used in traditional hierarchical labeling.

Conclusion

By introducing scalable construction and pruning techniques, this work transforms Landmark Hub Labeling from a theoretical hybrid into a practical solution for large-scale pathfinding. The resulting system offers the lightning-fast performance of Hub Labeling with a memory footprint that is manageable even for massive real-world networks.

Summary updated

BibTeX
@inproceedings{storandt2024scalable,
  author = {Sabine Storandt},
  title = {{Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure