Skip to Main content Skip to Navigation
Reports

Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms

Jilles Steeve Dibangoye 1 Christopher Amato 2 Olivier Buffet 1 François Charpillet 1
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) provide a general model for decision-making under uncertainty in cooperative decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be distributed. This new Dec-POMDP formulation, which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. When the curse of dimensionality becomes too prohibitive, we refine this basic approach and present ways to combine heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to eventually converge to an optimal solution. In particular, we introduce feature-based heuristic search that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that our feature-based heuristic search algorithms terminate in finite time with an optimal solution. We include an extensive empirical analysis using well known benchmarks, thereby demonstrating our approach provides significant scalability improvements compared to the state of the art.
Document type :
Reports
Complete list of metadata

Cited literature [67 references]  Display  Hide  Download

https://hal.inria.fr/hal-00975802
Contributor : Olivier Buffet <>
Submitted on : Wednesday, April 9, 2014 - 11:38:06 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on: : Wednesday, July 9, 2014 - 11:50:54 AM

File

RR-8517.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00975802, version 1

Citation

Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, François Charpillet. Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms. [Research Report] RR-8517, INRIA. 2014, pp.77. ⟨hal-00975802⟩

Share

Metrics

Record views

497

Files downloads

562