I am fascinated by single and multi-agent pathfinding problems, especially in two dimensions (e.g. a grid map or a road network). My research in this area aims to improve the state-of-the-art by developing algorithms which are fast, memory efficient and that produce optimal or near-optimal solutions. Together with my co-authors I have developed a number of such innovative algorithms. For example:

• SRC-dfs is a shortest path algorithm where we trade memory for speed. The idea is simple yet highly effective: instead of looking for a path we instead construct (offline) an oracle that can always tell us where to go next. Such an oracle is highly attractive because individual queries are very fast (typically on the order of nanoseconds), because re-planning is trivial and because it can be easily scaled to handle very large numbers of queries. SRC-dfs was the fastest algorithm at the 2014 Grid-based Path Planning Competition. (paper) (source code).
• Anya is a state of the art algorithm for the Any-angle Pathfinding Problem (APP). APP asks us to find shortest paths in a grid which are not restricted to passing through the points of the grid. Until recently it has been an open question whether such problems can be solved both online and optimally. Anya answers this question in the affirmative. (paper) (source code).
• Jump Point Search (JPS) is the current state-of-the-art for online pathfinding on grid maps. It speeds up search by very selectively exploring only certain nodes on the way to the goal. JPS is fast, optimal and requires no pre-processing and no 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. (paper) (source code).
• Hierarchical Annotated A* (HAA*) is a near-optimal pathfinding technique applicable to scenarios where agents can have multiple different sizes and must navigate across multi-terrain grid maps. (paper) (source code).