Path planning is a cornerstone of robotics, navigation, and game development. To achieve the near-instantaneous response times expected in modern applications, researchers often rely on preprocessing-based algorithms. These methods analyze a map in advance to create auxiliary data structures that accelerate subsequent queries.
Two prominent techniques have historically dominated different domains: Contraction Hierarchies (CH), the standard for road networks, and Subgoal Graphs (SG), which excel on grid-based maps. While CH is a general-purpose graph technique that adds "shortcuts" between nodes, SG is a domain-specific approach that identifies critical "subgoals" (like obstacle corners) to simplify the search space.
This research bridges the gap between these two methodologies. By infusing the CH framework with the concept of "reachability" from Subgoal Graphs, the authors develop hybrid algorithms that significantly outperform the state-of-the-art in both speed and memory efficiency on grid-based benchmarks.
The Reachability Relation ($R$)
The core innovation of this work is the formalization and application of the Reachability Relation ($R$). In the context of a grid, two nodes are considered $R$-reachable if a shortest path between them can be determined through a simple, "canonical" rule—such as a straight line or a specific sequence of diagonal and cardinal moves—without needing a complex search.
By identifying these $R$-reachable pairs, the authors can replace the traditional "unpacking" of shortcuts (which can account for up to 60% of query time) with a fast, mathematical refinement operation. This allows the system to calculate moves on the fly rather than retrieving them from memory.
Hybrid Pathfinding Algorithms
The authors propose three primary ways to augment Contraction Hierarchies with this reachability logic:
- CH-R (CH with R-Refine): This variant uses standard CH but optimizes the query phase. Any shortcut that is $R$-reachable is "refined" using the fast canonical rule instead of a recursive lookup.
- RCH (R-Contraction Hierarchies): This version only allows the creation of shortcuts if the two nodes are $R$-reachable. This restriction drastically reduces the number of edges the system must store, leading to massive memory savings.
- CH-SG (CH on Subgoal Graphs): This approach treats the Subgoal Graph as the "core" of a hierarchy. During a query, the algorithm uses an "R-connect" operation to jump directly from the start and goal positions to the high-level subgoal network, bypassing the lower levels of the graph entirely.
Key Insights and Performance
A major theoretical contribution of the paper is the realization that Subgoal Graphs are essentially two-level hierarchies. In this view, the subgoals form the "core" level, while all other nodes reside in a lower level. This insight allowed the authors to apply multi-level CH logic to SGs, creating the hybrid CH-SG-R variant.
On standard grid benchmarks, including game maps from Dragon Age: Origins and complex mazes, these hybrid algorithms demonstrated clear dominance:
- Speed: CH-SG-R is 3.6x faster than standard Contraction Hierarchies.
- Memory: It requires 4.6x less memory than previous state-of-the-art CH implementations.
- Efficiency: On non-random maps, the algorithms can ignore 97–98% of the graph's nodes and edges during the search phase.
Conclusion and Future Directions
While the current success of these hybrid algorithms is tied to grid-based "canonical-freespace-reachability," the underlying theory is general. The authors suggest that the next challenge lies in identifying effective reachability relations for other domains, such as road networks or state-lattices used in non-holonomic robot motion planning. By unifying CH and SG, this work provides a more flexible and powerful toolkit for real-time navigation in complex environments.
Summary updated