Multiagent Rollout and Policy Iteration for POMDP with Application to\n Multi-Robot Repair Problems

Abstract

In this paper we consider infinite horizon discounted dynamic programming\nproblems with finite state and control spaces, partial state observations, and\na multiagent structure. We discuss and compare algorithms that simultaneously\nor sequentially optimize the agents' controls by using multistep lookahead,\ntruncated rollout with a known base policy, and a terminal cost function\napproximation. Our methods specifically address the computational challenges of\npartially observable multiagent problems. In particular: 1) We consider rollout\nalgorithms that dramatically reduce required computation while preserving the\nkey cost improvement property of the standard rollout method. The per-step\ncomputational requirements for our methods are on the order of $O(Cm)$ as\ncompared with $O(C^m)$ for standard rollout, where $C$ is the maximum\ncardinality of the constraint set for the control component of each agent, and\n$m$ is the number of agents. 2) We show that our methods can be applied to\nchallenging problems with a graph structure, including a class of robot repair\nproblems whereby multiple robots collaboratively inspect and repair a system\nunder partial information. 3) We provide a simulation study that compares our\nmethods with existing methods, and demonstrate that our methods can handle\nlarger and more complex partially observable multiagent problems (state space\nsize $10^{37}$ and control space size $10^{7}$, respectively). Finally, we\nincorporate our multiagent rollout algorithms as building blocks in an\napproximate policy iteration scheme, where successive rollout policies are\napproximated by using neural network classifiers. While this scheme requires a\nstrictly off-line implementation, it works well in our computational\nexperiments and produces additional significant performance improvement over\nthe single online rollout iteration method.\n