Publications• Sorted by Date • Classified by Publication Type • Classified by Research Category • Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental ExpansionMatthijs T. J. Spaan, Frans A. Oliehoek, and Christopher Amato. Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion. In Proceedings of the Sixth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), pp. 63–70, 2011. DownloadAbstractPlanning 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 for 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. BibTeX Entry@InProceedings{Spaan11MSDM, 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 = MSDM11, year = {2011}, pages = {63--70}, keywords = {workshop}, 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 for 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. } }
Generated by
bib2html.pl
(written by Patrick Riley) on
Mon Oct 07, 2024 14:17:04 UTC |