Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion (bibtex)
by Matthijs T. J. Spaan, Frans A. Oliehoek and Christopher Amato
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 in its optimal solution, 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 doubly exponential in the node's depth. Instead we incrementally expand the children of a node only when a next child might have the highest heuristic value. We target a subsequent bottleneck by introducing a more memory-efficient representation fo our heuristic functions. Proof is given that the resulting algorithm is correct and experiments demonstrate a significant speed up over the state of the art allowing for the optimal solution over longer horizons for many benchmark problems.
Reference:
Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion (Matthijs T. J. Spaan, Frans A. Oliehoek and Christopher Amato), In Proceedings of the International Joint Conference on Artificial Intelligence, 2011.
Bibtex Entry:
@InProceedings{Spaan11IJCAI,
 author = {Matthijs T. J. Spaan and Frans A. Oliehoek and Christopher Amato},
 title = {Scaling Up Optimal Heuristic Search in {Dec-POMDP}s via Incremental Expansion},
 booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence},
 year = {2011},
 pages = {2027--2032},
keywords={Multiagent, MDP},
 bib2html_rescat = {Multiagent systems - Decentralized POMDPs},
 bib2html_pubtype = {Refereed Conference (International)},
 note={A version appeared in AAMAS Workshop on Multi-agent Sequential Decision Making in Uncertain Domains and as extended abstract in Proc. of 23rd Benelux Conference on Artificial Intelligence},
 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 in its optimal solution, 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 doubly exponential in the node's depth. Instead we
 incrementally expand the children of a node only when a next child
 might have the highest heuristic value. We target a subsequent
 bottleneck by introducing a more memory-efficient representation fo
 our heuristic functions. Proof is given that the resulting algorithm
 is correct and experiments demonstrate a significant speed up over the
 state of the art allowing for the optimal solution over longer horizons
 for many benchmark problems.
 },
url={http://people.csail.mit.edu/fao/docs/Spaan11IJCAI.pdf}
}
Powered by bibtexbrowser