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 Proceedings of the Sixth AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), pp. 63–70, 2011.

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 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 =     msdsm2011,
    year =          {2011},
    pages =         {63--70}, 
    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 Wed Nov 06, 2013 16:37:07 UTC