Multi-robot coordination and competition using mixed integer and linear programs

摘要

I would like to dedicate this work to my family. May you remain close even though you are far. Markov decision processes (MDPs) and partially observable Markov decision processes (POMDPs) are preferred methods representing complex uncertain dynamic systems and de-termining an optimal control policy to manipulate the system in the desired manner. Until recently, controlling a system composed of multiple agents using the MDP methodology was impossible due to an exponential increase in the size of the MDP problem representation. In this thesis, a novel method for solving large multi-agent MDP systems is presented which avoids this exponential size increase while still providing optimal policies for a large class of useful problems. This thesis provides the following main contributions: A novel description language for multi-agent MDPs: We develop two different mod-eling techniques for representing multi-agent MDP (MAMDP) coordination problems. The first phrases the problem using a linear program which avoids the exponential