Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion

Spaan, Matthijs T. J.; Oliehoek, Frans A.; Amato, Christopher

doi:10.5591/978-1-57735-516-8/IJCAI11-338

Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion

Matthijs T. J. Spaan, Frans A. Oliehoek, Christopher Amato

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2027-2031.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-338

Abstract

Planning under uncertainty for multiagent systems can be formalized as a decentralized partially observable Markov decision process. We advance the state of the art for optimal solution of this model, building on the Multiagent A* heuristic search method. A key insight is that we can avoid the full expansion of a search node that generates a number of children that is doubly exponential in the node's depth. Instead, we incrementally expand the children only when a next child might have the highest heuristic value. We target a subsequent bottleneck by introducing a more memory-efficient representation for our heuristic functions. Proof is given that the resulting algorithm is correct and experiments demonstrate a significant speedup over the state of the art, allowing for optimal solutions over longer horizons for many benchmark problems.

Matthijs T. J. Spaan, Frans A. Oliehoek, and Christopher Amato. 2011. Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2027–2031. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-338

@inproceedings{ijcai2011p338,
  title     = {Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion},
  author    = {Spaan, Matthijs T. J. and Oliehoek, Frans A. and Amato, Christopher},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2027--2031},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-338},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-338},
}

TY  - CPAPER
TI  - Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion
AU  - Spaan, Matthijs T. J.
AU  - Oliehoek, Frans A.
AU  - Amato, Christopher
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2027
EP  - 2031
DO  - 10.5591/978-1-57735-516-8/IJCAI11-338
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-338
ER  -