Paper Info
Title
Parallel Rollout for Online Solution of Dec-POMDPs
Abstract
A major research challenge is presented by scalability of al- gorithms 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 ap- proximation 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 in- stances 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 algo- rithm called memory bounded dynamic programming. Ex- perimental 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.
Year
Venue
Keywords
2008
the florida ai research society
online algorithm,dynamic programming algorithm
Field
DocType
Citations 
Dynamic programming,Online algorithm,Mathematical optimization,Computer science,Artificial intelligence,Finite horizon,Double exponential function,Machine learning,Bounded function,Scalability
Conference
5
PageRank 
References 
Authors
0.51
12
2
Name
Order
Citations
PageRank
Camille Besse1111.45
Chaib-draa, Brahim21190113.23