Efficient Planning of Multi-Robot Collective Transport using Graph Reinforcement Learning with Higher Order Topological Abstraction

Steve Paul, Wenyuan Li, Brian Smyth, Yuzhou Chen, Yulia R. Gel, Souma Chowdhury

Introduction

Multi-Robot Task Allocation (MRTA) represents a foundational challenge in autonomous systems, particularly in the context of Collective Transport (MRTA-CT). In these scenarios, a fleet of robots must coordinate to deliver supplies to various locations under strict deadlines, limited battery life, and constrained communication ranges. While traditional optimization methods like Mixed-Integer Linear Programming (MILP) provide high-quality solutions, their computational complexity makes them impractical for real-time, large-scale applications. Conversely, standard Reinforcement Learning (RL) approaches offer speed but often fail to generalize when the number of tasks or robots increases beyond the training distribution. This paper introduces CAPAM-TD, a framework designed to bridge this scalability gap by integrating algebraic topology with Graph Reinforcement Learning.

The Scalability Challenge in MRTA-CT

The primary difficulty in MRTA-CT lies in the "scalability gap." A model trained to manage a small fleet of 6 robots and 50 tasks often struggles when deployed in a scenario with 60 robots and 500 tasks. Traditional solvers scale exponentially in computation time, while simple neural architectures lack the structural understanding to adapt to varying task densities and spatial distributions. To address this, the researchers focused on a decentralized policy where each robot makes autonomous decisions based on local observations, yet remains informed by the global "shape" of the task environment.

Methodology: CAPAM-TD

The proposed architecture, CAPAM-TD, combines a Capsule Attention Mechanism (CAPAM) with Topological Descriptors (TD) to create a more robust representation of the problem space.

1. Capsule Attention Mechanism

Unlike standard Graph Neural Networks (GNNs) that may lose spatial hierarchy during message passing, Capsule networks are designed to preserve hierarchical relationships and spatial orientations. This is critical in robotics, where the relative positioning of tasks and agents determines the efficiency of the transport plan.

2. Persistent Homology and Topological Descriptors

The core innovation is the use of Persistent Homology, a tool from algebraic topology, to extract the underlying structure of task distributions. This process identifies "holes," clusters, and connectivity patterns across multiple scales. These features are summarized as Topological Descriptors.

3. TD-Augmented Laplacian

To integrate these topological features into the learning process, the model calculates the Wasserstein distance between the topological fingerprints of different task neighborhoods. This information is embedded into a modified Graph Laplacian. By doing so, the encoder generates node embeddings that are not just aware of Euclidean distances, but also the higher-order "shape" of the environment. This topological awareness allows the agent to learn strategies that are invariant to specific map layouts, facilitating better generalization.

4. Decentralized Training

The model is trained using Proximal Policy Optimization (PPO). The decentralized nature of the policy ensures that robots can operate asynchronously, making decisions based on their local belief of the environment and peer states without requiring a central controller.

Experimental Evaluation

The framework was evaluated using synthetic MRTA-CT scenarios. The model was trained on small-scale instances ($N=50$ tasks, $M=6$ robots) and then tested on significantly larger scales to measure generalizability and scalability.

  • Generalization Test: Scenarios with $N=25$ tasks.
  • Scalability Test: Scenarios with $N=100, 250,$ and $500$ tasks, involving up to $121$ robots.
  • Baselines: The performance was compared against MINLP (optimal), BIGMRTA (a high-performing bipartite matching heuristic), and standard RL architectures (MLP and CAPAM without topological features).

Results and Key Findings

Superior Generalization and Scaling

The inclusion of topological features significantly improved performance at scale. In the largest test case ($N=500$ tasks), the TD-augmented model achieved a 7.1% higher task completion rate compared to the base CAPAM model. This suggests that topological abstraction helps the network maintain a coherent strategy even as the problem size grows by an order of magnitude.

Computational Efficiency

CAPAM-TD demonstrated a massive speedup over traditional heuristics. For a problem with 500 tasks, the BIGMRTA heuristic required 604 seconds to reach a solution. In contrast, the CAPAM-TD model provided a solution in just 33 seconds—a 20-fold increase in speed. While the heuristic remains near-optimal, the RL approach offers a "good enough" solution in a fraction of the time, which is vital for time-sensitive missions like disaster relief.

Robustness

The model maintained competitive performance against near-optimal baselines while proving more resilient to the increased complexity of multi-robot coordination. The decentralized policy successfully managed the asynchronous nature of the tasks, allowing robots to adapt their plans dynamically.

Conclusion and Future Work

CAPAM-TD demonstrates that higher-order topological features can serve as a powerful tool for scaling multi-robot systems. By focusing on the structural "fingerprint" of a task distribution rather than raw coordinates, RL agents can generalize to environments far more complex than those seen during training.

Future research will focus on relaxing the assumption of full initial observability and addressing communication constraints, such as signal noise or data loss. Additionally, the authors plan to move from simplified simulations to high-fidelity physics engines and physical robot testbeds to validate the framework's performance against real-world dynamics.

Summary updated

Abstract

Efficient multi-robot task allocation (MRTA) is fundamental to various time-sensitive applications such as disaster response, warehouse operations, and construction. This paper tackles a particular class of these problems that we call MRTA-collective transport or MRTA-CT -- here tasks present varying workloads and deadlines, and robots are subject to flight range, communication range, and payload constraints. For large instances of these problems involving 100s-1000's of tasks and 10s-100s of robots, traditional non-learning solvers are often time-inefficient, and emerging learning-based policies do not scale well to larger-sized problems without costly retraining. To address this gap, we use a recently proposed encoder-decoder graph neural network involving Capsule networks and multi-head attention mechanism, and innovatively add topological descriptors (TD) as new features to improve transferability to unseen problems of similar and larger size. Persistent homology is used to derive the TD, and proximal policy optimization is used to train our TD-augmented graph neural network. The resulting policy model compares favorably to state-of-the-art non-learning baselines while being much faster. The benefit of using TD is readily evident when scaling to test problems of size larger than those used in training.
BibTeX
@inproceedings{paul2023efficient,
  author = {Steve Paul and Wenyuan Li and Brian Smyth and Yuzhou Chen and Yulia R. Gel and Souma Chowdhury},
  title = {{Efficient Planning of Multi-Robot Collective Transport using Graph Reinforcement Learning with Higher Order Topological Abstraction}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  doi = {10.1109/icra48891.2023.10161517},
}
Figure