LAB42 Talk | FOAM: Bernhard Nebel - On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Join us in this FOAM seminar from Bernhard Nebel, University of Freiburg.
Abstract
Multi-agent pathfinding”, also called “pebble motion on graphs” or “cooperative pathfinding”, is the problem of deciding the existence of or generating a collision-free movement plan for a set of agents moving on a graph. While the non-optimizing variant of multi-agent pathfinding on undirected graphs is known to be a polynomial-time problem since forty years, a similar result for directed graphs was missing. In the talk, it will be shown that this problem is NP-complete. For strongly connected directed graphs, however, the problem is polynomial. And both of these results hold even if one allows for synchronous rotations on fully occupied cycles.
FOAM seminars
The FOAM Seminar, organised by computer scientists at the ILLC, features research on questions of a fundamental nature in computer science and AI, in research areas such as algorithms, optimisation, data management, planning, knowledge representation, and multiagent systems. Talks are intended to be broadly accessible and pitched at the level you might find at a plenary talk of a relevant conference (such as IJCAI, AAAI, KR, ICAPS, AAMAS, EC, PODS, LICS, STOC, FOCS, and SODA).
FOAM usually takes place on a Friday at 15:00. Talks are roughly 45 minutes long, followed by a brief discussion. Afterwards, you are invited to stay for a chat and a drink. Everyone is welcome to attend!