Complexity of planning for connected agents
- PDF / 2,339,895 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 219 Views
(2020) 34:44
Complexity of planning for connected agents Tristan Charrier1 · Arthur Queffelec1 · Ocan Sankur1 · François Schwarzentruber1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study a variant of the multi-agent path finding (MAPF) problem in which the group of agents are required to stay connected with a supervising base station throughout the execution. In addition, we consider the problem of covering an area with the same connectivity constraint. We show that both problems are PSPACE-complete on directed and undirected topological graphs while checking the existence of a bounded plan is NP-complete when the bound is given in unary (and PSPACE-hard when the encoding is in binary). Moreover, we identify a realistic class of topological graphs on which the decision problem falls in NLOGSPACE although the bounded versions remain NP-complete for unary encoding. Keywords Artifical intelligence · Multi-agent systems · Planning · Computational complexity Mathematics Subject Classification 68T20 · 03D15
1 Introduction The multi-agent path finding (MAPF) problem asks for a plan to move a group of agents to a target configuration in a graph while avoiding collisions. It is an important problem in the design of groups of autonomous vehicles, and has been used in several applications such as Kiva (Amazon Robotics) warehouse systems [58], autonomous aircraft towing vehicles [36], characters in video games [49] and office robots [57]. A closely related problem is that of coverage path planning which consists in computing a plan that visits a set of given locations in a graph. A comprehensive survey is given
* Arthur Queffelec [email protected] Tristan Charrier [email protected] Ocan Sankur [email protected] François Schwarzentruber [email protected] 1
Univ Rennes, Inria, CNRS, IRISA, 263 Avenue Général Leclerc, 35000 Rennes, France
13
Vol.:(0123456789)
44
Page 2 of 31
Autonomous Agents and Multi-Agent Systems
(2020) 34:44
in [23]. Applications include underwater ship hull inspection [18], wildfire tracking with drones [40], to name a few. An important application area is that of information gathering missions in which agents must visit a set of locations in an area and gather information using sensors (e.g. camera, smoke sensor, hygrometer etc.). Some applications, such as search and rescue missions, might require continuous connection between all agents and a base station, for instance, in order to stream video and allow human operators to take decisions [2]. In this case, the path planning and coverage path planning algorithms must take additional connectivity constraints into account in order to compute suitable plans. Several works have explored planning algorithms in this setting e.g. [39, 44]. Some works on path planning and coverage path planning either assume a given discrete graph model obtained by cell decomposition or visibility graph [34], or applies a sampling method to construct a graph on which combinatorial algor
Data Loading...
