Paper Info
Title
Reachability and Coverage Planning for Connected Agents
Abstract
Unmanned autonomous vehicle assisted information gathering missions have quickly picked up interest. Indeed, the advances on drones are making this type of missions possible. Thus, we study multi-agent path planning problems, namely reachability and coverage, for such missions with a connectivity constraint. This version of the multi-agent path planning asks to generate a plan, a sequence of steps, for a group of agents that are to stay connected during the missions while satisfying the specified goal. In this paper, we study the complexity of the coverage and reach ability problems for a cooperation of agents with a connectivity constraint which restrain their movement. We identify a class of topological graphs which allows one to reduce the complexity of the decision problems from PSPACE-complete to LOGSPACE. We show, on the other hand, that the bounded versions of the previous problems are NP-complete.
Year
DOI
Venue
2019
10.24963/ijcai.2019/21
international joint conference on artificial intelligence
Keywords
Field
DocType
Multi-agent planning,Complexity theory and logic,Paths and connectivity problems
Motion planning,Graph,Decision problem,Computer science,Reachability,Drone,Multi-agent planning,Bounded function,Distributed computing
Conference
Citations 
PageRank 
References 
1
0.35
0
Authors
4
Name
Order
Citations
PageRank
Tristan Charrier1102.04
Arthur Queffelec211.37
Ocan Sankur310514.76
François Schwarzentruber417029.05