Path planning for multiple agents is the backbone of many interesting applications, ranging from video games to warehouse automation. The underlying problem is typically formulated as finding collision-free paths on graphs, called multi-agent pathfinding (MAPF). This talk dives deep into an important challenge for MAPF: can we build scalable algorithms, say tailored for 10k agents, while still having nice theoretical guarantees like completeness and optimality? Traditionally, these two aspects have been considered incompatible, given the inherent difficulties that guaranteed algorithms face in finding solutions amidst an increasing number of agents. Starting with vanilla approaches to MAPF like A* search, this talk outlines approaches for this quest.
Link to join virtually: https://cam-ac-uk.zoom.us/j/81322468305
This talk is being recorded.