  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.
