ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding
ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding
复制标题
具有 Flex 分布的 ECBS 用于有界次优多代理路径查找
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sven Koenig
中科院分区：
文献类型：
--
作者：
Shao;Jiaoyang Li;G. Gange;Daniel D. Harabor;P. Stuckey;Sven Koenig
多智能体路径查找（Multi-Agent Path Finding， MAPF）是为多个智能体寻找无冲突路径的问题。CBS是一种领先的最优两级MAPF求解器，其低层为单个代理规划最优路径，高层在约束树（CT）上运行最佳优先搜索以解决路径之间的冲突。ECBS是CBS的有界次优变体，它通过减少需要在高层解决的冲突数量来加快CBS的速度。它通过在低层次上生成与其他智能体路径冲突较少的有界次优路径，以及在高层次上扩展包含较少冲突的有界次优CT节点来实现这一点。在本文中，我们提出了灵活的ECBS (FECBS)，通过在低水平上使用更宽松的次优边界，进一步减少了需要在高水平上解决的碰撞数量，同时仍然提供有界次优解。FECBS不要求每条路径的代价为有界次优，只要求路径的总代价为有界次优，这使我们可以根据不同的智能体的需要自由地分配代价。我们的实证结果表明，FECBS可以在5分钟内解决比最先进的ECBS变体更多的MAPF实例。
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.