Optimal Control in Large Stochastic Multi-agent Systems
We study optimal control in large stochastic multi-agent systems in continuous space and time. We consider multi-agent systems where agents have independent dynamics with additive noise and control. The goal is to minimize the joint cost, which consists o
- PDF / 432,820 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 101 Downloads / 217 Views
Abstract. We study optimal control in large stochastic multi-agent systems in continuous space and time. We consider multi-agent systems where agents have independent dynamics with additive noise and control. The goal is to minimize the joint cost, which consists of a state dependent term and a term quadratic in the control. The system is described by a mathematical model, and an explicit solution is given. We focus on large systems where agents have to distribute themselves over a number of targets with minimal cost. In such a setting the optimal control problem is equivalent to a graphical model inference problem. Exact inference will be intractable, and we use the mean field approximation to compute accurate approximations of the optimal controls. We conclude that near to optimal control in large stochastic multi-agent systems is possible with this approach.
1
Introduction
A collaborative multi-agent system is a group of agents in which each member behaves autonomously to reach the common goal of the group. Some examples are teams of robots or unmanned vehicles, and networks of automated resource allocation. An issue typically appearing in multi-agent systems is decentralized coordination; the communication between agents may be restricted, there may be no time to receive all the demands for a certain resource, or an unmanned vehicle may be unsure about how to anticipate another vehicles movement and avoid a collision. In this paper we focus on the issue of optimal control in large multi-agent systems where the agents dynamics are continuous in space and time. In particular we look at cases where the agents have to distribute themselves in admissible ways over a number of targets. Due to the noise in the dynamics, a configuration that initially seems attainable with little effort may become harder to reach later on. Common approaches to derive a coordination rule are based on discretizations of space and time. These often suffer from the curse of dimensionality, as the complexity increases exponentially in the number of agents. Some successfull ideas, however, have recently been put forward, which are based on structures that are assumed to be present [1,2]. K. Tuyls et al. (Eds.): Adaptive Agents and MAS III, LNAI 4865, pp. 15–26, 2008. c Springer-Verlag Berlin Heidelberg 2008
16
B. van den Broek, W. Wiegerinck, and B. Kappen
Here we rather model the system in continuous space and time, following the approach of Wiegerinck et al. [3]. The agents satisfy dynamics with additive control and noise, and the joint behaviour of the agents is valued by a joint cost function that is quadratic in the control. The stochastic optimization problem may then be transformed into a linear partial differential equation, which can be solved using generic path integral methods [4,5]. The dynamics of the agents are assumed to factorize over the agents, such that the agents are coupled by their joint task only. The optimal control problem is equivalent to a graphical model inference problem [3]. In large and sparsely coupled mul
Data Loading...
