Point-based incremental pruning heuristic for solving finite-horizon DEC-POMDPs
By Jilles Steeve Dibangoye, Abdel-Illah Mouaddib, Brahim Chaib-draa. 2009
46 citations recorded by the source corpus.
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.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Frans Adriaan Oliehoek
- Matthijs T. J. Spaan
- Feng Wu
- Xiaoping Chen
- Chris Amato
- Shimon Whiteson
- Francisco S. Melo
- Bikramjit Banerjee
Citations in the corpus
- Multi-agent reinforcement learning as a rehearsal for decentralized planning (2016, neutral): “[24,1,10]); however, most of these approaches are centralized and assume the model is known a priori.”
- Rollout Sampling Policy Iteration for Decentralized POMDPs (2010, methodology): “These methods keep only a fixed number of trees at each iteration [1, 8, 17, 18].”
- Decentralized POMDPs (2012, methodology): “To reduce the burden of this complexity, many papers have proposed new methods for performing this point-based backup operation (Seuken and Zilberstein, 2007a; Carlin and Zilberstein, 2008; Dibangoye et al, 2009; Amato et al, 2009; Wu et al, 2010a).”
- Heuristic search for identical payoff Bayesian games (2010, methodology): “Since the number of sub-tree policies that are non-dominated tends to be very large, point-based DP (PBDP) methods [10, 8, 3] have been introduced.”