Research On Multi-agent Path Planning For Symmetry Conflict

Recent advances in robotics have laid the groundwork for building large-scale multiagent systems.A fundamental task in different multi-agent systems is to navigate agents in a shared environment to their goal locations without colliding with each other or bumping into obstacles.Specific practical applications include evacuation,formation control,object traffic,traffic management,search and rescue,autonomous vehicles,drone swarm coordination,video game character control,and warehouse automation,among others.The pathfinding problem involved in the above applications has formed a well-studied abstract model called MAPF(Multi Agents Path Finding,MAPF).In order to further improve the operating efficiency of the MAPF algorithm in different scenarios,the main research contents of this paper are as follows:1.Two types of MAPF problems studied in this paper are defined,which are classical MAPF based on discrete-time assumption and general MAPF based on continuous-time assumption.The path symmetry problem caused by the multi-solution of the optimal path of the agent is studied,and it is found that the symmetric conflict brought about by the path symmetry will lead to the problem of exponential expansion of the conflict state space on which the frontier MAPF algorithm depends,and then cause the algorithm The result of running too long to solve the MAPF problem in finite time.2.For the traditional CBS(Conflict Based Search,CBS)and its cutting-edge improved version,the problem of semi-symmetrical conflicts cannot be effectively solved in the classic MAPF problem,that is,due to the impact of semi-symmetrical conflicts,the number of nodes in the constraint tree Exponentially expanding,while the underlying pathfinding algorithm repeatedly plans invalid paths.A heuristic method based on the pruning degree of the solution space is proposed to identify semi-symmetrical conflicts in advance and reduce the generation of constraint tree nodes.At the same time,it can also generate a set of constraints corresponding to conflicts,thereby avoiding repeated planning of invalid paths.Through simulation analysis and comparison,it is verified that the improved CBS algorithm in this paper is more efficient in path planning than the previous work within the framework of the CBS algorithm.At the same time,the characteristics of high success rate and low running time of the improved CBS algorithm in this paper are also verified on maps of different scales and different scenarios.3.In view of the fact that the classic MAPF cannot be directly applied to the scene where the kinematic model is not strictly unified,the general MAPF problem is defined,that is,the discrete time step assumption is abandoned,and all moving actions and waiting actions are no longer strictly required to be time steps.Integer multiples.Based on the CCBS(Conflict Based Search with Continuous time,CCBS)algorithm for this problem,combined with the mutex propagation technology in the field of artificial intelligence planning,it can be used to identify symmetric conflicts universally.Therefore,the number of constraint tree nodes generated during the path planning process is reduced,especially in scenarios where symmetry conflicts occur frequently.Through simulation analysis and comparison,it is verified that the CCBS algorithm combined with the mutex propagation technology proposed in this paper is more efficient than the CCBS algorithm on the general MAPF problem.At the same time,the efficiency of the improved CCBS algorithm in this paper is also verified in maps of different types and scales.In addition,it is also verified that the mutex propagation technology combined with the CBS algorithm and the most cutting-edge bidirectional constraints still have performance improvements in the 4-way and 8-way neighborhood grid maps.