TL;DR
The paper introduces iSEM (iterative Sampling-based Expectation-Maximization), a robust algorithm for learning multi-robot coordination policies in complex, uncertain environments. By combining temporally extended "macro-actions" with a multi-threaded, randomized optimization approach, iSEM overcomes the local optima traps of previous methods, enabling a team of heterogeneous robots to perform effective search-and-rescue (SAR) missions in both simulation and real-world hardware trials.
What Problem Does This Paper Address?
Coordinating a team of robots in the real world is notoriously difficult. Environments are often "partially observable" (robots can't see everything at once) and "stochastic" (actions have uncertain outcomes). The standard mathematical framework for this, the Decentralized Partially Observable Markov Decision Process (Dec-POMDP), is computationally "NEXP-complete"—meaning it is virtually impossible to solve for large-scale problems.
To make this tractable, researchers use macro-actions (MAs)—high-level behaviors like "Go to Site A" or "Pick up Victim" that take variable amounts of time. While previous learning-based methods like PoEM (Policy-based EM) could learn from data, they were "greedy" and prone to getting stuck in poor "local optima" (sub-optimal solutions). They were also highly sensitive to how the algorithm was initialized. This paper aims to bridge the gap between theoretical models and reliable, large-scale hardware deployment.
Methods
The authors propose iSEM, which enhances the standard Expectation-Maximization (EM) approach through two key innovations:
- Concurrent Multi-threading: Instead of running one optimization, iSEM runs multiple instances of the PoEM algorithm in parallel, each starting with different random initial parameters drawn from a Dirichlet distribution.
- Iterative Re-sampling: The algorithm monitors the performance of these parallel "threads." If a thread converges to a solution that is significantly worse than the current best-known policy, iSEM "kills" that thread 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" (sequences of observations, macro-actions, and rewards) without needing a perfect model of the environment upfront.
Datasets
The algorithm was evaluated using:
- 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.
- Behavioral Data: Training data was generated using a mix of a hand-coded "expert" policy and a random policy. The authors varied the "expertness" ($\rho$) and the amount of training data ($K$) to test the algorithm's robustness.
- Hardware Implementation: Real-world trials were conducted in a 40x20 ft flight space using a DJI F330 quadrotor (UAV) and three Duckiebots (UGVs).
Key Insights and Ideas
- Overcoming the "Local Optima" Trap: The core "aha moment" is that in complex multi-robot spaces, the "value landscape" is incredibly bumpy. A single-shot optimization is likely to get stuck in a valley. iSEM’s re-sampling strategy acts like a "global explorer," constantly re-allocating computational resources to find the highest peaks.
- Macro-actions as a Complexity Reducer: By shifting from primitive actions (e.g., "move forward 1cm") to macro-actions (e.g., "Go to Muster Site"), the planning horizon is shortened, making it possible to solve problems that would otherwise be mathematically intractable.
- Consistency Matters: The authors found that iSEM doesn't just find better solutions; it finds them more consistently. In robotics, a policy with low variance (predictable performance) is often more valuable than one that is occasionally perfect but frequently fails.
Key Results
- Superior Performance: In simulations, iSEM consistently achieved higher cumulative rewards than the state-of-the-art PoEM algorithm across various controller sizes and data volumes.
- Data Efficiency: iSEM reached high performance levels with significantly fewer training demonstrations than previous methods.
- Hardware Success: The learned policies successfully controlled a heterogeneous team in real-time. The robots managed to save all victims in most trials, even while adhering to strict collision avoidance constraints (using Reciprocal Velocity Obstacles) and dealing with imperfect, range-limited communication.
- Scalability: The gap between iSEM and PoEM was most noticeable as the complexity of the controller ($|Q_n|$) increased, proving iSEM is better at navigating high-dimensional policy spaces.
Limitations and Future Work
- Random Sampling: Currently, iSEM uses random sampling to re-initialize threads. The authors suggest that "active sampling"—choosing new starting points more strategically—could further improve efficiency.
- Communication Modeling: While the hardware demo included range-limited communication, the authors aim to model communication and observation costs more explicitly as part of the action-selection process in the future.
- Computational Overhead: Running multiple threads in parallel requires more initial compute power, though the authors note the algorithm is highly parallelizable and training is typically done offline.
Summary updated