SPUDD: Stochastic Planning using Decision Diagrams

Abstract

Markov decisions processes (MDPs) are becoming increasing popular as models of decision theoretic planning. While traditional dynamic programming methods perform well for problems with small state spaces, structured methods are needed for large problems. We propose and examine a value iteration algorithm for MDPs that uses algebraic decision diagrams(ADDs) to represent value functions and policies. An MDP is represented using Bayesian networks and ADDs and dynamic programming is applied directly to these ADDs. We demonstrate our method on large MDPs (up to 63 million states) and show that significant gains can be had when compared to tree-structured representations (with up to a thirty-fold reduction in the number of nodes required to represent optimal value functions).

Appears in Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI1999)

References in corpus (5)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Context-Specific Independence in Bayesian Networks
• Topological Parameters for Time-Space Tradeoff
• Correlated Action Effects in Decision Theoretic Regression
• Exploiting the Rule Structure for Decision Making within the Independent Choice Logic

Cited by in corpus (30)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Efficient Solution Algorithms for Factored MDPs
• Decision-Theoretic Planning with non-Markovian Rewards
• Symbolic Generalization for On-line Planning
• Symbolic Dynamic Programming for Discrete and Continuous State MDPs
• FluCaP: A Heuristic Search Planner for First-Order MDPs
• SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes
• Value-Directed Belief State Approximation for POMDPs
• First Order Decision Diagrams for Relational MDPs
• dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts
• A Heuristic Search Algorithm for Solving First-Order MDPs
• Anytime State-Based Solution Methods for Decision Processes with non-Markovian Rewards
• Relational Approach to Knowledge Engineering for POMDP-based Assistance Systems as a Translation of a Psychological Model
• Chi-square Tests Driven Method for Learning the Structure of Factored MDPs
• Approximate Linear Programming for First-order MDPs
• A Sufficient Statistic for Influence in Structured Multiagent Environments
• Implementation and Comparison of Solution Methods for Decision Processes with Non-Markovian Rewards
• Probabilistic Relational Planning with First Order Decision Diagrams
• Proximity-Based Non-uniform Abstractions for Approximate Planning
• Active Deception using Factored Interactive POMDPs to Recognize Cyber Attacker's Intent
• CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPs
• Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
• ADD-Lib: Decision Diagrams in Practice
• Counterexample-guided Planning
• Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs (Extended Version)
• Compiling Stochastic Constraint Programs to And-Or Decision Diagrams
• Learning Efficient Representations for Reinforcement Learning
• Dynamic Programming for Structured Continuous Markov Decision Problems
• Solving Relational MDPs with Exogenous Events and Additive Rewards
• Stochastic Planning and Lifted Inference