2009 · 37 citations · 14 references
ComputingComputer ScienceAlgorithmsMarkov Decision ProcessesOptimizationDynamic ProgrammingHeuristic SearchPartially Observable Markov Decision ProcessesBackupDecentralized PomdpsFinite Horizon Dynamic ProgrammingFinite-horizon ApproximationIncremental ComputationPolicy Search For PomdpsPomdp SolversPruning
Recent scaling up of decentralized partially observable Markov decision process (DEC-POMDP) solvers towards realistic applications is mainly due to approximate methods. Of this family, Memory Bounded Dynamic Programming (MBDP), which combines in a suitable manner top-down heuristics and bottom-up value function updates, can solve DEC-POMDPs with large horizons. The performances of MBDP, can be, however, drastically improved by avoiding the systematic generation and evaluation of all possible policies which result from the exhaustive backup. To achieve that, we suggest a heuristic search method, namely Point Based Incremental Pruning (PBIP), which is able to distinguish policies with different heuristic estimates. Taking this insight into account, PBIP searches only among the most promising policies, finds those useful, and prunes dominated ones. Doing so permits us to reduce clearly the amount of computation required by the exhaustive backup. The computation experiment shows that PBIP solves DEC-POMDP benchmarks up to 800 times faster than the current best approximate algorithms, while providing solutions with higher values.
14
The Complexity of Decentralized Control of Markov Decision Processes
Daniel S. Bernstein, Robert Givan, Neil Immerman et al. · Mathematics of Operations Research · 2002 · 1.2K citations
Networked distributed POMDPs: a synthesis of distributed constraint optimization and POMDPs
Ranjit Nair, Pradeep Varakantham, Milind Tambe et al. · Institutional Knowledge (InK) - Institutional Knowledge at Singapore Management University (Singapore Management University) · 2005 · 212 citations · Full text