Point-Based POMDP Algorithms: Improved Analysis and Implementation
This work addresses computational bottlenecks in POMDP planning, offering incremental improvements for researchers and practitioners in robotics and AI.
The authors tackled the complexity analysis of point-based POMDP value iteration algorithms by deriving a new bound that combines dimensionality and history aspects, and they improved their heuristic search algorithm with tighter initial bounds and computational optimizations.
Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more effective use of sparsity.