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 (38)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Value-Function Approximations for Partially Observable Markov Decision Processes
• Online Planning Algorithms for POMDPs
• A Survey of Multi-Objective Sequential Decision-Making
• Anytime Point-Based Approximations for Large POMDPs
• Perseus: Randomized Point-based Value Iteration for POMDPs
• 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
• Policy Iteration for Decentralized Control of Markov Decision Processes
• Policy-contingent abstraction for robust robot control
• Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
• Optimal Limited Contingency Planning
• Value-Directed Belief State Approximation for POMDPs
• Approximate information state for approximate planning and reinforcement learning in partially observed systems
• 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
• Optimizing Sequential Medical Treatments with Auto-Encoding Heuristic Search in POMDPs
• Pilot Beam Sequence Design for Channel Estimation in Millimeter-Wave MIMO Systems: A POMDP Framework
• My Brain is Full: When More Memory Helps
• Observation Subset Selection as Local Compilation of Performance Profiles
• Sparse tree search optimality guarantees in POMDPs with continuous observation spaces
• Valuating Surface Surveillance Technology for Collaborative Multiple-Spot Control of Airport Departure Operations
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach
• Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
• Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: a Rule-Based Approach
• On Polynomial Sized MDP Succinct Policies
• Reconciling Rewards with Predictive State Representations
• Training Beam Sequence Design for Millimeter-Wave MIMO Systems: A POMDP Framework
• Partially Observed, Multi-objective Markov Games
• Dynamic Programming for Structured Continuous Markov Decision Problems
• On Anderson acceleration for partially observable Markov decision processes
• Environmental benefits of enhanced surveillance technology on airport departure operations
• Approximation Methods for Partially Observed Markov Decision Processes (POMDPs)