@inproceedings{db0b29f67bde4609aabec57446d5f1ed,
title = "On optimal cooperative patrolling",
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.",
author = "Fabio Pasqualetti and Antonio Franchi and Francesco Bullo",
year = "2010",
doi = "10.1109/CDC.2010.5717873",
language = "English",
isbn = "978-1-4244-7745-6",
series = "Proceedings of the IEEE Conference on Decision and Control (CDC)",
publisher = "IEEE",
pages = "7153--7158",
booktitle = "2010 49th IEEE Conference on Decision and Control, CDC 2010",
address = "United States",
note = "2010 49th IEEE Conference on Decision and Control, CDC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",
}