Research On Multi-Agent Cooperative Path Planning In Complex Environment

Multi-agent path planning refers to multiple agents starting from the starting point to the target point,avoiding obstacles without colliding with each other,and collaboratively planning the shortest path that meets the task requirements.This paper aims to use K-Means clustering algorithm and improved A*algorithm to solve multi-agent collaborative path planning problem.First of all,this article analyzes the advantages and disadvantages of mainstream algorithms in several types of path planning,and then choose A*algorithm as the main path planning algorithm on the basis of research problems.This paper mainly studies the problem of multiple agents should start from the same starting point,traverse all the target points in the map and back to the start point with the shortest time,and finally complete the optimal path solution.Secondly,this article analyzes the defects of the traditional A*algorithm,and then this article improves these defects.In order to solve the problem of low search efficiency of the A*algorithm,an optimization method and principle based on the A*algorithm are proposed.The improvement and optimization of the two defects are:(1)The traditional standard A*algorithm calculates the distance between nodes as Manhattan distance,Euclidean distance,and Chebyshev distance.Using these calculation methods will cause the search area to be too large,making the algorithm less efficient.Therefore,on this basis,this paper proposes an improved distance calculation formula-complex diagonal distance calculation formula,which greatly reduces the number of search nodes and search area.(2)The standard heuristic function of the traditional A*algorithm does not consider that during the actual operation of the agent,the change of the direction of travel will cause the agent to turn at different angles.In this process,there will be a certain time delay.The addition of constant term processing reduces the planning of stepped routes,greatly reduces the number of search nodes and turning angles,and improves the search efficiency of the algorithm.Finally,the specific strategy of multi-agent cooperative path planning is given.This paper use K-Means grouping clustering algorithm divide the map into four groups,and then the improved A*algorithm is used for path planning to complete the optimal path.Solution.This paper conducts simulation experiments in MATLAB system.(a)This article divides the map into grids,and then expands complex obstacles in the map.Set different start and end points on the map,and compare the results with the traditional A*algorithm.Experimental data shows that the improved A*algorithm improves the overall efficiency by 12?15%compared with the traditional A*algorithm.(b)Analyze the actual case,and take the example of express delivery robots on campus dormitory to realize multi-agent collaborative path planning based on K-Means clustering and A*algorithm.In summary,for the problem of multi-agent collaborative path planning in the complex environment studied in this paper,it mainly solves the defects of low search efficiency and large search area of the traditional A*algorithm;secondly,it uses the principle of obstacle expansion to process complex maps;Then,the strategy of using K-Means clustering algorithm to solve multi-agent cooperation is given,and finally the optimal path planning route is formed.