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)


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
Number of pages6
ISBN (Electronic)978-1-4244-7746-3, 978-1-4244-7744-9 (CD)
ISBN (Print)978-1-4244-7745-6
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)
ISSN (Print)0191-2216
ISSN (Electronic)0743-1546


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

Cite this