Reachability and Coverage Planning for Connected Agents

Reachability and Coverage Planning for Connected Agents

Tristan Charrier, Arthur Queffelec, Ocan Sankur, François Schwarzentruber

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 144-150. https://doi.org/10.24963/ijcai.2019/21

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. We study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents on various classes of topological graphs. We establish the complexity of these problems on known classes, and introduce a new class called sight-moveable graphs which admit efficient algorithms.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Planning and Scheduling: Theoretical Foundations of Planning