自适应延迟启发式的任意多智能体路径规划
原文中文，约1700字，阅读约需4分钟。
📝
内容提要
本文探讨了一种新型多智能体路径规划（MAPF）方法，提出了基于多臂赌博机的双层方案，显著提升了成本效益。研究结合了启发式搜索和机器学习策略，解决了高拥堵场景下的路径规划问题，并提出了两种算法变种（LNS-PBS和LNS-wPBS），在效率和稳定性上优于现有算法。
🔎
延伸解读
方法核心：多臂赌博机与双层搜索
文章提出基于多臂赌博机的双层方案，用于在线学习。该方法在大规模情景下，比目前最优的任意时刻多智能体路径规划方法提升至少50%的成本效益。双层结构可能指上层用多臂赌博机选择策略，下层执行路径规划，从而平衡探索与利用，适应动态环境。
算法变种：LNS-PBS与LNS-wPBS
研究提出两种算法变种LNS-PBS和LNS-wPBS，用于解决实时多智能体拾送配送问题及一般版。它们采用大邻域搜索和基于优先级的搜索，实验表明在效率和稳定性上优于现有完整算法CENTRAL和可扩展算法HBH+MLA*，能有效处理成千上万的任务和代理。
高拥堵场景的可扩展性突破
文章首次证明基于机器学习的多智能体路径规划方法在高拥塞场景（如20%智能体密度）中的可扩展性。通过结合启发式搜索与机器学习策略，解决了死锁问题并实现完全水平规划，显著提高了策略的成功率和可扩展性，为大规模应用提供了新思路。
❓
Q&A
什么是多智能体路径规划（MAPF）？
多智能体路径规划是解决一组智能体在不发生碰撞的情况下，从起点移动到目标位置的问题。
这项研究提出了哪些算法变种？
研究提出了两种算法变种：LNS-PBS和LNS-wPBS。
基于多臂赌博机的双层方案有什么优势？
该方案在大规模情景下能够提升至少50%的成本效益。
如何解决高拥堵场景下的路径规划问题？
研究结合了启发式搜索和机器学习策略，以有效解决高拥堵场景下的路径规划问题。
LNS-PBS和LNS-wPBS在效率和稳定性上如何表现？
LNS-PBS和LNS-wPBS在效率和稳定性上优于现有的完整MAPD算法和可扩展的MAPD算法。
这项研究首次证明了什么？
首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景中的可扩展性。
🏷️
