Pathfinding for video games and warehouses

People

Principal investigator

Research areas

Description

Pathfinding is the problem of finding a path in a graph or in a grid.  Compared to classical planning, the number of states is generally very small (millions or billions of states).

Algorithms in pathfinding can be evaluated according to the following criteria:

  • Is it optimal, or suboptimal within a bound?
  • How much time does it take?
  • How much resources that it require (in particular, pre-processing time and memory)?
Other properties of algorithms include the anytime ability (the ability to return a path early, and later compute a better path), the ability to handle multiple agents, the type of moves allowed, etc.

Pathfinding is a very active research area, with many new and exciting algorithms developed in the last ten years, some of which at the ANU.  This type of work has tremendous impact on game industry and warehousing.

We have a number of ideas that we would like to develop further:

  • Brigitte is a pathfinding algorithm for 8-connected grids.  It is arguably the fastest algorithm around, but it requires an insane amount of preprocessing.  Improvements in this dimension could make the whole approach actually practical.  
  • We also would like to develop a similar approach to any-angle path-finding.  For an example of any-angle pathfinding, look at Polyanya.  
  • We want to extend polyanya to make it applicable for terrains, i.e., maps with different costs (for instance, roads vs swamps).  
  • We want to explore a SAT-based approach to multi-agent pathfinding.  

Goals

Develop and analyse algorithms for pathfinding.

Requirements

Strong programming skills.

Understanding of datastructures, algorithms, and complexity.

Background Literature

Some relevant literature:

[Brigitte]
A Grastien.  Brigitte, a bridge-based grid path-finderTwelfth Annual Symposium on Combinatorial Search (SOCS-19).  pp. 176-177.  2019

[Polyanya]
M. Cui, D. Harabor, and A. Grastien.  Compromise-free pathfinding on a navigation mesh26th International Joint Conference on Artificial Intelligence (IJCAI-17).  pp. 496-502.  2017

[JPS]
D. Harabor and A. Grastien.  Online graph pruning for pathfinding on grid maps25th Conference on Artificial Intelligence (AAAI-11)/.  2011.

[CPD]
A. Botea, B. Strasser, and D. Harabor.  Complexity results for compressing optimal paths29th Conference on Artificial Intelligence (AAAI-15).  pp. 1100-1106.  2015.

[ICBS]
G. Sharon, R. Stern, A. Felner, and N. Sturtevant.  Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence (AIJ).  pp. 40-66.  vo. 219, 2015.

 

Keywords

pathfinding

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing