# MASP: Scalable GNN-based Planning for Multi-Agent Navigation

arXiv: https://arxiv.org/abs/2312.02522 · HTML: https://mlsanity.com/paper/2312.02522/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 5 Dec 2023.

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [A Survey of Deep Learning Techniques for Autonomous Driving](https://mlsanity.com/paper/1910.07738/) (2019)
- [Multi-Agent Reinforcement Learning is a Sequence Modeling Problem](https://mlsanity.com/paper/2205.14953/) (2022)
- [Deep Hierarchical Planning from Pixels](https://mlsanity.com/paper/2206.04114/) (2022)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Augmenting Reinforcement Learning with Behavior Primitives for Diverse Manipulation Tasks](https://mlsanity.com/paper/2110.03655/) (2021)
- [Hierarchical Reinforcement Learning for Precise Soccer Shooting Skills using a Quadrupedal Robot](https://mlsanity.com/paper/2208.01160/) (2022)
- [OmniDrones: An Efficient and Flexible Platform for Reinforcement Learning in Drone Control](https://mlsanity.com/paper/2309.12825/) (2023)
- [Learning Efficient Multi-Agent Cooperative Visual Exploration](https://mlsanity.com/paper/2110.05734/) (2021)
- [Heterogeneous Multi-Agent Reinforcement Learning for Unknown Environment Mapping](https://mlsanity.com/paper/2010.02663/) (2020)
- [Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios](https://mlsanity.com/paper/1702.05515/) (2017)
- [Multi-Agent Embodied Visual Semantic Navigation with Scene Prior Knowledge](https://mlsanity.com/paper/2109.09531/) (2021)
- [Learning Graph-Enhanced Commander-Executor for Multi-Agent Navigation](https://mlsanity.com/paper/2302.04094/) (2023)
- [Hierarchical Reinforcement Learning Framework for Stochastic Spaceflight Campaign Design](https://mlsanity.com/paper/2103.08981/) (2021)

## Abstract (arXiv)

We investigate multi-agent navigation tasks, where multiple agents need to reach initially unassigned goals in a limited time. Classical planning-based methods suffer from expensive computation overhead at each step and offer limited expressiveness for complex cooperation strategies. In contrast, reinforcement learning (RL) has recently become a popular approach for addressing this issue. However, RL struggles with low data efficiency and cooperation when directly exploring (nearly) optimal policies in a large exploration space, especially with an increased number of agents(e.g., 10+ agents) or in complex environments (e.g., 3-D simulators). In this paper, we propose the Multi-Agent Scalable Graph-based Planner (MASP), a goal-conditioned hierarchical planner for navigation tasks with a substantial number of agents in the decentralized setting. MASP employs a hierarchical framework to reduce space complexity by decomposing a large exploration space into multiple goal-conditioned subspaces, where a high-level policy assigns agents goals, and a low-level policy navigates agents toward designated goals. For agent cooperation and the adaptation to varying team sizes, we model agents and goals as graphs to better capture their relationship. The high-level policy, the Goal Matcher, leverages a graph-based Self-Encoder and Cross-Encoder to optimize goal assignment by updating the agent and the goal graphs. The low-level policy, the Coordinated Action Executor, introduces the Group Information Fusion to facilitate group division and extract agent relationships across groups, enhancing training efficiency for agent cooperation. The results demonstrate that MASP outperforms RL and planning-based baselines in task efficiency.