LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding

多智能体路径规划（MAPF）是物流和仓储管理的关键组成部分，它专注于为已知环境中的一组机器人规划无碰撞路径。最近的工作引入了一种新的MAPF方法，LNS2，它提出通过迭代重新规划来修复一组快速获得的不可行路径，依靠快速但较低质量的基于优先级的规划器。同时，最近也推出了基于多智能体强化学习（MARL）的MAPF算法，这些算法允许智能体学习分散的策略，展现了比优先级规划更好的合作，尽管速度不可避免地较慢。在本文中，我们介绍了一种新的MAPF算法，LNS2+RL，它结合了LNS2和MARL的不同但互补的特性，有效平衡了它们各自的限制，并充分发挥了两者的优点。在早期迭代中，LNS2+RL依靠MARL进行低级别的重新规划，我们展示了其比基于优先级的规划器更能消除碰撞。在这里，我们基于MARL的规划器允许智能体推理过去和未来/预测信息，通过一个精心设计的课程学习逐渐学习合作决策。在规划的后期阶段，LNS2+RL会自适应地切换到基于优先级的规划，以快速解决剩余的碰撞，自然地权衡解决方案质量和计算效率。我们在各种团队规模、世界大小和地图结构的具有挑战性的任务上进行的全面实验一致表明，LNS2+RL相比于许多MAPF算法（包括LNS2、LaCAM和EECBS）表现出更优异的性能，在复杂场景中表现出显着的优势。最后，我们在一个涉及100个（真实和模拟）机器人团队的仓库模型混合仿真中实验验证了我们的算法。

论文旨在解决多智能体路径规划（MAPF）中的冲突问题，并探索将优先级规划和多智能体强化学习相结合的新方法。

论文提出了一种新的MAPF算法，LNS2+RL，通过将LNS2和MARL相结合，有效平衡它们各自的限制，并在复杂场景下表现出更好的性能。

论文使用实验验证了LNS2+RL算法在各种任务、团队规模、世界大小和地图结构中的优越性，并在一个包含100个机器人的仓库模型的混合仿真中进行了实验验证。

最近的相关研究包括LNS2、LaCAM和EECBS等MAPF算法，以及基于MARL的MAPF算法，如COMA、QMIX和VDN等。