Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and $2^k$-neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.
翻译:以冲突为基础的搜索(CBS)是一个强大的算法框架,有助于以最佳方式解决典型的多试剂路径发现(MAPF)问题,将时间与时间步骤分离开来。CBS(CCBS)是CBS最近提出的一个版本,它保证了最佳解决办法,而不需要分开时间。然而,CBS的可缩放性是有限的,因为它不包括CBS的任何已知改进。在本文件中,我们开始缩小这一差距,并探讨如何使CBS的成功改进适应CBS的连续时间设置,即冲突优先处理(PC)、分解裂(DS)和高超常量超常量。这些调整并非微不足道,需要谨慎地处理不同类型的限制,采用安全间隔路径规划(SIPP)的通用算法,扩大主要冲突的概念。我们通过对一般图形和邻里网进行实验来评估所建议的改进的效果。CBS(CBS)与这些改进大大超越了Vanilla CCBS, 在某些案例中将问题作为许多代理人解决近两倍的问题,并在连续的域中推进多试管范围。