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 [2.2MB]  

Abstract

This article presents the state-of-the-art in optimal solution methodsfor decentralized partially observable Markov decision processes(Dec-POMDPs), which are general models for collaborative multiagentplanning under uncertainty. Building off the generalized multiagent A*(GMAA*) algorithm, which reduces the problem to a tree of one-shotcollaborative Bayesian games (CBGs), we describe several advances thatgreatly expand the range of Dec-POMDPs that can be solved optimally.First, we introduce lossless incremental clustering of the CBGs solvedby GMAA*, which achieves exponential speedups without sacrificingoptimality. Second, we introduce incremental expansion of nodes inthe GMAA* search tree, which avoids the need to expand all children,the number of which is in the worst case doubly exponential in thenode's depth. This is particularly beneficial when little clusteringis possible. In addition, we introduce new hybrid heuristicrepresentations that are more compact and thereby enable the solutionof larger Dec-POMDPs. We provide theoretical guarantees that, when asuitable heuristic is used, both incremental clustering andincremental expansion yield algorithms that are both complete andsearch equivalent. Finally, we present extensive empirical resultsdemonstrating that GMAA*-ICE, an algorithm that synthesizes theseadvances, 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,
    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 Wed Nov 06, 2013 16:37:07 UTC