首页|CBS-Budget (CBSB): A complete and bounded suboptimal search for multi-agent path finding
CBS-Budget (CBSB): A complete and bounded suboptimal search for multi-agent path finding
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
Elsevier
Multi-Agent Path Finding (MAPF) is the problem of finding a collection of conflict-free paths for a team of multiple agents while minimizing some global cost, such as the sum of the travel time of all agents, or the travel time of the last agent. Conflict Based Search (CBS) is a leading complete and optimal MAPF algorithm that lazily explores the joint agent state space, using an admissible heuristic joint plan. Such an admissible heuristic joint plan is computed by combining individual shortest paths computed without considering inter-agent conflicts, and becoming gradually more informed as constraints are added to the individual agents' path-planning problems to avoid discovered conflicts. In this paper, we seek to speed up CBS by finding a more informed heuristic joint plan that is bounded. We first propose the budgeted Class-Ordered A* (bCOA*), a novel algorithm that finds the least-cost path with the minimal number of conflicts that is upper bounded in terms of path length. Then, we propose a novel bounded-cost variant of CBS, called CBS-Budget (CBSB) by using bCOA* search at the low-level search of the CBS and by using a modified focal search at the high-level search of the CBS. We prove that CBSB is complete and bounded-suboptimal. In our numerical experiments, CBSB finds a near-optimal solution for hundreds of agents within a fraction of a second. CBSB shows state-of-the-art performance, comparable to Explicit Estimation CBS (EECBS), an enhanced recent version of CBS. On the other hand, CBSB is much easier to implement than EECBS, since only one priority queue at the low-level search is needed, as in CBS, and only two priority queues at the high-level search are needed, as in Enhanced CBS (ECBS).
Multi-agent path findingConflict based searchBounded suboptimality
Jaein Lim、Panagiotis Tsiotras
展开 >
The Daniel Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, 30332, GA, USA
The Daniel Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, 30332, GA, USA||The Institute for Robotics Intelligent Machines, Georgia Institute of Technology, Atlanta, 30332, GA, USA
NETL
NSTL
Elsevier
