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