多智能体路径查找旨在为在环境中运行的多个智能体规划一组无冲突的轨迹。这是人工智能和机器人学中的一个基本问题，目前广泛应用于自动化存储系统、无人运输、智能制造和多机器人协调[1],[2]。目前，MAPF问题已被证明是NP难的，并且由于其在工业应用中的巨大潜力而受到持续关注[3],[4]。
在实际应用中，特别强调路径规划结果的整体效率。它需要最小化成本总和（SoC）以最大化系统吞吐量，同时保持合理的物理成本，如空间距离总和（SoSD）和总转向次数（TTC），以降低能耗并提高执行可行性。
为了解决这些要求，现有的MAPF研究主要集中在提高时间效率上，并提出了多种在有限计算时间内获得高质量解决方案的想法。现有研究还考察了不同的MAPF解决方案范式及其在各种设置下的性能特征[5]。这些方法通常可以分为两类：（1）最优方法，这类方法通过全局搜索确保解决方案的最优性，例如基于冲突的搜索（CBS）及其改进变体，如增量CBS（ICBS）[4],[6]和ECBS/EECBS [7],[8]。（2）次优方法。这些方法采用局部“破坏-修复”循环在时间限制下获得高质量解决方案，大邻域搜索（LNS）是一个典型的例子[9]。
在现有方法中，CBS是一种获得全局最优解的代表性算法。它是一个两级算法，其中高级搜索在约束树（CT）上操作。CT中的每个节点编码了对单个智能体的时间和位置的约束。对于约束树中的每个节点，都会执行低级搜索以计算满足该高级节点所施加约束的所有智能体的路径。通过这种机制，CBS可以在离散时间、单位步长模型下严格保证SoC的全局最优解，因此它被广泛用作现有研究中最优MAPF算法的基准[4]。然而，在高冲突密度和大规模场景中，CBS由于冲突数量的迅速增加而出现指数级增长，这将导致搜索空间的爆炸性增长和运行时间的急剧增加。同时，其逐点冲突解决策略也容易引入多余的等待或绕行，进一步增加搜索步骤的数量并降低效率。
为了缓解这些问题，提出了多种改进措施。Boyarski等人[6]提出了带有冲突优先级分类和高级代理合并策略的ICBS，重点解决关键冲突以减少无效扩展，从而缓解约束树的膨胀。Barer等人[7]引入了ECBS，它结合了有界次优搜索机制和焦点搜索与双重启发式方法，以平衡搜索质量和效率，允许算法用较小的最优性差距换取显著的运行时间减少。Li等人[8]通过将显式估计搜索策略集成到框架中（EECBS）来增强CBS家族，以更高效地指导搜索并提高操作效率，同时允许存在少量次优解。Li等人[10]提出了不对称/不相交的冲突分割，在高级阶段对冲突的两侧施加互斥约束，避免了由对称冲突引起的重复搜索，并减少了回溯开销和分支因子。Andreychuk等人[11],[12]提出了连续时间CBS（CCBS），将CBS扩展到连续时间模型，并引入了改进的冲突确定和高级启发式方法以减少多余的等待并提高整体效率。Yakovlev K等人[13]证明了将任意角度运动纳入多智能体路径查找框架的可行性，为CBS的后续几何扩展奠定了概念基础，而Yakovlev等人[14]提出了CBS的连续时间扩展（CCBS），使智能体能够在几何空间中的任何角度使用线性连接，从而减少了低级节点的数量并加速了高级阶段的扩展。尽管上述改进在一定程度上提高了CBS的操作效率，但它们仍然依赖于全局冲突分解的思想，在高冲突密度或大规模场景中，高级约束树的大小仍会迅速扩大。这一根本的可扩展性限制仍未得到解决。
为了解决这一限制，Li等人提出了LNS框架[9]，这是一种优先考虑时间效率的近似次优方法。其核心思想是从一个可行解开始，迭代选择一部分路径被破坏的智能体，然后在其余路径固定的条件下进行修复。如果获得了更好的解决方案，则替换原始解决方案。通过每次迭代只重新规划一小部分智能体，LNS可以显著减少搜索空间，并避免像CBS那样全局扩展冲突搜索树，从而在相同的时间内更快地获得接近最优的解决方案。然而，LNS的迭代效果高度依赖于破坏子集的选择。如果子集耦合不足，可能会导致早期收敛缓慢或局部最优解。此外，LNS依赖于初始解决方案生成、子集划分、路径修复等阶段的高效启发式方法，否则解决方案质量的改进可能会受到迭代次数的限制。
为了进一步提高性能，研究人员提出了基于LNS的各种改进方法。Li等人[9]提出了MAPF-LNS2。通过自适应子集大小控制和基于解决方案质量的破坏策略，在早期阶段实现广泛探索，在后期阶段进行精细化，从而显著提高了解决方案的质量。Huang等人[15]提出了机器学习引导的LNS，并在子集选择和路径修复阶段引入了由图神经网络和强化学习模型构建的学习评分器，以识别高影响智能体集并加速迭代收敛。Phan等人[16]提出了一种方法，通过动态平衡子集大小和破坏强度来减轻早期收敛停滞或过度扰动的风险，从而增强了大规模实例的搜索稳定性。随后，他们引入了自适应破坏和修复的高效搜索策略[17]，将多个候选路径和启发式约束排序纳入修复阶段以减少重新规划时间。通过这些改进，基于LNS的方法在计算效率方面表现出色。
除了上述方法外，还探索了基于强化学习和图神经网络的学习方法，以指导路径规划并提高多智能体系统中的决策效率[18]。
尽管上述方法在时间效率方面取得了显著改进，但它们通常将时间成本作为主要的优化目标，而物理执行因素（如路径长度和转向频率）很少被纳入优化目标。现有研究表明，空间因素（如路径长度和转向频率）会显著影响移动系统的能耗[19],[20],[21]。在实际的冲突解决过程中，为减少完成时间而引入的绕行可能会导致路径显著延长和能耗增加。同时，忽略转向和速度等运动学因素也会限制规划结果在真实平台上的可部署性[19]。这些观察表明，在高密度或大规模场景中，仅通过优化时间成本不足以确保解决方案的执行稳定性和物理可行性，因此有必要探索一种能够同时考虑时间和物理成本的路径规划范式。
为了克服现有算法在控制物理成本方面的局限性，我们提出了一种名为“时间调度冲突解决”（CORTS）的多智能体路径规划框架。该框架为每个智能体生成一条几何上具有吸引力的路径，从而构建一组有吸引力的路径。然后它迭代匹配路径对，检测有吸引力路径集中的时间维度上的最早冲突，并通过时间调度解决冲突，直到实现无冲突的路径集。在具有不同数量智能体的各种地图上的广泛实验表明，所提出的CORTS框架显著降低了物理成本（包括路径长度和转向次数），同时保持了时间效率。
本文的其余部分组织如下。第2节阐述了MAPF问题并介绍了必要的定义。第3节介绍了提出的CORTS框架及其关键组件。第4节提供了理论分析和复杂性讨论。第5节报告了实验结果和分析。第6节总结了本文并概述了未来的工作。
