Abstract
The majority of multi-agent path finding (MAPF) methods compute collision-free space-time paths which require agents to be at a specific location at a specific discretized timestep. However, executing these space-time paths directly on robotic systems is infeasible due to real-time execution differences (e.g. delays) which can lead to collisions. To combat this, current methods translate the space-time paths into a temporal plan graph (TPG) that only requires that agents observe the order in which they navigate through locations where their paths cross. However, planning space-time paths and then post-processing them into a TPG does not reduce the required agent-to-agent coordination, which is fixed once the space-time paths are computed. To that end, we propose a novel algorithm Space-Order CBS that can directly plan a TPG and explicitly minimize coordination. Our main theoretical insight is our novel perspective on viewing a TPG as a set of space-visitation order paths where agents visit locations in relative orders (e.g. 1st vs 2nd) as opposed to specific timesteps. We redefine unique conflicts and constraints for adapting CBS for space-order planning. We experimentally validate how Space-Order CBS can return TPGs which significantly reduce coordination, thus subsequently reducing the amount of agent-agent communication and leading to more robustness to delays during execution.
Abstract (translated)
大多数多代理器路径规划（MAPF）方法计算碰撞免的空间-时间路径，这要求代理在特定的时间步长上位于特定的位置。然而，直接在机器人系统上执行这些空间-时间路径是不可行的，因为实时执行差异（例如延迟）可能导致碰撞。为了应对这个问题，现有方法将空间-时间路径转换为时间计划图（TPG），只需要要求代理观察他们通过位置相交的路径的顺序。然而，规划和处理空间-时间路径并将其转换为TPG并不能减少所需的代理与代理之间的协调，一旦空间-时间路径计算完成，这种协调就是固定的。因此，我们提出了一种新颖的算法——空间顺序CBS（Space-Order CBS），可以直接规划TPG，并明确最小化协调。我们主要的理论洞察是我们将TPG看作是一个相对位置访问顺序路径的集合，而不是特定的时间步。我们重新定义了为适应空间顺序计划而重新定义独特的冲突和约束。我们通过实验验证了Space-Order CBS如何返回具有显著降低协调的TPG，从而在后续减少代理与代理之间的通信，并导致在执行过程中延迟的减少。
URL
https://arxiv.org/abs/2404.15137
