基于多步长的多机器人分布式巡逻算法研究

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (02): 313-320.

基于多步长的多机器人分布式巡逻算法研究

白耀文1，2，杜亚江1，2，李宗刚1，2

（1.兰州交通大学机电工程学院，甘肃兰州 730070；2.兰州交通大学机器人研究所，甘肃兰州 730070）

收稿日期:2021-08-12 修回日期:2021-12-06 接受日期:2023-02-25 出版日期:2023-02-25 发布日期:2023-02-15
基金资助:
国家自然科学基金（61663020）；甘肃省高等学校科研项目成果转化项目（2018D-10）

A distributed multi-robot patrolling algorithm based on multi-step length

BAI Yao-wen1，2,DU Ya-jiang1，2,LI Zong-gang1，2

(1.School of Mechanical Engineering,Lanzhou Jiaotong University,Lanzhou 730070;
2.Robot Research Institute,Lanzhou Jiaotong University,Lanzhou 730070,China)

Received:2021-08-12 Revised:2021-12-06 Accepted:2023-02-25 Online:2023-02-25 Published:2023-02-15

摘要/Abstract

摘要： 针对多机器人巡逻中多数算法只利用被访问节点的相邻节点信息，导致平均空闲时间增加的问题，提出了一种基于多步长的分布式巡逻算法。首先，利用无向图对环境进行建模，其中存在路径的2个节点互为邻居，引入重要度刻画节点所在区域的重要程度。其次，设计基于个体机器人的效用函数，其中利用了被访问节点邻居的邻居信息，函数在结合相邻节点空闲时间和重要度的同时，考虑了相邻节点邻居的局部平均空闲时间和节点个数，进而通过比较效用函数来指导个体机器人运动。实验结果表明，该算法在机器人数量逐渐增多时，系统的全局平均空闲时间也逐渐缩短且具有很好的稳定性，相较于其他几种对比算法，该算法更加适用于机器人数量较多时的巡逻任务。

关键词: 多机器人巡逻系统, 多步长, 分布式巡逻算法, 全局平均空闲时间, 重要度

Abstract: Aiming at the problem that the average idle time increases because most algorithms in multi-robot patrolling only use the information of the adjacent nodes of the visited nodes, a distributed patrolling algorithm based on multi-step length is proposed. Firstly, an undirected graph is used to model the environment, in which two nodes with paths are neighbours to each other, and the importance degree is introduced to describe the importance degree of the region where the nodes are located. Secondly, the utility function based on the individual robot is designed, in which the neighbour information of the neighbours of the visited node is used. The function combines the idle time and importance of adjacent nodes and considers the local average idle time and the number of nodes of neighbours of adjacent nodes, and then guides the movement of individual robots by comparing the utility functions. Finally, experimental results show that the global average idle time of the proposed algorithm is gradually reduced and has good stability when the number of robots increases gradually. Compared with other algorithms, the proposed algorithm is more suitable for the patrolling task when the number of robots is large.

Key words: multi-robot patrol system, multi-step length, distributed patrolling algorithm, global average idle time, importance degree

白耀文, 杜亚江, 李宗刚, . 基于多步长的多机器人分布式巡逻算法研究[J]. 计算机工程与科学, 2023, 45(02): 313-320.

BAI Yao-wen, DU Ya-jiang, LI Zong-gang, . A distributed multi-robot patrolling algorithm based on multi-step length[J]. Computer Engineering & Science, 2023, 45(02): 313-320.

参考文献［8］

［1］	Li H, Zhou M C,Hao K R,et al.A survey of multi-robot regular and adversarial patrolling［J］.IEEE/CAA Journal of Automatica Sinica,2019,6(4):894-903.
［2］	Machado A,Alemeida A,Ramalho G,et al.Multi-agent movement coordination in patrolling［C］∥Proc of the 3rd International Conference on Computers and Games,2002:456-461.
［3］	Sak T,Wainer J,Goldenstein S K. Probabilistic multiagent patrolling［C］∥Proc of the 19th Brazilian Symposium on Artificial Intelligence，2008:124-133.
［4］	Portugal D, Couceiro M S,Rocha R P.Applying Bayesian learning to multi-robot patrol［C］∥Proc of IEEE International Symposium on Safety,Security and Rescue Robotics,2013:21-26.
［5］	Portugal D, Rocha R P.Distributed multi-robot patrol:A scalable and fault-tolerant framework［J］.Robotics and Autonomous Systems,2013,61(12):1572-1587.
［6］	Portugal D,Rocha R P.Cooperative multi-robot patrol with Bayesian learning［J］.Autonomous Robots,2016,40(5):929-953.
［7］	Farinelli A, Iocchi L,Nardi D.Distributed on-line dynamic task assignment for multi-robot patrolling［J］.Autonomous Robots,2017,41(6):1321-1345.
［8］	Zhao Yun-tao,Li Zong-gang,Du Ya-jiang.Quantity optimization of distributed patrol robots based on maximum idle time［J］.Pattern Recognition and Artificial Intelligence,2020,33(4):375-382.(in Chinese)
［9］	Almeida A,Ramalho G,Santana H,et al.Recent advances on multi-agent patrolling［C］∥Proc of the 17th Brazilian Symposium on Artificial Intelligence,2004:474-483.
［10］	Agmon N,Urieli D,Stone P.Multiagent patrol generalized to complex environmental conditions［C］∥Proc of the 25th AAAI Conference on Artificial Intelligence,2011:1090-1095.
［11］	Zhong J,Cheng H,He L,et al.Decentralized full coverage of unknown areas by multiple robots with limited visibility sensing［J］.IEEE Robotics and Automation Letters,2019,4(2):338-345.
	附中文参考文献:
［8］	赵云涛,李宗刚,杜亚江.基于最大空闲时间的分布式巡逻机器人数量优化［J］.模式识别与人工智能,2020,33(4):375-382.