Automated Generation of Interaction Graphs for Value-Factored Decentralized POMDPs

• Main Authors: YEOH, William, KUMAR, Akshat, Zilberstein, Shlomo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2013
• Subjects: Artificial Intelligence and Robotics; Computer Sciences
• Online Access: https://ink.library.smu.edu.sg/sis_research/2200; https://ink.library.smu.edu.sg/context/sis_research/article/3200/viewcontent/Automated_Generation_of_Interaction_Graphs_for_Value_Factored.pdf
• Institution: Singapore Management University

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.