Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes

Abstract

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.

Appears in Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI1997)

Cited by in corpus (17)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Value-Function Approximations for Partially Observable Markov Decision Processes
• The Complexity of Decentralized Control of Markov Decision Processes
• Solving POMDPs by Searching in Policy Space
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
• Point-Based POMDP Algorithms: Improved Analysis and Implementation
• Optimal Limited Contingency Planning
• Value-Directed Belief State Approximation for POMDPs
• Vector-space Analysis of Belief-state Approximation for POMDPs
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes
• Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method
• Restricted Value Iteration: Theory and Algorithms
• My Brain is Full: When More Memory Helps
• Observation Subset Selection as Local Compilation of Performance Profiles
• On Polynomial Sized MDP Succinct Policies
• Dynamic Programming for Structured Continuous Markov Decision Problems