Online Graph Pruning for Pathfinding on Grid Maps
Daniel Harabor and Alban Grastien
NICTA and The Australian National University
Email: fi[email protected]
Abstract
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 hierar-
chical 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 iden-
tifies 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.
Introduction
Widely employed in areas such as robotics (Lee and Yu
2009), artificial intelligence (Wang and Botea 2009) and
video games (Davis 2000; Sturtevant 2007), the ubiqui-
tous undirected uniform-cost grid map is a highly popular
method for representing pathfinding environments. Regu-
lar in nature, this domain typically features a high degree
of path symmetry (Harabor and Botea 2010; Pochter et al.
2010). Symmetry in this case manifests itself as paths (or
path segments) which share the same start and end point,
have the same length and are otherwise identical save for the
order in which moves occur. Unless handled properly, sym-
metry can force search algorithms to evaluate many equiva-
lent states and prevents real progress toward the goal.
In this paper we deal with such path symmetries by devel-
oping a macro operator that selectively expands only certain
nodes from the grid, which we call jump points. Moving
from one jump point to the next involves travelling in a fixed
direction while repeatedly applying a set of simple neigh-
bour pruning rules until either a dead-end or a jump point is
reached. Because we do not expand any intermediate nodes
between jump points our strategy can have a dramatic pos-
itive effect on search performance. Furthermore, computed
Copyright
c
2011, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.
solutions are guaranteed to be optimal. Jump point pruning
is fast, requires no preprocessing and introduces no mem-
ory overheads. It is also largely orthogonal to many existing
speedup techniques applicable to grid maps.
We make the following contributions: (i) a detailed de-
scription of the jump points algorithm; (ii) a theoretical re-
sult which shows that searching with jump points preserves
optimality; (iii) an empirical analysis comparing our method
with two state-of-the-art search space reduction algorithms.
We run experiments on a range of synthetic and real-world
benchmarks from the literature and find that jump points
improve the search time performance of standard A* by
an order of magnitude and more. We also report signif-
icant improvement over Swamps (Pochter et al. 2010), a
recent optimality preserving pruning technique, and perfor-
mance that is competitive with, and in many cases domi-
nates, HPA* (Botea, M
¨
uller, and Schaeffer 2004); a well
known sub-optimal pathfinding algorithm.
Related Work
Approaches for identifying and eliminating search-space
symmetry have been proposed in areas including planning
(Fox and Long 1999), constraint programming (Gent and
Smith 2000), and combinatorial optimization (Fukunaga
2008). Very few works however explicitly identify and deal
with symmetry in pathfinding domains such as grid maps.
Empty Rectangular Rooms (Harabor and Botea 2010) is
an offline symmetry breaking technique which attempts to
redress this oversight. It decomposes grid maps into a se-
ries of obstacle-free rectangles and replaces all nodes from
the interior of each rectangle with a set of macro edges that
facilitate optimal travel. Specific to 4-connected maps, this
approach is less general than jump point pruning. It also re-
quires offline pre-processing whereas our method is online.
The dead-end heuristic (Bj
¨
ornsson and Halld
´
orsson 2006)
and Swamps (Pochter et al. 2010) are two similar pruning
techniques related to our work. Both decompose grid maps
into a series of adjacent areas. Later, this decomposition
is used to identify areas not relevant to optimally solving a
particular pathfinding instance. This objective is similar yet
orthogonal to our work where the aim is to reduce the effort
required to explore any given area in the search space.
A different method for pruning the search space is to
identify dead and redundant cells (Sturtevant, Bulitko, and
评论0