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 Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), pp. 2027–2032, 2011.

Download

pdf [130.3kB]  ps.gz ps HTML 

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{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 =    IJCAI11,
    year =         {2011},
    pages =        {2027--2032},
    url =          {https://www.ijcai.org/Proceedings/11/Papers/338.pdf},
    doi =          {10.5591/978-1-57735-516-8/IJCAI11-338},
    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 Tue Nov 05, 2024 16:13:37 UTC