2019/03/11 by Tristan Charrier, Charrier, Tristan, Arthur Queffelec +5
Computer Science · Engineering · #Robotic Path Planning Algorithms #Optimization and Search Problems #Modular Robots and Swarm Intelligence
paper · pdf · doi:10.48550/arxiv.1903.04300
Motivated by the increasing appeal of robots in information-gathering\nmissions, we study multi-agent path planning problems in which the agents must\nremain interconnected. We model an area by a topological graph specifying the\nmovement and the connectivity constraints of the agents. We study the\ntheoretical complexity of the reachability and the coverage problems of a fleet\nof connected agents on various classes of topological graphs. We establish the\ncomplexity of these problems on known classes, and introduce a new class called\nsight-moveable graphs which admit efficient algorithms.\n