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
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.
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
Hierarchical Annotated A* (HAA*) is a
near-optimal pathfinding technique applicable to
scenarios involving multi-size agents navigating
across multi-terrain grid maps.
Jump Point Search is described in the following papers:
This poster gives an
overview of the main idea behind RSR. The following subsequent
papers expand and improve on that idea:
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.
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.
HAA* is introduced in the following industry and conference
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),
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.
D. Harabor. 2009. Clearance-based Pathfinding and Hierarchical
Annotated A* Search. In AiGameDev.com.
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.
The source code for HAA* is available here (Mac OSX).
The source code for Jump Point Search is available here (Mac OSX).