Stochastic Optimal Control in Continuous SpaceTime MultiAgent Systems
Wim Wiegerinck, Bart van den Broek, Hilbert Kappen
Abstract:
Recently, a theory for stochastic optimal control in nonlinear dynamical systems in continuous spacetime has been developed (Kappen, 2005). We apply this theory to collaborative multiagent systems. The agents evolve according to a given nonlinear dynamics with additive Wiener noise. Each agent can control its own dynamics. The goal is to minimize the accumulated joint cost, which consists of a state dependent term and a term that is quadratic in the control. We focus on systems of noninteracting agents that have to distribute themselves optimally over a number of targets, given a set of endcosts for the different possible agenttarget combinations. We show that optimal control is the combinatorial sum of independent singleagent singletarget optimal controls weighted by a factor proportional to the endcosts of the different combinations. Thus, multiagent control is related to a standard graphical model inference problem. The additional computational cost compared to singleagent control is exponential in the treewidth of the graph specifying the combinatorial sum times the number of targets. We illustrate the result by simulations of systems with up to 42 agents.
Keywords:
Pages: 528535
PS Link:
PDF Link: /papers/06/p528wiegerinck.pdf
BibTex:
@INPROCEEDINGS{Wiegerinck06,
AUTHOR = "Wim Wiegerinck
and Bart van den Broek and Hilbert Kappen",
TITLE = "Stochastic Optimal Control in Continuous SpaceTime MultiAgent Systems",
BOOKTITLE = "Proceedings of the TwentySecond Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI06)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2006",
PAGES = "528535"
}

