On Optimal Cooperative Patrolling

TitleOn Optimal Cooperative Patrolling
Publication TypeConference Paper
Year of Publication2010
AuthorsPasqualetti, F, Franchi, A, Bullo, F
Conference Name49th IEEE Conference on Decision and Control
Date Published12/2010
Conference LocationAtlanta, GA, USA
KeywordsCoverage, Distributed algorithms, Multi-robot systems, Patrolling / Surveillance

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.

Citation Key2010e-PasFraBul
PDF icon pdf465.44 KB

Taxonomy upgrade extras: