Optimal patrolling of fragmented boundaries

ABSTRACT

A set of mobile robots is deployed on a simple curve of finite length, composed of a finite set of vital segments separated by neutral segments. The robots have to patrol the vital segments by perpetually moving on the curve, without exceeding their uniform maximum speeds. The quality of patrolling is measured by the idleness, i.e., the longest time period during which any vital point on the curve is not visited by any robot. Given a configuration of vital segments, our goal is to provide algorithms describing the movement of the robots along the curve so as to minimize the idleness.

Our main contribution is a proof that the optimal solution to the patrolling problem is attained either by the cyclic strategy, in which all the robots move in one direction around the curve, or by the partition strategy, in which the curve is partitioned into sections which are patrolled separately by individual robots. These two fundamental types of strategies were studied in the past in the robotics community in different theoretical and experimental settings. However, to our knowledge, this is the first theoretical analysis proving optimality in such a general scenario. Throughout the paper we assume that all robots have the same maximum speed. In fact, the claim is known to be invalid when this assumption does not hold, cf. [Czyzowicz et al., Proc. ESA 2011].

References

1. A. Aggarwal. The Art Gallery Theorem and Algorithm. PhD thesis, Johns Hopkins University, 1984.
2. N. Agmon, S. Kraus, and G. A. Kaminka. Multi-robot perimeter patrol in adversarial settings. In ICRA, pages 2339--2345, 2008.
3. A. Almeida, G. Ramalho, H. Santana, P. A. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyre. Recent advances on multi-agent patrolling. In SBIA, pages 474--483, 2004.
4. E. M. Arkin, J. S. B. Mitchell, and C. D. Piatko. Minimum-link watchman tours. IPL, 86:203--207, 2003.
5. S. Carlsson, B. J. Nilsson, and S. C. Ntafos. Optimum guard covers and m-watchmen routes for restricted polygons. Int. J. Comp. Geom. Appl., 3:85--105, 1993.
6. Y. Chevaleyre. Theoretical analysis of the multi-agent patrolling problem. In IAT, pages 302--308, 2004.
7. W. Chin and S. C. Ntafos. Optimal watchman routes. Inf. Proc. Lett., 28:39--44, 1988.
8. W. Chin and S. C. Ntafos. Shortest watchman routes in simple polygons. Discr. Comp. Geom., 6:9--31, 1991.
9. W. Chin and S. C. Ntafos. The zookeeper route problem. Inf. Sci., 63:245--259, 1992.
10. J. Czyzowicz, P. Egyed, H. Everett, D. Rappaport, T. C. Shermer, D. L. Souvaine, G. T. Toussaint, and J. Urrutia. The aquarium keeper's problem. In SODA, pages 459--464, 1991.
11. J. Czyzowicz, L. Gkasieniec, A. Kosowski, and E. Kranakis. Boundary patrolling by mobile agents with distinct maximal speeds. In ESA 2011, pages 701--712. Springer, 2011.
12. M. Dror, A. Efrat, A. Lubiw, and J. S. B. Mitchell. Touring a sequence of polygons. In STOC, pages 473--482, 2003.
13. A. Dumitrescu and C. Tóth. Watchman tours for polygons with holes. Comput. Geom. Theory Appl., 45:326--333, 2012.
14. K. Easton and J. W. Burdick. A coverage algorithm for multi-robot boundary inspection. In ICRA, pages 727--734. IEEE, 2005.
15. S. Eidenbenz, C. Stamm, and P. Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79--113, 2001.
16. Y. Elmaliach, N. Agmon, and G. A. Kaminka. Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell., 57(3-4):293--320, 2009.
17. Y. Elmaliach, A. Shiloni, and G. A. Kaminka. A realistic model of frequency-based multi-robot polyline patrolling. In AAMAS (1), pages 63--70, 2008.
18. Y. Elor and A. M. Bruckstein. Autonomous multi-agent cycle based patrolling. In ANTS, pages 119--130, 2010.
19. F. V. Fomin, P. A. Golovach, A. Hall, M. Mihalák, E. Vicari, and P. Widmayer. How to guard a graph? Algorithmica, 61(4):839--856, 2011.
20. F. V. Fomin and D. M. Thilikos. An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci., 399(3):236--245, 2008.
21. Y. Gabriely and E. Rimon. Spanning-tree based coverage of continuous areas by a mobile robot. In ICRA, pages 1927--1933, 2001.
22. S. K. Ghosh. Approximation algorithms for art gallery problems in polygons and terrains. In WALCOM, pages 21--34, 2010.
23. N. Hazon and G. A. Kaminka. On redundancy, efficiency, and robustness in coverage for multiple robots. Rob. and Autonom. Syst., 56:1102--1114, 2008.
24. A. Kawamura and Y. Kobayashi. Fence patrolling by mobile agents with distinct speeds. In ISAAC'12, pages 598--608, 2012.
25. G. D. Kazazakis and A. A. Argyros. Fast positioning of limited-visibility guards for the inspection of 2d workspaces. In IEEE Int. Conf. on Intelligent Robots and Systems, Vol. 3, pages 2843--2848, 2002.
26. A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul. Multi-agent patrolling: An empirical analysis of alternative architectures. In MABS, pages 155--170, 2002.
27. A. Marino, L. E. Parker, G. Antonelli, and F. Caccavale. Behavioral control for multi-robot perimeter patrol: A finite state automata approach. In ICRA, pages 831--836, 2009.
28. J. Mitchell. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, Chapter 15, pages 633--701, 2000.
29. B. J. Nilsson. Guarding art galleries; Methods for mobile guards. PhD thesis, Lund U., Sweden, 1995.
30. B. J. Nilsson and D. Wood. Optimum watchmen route in spiral polygons. In 2nd Canadian Conf. Comput. Geometry, pages 269--272, 1990.
31. S. C. Ntafos. Watchman routes under limited visibility. Comput. Geom., 1:149--170, 1991.
32. J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
33. E. Packer. Computing multiple watchman routes. In WEA'08 Proc. 7th Workshop on Experimental Algorithms, pages 114--128, 2008.
34. F. Pasqualetti, A. Franchi, and F. Bullo. On optimal cooperative patrolling. In CDC, 2010.
35. T. C. Shermer. Recent results in art galleries. In Proc. of the IEEE, volume 80, pages 1384--1399, 1992.
36. M. Yamashita, H. Umemoto, I. Suzuki, and T. Kameda. Searching for mobile intruders in a polygonal region by a group of mobile searchers. Algorithmica, 31:208--236, 2001.
37. V. Yanovski, I. A. Wagner, and A. M. Bruckstein. A distributed ant algorithm for efficiently patrolling a network. Algorithmica, 37(3):165--186, 2003.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles