Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning
作者: Alexey Skrynnik, Anton Andreychuk, Maria Nesterova, Konstantin Yakovlev, Aleksandr Panov
分类: cs.AI, cs.MA
发布日期: 2023-10-02
备注: 12 pages, 11 figures
💡 一句话要点
提出去中心化的终身多智能体路径规划方法以解决MAPF问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 多智能体系统 路径规划 去中心化 强化学习 启发式搜索 机器人导航 动态环境
📋 核心要点
- 现有的多智能体路径规划方法通常依赖于集中式控制，缺乏灵活性和适应性，难以应对动态环境中的变化。
- 本文提出了一种去中心化的路径规划方法，结合了启发式搜索和强化学习，允许智能体在缺乏全局信息的情况下自主决策。
- 实验结果显示，该方法在通量和泛化能力上均优于现有的学习型和基于规则的竞争者，表现出显著的性能提升。
📝 摘要（中文）
多智能体路径规划（MAPF）问题通常要求为一组在图中受限的智能体找到一组无冲突的路径，通常采用集中式方法解决。本文研究去中心化的MAPF设置，智能体在没有中央控制器的情况下，需自行决定行动。我们提出了一种结合启发式搜索规划和强化学习的解决方案，专注于终身MAPF变体，智能体在完成目标后会不断接收新目标。通过规划算法构建和重新规划路径，并利用强化学习发现有效的避碰策略，最终实现了在多种设置下的评估，结果表明该方法在通量和泛化能力上均优于现有的学习型竞争者。
🔬 方法详解
问题定义：本文解决的是去中心化的多智能体路径规划（MAPF）问题，现有方法通常依赖于集中式控制，无法适应动态环境中的变化，导致灵活性不足。
核心思路：论文的核心思路是结合启发式搜索规划与强化学习，通过自主决策的方式使智能体能够在缺乏全局信息的情况下有效避碰并完成任务。
技术框架：整体架构包括两个主要模块：首先是规划模块，负责构建和重新规划个体路径；其次是强化学习模块，通过训练神经网络来发现有效的避碰策略。
关键创新：最重要的技术创新在于将规划与强化学习相结合，特别是针对去中心化环境下的路径规划问题，显著提高了系统的通量和适应性。
关键设计：在技术细节上，规划算法经过专门设计以避免拥堵，并提高系统的通量；强化学习策略则通过无奖励塑形的方式进行训练，确保智能体能够在复杂环境中有效学习。
🖼️ 关键图片
📊 实验亮点
实验结果表明，所提方法在多种设置下均优于现有的学习型竞争者，通量提高了显著，且在未见过的地图上表现出更好的泛化能力。此外，该方法在速度上比基于规则的解决方案快了一个数量级。
🎯 应用场景
该研究的潜在应用领域包括机器人导航、无人驾驶汽车、智能交通系统等，能够在动态和复杂环境中实现高效的路径规划，具有重要的实际价值和未来影响。
📄 摘要（原文）
Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph and is typically solved in a centralized fashion. Conversely, in this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent and the agents have to sequientially decide the actions on their own without having access to a full state of the environment. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones. To address this complex problem, we propose a method that integrates two complementary approaches: planning with heuristic search and reinforcement learning through policy optimization. Planning is utilized to construct and re-plan individual paths. We enhance our planning algorithm with a dedicated technique tailored to avoid congestion and increase the throughput of the system. We employ reinforcement learning to discover the collision avoidance policies that effectively guide the agents along the paths. The policy is implemented as a neural network and is effectively trained without any reward-shaping or external guidance. We evaluate our method on a wide range of setups comparing it to the state-of-the-art solvers. The results show that our method consistently outperforms the learnable competitors, showing higher throughput and better ability to generalize to the maps that were unseen at the training stage. Moreover our solver outperforms a rule-based one in terms of throughput and is an order of magnitude faster than a state-of-the-art search-based solver.