MAGNNET: Multi-Agent Graph Neural Network-based Efficient Task Allocation for Autonomous Vehicles with Deep Reinforcement Learning

📄 arXiv: 2502.02311v2 📥 PDF

作者: Lavanya Ratnabala, Aleksey Fedoseev, Robinroy Peter, Dzmitry Tsetserukou

分类: cs.RO, cs.LG, cs.MA

发布日期: 2025-02-04 (更新: 2025-02-20)

备注: Submitted to IEEE Intelligent Vehicle Symposium (2025)

💡 一句话要点

提出基于多智能体图神经网络的MAGNNET，解决异构无人系统高效任务分配问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体系统 任务分配 图神经网络 深度强化学习 无人机 无人车 集中式训练分散式执行

📋 核心要点

  1. 现有方法难以在通信受限的异构多智能体系统中实现高效的任务分配，尤其是在动态变化的环境中。
  2. MAGNNET框架结合图神经网络和多智能体强化学习，利用集中式训练分散式执行的模式，实现智能体间的协同任务分配。
  3. 实验结果表明，该方法在任务分配成功率、效率和鲁棒性方面均优于现有方法，并具备良好的可扩展性。

📝 摘要（中文）

本文提出了一种新颖的框架，用于解决通信约束下异构多智能体系统中的去中心化任务分配问题。该框架集成了图神经网络（GNN）与集中式训练和分散式执行（CTDE）范式，并结合了为多智能体深度强化学习（MARL）量身定制的近端策略优化（PPO）算法。该方法使无人机（UAV）和无人地面车辆（UGV）能够在3D网格环境中动态高效地分配任务，而无需中央协调。该框架在最小化总旅行时间的同时，避免了任务分配中的冲突。在成本计算和路径规划方面，我们采用了基于预定的A和R路径规划器。实验结果表明，该方法实现了高达92.5%的无冲突成功率，与集中式匈牙利方法相比，性能差距仅为7.49%，并且优于基于贪婪方法的启发式去中心化基线。此外，该框架展现了高达20个智能体的可扩展性，分配处理时间为2.8秒，并且在响应动态生成的任务时具有鲁棒性，突显了其在复杂多智能体场景中实际应用的潜力。

🔬 方法详解

问题定义：论文旨在解决异构多智能体系统（如无人机和无人车协同）在通信受限环境下进行高效、无冲突的任务分配问题。现有方法，如集中式算法，在面对大规模和动态环境时，计算复杂度高，难以扩展。而传统的去中心化方法，如贪婪算法，容易陷入局部最优，导致任务分配效率低下，冲突率高。

核心思路：论文的核心思路是将任务分配问题建模为图结构，利用图神经网络（GNN）学习智能体和任务之间的关系，并通过多智能体强化学习（MARL）训练智能体做出最优决策。采用集中式训练分散式执行（CTDE）的范式，在训练阶段利用全局信息，而在执行阶段仅依赖局部观测，从而保证了算法的可扩展性和鲁棒性。

技术框架：MAGNNET框架主要包含以下几个模块：1) 环境建模：将3D网格环境中的智能体和任务表示为图结构，节点表示智能体或任务，边表示它们之间的关系（如距离、通信状态等）。2) 图神经网络：使用GNN学习图中节点和边的表示，提取智能体和任务的特征。3) 多智能体强化学习：使用PPO算法训练智能体的策略，目标是最小化总旅行时间并避免任务冲突。4) 路径规划：使用基于预定的A和R算法为每个智能体规划到达任务点的最优路径。

关键创新：论文的关键创新在于将图神经网络和多智能体强化学习相结合，用于解决去中心化的任务分配问题。GNN能够有效地学习智能体和任务之间的复杂关系，而MARL则能够训练智能体做出协同决策。此外，论文还针对多智能体任务分配问题，对PPO算法进行了定制化改进。

关键设计：在GNN方面，论文采用了多层图卷积网络，用于聚合邻居节点的信息。在MARL方面，论文使用了共享策略的PPO算法，并设计了奖励函数，鼓励智能体完成任务、避免冲突并减少旅行时间。此外，论文还使用了经验回放和目标网络等技术，以提高训练的稳定性和效率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，MAGNNET框架在任务分配成功率方面达到了92.5%，与集中式匈牙利方法相比，性能差距仅为7.49%，同时优于基于贪婪算法的去中心化基线。此外，该框架在高达20个智能体的场景下，分配处理时间仅为2.8秒，展现了良好的可扩展性和鲁棒性。

🎯 应用场景

该研究成果可应用于多种场景，例如：灾后救援、物流配送、环境监测、农业自动化等。通过无人机和无人车等智能体的协同工作，可以提高任务执行效率，降低人力成本，并减少安全风险。未来，该技术有望在智慧城市、智能交通等领域发挥重要作用。

📄 摘要（原文）

This paper addresses the challenge of decentralized task allocation within heterogeneous multi-agent systems operating under communication constraints. We introduce a novel framework that integrates graph neural networks (GNNs) with a centralized training and decentralized execution (CTDE) paradigm, further enhanced by a tailored Proximal Policy Optimization (PPO) algorithm for multi-agent deep reinforcement learning (MARL). Our approach enables unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs) to dynamically allocate tasks efficiently without necessitating central coordination in a 3D grid environment. The framework minimizes total travel time while simultaneously avoiding conflicts in task assignments. For the cost calculation and routing, we employ reservation-based A and R path planners. Experimental results revealed that our method achieves a high 92.5% conflict-free success rate, with only a 7.49% performance gap compared to the centralized Hungarian method, while outperforming the heuristic decentralized baseline based on greedy approach. Additionally, the framework exhibits scalability with up to 20 agents with allocation processing of 2.8 s and robustness in responding to dynamically generated tasks, underscoring its potential for real-world applications in complex multi-agent scenarios.