Reachability and Coverage Planning for Connected Agents: Extended Version
This work addresses path planning for interconnected multi-agent systems in robotics, which is incremental as it builds on existing graph-based models by analyzing complexity and proposing a new graph class.
The paper tackles the problem of planning paths for multiple robots that must stay connected while gathering information, establishing the computational complexity of reachability and coverage tasks on various graph classes and introducing a new class called sight-moveable graphs that allows for efficient algorithms.
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.