Publications

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

Incremental Clustering and Expansion for Faster Optimal Planning in Decentralized POMDPs

Frans A. Oliehoek, Matthijs T. J. Spaan, Christopher Amato, and Shimon Whiteson. Incremental Clustering and Expansion for Faster Optimal Planning in Decentralized POMDPs. Journal of Artificial Intelligence Research, 46:449–509, 2013.

Download

pdf [7.2MB]  ps.gz ps [2.2MB]  HTML 

Abstract

This article presents the state-of-the-art in optimal solution methods for decentralized partially observable Markov decision processes (Dec-POMDPs), which are general models for collaborative multiagent planning under uncertainty. Building off the generalized multiagent A* (GMAA*) algorithm, which reduces the problem to a tree of one-shot collaborative Bayesian games (CBGs), we describe several advances that greatly expand the range of Dec-POMDPs that can be solved optimally. First, we introduce lossless incremental clustering of the CBGs solved by GMAA*, which achieves exponential speedups without sacrificing optimality. Second, we introduce incremental expansion of nodes in the GMAA* search tree, which avoids the need to expand all children, the number of which is in the worst case doubly exponential in the node's depth. This is particularly beneficial when little clustering is possible. In addition, we introduce new hybrid heuristic representations that are more compact and thereby enable the solution of larger Dec-POMDPs. We provide theoretical guarantees that, when a suitable heuristic is used, both incremental clustering and incremental expansion yield algorithms that are both complete and search equivalent. Finally, we present extensive empirical results demonstrating that GMAA*-ICE, an algorithm that synthesizes these advances, can optimally solve Dec-POMDPs of unprecedented size.

BibTeX Entry

@article{Oliehoek13JAIR,
    author =    {Frans A. Oliehoek and 
                 Matthijs T. J. Spaan and 
                 Christopher Amato and 
                 Shimon Whiteson},
    title =     {Incremental Clustering and Expansion for Faster 
                 Optimal Planning in Decentralized {POMDPs}},
    journal =   JAIR,
    volume =    {46},
    pages =     {449--509},
    year =      2013,
    url =       {https://doi.org/10.1613/jair.3804},
    doi =       {10.1613/jair.3804},
    abstract = {
    This article presents the state-of-the-art in optimal solution methods
    for decentralized partially observable Markov decision processes
    (Dec-POMDPs), which are general models for collaborative multiagent
    planning under uncertainty. Building off the generalized multiagent A*
    (GMAA*) algorithm, which reduces the problem to a tree of one-shot
    collaborative Bayesian games (CBGs), we describe several advances that
    greatly expand the range of Dec-POMDPs that can be solved optimally.
    First, we introduce lossless incremental clustering of the CBGs solved
    by GMAA*, which achieves exponential speedups without sacrificing
    optimality.  Second, we introduce incremental expansion of nodes in
    the GMAA* search tree, which avoids the need to expand all children,
    the number of which is in the worst case doubly exponential in the
    node's depth.  This is particularly beneficial when little clustering
    is possible.  In addition, we introduce new hybrid heuristic
    representations that are more compact and thereby enable the solution
    of larger Dec-POMDPs.  We provide theoretical guarantees that, when a
    suitable heuristic is used, both incremental clustering and
    incremental expansion yield algorithms that are both complete and
    search equivalent.  Finally, we present extensive empirical results
    demonstrating that GMAA*-ICE, an algorithm that synthesizes these
    advances, can optimally solve Dec-POMDPs of unprecedented size.
    }
}

Generated by bib2html.pl (written by Patrick Riley) on Tue Nov 05, 2024 16:13:37 UTC