Graph Neural Planning and Predictive Control for Multi-Robot Communication-Constrained Unlabeled Motion Planning

Technical Summary: Graph Neural Planning and Predictive Control for Multi-Robot Communication-Constrained Unlabeled Motion Planning

Problem Formulation
The paper addresses the unlabeled motion planning problem for homogeneous multi-robot systems. In this setting, $N$ interchangeable robots must cooperatively reach a set of $N$ goals without pre-assigned pairings. The objective is to minimize total travel time and distance while ensuring collision avoidance. The problem is formulated as a joint assignment and trajectory planning task, which is PSPACE-hard.

The authors identify critical gaps in existing Graph Neural Network (GNN) approaches for this problem:

1. Simplified Dynamics: Prior GNN methods often rely on simplified dynamics in simulation and predict velocity commands directly, failing to account for real-world nonlinear dynamics and actuation limits.
2. Safety Guarantees: Collision avoidance is frequently treated as a soft constraint or a post-hoc filter, which does not guarantee safety under actuation limits.
3. Communication Constraints: Existing GNN architectures often require multi-hop communication (4–5 layers), making them vulnerable to real-world communication delays and drops.
4. Deployment: Most learning-based methods rely on centralized, off-board inference rather than decentralized, on-board execution.

Methodology: Hierarchical GATP-NMPC Framework
The authors propose a hierarchical framework (Figure 1) that decouples high-level planning from low-level control, integrating a Graph ATtention Planner (GATP) with a decentralized Nonlinear Model Predictive Controller (NMPC).

1. High-Level Planning (GATP):

   • Architecture: The planner utilizes a Graph Attention Network (GAT) with only 2 layers of message passing. Each robot communicates only with its $M$ closest neighbors (e.g., $M=2$).
   • Mechanism: The GNN processes local observations (relative positions of $P_g$ closest goals and $P_r$ closest robots) to predict intermediate subgoals ($s_i$) rather than direct velocity commands.
   • Design Choices: The architecture employs Multi-Layer Perceptrons (MLPs) to fuse initial node embeddings with aggregated neighbor information. This "update function" ($f_1$) preserves permutation invariance and enhances node differentiation. The output is scaled to a spatial horizon $S_p$ (e.g., 4m) based on a desired time horizon $T_p$ and maximum speed $v_{max}$.
   • Training: The GATP is trained via imitation learning using a centralized expert (Hungarian Algorithm) to generate optimal subgoals. A scheduled sampling scheme is used to gradually replace expert subgoals with GATP predictions during training.

2. Low-Level Control (NMPC):

   • Execution: Each robot runs a decentralized NMPC to track the subgoal provided by the GATP.
   • Constraints: The NMPC solves a nonlinear optimization problem over a prediction horizon $T_c$ to generate control inputs. It explicitly enforces:
     • Nonlinear Dynamics: Quadrotor dynamics are modeled as control-affine systems.
     • Safety: Hard safety constraints are enforced using Exponential Control Barrier Functions (ECBFs) to maintain a safety distance $d_{safe}$ between robots.
     • Actuation Limits: Motor thrust constraints are respected.
   • Integration: The GATP continuously updates the NMPC reference trajectory based on the robots' evolving positions, allowing for low-frequency replanning (e.g., 1–2 Hz) while the NMPC runs at high frequency (e.g., 100–160 Hz).

Key Contributions

• Hierarchical Framework: A novel integration of a GNN-based planner with a safety-guaranteed NMPC, enabling the application of learning-based methods to real-world systems with nonlinear dynamics and actuation constraints.
• Robust GNN Architecture: A 2-layer Graph Attention Network that requires minimal communication (1-hop, $M=2$ neighbors). The authors demonstrate that this shallow architecture improves robustness to communication delays compared to deeper GNNs used in prior works.
• Real-World Deployment: The first validation of a GNN-based unlabeled motion planner in a fully decentralized, on-board inference setting on physical quadrotors.
• Ablation and Benchmarking: A comparative study showing that the proposed GATP architecture (with specific update functions) outperforms standard Graph Convolutional Networks (GCN) and alternative update strategies in terms of coverage performance and generalization to larger team sizes.

Experimental Results

• Simulation (10 Quadrotors):
  • Coverage Performance: GATP achieved comparable coverage to GCN (94.55% vs. 95.00% in 40s for 10 robots) but demonstrated superior generalization to larger teams (up to 50 robots). GATP showed a smaller performance drop (23.5%) compared to GCN (34.5%) as team size increased, attributed to the attention mechanism's ability to weight neighbor importance dynamically.
  • Communication Delays: The system was tested with simulated communication delays up to 0.6s. The framework remained robust to delays up to 200 ms (total delay $D=0.2$s), with only a ~3.8–5.5% increase in coverage time. Performance degraded significantly only when delays approached the planning update interval (0.5s).
• Real-World Experiments (4 Quadrotors):
  • Deployment: The system was deployed on custom quadrotors with Qualcomm VOXL 2 processors in an indoor testbed.
  • Tasks: Successfully executed circle formation and zone coverage tasks, as well as dynamic obstacle avoidance where the planner re-assigned goals to avoid collisions.
  • Latency: The GATP inference time was approximately 1 ms (excluding communication). The average communication delay per layer was 26 ms, resulting in a total planning time per robot ranging from 51 ms to 134 ms. This confirms the system operates within the robust delay range identified in simulation.

Significance and Claims
The paper claims that this work bridges the gap between scalable, learning-based multi-robot planning and the rigorous safety requirements of real-world deployment. By combining a communication-efficient GNN with a constraint-aware NMPC, the authors demonstrate that:

1. Safety and Feasibility: It is possible to use GNNs for high-level coordination while guaranteeing safety and dynamic feasibility through NMPC.
2. Scalability and Robustness: A shallow, attention-based GNN architecture offers better generalization to larger teams and greater robustness to communication delays than deeper, multi-hop architectures.
3. Practical Viability: Decentralized, on-board inference is feasible for multi-robot systems, as evidenced by the successful real-world experiments with quadrotors.

The authors modestly conclude that while their current design handles bounded delays well, future work will investigate more realistic asynchronous communication conditions and tighter coupling between planning and control during the training process.