Abstract
This paper presents a data-driven approach for multi-robot coordination in partially-observable domains based on Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) and macro-actions (MAs). We propose an iterative sampling-based Expectation-Maximization algorithm (iSEM) to learn policies using only trajectory data containing observations, MAs, and rewards. Our experiments show that iSEM achieves better solution quality than state-of-the-art learning-based methods. We demonstrate the learned policies on a team of heterogeneous robots in multi-robot Search and Rescue (SAR) domains to show their effectiveness in partially observable stochastic environments.
Introduction: The Challenge of Multi-Robot Coordination
Coordinating a team of robots in real-world scenarios is a significant challenge due to partial observability (robots cannot see everything at once) and stochasticity (actions have uncertain outcomes). The Decentralized Partially Observable Markov Decision Process (Dec-POMDP) framework is the standard for modeling these problems, but solving it for large-scale systems is computationally prohibitive, categorized as NEXP-complete.
To make this tractable, researchers use macro-actions (MAs)—high-level, temporally extended behaviors like "Go to Site A" or "Pick up Victim." While previous learning-based methods like PoEM (Policy-based EM) could learn from data, they were often "greedy" and prone to getting stuck in poor local optima. This work introduces iSEM to bridge the gap between theoretical models and robust hardware deployment.
Methodology: The iSEM Algorithm
The proposed iSEM (iterative Sampling-based Expectation-Maximization) algorithm improves upon standard EM through two main innovations:
- Concurrent Multi-threading: Instead of a single optimization run, iSEM executes multiple instances of the PoEM algorithm in parallel, each starting with different random initial parameters.
- Iterative Re-sampling: The algorithm monitors the performance of these parallel threads. If a thread converges to a solution significantly worse than the current best-known policy, iSEM terminates it and re-initializes it with new random parameters.
Policies are represented as Finite State Controllers (FSCs)—specifically Mealy machines—which allow robots to make decisions based on a compact abstraction of their history and current observations. This structure is learned entirely from trajectory data without requiring a perfect model of the environment upfront.
Experimental Setup
The algorithm was evaluated using both simulation and real-world hardware trials:
- Simulated SAR Domain: A large-scale 20x10 grid environment with 4 agents (1 UAV, 3 UGVs), 6 sites, and 6 victims. Victim health degrades over time, requiring robots to prioritize rescues.
- Hardware Implementation: Real-world trials were conducted in a 40x20 ft flight space using a DJI F330 quadrotor (UAV) and three Duckiebots (UGVs).
Results and Discussion
iSEM demonstrated significant improvements over the baseline PoEM algorithm across several metrics, proving its ability to navigate complex "value landscapes" more effectively.
Key findings include:
- Superior Performance: iSEM consistently achieved higher cumulative rewards than PoEM across various controller sizes and data volumes. The gap was most noticeable as controller complexity ($|Q_n|$) increased.
- Data Efficiency: The algorithm reached high performance levels with significantly fewer training demonstrations than previous methods.
- Hardware Success: The learned policies successfully controlled the heterogeneous team in real-time. The robots managed to save all victims in most trials, even while adhering to strict collision avoidance constraints and dealing with range-limited communication.
Conclusion and Future Work
iSEM provides a robust framework for learning multi-robot coordination policies from data, overcoming the local optima traps of previous methods. Future work will explore "active sampling" to choose new starting points more strategically and aim to model communication and observation costs more explicitly within the action-selection process.
Summary updated