MASP: Scalable Graph-Based Planning Towards Multi-UAV Navigation

Xinyi Yang, Xiao-Peng Yang, Chao Yu, Jiayu Chen, Wenbo Ding, Huazhong Yang, Yu WangDrones 2025 · DOI

TL;DR

This paper introduces MASP, a novel hierarchical reinforcement learning framework for multi-UAV navigation. MASP tackles the challenge of efficiently assigning and navigating multiple drones to unassigned goals by decomposing the problem into goal assignment and navigation sub-tasks, leveraging graph-based representations and attention mechanisms for scalability and cooperation.

What Problem Does This Paper Address?

Coordinating multiple drones (UAVs) to navigate to a set of unassigned goals is a critical task with applications ranging from logistics to disaster response. Traditional planning-based methods struggle with complex coordination and require extensive hyperparameter tuning. Reinforcement learning (RL) offers a powerful alternative but faces significant challenges with low sample efficiency, especially as the number of drones or environmental complexity increases. This is due to the exponential growth of the state-action space, making it difficult for RL agents to learn optimal policies. Existing RL approaches often fail to scale beyond a few drones or simple environments.

Methods

MASP proposes a goal-conditioned hierarchical reinforcement learning (HRL) framework to address these limitations. It decomposes the complex multi-UAV navigation problem into two stages:

  • High-Level Policy (Goal Matcher - GM): This policy is responsible for goal assignment. It uses a graph-based representation of drones and goals, employing an attention-based mechanism to efficiently compute matching scores and assign goals to individual drones. This approach breaks down the large exploration space into smaller, manageable goal-conditioned subspaces.
  • Low-Level Policy (Coordinated Action Executor - CAE): This policy handles goal navigation. It takes the assigned goal from GM and outputs actions for each drone. To maintain scalability and efficiency, CAE utilizes a group division mechanism. This mechanism partitions other drones into groups, allowing CAE to focus on local interactions within these groups rather than processing information from all drones simultaneously. Graph Convolutional Networks (GCNs) are used within each group to capture inter-drone relationships.

MASP follows a centralized training with decentralized execution (CTDE) paradigm, allowing each drone to have its own MASP instance while benefiting from centralized training.

Datasets

The paper evaluates MASP on two established simulation environments:

  • MPE (Multi-Agent Particle Environments): A 2D environment where drones are abstracted as particles. This environment is used for faster verification and testing of the method's scalability.
  • OmniDrones: A more complex 3D simulator for drone control, offering realistic aerodynamic models and continuous action spaces. This environment is used to test MASP's performance in a more challenging and realistic setting.

No new datasets were introduced in this paper.

Key Insights and Ideas

  • Hierarchical Decomposition is Key for Scalability: Breaking down the complex multi-UAV navigation problem into distinct goal assignment and navigation sub-problems significantly improves learning efficiency and scalability.
  • Graph-Based Representations and Attention Mechanisms Excel at Coordination: Representing drones and goals as dynamic graphs, coupled with attention mechanisms, allows MASP to effectively model and leverage inter-agent relationships, even with a large and varying number of agents.
  • Group Division Mitigates Curse of Dimensionality: The group division mechanism in the low-level policy is crucial for handling a large number of drones by reducing the input dimensionality and computational load, enabling efficient local coordination.
  • Goal Assignment and Navigation Synergy: Jointly optimizing goal assignment and navigation, as done by MASP's hierarchical structure, leads to more efficient and effective overall task completion compared to methods that treat these as separate problems.

Key Results

MASP demonstrates superior performance compared to both planning-based and RL-based baselines across various scenarios:

  • Task Efficiency: MASP significantly improves task efficiency. For instance, it achieves over 27.92% improvement in task efficiency in the OmniDrones environment with 20 drones compared to planning-based competitors. It also shows at least a 47.87% enhancement across varying team sizes.
  • Success Rate: MASP consistently achieves near 100% Success Rate in both MPE and OmniDrones, even with a large number of drones (e.g., 50 drones in MPE).
  • Steps (Execution Time): MASP requires significantly fewer steps to complete tasks. In MPE with 50 drones, it requires 32x fewer steps than the best planning-based competitor.
  • Scalability: MASP demonstrates strong scalability, performing well with up to 50 drones in MPE and 20 drones in OmniDrones.
  • Robustness: MASP shows robustness to sensor noise and time delay in the OmniDrones environment, maintaining high success rates where planning-based baselines struggle.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Task Decomposition Assumption: The current approach relies on the assumption that tasks can be naturally decomposed into goal assignment and navigation. For more complex multi-agent scenarios where subtasks are not clearly defined, learning latent subtask representations would be beneficial.
  • Global Pose Assumption: The method assumes agents can receive global pose information. In real-world deployments, communication delays or data loss can pose challenges. Future work should explore adaptive bandwidth allocation and robust state estimation.
  • Lack of Vision-Based Modules: MASP currently lacks vision-based mapping and dynamic perception modules. The authors intend to integrate lightweight vision sensors and adopt incremental vision-based mapping techniques to address this.

Summary updated

Abstract

This work investigates multi-UAV navigation tasks where multiple drones need to reach initially unassigned goals in a limited time. Reinforcement learning (RL) has recently become a popular approach for such tasks. However, RL struggles with low sample efficiency when directly exploring (nearly) optimal policies in a large exploration space, especially with an increased number of drones (e.g., 10+ drones) or in complex environments (e.g., a 3D quadrotor simulator). To address these challenges, this paper proposes Multi-UAV Scalable Graph-based Planner (MASP), a goal-conditioned hierarchical planner that reduces space complexity by decomposing the large exploration space into multiple goal-conditioned subspaces. MASP consists of a high-level policy that optimizes goal assignment and a low-level policy that promotes goal navigation. MASP uses a graph-based representation and introduces an attention-based mechanism as well as a group division mechanism to enhance cooperation between drones and adaptability to varying team sizes. The results demonstrate that MASP outperforms RL and planning-based baselines in task and execution efficiency. Compared to planning-based competitors, MASP improves task efficiency by over 27.92% in a 3D continuous quadrotor environment with 20 drones.
BibTeX
@inproceedings{yang2025masp,
  author = {Xinyi Yang and Xiao-Peng Yang and Chao Yu and Jiayu Chen and Wenbo Ding and Huazhong Yang and Yu Wang},
  title = {{MASP: Scalable Graph-Based Planning Towards Multi-UAV Navigation}},
  booktitle = {Drones},
  year = {2025},
  doi = {10.3390/drones9070463},
}
Figure