Patrolling represents a potential application area for multi-robot systems, as it can enable efficient surveillance. A key aspect in facilitating the real-world applications of such missions is the enhancement of situation awareness of the base station (BS), in addition to ensuring well-coordinated patrol behavior. This paper addresses this requirement by proposing a layered patrol algorithm designed to maintain network connectivity with the BS. The novelty of this research lies in the distributed nature of the algorithm, despite the presence of the BS. Each robot independently determines its behavior based on local information while concurrently preserving connectivity to the BS. Additionally, this study introduces a novel performance metric to assess the situation awareness of the BS, focusing on the algorithm’s ability to provide prompt information about mission progress. Simulated missions revealed that the proposed algorithm outperformed existing algorithms, visited locations of interest more frequently and comprehensively, and provided the BS with improved situation awareness. Enhancing situation awareness may enable human operators to quickly gain insights into the system’s behavior based on mission progress, allowing for timely interventions if necessary. This capability contributes to improving human trust in autonomous systems.

1. [1] E. Şahin, “Swarm robotics: From sources of inspiration to domains of application,” E. Şahin and W. M. Spears (Eds.), “Swarm Robotics,” pp. 10-20, Springer, 2005. https://doi.org/10.1007/978-3-540-30552-1_2
2. [2] 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
3. [3] 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
4. [4] 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
5. [5] M. R. Endsley, “Design and evaluation for situation awareness enhancement,” Proc. of the Human Factors Society Annual Meeting, Vol.32, No.2, pp. 97-101, 1988. https://doi.org/10.1177/154193128803200221
6. [6] K. Kobayashi, T. Higuchi, and S. Ueno, “Hierarchical and distributed patrol strategy for robotic swarms with continuous connectivity,” Proc. of the Joint Symp. of AROB-ISBC-SWARM2023, pp. 1491-1496, 2023.
7. [7] L. Huang, M. Zhou, K. Hao, and E. Hou, “A survey of multi-robot regular and adversarial patrolling,” IEEE/CAA J. of Automatica Sinica, Vol.6, No.4, pp. 894-903, 2019. https://doi.org/10.1109/JAS.2019.1911537
8. [8] A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul, “Multi-agent patrolling: An empirical analysis of alternative architectures,” J. S. Sichman, F. Bousquet, and P. Davidsson (Eds.), “Multi-Agent-Based Simulation II,” pp. 155-170, Springer, 2003. https://doi.org/10.1007/3-540-36483-8_11
9. [9] 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
10. [10] D. Portugal, M. S. Couceiro, and R. P. Rocha, “Applying Bayesian learning to multi-robot patrol,” 2013 IEEE Int. Symp. on Safety, Security, and Rescue Robotics (SSRR), 2013. https://doi.org/10.1109/SSRR.2013.6719325
11. [11] 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
12. [12] 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
13. [13] 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 (in Japanese). https://doi.org/10.7210/jrsj.41.869
14. [14] J. Scherer and B. Rinner, “Persistent multi-UAV surveillance with energy and communication constraints,” 2016 IEEE Int. Conf. on Automation Science and Engineering (CASE), pp. 1225-1230, 2016. https://doi.org/10.1109/COASE.2016.7743546
15. [15] 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
16. [16] 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 (IROS), pp. 616-622, 2015. https://doi.org/10.1109/IROS.2015.7353436
17. [17] 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
18. [18] 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
19. [19] K. Kobayashi, T. Higuchi, and S. Ueno, “Hierarchical control and subgroup formation for robotic swarms in patrol missions,” Int. J. of Mechanical Engineering and Robotics Research, Vol.12, No.5, pp. 258-263, 2023. https://doi.org/10.18178/ijmerr.12.5.258-263
20. [20] 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
21. [21] P. Yang et al., “Decentralized estimation and control of graph connectivity for mobile sensor networks,” Automatica, Vol.46, No.2, pp. 390-396, 2010. https://doi.org/10.1016/j.automatica.2009.11.012
22. [22] L. Sabattini, N. Chopra, and C. Secchi, “Decentralized connectivity maintenance for cooperative control of mobile robotic systems,” The Int. J. of Robotics Research, Vol.32, No.12, pp. 1411-1423, 2013. https://doi.org/10.1177/0278364913499085
23. [23] 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
24. [24] 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
25. [25] 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
26. [26] K. Kobayashi, T. Higuchi, and S. Ueno, “Connectivity maintenance for robotic swarms by distributed role switching algorithm,” Artificial Life and Robotics, Vol.27, No.4, pp. 876-884, 2022. https://doi.org/10.1007/s10015-022-00803-5
27. [27] K. Kobayashi, “Study on patrol missions and improvement of base station’s situation awareness by multi-robot systems,” Ph.D. Thesis, Yokohama National University, 2024.
28. [28] D. Portugal and R. P. Rocha, “Multi-robot patrolling algorithms: Examining performance and scalability,” Advanced Robotics, Vol.27, No.5, pp. 325-336, 2013. https://doi.org/10.1080/01691864.2013.763722
29. [29] D. Sugiyama, S. Azuma, R. Ariizumi, and T. Asai, “Relation between leader–follower consensus control and feedback vertex sets,” Advanced Robotics, Vol.37, Nos.1-2, pp. 37-45, 2023. https://doi.org/10.1080/01691864.2022.2126730
30. [30] 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
31. [31] Y. Sueoka, M. Okada, Y. Tsunoda, Y. Sugimoto, and K. Osuka, “Exploration of a simple navigation method for swarm robots pioneered by heterogeneity,” J. Robot. Mechatron., Vol.35, No.4, pp. 948-956, 2023. https://doi.org/10.20965/jrm.2023.p0948
32. [32] M. Hiraga, D. Morimoto, Y. Katada, and K. Ohkura, “When less is more in embodied evolution: Robotic swarms have better evolvability with constrained communication,” J. Robot. Mechatron., Vol.35, No.4, pp. 988-996, 2023. https://doi.org/10.20965/jrm.2023.p0988
33. [33] H. Kata and S. Ueno, “Connectivity maintenance with application to target search,” SICE J. of Control, Measurement, and System Integration, Vol.14, No.2, pp. 22-29, 2021. https://doi.org/10.1080/18824889.2021.1893971