Decentralized Control of Cooperative Systems.
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.