Research On Heuristic Multi-Agent Path Finding Algorithm For Conflict-Baesd-Search

The conflict-based search is one of the best algorithms to solve the multi-agent path finding problem at present.Because it combines the advantages of decoupling and coupling algorithms,and ensures the completeness and optimality,it has been widely concerned by researchers.The key of conflict-based search is how to resolve the conflicts between agents.However,most of the current studies only consider a pair of conflicts between two agents when resolving conflicts,which leads to the problem of repeatedly finding paths when the internal coupling of agents is high.Merging the agents with high coupling into meta-agents is an effective strategy to solve this problem,but the current algorithm’s merging strategy is not enough to identify all the agents with high internal coupling.In addition,the multi-agent path finding problem is NP-hard.Given sufficient time,the search algorithm based on A *can always return the optimal solution,but users usually need an available solution rather than the optimal one.Therefore,how to make a reasonable balance between the quality and time of the solution is also a key problem.In view of the above problems,this paper has made two improvements to the traditional conflict-based search algorithm:(1)A heuristic meta-agent path planning algorithm based on high coupling and multiple conflicts is proposed,and more work is done in the root node of the constraint tree.The heuristic information is used to judge the coupling degree between agents,so as to determine the agents to be merged.First,establish the root node,call the low-level search to find the path independently for each agent,then build the weighted dependency graph according to the conflict between agents,and then use the weighted vertex coverage value of the independent subgraph as the index of consolidation.If its value is greater than the prespecified border,the agents on the subgraph will be merged,realizing the consolidation of merge agents in a single step.The proposed algorithm only needs to perform the consolidation operation in the root node,Thus,the problem that the same agent group is merged repeatedly in different positions of the constraint tree is avoided.(2)A bounded suboptimal algorithm about conflict based search is proposed.First,the restrictions on high-level search are relaxed,and nodes with feasible non-minimum cost but total cost within the specified suboptimal range are allowed to be selected as target nodes.The second is to propose a new high-level node priority ranking strategy,which is different from the previous way of ranking only based on cost.Within the specified suboptimal bound,first consider the number of cardinal conflicts,and then prioritize nodes based on the number of internal constraints,so that the advanced search can quickly expand the lower bound and jump out of some special conflicts as soon as possible.Heuristic information is also used to identify conflict types.Experimental results show that this algorithm effectively improves the search efficiency of existing algorithms.