Distributed Byesian Decision-Making for Adaptive Solution of Complex Problems

Motivation

Bayesian decision-making theory is well known as theoretical base for design of decision strategies in centralized decision making under uncertainty. However, centralized approach becomes impractical when dealing with complex systems. In such cases, decentralized approach is needed as demonstrated by success of distributed control in control theory and multi-agent systems in computer science. Formal theories of feasible distributed decision making under uncertainty are still incomplete. Therefore, ad-hoc and heuristic solutions are preferred in practical implementations.
The principal aim of this project is to develop and verify methodology of distributed decision-making that is based on formal Bayesian decision-making theory but yields computationally feasible algorithms.

Background work

The basic framework should represent one decision-making unit an autonomous Bayesian decision-maker which has its own aims, model of its environment, and ability to communicate with only a limited amount of its neighbours.
Its strategy is selected as minimizer of Kullback-Leibler divergence from the joint distribution  describing behaviour of the closed loop (i.e. model and decision strategy) to the desired behaviour. Thus, models, estimates, decision aims, and constaraints are expressed within a unified probabilistic language. Under this assumption, the tasks of information fusion, negotiation and cooperation can be formalized using probability calculus. Furthermore, these operations can be interpreted as optimization problems, many of which can be effectively solved.

Potential Impact
The impact can be safely extrapolated from successes of heuristically constructed or naturally arising distributed
decision-making systems. Formalized background should provide higher achievable quality, reliability and extensive re-usability.
It allows us to construct adaptive, efficient, problem tailored, intelligent and cooperating agents. Adaptivity of the Bayesian
decision maker is a natural consequence of Bayesian learning in uncertain environment. It acts independently of other decision
makers and uses relatively simple models as well as strategies as it learns recursively and optimizes its DM strategy on-line. In
this way, it tries to achieve his own aims. Cooperation with neighbours based on knowledge sharing and negotiation about aims
becomes a specific problem of Bayesian decision-making.

Note that the cooperation addresses the problems inspected in multi-agent systems (MAS). This overlap promises benefits both to
MAS and the Bayesian distributed decision-making being developed.

Aims of the project:

• theoretical: elaboration of the basic idea into a systematic design methodology and inspect theoretical properties of the
               proposed scheme.
  
• implementation: development of an open-source software toolbox for Bayesian decision-making,that at least facilitates experimental testing of the proposed methodology,
  

• application: testing of potential benefits of the theory and algorithms in particular application domain.

In the theoretical part, we expect to address the following problems. First, theoretical properties such as optimality of the proposed approach needs to be investigated. Second, the required operations of probability calculus are defined as optimization problems, analytical solution of which is available only for a limited class of models. Approximate solutions for more advanced models, such as probabilistic mixtures, Bayesian networks or graphical models in general needs to be developed. Third, the proposed probabilistic representation of the decision-making aims lacks clear statement of conditions under which is to be used. Fourth, the proposed methodology may have close relation to some already available algorithms. This relation should be revealed and understood.

In the implementation part, we intend to develop an open-sourced, cross-platform toolbox (and library) containing all the necessary functions and algorithms implied by the theory. Integration of library into existing environments (such as Java Agent Development Environment) will be investigated and implemented where suitable.

In the application part, we will inspect practical problems in which distributed decision-making under uncertainty is worth considering. At this stage of research, undesirable global behaviors of the proposed framework may occur. Therefore, we seek domain specific testing environments.
One such problem that has been investigated is decentralized control of traffic lights in urban areas. Multi-agent approach to this problem allows for scalability and flexibility of the solution, however, it must address problems with uncertainty that is intrinsic to the system. Another possible applications include navigation of mobile robots, sensor-less control of motion vehicles, and many others.

Bayesian theory
Multi-agent systems
decision-making theory
decentralized control
adaptive learning
approximate dynamic programming

The team should be build to cover the area of Bayesian theory, decision making theory, optimization theory, artificial intelligence, multi-agent systems, and computer networks. One possible composition of the groups follows:

We seek:

Theoretical groups, experienced with some form of distributed control and decision-making, such as multi-agent control systems, distributed control, distributed artificial intelligence, etc.

Practically-oriented group, experienced with application domain where distributed decision-making under uncertainty naturally arise.

The project is based on extensive collaboration.

We expect to distribute theoretical and implementation task between groups.

Theoretical groups will share the following tasks:
1) Integration of Bayesian and Multi-agent paradigms.
2) Development of algorithms for particular model classes,
3) Contribution of code to the open-source toolbox.

Application to a practical problem (or realistic simulator) will be based on testing of integration of the developed toolbox with current technology.

Since the problem is mostly theoretical, most of the partners should have academical background.

The application partner can be either academical or industrial company with a clear idea how the proposed approach can contribute to solution in the application domain.

Yes