Parallel Rollout for Online Solution of dec-Pomdps

摘要

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.