论文标题
基于冲突的搜索可解释的多代理路径查找
Conflict-Based Search for Explainable Multi-Agent Path Finding
论文作者
论文摘要
在多代理路径查找（MAPF）问题中，目标是在环境中找到代理的非收缩路径，以便每个代理都从其初始位置达到其目标。在关键安全应用中，人类主管可能想验证该计划确实没有碰撞。为此，最近的一项工作介绍了MAPF的解释性概念，该概念基于计划的可视化，作为代表时间段的简短图像序列，在每个时间段中，代理的轨迹都是不相交的。然后，可解释的MAPF问题要求一组非填塞路径，这些路径可以接受短暂的解释。可解释的MAPF添加了MAPF的新困难，因为它相对于环境的大小，而不仅仅是代理的数量。因此，传统的MAPF算法无法直接处理可解释的MAPF。在这项工作中，我们调整了基于冲突的搜索（CBS），这是一种经过良好研究的MAPF算法，用于处理可解释的MAPF。我们展示了如何在标准CBS树的顶部及其基础*搜索添加解释性约束。我们研究了这种方法的有用性，尤其是计划时间和解释性之间的权衡。
In the Multi-Agent Path Finding (MAPF) problem, the goal is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial location. In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. To this end, a recent work introduces a notion of explainability for MAPF based on a visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint. Then, the explainable MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NP-hard with respect to the size of the environment, and not just the number of agents. Thus, traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. In this work, we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF. We show how to add explainability constraints on top of the standard CBS tree and its underlying A* search. We examine the usefulness of this approach and, in particular, the tradeoff between planning time and explainability.
