Research On Patrol Algorithm Of Multi-robot System Based On Idle Time

With the advantages of adaptability,parallelizability and scalability,multi-robot systems have broad application prospects in manufacturing,military,educational field and service industries.The coordination and cooperation among robots also has a good application prospect and research value in its own field.The patrol task embodies the advantages of multi-robot system,and how to deal with multi-robot cooperation is one of the main problems in multi-robot research.Through effective coordination mechanism,the robots assign patrol tasks to obtain and monitor the information of patrol environment to ensure that the whole patrol area is in a safe state.This thesis mainly studies the multi-robot patrol algorithm,which enables the robot to plan the path autonomously according to the information of target points in the patrol environment,and verifies the proposed patrol algorithm by taking the system's idle time and the access frequency of target points as the evaluation criteria for the global task.The main research contents include the following aspects:(1)Of the multi-robot patrol problems,this thesis proposes a distributed patrol algorithm based on Estimated Global Maximum Idleness(EGMI),ensuring that each patrol vertex can be visited by robots in a certain period of time.By the process of algorithm execution,each robot uses the shared information to estimate the global average maximum idle time and combines the information collected by the robot at the current vertex to make decisions to select the next target point to be visited.Then the performance of the multi-robot team during the patrol task is estimated according to the global mean maximum idle time,so the optimal number of robots required to complete the patrol task can be obtained.By comparing the simulation experiment with several existing distributed patrol algorithms,it can be seen that under the same experimental conditions,the EGMI algorithm has a faster convergence speed and a smaller global average maximum idle time.The better effect is achieved by using this algorithm to complete the multi-robot patrol task.(2)A distributed patrol algorithm based on fraction of coverage is proposed to solve the coverage problem of multi-robot patrol.The robots choose the appropriate patrol path to cover the environment through coordination,and reduce the overlap rate between adjacent robots to ensure that the access frequency of each vertex in the map tends to be consistent.By increasing the coverage rate of the multi-robot system to the target points in the environment and reducing the overlap rate of the patrol area,the patrol efficiency can be improved,so as to further reduce the idle time of the multi-robot system and improve the patrol efficiency.(3)A distributed patrol algorithm based on global average idle time is designed to solve the problem of multi-robot system patrolling in dynamic environment.During the execution of the patrol task,the robots estimate the global average idle time through the Shared information,and decide the next target point to be visited based on the information collected at the current node and the path selection strategy in the dynamic environment.The global average idle time of multi-robot system patrolling can be reduced by increasing the frequency of visiting nodes with higher importance and larger idle time in the patrol environment.The performance of the algorithm in dynamic environment and static environment is compared and analyzed by simulation experiments,which verifies the effectiveness and stability of the algorithm.