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)?
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.
Develop and analyse algorithms for pathfinding.
Strong programming skills.
Understanding of datastructures, algorithms, and complexity.
Some relevant literature:
A Grastien. Brigitte, a bridge-based grid path-finder. Twelfth Annual Symposium on Combinatorial Search (SOCS-19). pp. 176-177. 2019
M. Cui, D. Harabor, and A. Grastien. Compromise-free pathfinding on a navigation mesh. 26th International Joint Conference on Artificial Intelligence (IJCAI-17). pp. 496-502. 2017
D. Harabor and A. Grastien. Online graph pruning for pathfinding on grid maps. 25th Conference on Artificial Intelligence (AAAI-11)/. 2011.
A. Botea, B. Strasser, and D. Harabor. Complexity results for compressing optimal paths. 29th Conference on Artificial Intelligence (AAAI-15). pp. 1100-1106. 2015.
G. Sharon, R. Stern, A. Felner, and N. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence (AIJ). pp. 40-66. vo. 219, 2015.