Patrolling with multiple robots enables efficient surveillance for detecting and managing undesirable situations. This necessitates improved patrol efficiency and operator situational awareness at base stations. An enhanced situational awareness enables operators to predict robot behavior, support recognition and decision-making, and execute emergency interventions. This paper presents the local reactive and partition (LR-PT) algorithm. It is a novel multi-robot patrolling approach. In the simulations, LR-PT outperformed the existing methods by ensuring frequent patrols of all the locations of interest and enhancing the situational awareness of the base station. The robots independently select patrol targets based on locally available information. It integrates patrol requirements and the urgency of reporting mission progress to base stations into a unified utility function. This locality also contributes to the robustness against communication constraints and robot failures, as demonstrated in this study. The algorithm further autonomously performs emergent area partitioning. This can prevent falling into local optima and realize a comprehensive patrol over the entire mission area. The simulation results demonstrate the superior performance of LR-PT for multi-robot patrolling. It utilizes the advantages of swarm robotics and addresses real-world operational challenges.

1. [1] E. T. Alotaibi, S. S. Alqefari, and A. Koubaa, “LSAR: Multi-UAV collaboration for search and rescue missions,” IEEE Access, Vol.7, pp. 55817-55832, 2019. https://doi.org/10.1109/ACCESS.2019.2912306
2. [2] E. Şahin, “Swarm robotics: From sources of inspiration to domains of application,” Swarm Robotics: SAB 2004 Int. Workshop, pp. 10-20, 2005. https://doi.org/10.1007/978-3-540-30552-1_2
3. [3] M. Schranz, M. Umlauft, M. Sende, and W. Elmenreich, “Swarm robotic behaviors and current applications,” Frontiers in Robotics and AI, Vol.7, Article No.36, 2020. https://doi.org/10.3389/frobt.2020.00036
4. [4] D. Carrillo-Zapata et al., “Mutual shaping in swarm robotics: User studies in fire and rescue, storage organization, and bridge inspection,” Frontiers in Robotics and AI, Vol.7, Article No.53, 2020. https://doi.org/10.3389/frobt.2020.00053
5. [5] Y. Watanobe et al., “Disaster rescue via multi-robot collaboration: Development, control, and deployment,” J. Robot. Mechatron., Vol.35, No.1, pp. 85-98, 2023. https://doi.org/10.20965/jrm.2023.p0085
6. [6] B. M. Pillai et al., “A heterogeneous robots collaboration for safety, security, and rescue robotics: e-ASIA joint research program for disaster risk and reduction management,” Advanced Robotics, Vol.38, No.3, pp. 129-151, 2024. https://doi.org/10.1080/01691864.2024.2309622
7. [7] M. R. Endsley, “Design and evaluation for situation awareness enhancement,” Proc. of the Human Factors and Ergonomics Society Annual Meeting, Vol.32, No.2, pp. 97-101, 1988. https://doi.org/10.1177/154193128803200221
8. [8] A. Kolling, P. Walker, N. Chakraborty, K. Sycara, and M. Lewis, “Human interaction with robot swarms: A survey,” IEEE Trans. on Human-Machine Systems, Vol.46, No.1, pp. 9-26, 2016. https://doi.org/10.1109/THMS.2015.2480801
9. [9] K. Kobayashi, S. Ueno, and T. Higuchi, “Multi-robot patrol algorithm with distributed coordination and consciousness of the base station’s situation wareness,” arXiv:2307.08966, 2023. https://doi.org/10.48550/arXiv.2307.08966
10. [10] A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul, “Multi-agent patrolling: An empirical analysis of alternative architectures,” Multi-Agent-Based Simulation II: 3rd Int. Workshop (MABS 2002), pp. 155-170, 2003. https://doi.org/10.1007/3-540-36483-8_11
11. [11] A. Glad, O. Simonin, O. Buffet, and F. Charpillet, “Theoretical study of ant-based algorithms for multi-agent patrolling,” 18th European Conf. on Artificial Intelligence, pp. 626-630, 2008. https://doi.org/10.3233/978-1-58603-891-5-626
12. [12] A. Glad, O. Buffet, O. Simonin, and F. Charpillet, “Self-organization of patrolling-ant algorithms,” 3rd IEEE Int. Conf. on Self-Adaptive and Self-Organizing Systems, pp. 61-70, 2009. https://doi.org/10.1109/SASO.2009.39
13. [13] D. Portugal and R. P. Rocha, “Distributed multi-robot patrol: A scalable and fault-tolerant framework,” Robotics and Autonomous Systems, Vol.61, No.12, pp. 1572-1587, 2013. https://doi.org/10.1016/j.robot.2013.06.011
14. [14] D. Portugal and R. P. Rocha, “Cooperative multi-robot patrol with Bayesian learning,” Autonomous Robots, Vol.40, No.5, pp. 929-953, 2016. https://doi.org/10.1007/s10514-015-9503-7
15. [15] M. Othmani-Guibourg, A. El Fallah-Seghrouchni, and J.-L. Farges, “Path generation with LSTM recurrent neural networks in the context of the multi-agent patrolling,” IEEE 30th Int. Conf. on Tools with Artificial Intelligence (ICTAI), pp. 430-437, 2018. https://doi.org/10.1109/ICTAI.2018.00073
16. [16] M. Othmani-Guibourg, A. El Fallah-Seghrouchni, and J.-L. Farges, “LSTM Path-Maker: A new LSTM-based strategy for the multi-agent patrolling,” Proc. of the 52nd Hawaii Int. Conf. on System Sciences, pp. 616-625, 2019.
17. [17] C. Yan and T. Zhang, “Multi-robot patrol: A distributed algorithm based on expected idleness,” Int. J. of Advanced Robotic Systems, Vol.13, No.6, 2016. https://doi.org/10.1177/1729881416663666
18. [18] K.-S. Hwang, J.-L. Lin, and H.-L. Huang, “Cooperative patrol planning of multi-robot systems by a competitive auction system,” 2009 ICCAS-SICE, pp. 4359-4363, 2009.
19. [19] C. Pippin, H. Christensen, and L. Weiss, “Performance based task assignment in multi-robot patrolling,” Proc. of the 28th Annual ACM Symp. on Applied Computing, pp. 70-76, 2013. https://doi.org/10.1145/2480362.2480378
20. [20] A. Farinelli, L. Iocchi, and D. Nardi, “Distributed on-line dynamic task assignment for multi-robot patrolling,” Autonomous Robots, Vol.41, No.6, pp. 1321-1345, 2017. https://doi.org/10.1007/s10514-016-9579-8
21. [21] S. Hoshino and K. Takahashi, “Dynamic partitioning strategies for multi-robot patrolling systems,” J. Robot. Mechatron., Vol.31, No.4, pp. 535-545, 2019. https://doi.org/10.20965/jrm.2019.p0535
22. [22] T. Sato et al., “Probabilistic presence density control for areal wide-area distributed exploration with swarm robots,” J. of the Robotics Society of Japan, Vol.41, No.10, pp. 869-880, 2023. https://doi.org/10.7210/jrsj.41.869
23. [23] J. Scherer and B. Rinner, “Short and full horizon motion planning for persistent multi-UAV surveillance with energy and communication constraints,” 2017 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 230-235, 2017. https://doi.org/10.1109/IROS.2017.8202162
24. [24] J. Scherer and B. Rinner, “Multi-UAV surveillance with minimum information idleness and latency constraints,” IEEE Robotics and Automation Letters, Vol.5, No.3, pp. 4812-4819, 2020. https://doi.org/10.1109/LRA.2020.3003884
25. [25] J. Scherer and B. Rinner, “Persistent multi-UAV surveillance with energy and communication constraints,” 2016 IEEE Int. Conf. on Automation Science and Engineering, pp. 1225-1230, 2016. https://doi.org/10.1109/COASE.2016.7743546
26. [26] J. Scherer and B. Rinner, “Multi-robot persistent surveillance with connectivity constraints,” IEEE Access, Vol.8, pp. 15093-15109, 2020. https://doi.org/10.1109/ACCESS.2020.2967650
27. [27] J. Banfi, N. Basilico, and F. Amigoni, “Minimizing communication latency in multirobot situation-aware patrolling,” 2015 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 616-622, 2015. https://doi.org/10.1109/IROS.2015.7353436
28. [28] F. Amigoni, J. Banfi, and N. Basilico, “Multirobot exploration of communication-restricted environments: A survey,” IEEE Intelligent Systems, Vol.32, No.6, pp. 48-57, 2017. https://doi.org/10.1109/MIS.2017.4531226
29. [29] T. Nestmeyer, P. Robuffo Giordano, H. H. Bülthoff, and A. Franchi, “Decentralized simultaneous multi-target exploration using a connected network of multiple robots,” Autonomous Robots, Vol.41, No.4, pp. 989-1011, 2017. https://doi.org/10.1007/s10514-016-9578-9
30. [30] E. Y. Adam, “Leveraging connectivity for coverage in drone networks for target detection,” Balkan J. of Electrical and Computer Engineering, Vol.7, No.3, pp. 218-225, 2019. https://doi.org/10.17694/bajece.503818
31. [31] K. Kobayashi, S. Ueno, and T. Higuchi, “Multi-robot patrol with continuous connectivity and assessment of base station situation awareness,” J. Robot. Mechatron., Vol.36, No.3, pp. 526-537, 2024. https://doi.org/10.20965/jrm.2024.p0526
32. [32] P. D. Hung, T. Q. Vinh, and T. D. Ngo, “Hierarchical distributed control for global network integrity preservation in multirobot systems,” IEEE Trans. on Cybernetics, Vol.50, No.3, pp. 1278-1291, 2020. https://doi.org/10.1109/TCYB.2019.2913326
33. [33] T. Murayama and A. Iwasaki, “Bi-connectivity control for multi-robot network considering line-of-sight communication,” J. Robot. Mechatron., Vol.35, No.4, pp. 1028-1037, 2023. https://doi.org/10.20965/jrm.2023.p1028
34. [34] Y. Sano, T. Endo, T. Shibuya, and F. Matsuno, “Decentralized navigation and collision avoidance for robotic swarm with heterogeneous abilities,” Advanced Robotics, Vol.37, Nos.1-2, pp. 25-36, 2023. https://doi.org/10.1080/01691864.2022.2117996
35. [35] A. Caregnato-Neto, M. R. O. A. Maximo, and R. J. M. Afonso, “Real-time motion planning and decision-making for a group of differential drive robots under connectivity constraints using robust MPC and mixed-integer programming,” Advanced Robotics, Vol.37, No.5, pp. 356-379, 2023. https://doi.org/10.1080/01691864.2022.2117997
36. [36] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robotics and Autonomous Systems, Vol.61, No.12, pp. 1258-1276, 2013. https://doi.org/10.1016/j.robot.2013.09.004
37. [37] C. S. Tan, R. Mohd-Mokhtar, and M. R. Arshad, “A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms,” IEEE Access, Vol.9, pp. 119310-119342, 2021. https://doi.org/10.1109/ACCESS.2021.3108177
38. [38] H. Choset and P. Pignon, “Coverage path planning: The boustrophedon cellular decomposition,” Field and Service Robotics, pp. 203-209, 1998. https://doi.org/10.1007/978-1-4471-1273-0_32
39. [39] I. Rekleitis, A. P. New, E. S. Rankin, and H. Choset, “Efficient boustrophedon multi-robot coverage: An algorithmic approach,” Annals of Mathematics and Artificial Intelligence, Vol.52, No.2, pp. 109-142, 2008. https://doi.org/10.1007/s10472-009-9120-2
40. [40] N. Hazon, F. Mieli, and G. A. Kaminka, “Towards robust on-line multi-robot coverage,” Proc. 2006 IEEE Int. Conf. on Robotics and Automation, pp. 1710-1715, 2006. https://doi.org/10.1109/ROBOT.2006.1641953
41. [41] K. Kobayashi, T. Higuchi, and S. Ueno, “Performance metric for base station situational awareness in robotic swarm patrolling,” The Proc. of 2023 JSME Annual Conf. on Robotics and Mechatronics (Robomec), Session No.1P1-G01, 2023. https://doi.org/10.1299/jsmermd.2023.1P1-G01
42. [42] S. Aggarwal and N. Kumar, “Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges,” Computer Communications, Vol.149, pp. 270-299, 2020. https://doi.org/10.1016/j.comcom.2019.10.014