Robust Multi-Agent Path Finding
Robust Multi-Agent Path Finding
复制标题
鲁棒的多代理路径查找
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Neng
中科院分区：
文献类型：
--
作者：
Dor Atzmon;Roni Stern;Ariel Felner;Glenn Wagner;R. Barták;Neng
在多智能体路径搜索(MAPF)问题中，任务是找到一个计划来将一组智能体从其初始位置移动到其目标位置而不发生碰撞。然而，由于意外事件延误了一些代理，遵循此计划可能是不可能的。我们探讨了k-稳健MAPF的概念，其中的任务是找到一个即使发生有限数量的此类延迟也可以遵循的计划。K-稳健MAPF特别适用于具有控制机制的代理，该机制保证每个代理距离其预定义计划在有限的步骤内。我们提出了寻找k-稳健规划的充分必要条件，并展示了如何转换几个MAPF求解器来寻找这样的规划。然后，我们展示了在执行过程中使用k-健壮计划的好处，以及在寻找可能成功的计划方面的好处。
In the multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. We explore the notion of k-robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we show the benefit of using a k-robust plan during execution, and for finding plans that are likely to succeed.