Daniel Harabor >>
Projects >>
Pathfinding
Pathfinding is the problem of navigating from one place to another.
My research in this area is primarily focused on
single-agent pathfinding problems where the world is represented
as a static 2-dimensional grid. This is a common setting which
appears in many application areas including logistics, robotics and
video games.
Goals
The principal aim of this project is to improve the state-of-the-art
in pathfinding by developing algorithms which are fast, require
little memory and produce optimal or near-optimal solutions.
Main Result
Together with my co-authors I have developed several innovative algorithms
for efficiently solving a range of common pathfinding problems.
-
Jump Point Search (JPS) is the state-of-the-art
in graph pruning for grid maps.
It speeds up pathfinding by very
selectively expanding only certain nodes on the way to the goal.
JPS is fast, optimal and requires no pre-processing or extra memory.
It can consistently speed up a classical search algorithm
such as A* by an order of magnitude and more on a range of
synthetic and realistic maps.
-
Rectangular Symmetry Reduction (RSR) is a
graph pruning technique which
speeds up search by identifying and
eliminating symmetries in a grid map. RSR is
fast, optimal and requires very little extra
memory.
-
Hierarchical Annotated A* (HAA*) is a
near-optimal pathfinding technique applicable to
scenarios involving multi-size agents navigating
across multi-terrain grid maps.
Resources
Jump Point Search is described in the following papers:
D. Harabor and A. Grastien. 2011. Online Graph Pruning for Pathfinding on Grid Maps.
In Proceedings of the 25th National Conference on Artificial Intelligence (AAAI),
San Francisco, USA.
(pdf)
D. Harabor and A. Grastien. Improving Jump Point Search.
Pathfinding Algorithm. 2014. In Proceedings of the
24th International Conference on Automated Planning
and Scheduling (ICAPS). Portsmouth (NH), USA.
(pdf)
D. Harabor, A. Botea and P. Kilby. 2011. Path Symmetries in Uniform-cost Grid Maps.
In Proceedings of the Symposium on Abstraction Reformulation and Approximation (SARA),
Barcelona, Spain.
(pdf)
D. Harabor, A. Botea. 2010. Breaking Path Symmetries in 4-connected
Grid Maps. In Proceedings of the AI and Interactive Digital Entertainment
Conference (AIIDE-2010), Stanford University, Palo Alto, CA, USA.
(pdf)
D. Harabor. 2009. Clearance-based Pathfinding and Hierarchical
Annotated A* Search. In AiGameDev.com.
(pdf)
D. Harabor, A. Botea. 2008.
Hierarchical Path Planning with Multi-Size Agents in Heterogenous Environments.
In the IEEE Symposium on Computational Intelligence and Games (CIG-08).
Also, in the ICAPS-08 Workshop KEPS-08.
(pdf)
Source Code
The source code for HAA* is available here (Mac OSX).
The source code for Jump Point Search is available here (Mac OSX).
|