Abstract
This work considers the problem of designing optimal multi-agent trajectories to patrol an environment. As performance criterion for optimal patrolling we consider the worst-case time gap between any two visits of the same region. We represent the area to be patrolled with a graph, and we characterize the computational complexity of the trajectory design (patrolling) problem with respect to the environment topology and to the number of robots employed in the patrolling task. Even though the patrolling problem is generally NP-hard, we identify particular cases that are solvable efficiently, and we describe optimal patrolling trajectories. Finally, we present a heuristic with performance guarantees, and an 8-approximation algorithm to solve the NP-hard patrolling problem.
| Original language | English |
|---|---|
| Title of host publication | 2010 49th IEEE Conference on Decision and Control, CDC 2010 |
| Place of Publication | Piscataway, NJ |
| Publisher | IEEE |
| Pages | 7153-7158 |
| Number of pages | 6 |
| ISBN (Electronic) | 978-1-4244-7746-3, 978-1-4244-7744-9 (CD) |
| ISBN (Print) | 978-1-4244-7745-6 |
| DOIs | |
| Publication status | Published - 2010 |
| Externally published | Yes |
| Event | 49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, United States Duration: 15 Dec 2010 → 17 Dec 2010 Conference number: 49 |
Publication series
| Name | Proceedings of the IEEE Conference on Decision and Control (CDC) |
|---|---|
| Publisher | IEEE |
| Volume | 2010 |
| ISSN (Print) | 0191-2216 |
| ISSN (Electronic) | 0743-1546 |
Conference
| Conference | 49th IEEE Conference on Decision and Control, CDC 2010 |
|---|---|
| Abbreviated title | CDC |
| Country/Territory | United States |
| City | Atlanta |
| Period | 15/12/10 → 17/12/10 |