Parallel Rollout for Online Solution of dec-Pomdps

Camille Besse, Brahim Chaib-draa

A major research challenge is presented by scalability of algorithms for solving decentralized POMDPs because of their double exponential worst-case complexity for finite horizon problems. First algorithms have only been able to solve very small instances on very small horizons. One exception is the Memory-Bounded Dynamic Programming algorithm—an approximation technique that has proved efficient in handling same sized problems but on large horizons. In this paper, we propose an online algorithm that also approximates larger instances of finite horizon DEC-POMDPs based on the Rollout algorithm. To evaluate the effectiveness of this approach, we compare the presented approach to a recently proposed algorithm called memory bounded dynamic programming. Experimental results show that despite the very high complexity of DEC-POMDPs, the combination of Rollout techniques and estimation techniques performs well and leads to a significant improvement of existing approximation techniques.

Subjects: 7.1 Multi-Agent Systems; 1.11 Planning

Submitted: Feb 13, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.