A Multi-agents Pathfinding Algorithm Based on Solution Space Clipping Degree
YUE Rongkang
LONG Yin
Abstract：Conflict Base Search(CBS)is one of the methods of current multi-agent path planning,and it can be combined with Mutex Propagation(MP)method to improve the performance of searching for conflict-free paths.However,CBS-MP has the problem that it is difficult to accurately distinguish non-cardinal conflicts and semi-cardinal conflicts.To this end,CBS-CMP is proposed.By setting the degree of tailoring of the solution space of different mutex as the heuristic value,the method searches for the path solution with the least influence on the solution space of other agents,and then uses the obtained path solution as the con-straint of other agents,and searches for the path solutions without conflicts.Compared with the existing CBS-MP algorithm,this method not only improves the processing of different collision types,but also further improves the path search performance.The re-sults show that the performance advantage of this method is obvious in the barrier-free environment where non-cardinal conflicts fre-quently occur.
Keywords：multi-agentspathfindingmutex propagationbarrier-free environmentmulti-valued decision diagram
Publication Date：2025-02-20
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：6( 389-394 )