Constraint-Based Dynamic Programming for Decentralized POMDPs with Structured Interactions
Conference Proceeding Article
Decentralized partially observable MDPs (DEC-POMDPs) provide a rich framework for modeling decision making by a team of agents. Despite rapid progress in this area, the limited scalability of solution techniques has restricted the applicability of the model. To overcome this computational barrier, research has focused on restricted classes of DEC-POMDPs, which are easier to solve yet rich enough to capture many practical problems. We present CBDP, an efficient and scalable point-based dynamic programming algorithm for one such model called ND-POMDP (Network Distributed POMDP). Specifically, CBDP provides magnitudes of speedup in the policy computation and generates better quality solution for all test instances. It has linear complexity in the number of agents and horizon length. Furthermore, the complexity per horizon for the examined class of problems is exponential only in a small parameter that depends upon the interaction among the agents, achieving significant scalability for large, loosely coupled multi-agent systems. The efficiency of CBDP lies in exploiting the structure of interactions using constraint networks. These results extend significantly the effectiveness of decision-theoretic planning in multi-agent settings.
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
Proceedings of the 8th International Conference on Autonomous Agents and Multimagent Systems: May 10-15, 2009, Budapest, Hungary
International Foundation for Autonomous Agent and Multiagent Systems
City or Country
KUMAR, Akshat and Zilberstein, Shlomo.
Constraint-Based Dynamic Programming for Decentralized POMDPs with Structured Interactions. (2009). Proceedings of the 8th International Conference on Autonomous Agents and Multimagent Systems: May 10-15, 2009, Budapest, Hungary. 561-568. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2212