Back to Search
Start Over
Dynamic Connected Cooperative Coverage Problem
- Publication Year :
- 2018
-
Abstract
- We study the so-called dynamic coverage problem by agents located in some topological graph. The agents must visit all regions of interest but they also should stay connected to the base via multi-hop. We prove that the algorithmic complexity of this planning problem is PSPACE-complete. Furthermore we prove that the problem becomes NP-complete for bounded plans. We also prove the same complexities for the reachability problem of some positions. We also prove that complexities are maintained for a subclass of topological graphs.
- Subjects :
- Computer Science - Multiagent Systems
Computer Science - Computational Complexity
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1810.06213
- Document Type :
- Working Paper