Connected multi-agent path finding

Speaker: Francois Schwarzentruber, ENS Rennes and IRISA.

Tuesday March 29 2022, 11:00, (salle 1Z71 ENS Paris-Saclay and online)

Abstract: Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. In the first part of the talk, we study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents. We also introduce a new class called sight-moveable graphs which admit efficient algorithms. In the second part, we discuss conflict-based search and rapidly-exploring random tree.