Scaling up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion
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.
Cite
Text
Spaan et al. "Scaling up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-338Markdown
[Spaan et al. "Scaling up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/spaan2011ijcai-scaling/) doi:10.5591/978-1-57735-516-8/IJCAI11-338BibTeX
@inproceedings{spaan2011ijcai-scaling,
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 = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {2027-2032},
doi = {10.5591/978-1-57735-516-8/IJCAI11-338},
url = {https://mlanthology.org/ijcai/2011/spaan2011ijcai-scaling/}
}