D-CIS Publication Database


Type of publication:Inproceedings
Entered by:JOSM
TitleStochastic optimal control in continuous space-time multi-agent systems
Bibtex cite ID
Booktitle Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence (UAI 2006)
Year published 2006
Month July
Location 13-16 July 2006, Cambridge, USA
Keywords stochastic optimal control,multi-agent systems
Recently, a theory for stochastic optimal control in non-linear dynamical systems in continuous space-time has been developed (Kappen, 2005). We apply this theory to collaborative multi-agent systems. The agents evolve according to a given non-linear 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 non-interacting agents that have to distribute themselves optimally over a number of targets, given a set of end-costs for the different possible agent-target combinations. We show that optimal control is the combinatorial sum of independent single- agent single-target optimal controls weighted by a factor proportional to the end-costs of the different combinations. Thus, multi- agent control is related to a standard graphical model inference problem. The additional computational cost compared to single-agent control is exponential in the tree-width 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.
Wiegerinck, Wim
van den Broek, Bart
Kappen, Hilbert J.
Total mark: 5