Accelerating Point-Based POMDP Algorithms through Successive Approximations of the Optimal Reachable Space
No Thumbnail Available
Date
2007-04-29
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Point-based approximation algorithms have drastically im-proved the speed of POMDP planning. This paper presents a new point-based POMDP algorithm called SARSOP. Like earlier point-based algorithms, SARSOP performs value iter-ation at a set of sampled belief points; however, it focuses on sampling near the space reachable from an initial belief point under the optimal policy. Since neither the optimal policynor the optimal reachable space is known in advance, SARSOP builds successive approximations to it through sampling and pruning. In our experiments, the new algorithm solved dif-.cult POMDP problems with more than 10,000 states. Its running time is competitive with the fastest existing point-based algorithm on most problems andfasterby manytimes on some. Our approach is complementary to existing point-based algorithms and can be integrated with them to improve their performance.