在高障碍密度和大型地图中的高性能多智能体路径寻找

《Neurocomputing》：High-performance multi-agent path finding in high-obstacle-density and large-size maps

　　针对多智能体路径规划中的奖励稀疏、信用分配困难及非平稳环境问题，提出基于集中训练与分布式执行的近值分解网络PVDN，结合团队奖励机制与局部视野优化，显著提升大规模复杂地图下的规划成功率与协调性，实验验证其优于现有RL方法。

　　在当前的工业应用中，人工智能技术正在迅速发展并被广泛采用，涉及多个关键领域，如航空发动机缺陷检测、电池健康管理以及智能设备巡检等。这些应用场景表明，具有可扩展性和高效性的学习算法在解决现实世界中的复杂问题方面扮演着至关重要的角色。同样地，工业场景中的多智能体系统往往需要在大规模和资源受限的条件下实现可靠且高效的决策机制。多智能体路径规划（Multi-Agent Path Finding, MAPF）问题因其在机器人技术、自动驾驶、机场牵引、物流仓储、电子游戏等多个领域的广泛应用而受到越来越多的关注。MAPF的核心任务是为多个智能体从各自的起点找到通向目标点的无冲突路径。然而，MAPF问题本质上属于组合优化中的NP难问题，其复杂性随着智能体数量的增加呈指数级增长，使得传统的搜索算法难以在大规模场景中保持高效性。

近年来，多智能体强化学习（Multi-Agent Reinforcement Learning, MARL）被广泛应用于多智能体系统中，成为解决MAPF问题的一种有前景的方法。与传统的集中式规划算法不同，基于强化学习的方法通常只需要局部观察信息即可进行路径规划，从而降低了计算负担。然而，现有的基于强化学习的MAPF方法在处理复杂任务时表现欠佳，特别是在高障碍密度和大规模智能体场景下。例如，在一个20x20的随机地图中，障碍物密度为30%，有64个智能体的情况下，最先进的方法SCRIMP仅能实现60%的成功率，并且存在频繁的碰撞问题。在更复杂的80x80地图中，障碍物密度仍为30%，但智能体数量增加到512，SCRIMP的成功率进一步下降至7%。这些结果表明，现有方法在面对大规模和高复杂度的MAPF任务时，面临着显著的性能瓶颈。

现有的基于强化学习的MAPF方法主要存在两个关键问题。首先，这些方法通常在大规模地图上表现出较差的协调能力，导致成功率低下。这主要是由于个体奖励函数的设计不合理。例如，一些方法仅在所有智能体到达目标点时给予正向奖励，否则对无碰撞的移动行为给予固定的负向奖励。这种稀疏奖励机制使得智能体在接近目标点时容易陷入停滞状态，从而导致死锁现象。此外，个体奖励的稀疏性以及最终奖励的延迟接收，使得智能体在长时间序列中难以准确判断哪些行为对最终结果产生了影响，进而加剧了学习过程中的困难。

其次，独立强化学习方法在处理多智能体系统的信用分配问题和环境非平稳性问题时存在明显不足。信用分配问题指的是如何在团队奖励中合理地分配每个智能体的贡献，而环境非平稳性则源于智能体之间策略的相互影响，导致每个智能体的转移概率随其他智能体策略的变化而变化。这些问题使得传统的多智能体强化学习方法难以有效应对复杂和动态的路径规划任务。

为了解决上述问题，本文提出了一种基于集中式训练与分布式执行（Centralized Training with Decentralized Execution, CTDE）的多智能体强化学习算法——Proximal Value Decomposition Network（PVDN）。PVDN通过引入基于势函数的奖励塑造技术，优化了个体奖励函数的设计，从而确保智能体的策略不受目标距离的影响，并有效缓解了智能体间的拥堵问题。此外，PVDN在训练过程中仅关注智能体及其邻近智能体的联合行动，简化了联合行动值函数的复杂度，降低了内存需求。通过将团队Q函数分解为个体Q函数，PVDN不仅解决了信用分配问题，还能够在一定程度上遵循个体全局最大化（Individual Global Max, IGM）原则，从而促进接近全局最优的路径规划。

在PVDN的基础上，本文进一步提出了H2L（High-performance, High-obstacle-density, and Large-scale）算法，该算法结合了局部团队奖励机制和PVDN算法，以应对高障碍密度和大规模智能体路径规划任务。H2L算法的核心思想是利用智能体的视野（Field of View, FOV）来计算局部奖励，使得智能体在局部范围内进行合作，同时避免因全局信息的缺失而导致的决策偏差。在大规模MAPF场景中，智能体的行为往往在一定距离之外趋于独立，因此H2L算法通过将全局问题分解为多个局部子问题，实现了高效且可扩展的路径规划。此外，本文还提供了理论分析，证明在局部子问题相互独立的前提下，PVDN的优化目标与经典的MAPF问题保持一致，从而保证了算法的有效性。

实验部分表明，H2L算法在多个基准测试中显著优于现有的基于强化学习的路径规划方法。在具有30%障碍物密度的随机地图上，H2L能够实现更高的成功率，并有效减少智能体之间的碰撞。同时，实验结果还展示了H2L算法在不同规模地图上的良好泛化能力，证明了其在实际应用中的适应性。这些实验不仅验证了PVDN和H2L算法的有效性，还为未来的多智能体路径规划研究提供了新的思路和方法。

本文的主要贡献包括：首先，提出了一种新颖的团队奖励函数，该函数确保每个智能体的策略不受目标距离的影响，并有效缓解了智能体间的拥堵问题，特别是在部分可观测环境中；其次，设计了PVDN算法，该算法通过集中式训练与分布式执行的范式，解决了行动-观察空间指数增长和训练内存需求过高的问题，并在理论上验证了其适用于MAPF问题的可行性；最后，通过实验验证了H2L算法在复杂MAPF任务中的优越性能，展示了其在高障碍密度和大规模智能体场景下的应用潜力。

H2L算法的设计理念体现了对实际工业场景中多智能体系统需求的深入理解。在工业应用中，多智能体系统通常需要在有限的资源条件下实现高效的路径规划，这要求算法不仅具备良好的可扩展性，还应能适应不同的环境条件和任务需求。H2L算法通过将全局路径规划问题分解为多个局部子问题，并利用局部奖励机制促进智能体间的协作，为解决实际工业中的多智能体路径规划问题提供了一种可行的方案。此外，H2L算法在训练过程中采用集中式训练策略，而在执行过程中采用分布式策略，这一设计既保证了训练的效率，又避免了执行时对全局信息的依赖，从而提高了系统的鲁棒性和适应性。

本文的研究不仅对多智能体路径规划领域具有重要的理论和实践意义，也为人工智能在工业场景中的应用提供了新的技术路径。随着工业自动化和智能化的不断推进，多智能体系统将在更多领域发挥关键作用，而高效的路径规划算法将成为实现这些系统性能的关键因素。因此，本文提出的H2L算法及其核心组件PVDN，为未来的多智能体路径规划研究和实际应用提供了有价值的参考。通过优化奖励函数和算法结构，H2L能够在复杂的工业环境中实现更高的规划效率和成功率，从而为相关技术的发展奠定了坚实的基础。