Learning for Multi-robot Cooperation in Partially Observable Stochastic Environments with Macro-actions

Miao Liu, Kavinayan Sivakumar, Shayegan Omidshafiei, Christopher Amato, Jonathan P. How

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:

  1. 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.
  2. 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).
The DJI F330 quadrotor used as the UAV in real-world Search and Rescue hardware trials.

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.

Comprehensive evaluation of iSEM: (a) SAR domain visualization, (b) reward vs. training trajectories, (c) reward vs. expert policy percentage, and (d) reward vs. controller size.

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

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). Dec-POMDPs provide a general framework for cooperative sequential decision making under uncertainty and MAs allow temporally extended and asynchronous action execution. To date, most methods assume the underlying Dec-POMDP model is known a priori or a full simulator is available during planning time. Previous methods which aim to address these issues suffer from local optimality and sensitivity to initial conditions. Additionally, few hardware demonstrations involving a large team of heterogeneous robots and with long planning horizons exist. This work addresses these gaps by proposing an iterative sampling based Expectation-Maximization algorithm (iSEM) to learn polices using only trajectory data containing observations, MAs, and rewards. Our experiments show the algorithm is able to achieve better solution quality than the state-of-the-art learning-based methods. We implement two variants of multi-robot Search and Rescue (SAR) domains (with and without obstacles) on hardware to demonstrate the learned policies can effectively control a team of distributed robots to cooperate in a partially observable stochastic environment.
BibTeX
@inproceedings{liu2017learning,
  author = {Miao Liu and Kavinayan Sivakumar and Shayegan Omidshafiei and Christopher Amato and Jonathan P. How},
  title = {{Learning for Multi-robot Cooperation in Partially Observable Stochastic Environments with Macro-actions}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2017},
  doi = {10.1109/iros.2017.8206001},
}
Figure