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

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.