Research On Distributed Patrol Algorithm Of Multi-robot System

Multi robot system is one of the important directions in the field of robotics.It mainly studies the methods that multiple robots cooperate to complete tasks that single robot is difficult to complete,such as environment map construction,search and rescue,patrol,monitoring and so on.Among them,the core of multi robot patrol is to design an appropriate algorithm,so that multiple robots can cover the environment in a given time interval,so as to realize the monitoring and protection of a given area.At present,multi robot patrol algorithms are mainly divided into centralized and distributed.In the process of completing the patrol task,the main difference between the two kinds of algorithms is that in the centralized algorithm,each robot has all the information of other robots and environment,while in the distributed algorithm,each robot only has the information of its adjacent robots and environment.Obviously,the distributed patrol algorithm has strong robustness in the dynamic environment.This thesis focuses on the research of distributed patrol algorithm in multi-robot system patrol task,the main contents are as follows:1.Under the condition that the path of the robot visits the target node is determined,a distributed patrol algorithm based on the local average idleness is proposed to reduce the global average idleness of the system for the information sharing problem of multi-robot system patrol.Firstly,each robot uses the information of neighboring robots to estimate the local average idleness,and uses it as a negotiation variable to give a discrete-time consensus algorithm for estimating the global average idleness.Secondly,a utility function based on the global average idleness is designed,and the robot chooses the point with the largest utility function as the next target node.Finally,compared with the existing algorithm on the robot simulation platform,the global average idle value under this algorithm is better than others.2.In order to solve the existence of dynamic obstacles in the environment and the absence of a fixed path among the target nodes,a distributed algorithm based on probability foam is designed to solve the problem of dynamic generation of patrol paths and obstacle avoidance.On the basis of using the aforementioned consensus algorithm to realize local information sharing,the robot is modeled as a bubble,and its patrol environment is covered by a set of generated probability bubbles.This set is composed of overlapping convex subsets of bubbles.The robot moves from the initial node to the target.The path of the node is generated by randomly propagating bubbles in the patrol environment through the search tree.When two obstacles with different structures are randomly added to the patrol environment to form a dynamic environment,all robots need to negotiate obstacle avoidance and re-plan to generate a new path.Through the simulation platform analysis and comparison of the total number of bubbles generated when the robot completes the patrol task in the two environments,the total time spent and the overlap rate of the bubbles,it is proved that the algorithm shows better performance in a dynamic environment.