Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
This work addresses the computational challenge of exact POMDP solving, which is incremental as it builds on existing dynamic programming approaches.
The paper tackled the problem of solving partially observable Markov decision processes (POMDPs) by examining variations of the incremental pruning method, finding it to be the most efficient exact method currently available.
Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of one value function is transformed into another. We examine variations of the "incremental pruning" method for solving this problem and compare them to earlier algorithms from theoretical and empirical perspectives. We find that incremental pruning is presently the most efficient exact method for solving POMDPs.