LaCAM 是一种基于搜索的多智能体路径规划（MAPF）求解器，它在联合配置上进行深度优先搜索，使用 PIBT 产生后继并惰性地加入单智能体约束以探索备选方案。虽然 LaCAM 完备，但在密集且走廊众多的实例上表现不佳，因为要从死锁中抽取阻塞智能体需要多智能体协同移动，往往要暂时离开目标，而 PIBT 的贪婪一步后继很少会提出此类移动，LaCAM 只能通过一次枚举单个约束来实现。为此本文提出 Goal-Branching：为阻塞智能体分配临时目标，并将每个临时目标作为 LaCAM 搜索的额外分支。我们研究了随机和走廊感知两类临时目标选择规则，并证明在任意规则下完整性仍然保持。实验在三种迷宫和房间地图上进行，密度在 60%~90% 的情况下，Goal-Branching 的求解成功率为 89%，而 LaCAM 为 44%。在两者都能求解的实例上，Goal-Branching 的首次解出现时间提升 10~14 倍，在 75% 密度的 room-32-32-4 上中位时间提升近 200 倍。解的代价在两者都能求解的实例上增加 15%~22%，而在开放地图和完整 MovingAI 基准上，解的代价不高于 LaCAM，运行时间最多慢 3%。
点评