Scaling Up Decentralized MDPs Through Heuristic Search

Jilles Steeve Dibangoye 1, * Amato Christopher 2 Doniec Arnaud 3
* Corresponding author
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-00765221
Contributor : Jilles Steeve Dibangoye <>
Submitted on : Friday, December 14, 2012 - 12:20:04 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM

Identifiers

  • HAL Id : hal-00765221, version 1

Citation

Jilles Steeve Dibangoye, Amato Christopher, Doniec Arnaud. Scaling Up Decentralized MDPs Through Heuristic Search. Conference on Uncertainty in Artificial Intelligence, Aug 2012, Catalina, United States. ⟨hal-00765221⟩

Share

Metrics

Record views

208