IEEE Transactions on Automation Science and Engineering

GNN-IL-PPO: Imitation Guided Exploration for Large-Scale Multi-Agent Task Assignment in Robotic Warehouses

Le Duc Nguyen Hanoi University of Science and Technology
Vu Duc Nguyen Hanoi University of Science and Technology
Download PDF Read Abstract

Abstract

Deploying hundreds of robots in a warehouse, where conditions change by the minute, is a complex task. Moreover, exact solutions such as the Hungarian algorithm are too slow to be used in real-time. In classical Reinforcement Learning (RL), the above-mentioned state-of-the-art methods hardly scale to learning in very high-dimensional spaces.

We name our method as GNN-IL-PPO, which is a composite policy by GNN and imitation pre-training, together with PPO fine-tuning. We describe the warehouse as a heterogeneous graph having three kinds of nodes, but our policy is scalable to more robots. The trained task-efficient-urgent bimodal heuristic expert is then bootstrapped with demonstrations, and the requirements of exploration are reduced. PPO further generalizes the policy to new tasks.

In simulations with 15 robots, the proposed method has comparable performance as state-of-the-art in terms of makespan loss (up to 8%) while running orders of magnitude faster. Ablations indicate the importance of the graph structure and pre-training, which are 2x faster converge than training from scratch.

Key Contributions

🔗

Heterogeneous Super-Graph

Novel graph representation integrating robot states, tasks, and warehouse layout with typed nodes and edges for permutation-invariant, scalable learning.

🧠

GNN-Transformer Policy

Graph Attention Networks for local neighborhood aggregation combined with Transformer layers for global reasoning and coordination patterns.

🎯

Hybrid IL-RL Training

Two-phase pipeline using behavior cloning from expert heuristics followed by PPO fine-tuning for sample-efficient learning with long-term optimization.

📊

Extensive Evaluation

Comprehensive experiments comparing against state-of-the-art methods with detailed ablation studies validating each component's contribution.

Results Highlights

7.9%
Gap vs. Optimal
Comparable to MAGNNET (7.49%)
2.5×
Faster Inference
vs. Hungarian Algorithm
2×
Training Speed
vs. Training from Scratch
94.2%
Success Rate
Conflict-free Task Completion

Method Overview

Super-graph Representation
Fig. 1: Super-graph representation with robot nodes (blue), task nodes (red), and waypoint nodes (gray).
Network Architecture
Fig. 2: GNN-IL-PPO network architecture with GAT encoder and Transformer policy head.
Training Curves
Fig. 3: Training reward comparison and sample efficiency analysis.
Scalability Analysis
Fig. 4: Scalability analysis showing makespan and allocation time vs. number of robots.

Comparison with State-of-the-Art

Method Makespan (s) Success (%) Throughput Time (s)
Hungarian (Optimal) 58.2 ± 2.1 100.0 0.86 ± 0.03 1.82
GNN-IL-PPO (Ours) 62.8 ± 2.5 94.2 ± 1.8 0.80 ± 0.04 0.72
GNN-PPO (Ablation) 66.5 ± 3.2 88.5 ± 2.5 0.75 ± 0.05 0.71
Greedy-Nearest 68.5 ± 3.8 78.5 ± 3.2 0.73 ± 0.05 0.18
Random 85.2 ± 5.5 62.5 ± 4.5 0.59 ± 0.06 0.05

Keywords

Multi-Agent Systems Task Allocation Deep Reinforcement Learning Graph Neural Network Imitation Learning Warehouse Automation Proximal Policy Optimization