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.
赵云涛, 李宗刚, 杜亚江. 基于最大空闲时间的分布式巡逻机器人数量优化[J]. 模式识别与人工智能, 2020, 33(4): 375-382.
ZHAO Yuntao, LI Zonggang,DU Yajiang. Team Size Optimization for Distributed Patrol of Multi-robot Systems Based on Maximum Idle Time. , 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.