Multi-Agent Path-Finding and Algorithmic Graph Theory (Student Abstract)


  • David Fairbairn Durham University Tharsus Limited



MAPF, Multi-Agent Path-Finding, Algorithmic Graph Theory, Graph Theory, Algorithms, Agents, CUDA, High Performance Computing, Massively Parallelised Computing, AGT, Graph Classes, Complexity Theory


I specialise in conducting research in Multi-Agent Path- Finding (MAPF) and Algorithmic Graph Theory. Specifically, I investigate the impact of geometric constraints on a given instance of MAPF, as well as the expansion of MAPF to include resource constraints, target assignment path-finding (TAPF), and academic problems that are relevant to industry. In Algorithmic Graph Theory, I extend the capabilities of standard and novel MAPF solvers to temporal graphs, and explore clustering techniques and ideas that utilise Graph Classifications on MAPF domains to reduce the computational complexity of MAPF. Furthermore, I research the implementation and application of massively parallelized computing techniques on MAPF, especially in relation to distance matrix computation and parallelized centralized MAPF. Aside from my PhD research, I have the pleasure to collaborate with researchers at Tharsus Limited, to directly apply my research to novel industrial problems and develop benchmarks that are relevant to both the industry and the research community for Multi-Agent Systems.