Daniel Harabor >>
Projects >>
Pathfinding
Pathfinding is the problem of navigating from one place to another.
My research in this area is primarily focused on
singleagent pathfinding problems where the world is represented
as a static 2dimensional 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 stateoftheart
in pathfinding by developing algorithms which are fast, require
little memory and produce optimal or nearoptimal solutions.
Main Result
Together with my coauthors I have developed several innovative algorithms
for efficiently solving a range of common pathfinding problems.

Jump Point Search (JPS) is the stateoftheart
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 preprocessing 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
nearoptimal pathfinding technique applicable to
scenarios involving multisize agents navigating
across multiterrain 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)
This poster gives an
overview of the main idea behind RSR. The following subsequent
papers expand and improve on that idea:
D. Harabor, A. Botea and P. Kilby. 2011. Path Symmetries in Uniformcost 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 4connected
Grid Maps. In Proceedings of the AI and Interactive Digital Entertainment
Conference (AIIDE2010), Stanford University, Palo Alto, CA, USA.
(pdf)
HAA* is introduced in the following industry and conference
articles:
D. Harabor. 2009. Clearancebased Pathfinding and Hierarchical
Annotated A* Search. In AiGameDev.com.
(pdf)
D. Harabor, A. Botea. 2008.
Hierarchical Path Planning with MultiSize Agents in Heterogenous Environments.
In the IEEE Symposium on Computational Intelligence and Games (CIG08).
Also, in the ICAPS08 Workshop KEPS08.
(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).
