On optimal cooperative patrolling

Fabio Pasqualetti*, Antonio Franchi, Francesco Bullo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

32 Citations (Scopus)

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 languageEnglish
Title of host publication2010 49th IEEE Conference on Decision and Control, CDC 2010
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages7153-7158
Number of pages6
ISBN (Electronic)978-1-4244-7746-3, 978-1-4244-7744-9 (CD)
ISBN (Print)978-1-4244-7745-6
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event2010 49th IEEE Conference on Decision and Control, CDC 2010 - Atlanta, GA, United States
Duration: 15 Dec 201017 Dec 2010

Publication series

NameProceedings of the IEEE Conference on Decision and Control (CDC)
PublisherIEEE
Volume2010
ISSN (Print)0191-2216
ISSN (Electronic)0743-1546

Conference

Conference2010 49th IEEE Conference on Decision and Control, CDC 2010
Country/TerritoryUnited States
CityAtlanta, GA
Period15/12/1017/12/10

Cite this