Abstract:

Decentralized control of a cooperative system is the problem faced by a
group of decision makers who share a single global objective function.
Examples of such systems include multiple-rovers missions, flexible 
manufacturing, collaborative robots systems, distributed systems. The
difficulty in solving optimally such problems arises when the agents 
lack full observability of the global state of the system at execution
time. In my talk, I will identify classes of decentralized control
problems whose complexity ranges between NEXP (known for the general problem) 
and P. No algorithms were known so far short of full search of the policy
space. I will introduce the first algorithms that solve optimally
certain classes of problems, where transitions and observations are independent
and the system behavior may be goal-oriented.
 
The second part of the talk will focus on information sharing among the
decision-makers, which can improve their performance. Agents can
exchange information in three different ways: indirect communication, direct 
communication and sharing common features that are uncontrollable by the
agents. The decentralized control problem is then to optimize over
actions and communication. The decision makers trade-off the cost of
communication with the value of the information acquired computing when it is
beneficial to communicate and what information they should exchange. 

Finally, I will present a general approximation scheme based on
mechanism design to solve decentralized control problems with direct
communication. Empirical results will be shown for two polynomial
algorithms tested: myopic-greedy and backward induction. These results
offer one of the first practical approaches to address the complexity of
decentralized control with communication.