Online Graph Pruning for Pathfinding on Grid Maps

Select |




Print


Harabor, Daniel; Grastien, Alban

Harabor, Daniel; Grastien, Alban


2011-08-07


Conference Material


AAAI Conference on Artificial Intelligence (AAAI)


San Francisco, USA


Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A* by an order of magnitude and more and report significant improvement over the current state of the art.


pathfinding a* symmetry search


http://www.aaai.org/Conferences/AAAI/aaai11.php


nicta:4856


Harabor, Daniel; Grastien, Alban. Online Graph Pruning for Pathfinding on Grid Maps. In: AAAI Conference on Artificial Intelligence (AAAI); San Francisco, USA. 2011-08-07.



Loading citation data...

Citation counts
(Requires subscription to view)