Conference Proceeding Article
The Decentralized Partially Observable Markov Decision Process (Dec-POMDP) is a powerful model for multi-agent planning under uncertainty, but its applicability is hindered by its high complexity – solving Dec-POMDPs optimally is NEXP-hard. Recently, Kumar et al. introduced the Value Factorization (VF) framework, which exploits decomposable value functions that can be factored into subfunctions. This framework has been shown to be a generalization of several specialized models such as TI-Dec-MDPs, ND-POMDPs and TD-POMDPs, which leverage different forms of sparse agent interactions to improve the scalability of planning. Existing algorithms for these models assume that the interaction graph of the problem is given. So far, no studies have addressed the generation of interaction graphs. In this paper, we address this gap by introducing three algorithms to automatically generate interaction graphs for models within the VF framework and establish lower and upper bounds on the expected reward of an optimal joint policy. We illustrate experimentally the bene- fits of these techniques for sensor placement in a decentralized tracking application.
Artificial Intelligence and Robotics | Computer Sciences
Intelligent Systems and Decision Analytics
IJCAI '13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence
City or Country
YEOH, William; KUMAR, Akshat; and Zilberstein, Shlomo.
Automated Generation of Interaction Graphs for Value-Factored Decentralized POMDPs. (2013). IJCAI '13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. 411-417. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2200
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.