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

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

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

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.