Bounded Dynamic Programming for Decentralized POMDPs
Christopher Amato
Alan Carlin
Shlomo Zilberstein
Abstract
Solving decentralized POMDPs (DEC-POMDPs) optimally
is a very hard problem. As a result, several approximate algorithms
have been developed, but these do not have satisfactory
error bounds. In this paper, we first discuss optimal
dynamic programming and some approximate finite horizon
DEC-POMDP algorithms. We then present a bounded
dynamic programming algorithm. Given a problem and an
error bound, the algorithm will return a solution within that
bound when it is able to solve the problem. We give a proof
of this bound and provide some experimental results showing
high quality solutions to large DEC-POMDPs for large
horizons.
Download
[pdf]