Publications

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

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

Matthijs T. J. Spaan, Frans A. Oliehoek, and Christopher Amato. Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion. In Multi-agent Sequential Decision Making in Uncertain Domains, 2011. Workshop at AAMAS11

Download

pdf [229.0kB]  

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 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 speedup over the state of the art, allowing for optimal solutions 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-POMDPs}
                  via Incremental Expansion},
  booktitle =    {Multi-agent Sequential Decision Making in Uncertain
                  Domains},
  year =         2011,
  note =         {Workshop at AAMAS11}
}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by bib2html.pl (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC