Incremental Clustering and Expansion for Faster Optimal Planning in Decentralized POMDPs

This article presents the state-of-the-art in optimal solu tion methods for decentralized partially observable Markov decision processes (Dec-POMD Ps) , which are general models for collaborative multiagent planning under uncertainty. Bui lding off the generalized multia- gent 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 los sless 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 numbe r of which is in the worst case doubly exponential in the node’s depth. This is particularl y 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-POMDP s. We provide theoretical guarantees that, when a suitable heuristic is used, both inc remental clustering and incre- mental expansion yield algorithms that are both complete an d search equivalent . Finally, we present extensive empirical results demonstrating that GMAA*-ICE , an algorithm that synthesizes these advances, can optimally solve Dec-POMDP s of unprecedented size.