Research On Heterogeneous Multi-robot Collaborative Area Search Method In Urban Blocks

Robot collaborative area search is an important research direction in the field of robotics,which can be applied to many fields such as rescue and exploration.With the rapid development of cities,the need for regional search in urban block environments is increasing,but it also brings many challenges.For example,the large scenes of urban blocks and the energy constraints of robots make it impossible to complete coverage from the same point,and the task imbalance between robots will greatly extend the task completion time.To address the problem of regional search in urban block environments,this paper proposes a two-stage system structure based on heterogeneous multi-robots.Heterogeneous multi-robots are divided into different robot groups,each of which includes a transport robot and multiple coverage robots.In the first stage,the graph is divided into multiple sub-graphs in a balanced manner,and then the sub-graphs are assigned to different robot groups,and the path between the sub-graphs for the transport robot is planned.Then,for each robot group,the coverage path is planned on the assigned sub-graphs.In order to reduce the impact of task imbalance between robots on the system completion time,this paper proposes the Balanced Graph Partitioning algorithm and the Balanced Ulusoy Partitioning algorithm.The Balanced Graph Partitioning algorithm aims to divide the graph into multiple balanced sub-graphs.The algorithm includes three stages.The first is an improved K-medoids clustering algorithm.In the clustering process,the edge assignment is changed by adding a scaling factor.In the iteration process,the scaling factor is adjusted according to the results of the previous iteration,making the clustering get balanced sub-graphs.Then,the disconnected sub-graphs are processed by redistributing the disconnected edges to make all sub-graphs connected.Finally,the boundary edges of the sub-graphs are redistributed to further improve the balance between sub-graphs.The Balanced Ulusoy Partitioning algorithm aims to plan multiple balanced coverage paths.The algorithm is divided into three stages.The first is to solve the Euler path.Then,an auxiliary directed graph is constructed by taking out and renumbering the demand edges in the Euler path,and the vertices in the directed graph correspond to the demand edges in the Euler path and arcs are added according to certain rules.Finally,the shortest path in the directed graph is solved using dynamic programming and iteration.Dynamic programming can specify the number of paths,and multiple iterations can adjust the auxiliary directed graph,ultimately resulting in multiple balanced coverage paths.Finally,a series of experiments were conducted using seven maps of different sizes obtained from real scenarios,which showed that the task balance between robots was significantly improved and the task completion time was reduced,validating the effectiveness of the system structure and the two algorithms.