Multi-Robot Sequential Decision Making

Simulation Video

Decision-making under uncertainty with multiple-robots systems is essential for various applications. Real-world robotic sequential decision problems entail several challenges, including partial observation, dynamic environment, a large state space due to a complex system, and a large control space given by multiple agents, partial communication. We consider infinite-horizon discounted Markov decision problems under partial observation (POMDP) with finite, discrete state and control space. The size of the state space is 1037, and the control space is 107 for a team of 10 agents.

In the paper [1], we discuss an algorithm that uses multi-step lookahead, truncated rollout with a known base policy, and a terminal cost function approximation. This algorithm is also used for policy improvement in an approximate policy iteration scheme, where successive policies are approximated by using a neural network classifier. A novel feature of our approach is that it is well suited for distributed computation through the use of a partitioned architecture, which is trained with multiple neural networks. We apply our methods in simulation to a class of sequential repair problems where a robot inspects and repairs a pipeline with potentially several rupture sites under partial information about the state of the pipeline. We present a favorable comparison of our algorithm with the standard rollout and other existing algorithms, including POMCP and DESPOT.

In the paper [2], we discuss methods that specifically address the computational challenges of partially observable multiagent problems. We discuss and compare algorithms that simultaneously or sequentially optimize the agents’ controls by using multistep lookahead, truncated rollout with a known base policy, and a terminal cost function approximation. This method dramatically reduces required computation while preserving the key cost improvement property of the standard methods. The per-step computational requirements for our method are linear as compared with exponential in terms of the number of agents for the standard methods. We apply our method to a challenging problem with a graph structure, including a class of robot repair problems whereby multiple robots collaboratively inspect and repair a system under partial information. We provide a simulation study that compares our methods with existing methods. Additionally, we incorporate our multiagent rollout algorithms as building blocks in an approximate policy iteration scheme, where successive rollout policies are approximated by using neural network classifiers. While this scheme requires a strictly off-line implementation, it works well in our computational experiments and produces additional significant performance improvement over the single online rollout iteration method.

Presentation on Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems in CoRL 2020

Multi-Robot Sequential Decision Making Publications

Orhan Eren Akgün, Arif Kerem Dayı, Stephanie Gil, and Angelia Nedić. Submitted. “Learning Trust Over Directed Graphs in Multiagent Systems (extended version)”

Sushmita Bhattacharya, Siva Kailas, Sahil Badyal, Stephanie Gil, and Dimitri Bertsekas. 11/9/2020. “Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems.” In 4th Conference on Robot Learning. Cambridge MA, USA.

Thomas Wheeler, Ezhil Bharathi, and Stephanie Gil. 5/20/2019. “Reinforcement Learning for POMDP: Rollout and Policy Iteration with Application to Sequential Repair.” IEEE International Conference on Robotics and Automation (ICRA).

Sushmita Bhattacharya, Sahil Badyal, Thomas Wheeler, Stephanie Gil, and Dimitri Bertsekas. 1/23/2020. “Reinforcement Learning for POMDP: Partitioned Rollout and Policy Iteration with Application to Autonomous Sequential Repair Problems.” RAL 1/23/2020