Daniel Harabor

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.


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.


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.

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.

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 Uniform-cost Grid Maps. In Proceedings of the Symposium on Abstraction Reformulation and Approximation (SARA), Barcelona, Spain.

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.

HAA* is introduced in the following industry and conference articles:

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.

Source Code

The source code for HAA* is available here (Mac OSX).
The source code for Jump Point Search is available here (Mac OSX).