@article {2010f-FraPasBul, title = {On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms}, journal = {IEEE Transaction on Robotics}, volume = {28}, year = {2012}, month = {06/2012}, pages = {592-606}, abstract = {The subject of this work is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties, and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region, and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory, and we propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.}, keywords = {Coverage, Distributed algorithms, Multi-robot systems, Patrolling / Surveillance}, attachments = {https://homepages.laas.fr/afranchi/robotics/sites/default/files/2010f-FraPasBul-preprint.pdf}, author = {Fabio Pasqualetti and Antonio Franchi and Francesco Bullo} } @article {2011c-DurFraBul, title = {Distributed Pursuit-Evasion without Mapping or Global Localization via Local Frontiers}, journal = {Autonomous Robots}, volume = {32}, year = {2012}, month = {01/2012}, pages = {81-95}, abstract = {This paper addresses a visibility-based pursuit-evasion problem in which a team of mobile robots with limited sensing and communication capabilities must coordinate to detect any evaders in an unknown, multiply-connected planar environment. Our distributed algorithm to guarantee evader detection is built around maintaining complete coverage of the frontier between cleared and contaminated regions while expanding the cleared region. We detail a novel distributed method for storing and updating this frontier without building a map of the environment or requiring global localization. We demonstrate the functionality of the algorithm through simulations in realistic environments and through hardware experiments. We also compare Monte Carlo results for our algorithm to the theoretical optimum area cleared as a function of the number of robots available.}, keywords = {Coverage, Distributed algorithms, Multi-robot systems, Pursuit-evasion / Clearing}, url = {http://www.springerlink.com/content/a02pr41790ll754w/}, attachments = {https://homepages.laas.fr/afranchi/robotics/sites/default/files/2011c-DurFraBul-preprint.pdf , https://homepages.laas.fr/afranchi/robotics/sites/default/files/2011c-DurFraBul-video1.mp4}, author = {Joseph W. Durham and Antonio Franchi and Francesco Bullo} } @conference {2010b-DurFraBul, title = {Distributed Pursuit-Evasion with Limited-Visibility Sensor Via Frontier-based Exploration}, booktitle = {2010 IEEE Int. Conf. on Robotics and Automation}, year = {2010}, month = {05/2010}, pages = {3562-3568}, address = {Anchorage, AK}, abstract = {This paper addresses a novel visibility-based pursuit-evasion problem in which a team of searchers with limited range sensors must coordinate to clear any evaders from an unknown planar environment. We present a distributed algorithm built around guaranteeing complete coverage of the frontier between cleared and contaminated areas while expanding the cleared area. Our frontier-based algorithm can guarantee detection of evaders in unknown, multiply-connected planar environments which may be non-polygonal. We also detail a method for storing and updating the global frontier between cleared and contaminated areas without building a global map or requiring global localization, which enables our algorithm to be truly distributed. We demonstrate the functionality of the algorithm through Player/Stage simulations. }, keywords = {Coverage, Distributed algorithms, Multi-robot systems, Pursuit-evasion / Clearing}, attachments = {https://homepages.laas.fr/afranchi/robotics/sites/default/files/2010b-DurFraBul.pdf , https://homepages.laas.fr/afranchi/robotics/sites/default/files/ICRA10-FinalSub.mp4}, author = {Joseph W. Durham and Antonio Franchi and Francesco Bullo} } @conference {2010e-PasFraBul, title = {On Optimal Cooperative Patrolling}, booktitle = {49th IEEE Conference on Decision and Control}, year = {2010}, month = {12/2010}, pages = {7153-7158}, address = {Atlanta, GA, USA}, 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.}, keywords = {Coverage, Distributed algorithms, Multi-robot systems, Patrolling / Surveillance}, attachments = {https://homepages.laas.fr/afranchi/robotics/sites/default/files/2010e-PasFraBul-preprint.pdf , https://homepages.laas.fr/afranchi/robotics/sites/default/files/2010e-PasFraBul.pdf}, author = {Fabio Pasqualetti and Antonio Franchi and Francesco Bullo} }