  This paper investigates the multi-agent navigation problem, which requires
multiple agents to reach the target goals in a limited time. Multi-agent
reinforcement learning (MARL) has shown promising results for solving this
issue. However, it is inefficient for MARL to directly explore the (nearly)
optimal policy in the large search space, which is exacerbated as the agent
number increases (e.g., 10+ agents) or the environment is more complex (e.g.,
3D simulator). Goal-conditioned hierarchical reinforcement learning (HRL)
provides a promising direction to tackle this challenge by introducing a
hierarchical structure to decompose the search space, where the low-level
policy predicts primitive actions in the guidance of the goals derived from the
high-level policy. In this paper, we propose Multi-Agent Graph-Enhanced
Commander-Executor (MAGE-X), a graph-based goal-conditioned hierarchical method
for multi-agent navigation tasks. MAGE-X comprises a high-level Goal Commander
and a low-level Action Executor. The Goal Commander predicts the probability
distribution of goals and leverages them to assign each agent the most
appropriate final target. The Action Executor utilizes graph neural networks
(GNN) to construct a subgraph for each agent that only contains crucial
partners to improve cooperation. Additionally, the Goal Encoder in the Action
Executor captures the relationship between the agent and the designated goal to
encourage the agent to reach the final target. The results show that MAGE-X
outperforms the state-of-the-art MARL baselines with a 100% success rate with
only 3 million training steps in multi-agent particle environments (MPE) with
50 agents, and at least a 12% higher success rate and 2x higher data efficiency
in a more complicated quadrotor 3D navigation task.
