Resolving Head-on Conflicts For CBS-Based Multi-Agent Path Finding Problem

Path planning has always been an active issue in the field of robotics.With the development of society,single robot may not capable of getting the job done.In more and more scenes we need multiple robots to work together to achieve a same goal,such as airport automatic aircraft tractor,automatic warehouse system,office robot and the role in the video games and so on.Because robots can't collide with each other,these problems can't be solved by simply planning paths for each robot.Multi-agent path finding means to solve this problem,to plan a set of paths for a group of robots that lead them to the designated location efficiently and safely,so as to improve the efficiency of the overall task.Conflict-based search is one of the most popular methods for of multi-agent path finding.It searches a binary search tree to find the solution.The root node plans paths for each agent separately,and then resolves the conflicts by adding constraints.Each node only considers the constraints imposed on it and ignores other agents when planning paths.However,in some cases after the first conflict is resolved,a predictable conflict occurs in the subtree of the node.In other words,the existing ways of resolving conflicts can't completely resolve this kind of conflicts.Given that,this paper optimize the conflict-based search by resolving these two conflict in one split.In view of the above problems,this paper has done the following work: Firstly analyzing the shortcomings of conflict-based search,and prove that resolving the conflict will lead to another foreseeable conflict under some conditions.On this basis,the conflicts' head-on attribute is defined.Secondly,this paper defines the head-on and semi-head-on conflicts,the priority of resolving conflicts is rearranged,and the properties of head-on conflicts is discussed.Thirdly this paper introduces how to resolve head-on and semi-head-on conflicts,proves the completeness of each resolving method.Besides that,the head-on technique is proposed and its optimality is proved.Finally this paper conducts experiments on standard map,random map and simulation map.The experimental results show that the head-on improves conflict-based search in both runtime and success rate.The head-on technique works slightly better than the rectangular reasoning technique.