Online Graph Pruning for Pathfinding On Grid Maps

By Daniel Damir Harabor, Alban Grastien. AAAI Conference on Artificial Intelligence, 2011

426 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/9cee0ebab3d96627359424d8655161efc67f76bf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Graphics and Computer-Aided Design

Vijay R. Kumar

In Computer Vision and Pattern Recognition

Citations in the corpus

Planning Dynamically Feasible Trajectories for Quadrotors Using Safe Flight Corridors in 3-D Complex Environments (2017, methodology): “As defined in [16], the natural neighbors refer to the set of nodes that remain after pruning.”