|
Organization responsible: SNN Adaptive Intelligence People involved: Project description: This project aims to investigate decision making in graphical network models representing distributed multi-agent systems, which should lead to new means to deal with collaborative reasoning in dynamic large-scale agent organizations.
Real world decision making often involves making decisions in a complex, partially observable dynamic environment with multiple agents (team players as well as opponents) that can influence the environment by their actions. If an agent is to take an optimal action, it must have an idea of the state of its environment, if the decisions by other actors and it needs to be able to oversee the consequences of its actions, in conjunction with the dynamics of the environment, the current and future behaviour of other agents in the system, and its own possibilities to take future actions. For any realistic system, a naïve approach of even the description of optimal decision making will be infeasible, since the number of states and the number of possible actions in different situations will grow exponentially in the system size and will be impossible to enumerate.
Recently, we developed a new approach for computing the optimal control policy in stochastic control problems. The usual approach is to make a discretization of space and time, but in high dimensions this makes the computation intractable both in memory requirement and CPU time. In the new approach we considers control problems that are typically described by a stochastic differential equation that is linear in the control, and a cost function that is quadratic in the control. Such problems can be solved using the theory of stochastic integration or path integrals. Since path integrals appear in other branches of physics, such as statistical physics and quantum mechanics, one can borrow approximation methods from those fields to compute the optimal control approximately. Among these approximation methods are the Laplace approximation and Monte Carlo sampling. Since the above method of tackling stochastic optimal control problems works in higher dimensions, we can use it to solve similar problems stated in a multi-agent setting. A typical example of the problems that we study is one in which a number of agents have to distribute themselves over a number of targets (fire fighters extinguishing fires). In contrast with the single-agent case, the agents are now also facing a distributed decision making problem, because usually it matters for one agent where the other agents go. If a fire fighter goes to extinguish one small fire, then it may be better for the other fire fighters to extinguish other fires. For the computation of the optimal joint policy, it means that a combinatorial problem has to be solved: given the locations of the agents and the targets, find the best distribution of the agents over the targets. When the number of agents and targets is large, this problem becomes intractable, and we resort to approximation methods. The main research questions are as follows: - The research goal is to study and further develop decision making in large scale multi-agent systems represented as graphical models. The systems that we will consider will range from systems with collaborative agents in a static domain to dynamic systems, with fully or partially observable worlds.
- A computationally very demanding inference problem, is the problem of optimal control under uncertainty. The problem requires the computation of 'what to do now' in order to reach a certain goal in expectation. Such computation has similarity with inference computations and the objective is to further develop inference methods for optimal control tasks.
Publications:
|
