Abstract Aiming at multi-robot patrol problems, a distributed patrol algorithm based on estimated global maximum idleness(EGMI) is proposed to ensure that each patrol vertex can be visited by robots in a certain period of time. In the execution process of algorithm, the global average maximum idle time is estimated using the shared information by each robot, and the next target point to be visited is decided and selected by the robot at the current vertex combining the information collected. Then, performance of the multi-robot team during the patrol task is evaluated according to the global mean maximum idle time. Thus, the optimal number of robots required to complete the patrol task can be obtained. Simulation experiments show that EGMI produces a higher convergence speed and a lower global average maximum idle time. A better result of completing the multi-robot patrol task is achieved.
Fund:Supported by National Natural Science Foundation of China(No.61663020), Science and Research Project of Colleges in Gansu Province(No.2018D-10), 100-Talents Program of Lanzhou Jiaotong University(No.1520220305)
Corresponding Authors:
LI Zonggang, Ph.D., professor. His research interests include intelligent bionic robot and multi-robot system cooperative control.
About author:: ZHAO Yuntao, master student. His research interests include multi-robot system cooperative control.LI ZonggangCorresponding author, Ph.D., professor. His research interests include intelligent bionic robot and multi-robot system cooperative control.DU Yajiang, master, professor. His research inte-rests include electro-mechanical equipment detection and control, rail transit equipment automation and monitoring.
ZHAO Yuntao,LI Zonggang,DU Yajiang. Team Size Optimization for Distributed Patrol of Multi-robot Systems Based on Maximum Idle Time[J]. , 2020, 33(4): 375-382.
[1] PASQUALETTI F, FRANCHI A, BULLO F. On Cooperative Patro-lling: Optimal Trajectories Complexity Analysis, And Approximation Algorithms. IEEE Transactions on Robotics, 2012, 28(3): 592-606. [2] ELMALIACH Y, AGMON N, KAMINKA G A. Multi-robot Area Patrol under Frequency Constraints. Annals of Mathematics and Artificial Intelligence, 2009, 57: 293-320. [3] PORTUGAL D, ROCHA R P. Multi-robot Patrolling Algorithms: Examining Performance and Scalability. Advanced Robotics, 2013, 27(5): 325-336. [4] PORTUGAL D, ROCHA R P. Distributed Multi-robot Patrol: A Scalable and Fault-Tolerant Framework. Robotics and Autonomous Systems, 2013, 61(12): 1572-1587. [5] PORTUGAL D, ROCHA R P. Cooperative Multi-robot Patrol with Bayesian Learning. Autonomous Robots, 2016, 40(5): 929-953. [6] FARINELLI A, IOCCHI L, NARDI D. Distributed On-line Dyna-mic Task Assignment for Multi-robot Patrolling. Autonomous Robots, 2017, 41(6): 1321-1345. [7] YAN C B, ZHANG T. Multi-robot Patrol: A Distributed Algorithm Based on Expected Idleness. International Journal of Advanced Robotic Systems, 2016, 13(6). DOI: 10.1177/1729881416663666. [8] PORTUGAL D, PIPPIN C, ROCHA R P, et al. Finding Optimal Routes for Multi-robot Patrolling in Genetic Graphs // Proc of the IEEE/RSJ International Conference on Intelligent Robotics and Systems. Washington, USA: IEEE, 2014, II: 363-369. [9] ALMEIDA A, RAMALHO G, SANTANA H, et al. Recent Advances on Multi-agent Patrolling // Proc of the Brazilian Symposium on Artificial Intelligence. Berlin, Germany: Springer, 2004: 474-483. [10] AGMON N, URIELI D, STONE P. Multiagent Patrol Generalized to Complex Environmental Conditions // Proc of the 25th Confe-rence on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2011: 1090-1095.
2020, Vol. 33 
