Abstract
Motivated by the increasing appeal of robots in
information-gathering missions, we study multiagent 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