Decision-Theoretic Planning: Structural Assumptions and Computational Leverage

Abstract

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.

References in corpus (11)

• Context-Specific Independence in Bayesian Networks
• SPUDD: Stochastic Planning using Decision Diagrams
• On the Complexity of Solving Markov Decision Problems
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Hierarchical Solution of Markov Decision Processes using Macro-actions
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
• Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems
• Structured Reachability Analysis for Markov Decision Processes
• Context-Specific Approximation in Probabilistic Inference
• Correlated Action Effects in Decision Theoretic Regression
• Exploiting the Rule Structure for Decision Making within the Independent Choice Logic

Cited by in corpus (97)

• Value-Function Approximations for Partially Observable Markov Decision Processes
• A Survey of Multi-Objective Sequential Decision-Making
• SPUDD: Stochastic Planning using Decision Diagrams
• The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
• Anytime Point-Based Approximations for Large POMDPs
• Optimal and Approximate Q-value Functions for Decentralized POMDPs
• Learning Finite-State Controllers for Partially Observable Environments
• Accelerating Reinforcement Learning through Implicit Imitation
• Efficient Solution Algorithms for Factored MDPs
• Solving POMDPs by Searching the Space of Finite Policies
• Game-Theoretic Multiagent Reinforcement Learning
• Planning under Continuous Time and Resource Uncertainty: A Challenge for AI
• Nonapproximability Results for Partially Observable Markov Decision Processes
• Affect Control Processes: Intelligent Affective Interaction using a Partially Observable Markov Decision Process
• Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations
• Monte Carlo Sampling Methods for Approximating Interactive POMDPs
• Decision-Theoretic Planning with non-Markovian Rewards
• Inductive Policy Selection for First-Order MDPs
• Regret-based Reward Elicitation for Markov Decision Processes
• Environment-Independent Task Specifications via GLTL
• Distributed Planning in Hierarchical Factored MDPs
• Metrics for Finite Markov Decision Processes
• A Framework for Sequential Planning in Multi-Agent Settings
• Metrics for Markov Decision Processes with Infinite State Spaces
• The Two Kinds of Free Energy and the Bayesian Revolution
• Neural Predictive Belief Representations
• Symbolic Dynamic Programming for Discrete and Continuous State MDPs
• Planning with Noisy Probabilistic Relational Rules
• Representation Policy Iteration
• Practical Linear Value-approximation Techniques for First-order MDPs
• FluCaP: A Heuristic Search Planner for First-Order MDPs
• SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes
• Continuous Value Function Approximation for Sequential Bidding Policies
• Value-Directed Belief State Approximation for POMDPs
• First Order Decision Diagrams for Relational MDPs
• Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
• A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains
• Reinforcement Learning for Agents with Many Sensors and Actuators Acting in Categorizable Environments
• Probabilistic Hybrid Action Models for Predicting Concurrent Percept-driven Robot Behavior
• Methods for computing state similarity in Markov Decision Processes
• A Heuristic Search Algorithm for Solving First-Order MDPs
• Engineering a Conformant Probabilistic Planner
• An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities
• Anytime State-Based Solution Methods for Decision Processes with non-Markovian Rewards
• Building a Stochastic Dynamic Model of Application Use
• On-line Planning and Scheduling: An Application to Controlling Modular Printers
• Vector-space Analysis of Belief-state Approximation for POMDPs
• A Sufficient Statistic for Influence in Structured Multiagent Environments
• Approximate Linear Programming for First-order MDPs
• Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs
• Monte-Carlo optimizations for resource allocation problems in stochastic network systems
• Learning Compact Models for Planning with Exogenous Processes
• Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks
• AGI Agent Safety by Iteratively Improving the Utility Function
• Planning and Acting under Uncertainty: A New Model for Spoken Dialogue Systems
• Probabilistic Relational Planning with First Order Decision Diagrams
• A Model-Based, Decision-Theoretic Perspective on Automated Cyber Response
• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Decision Making under Uncertainty: A Quasimetric Approach
• A Clustering Approach to Solving Large Stochastic Matching Problems
• Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
• A Solution to Time-Varying Markov Decision Processes
• Kernel-based diffusion approximated Markov decision processes for autonomous navigation and control on unstructured terrains
• Loss Bounds for Approximate Influence-Based Abstraction
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning
• Influence-Augmented Online Planning for Complex Environments
• iCORPP: Interleaved Commonsense Reasoning and Probabilistic Planning on Robots
• Influence-aware Memory Architectures for Deep Reinforcement Learning
• Open Problems in Universal Induction & Intelligence
• Reinforcement Learning with Feedback Graphs
• Counterexample Explanation by Learning Small Strategies in Markov Decision Processes
• Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
• On Polynomial Sized MDP Succinct Policies
• CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPs
• Probabilistic Planning by Probabilistic Programming
• Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs (Extended Version)
• Multi-Agent Decentralized Belief Propagation on Graphs
• State-Continuity Approximation of Markov Decision Processes via Finite Element Methods for Autonomous System Planning
• Counterexample-guided Planning
• Economics of Human-AI Ecosystem: Value Bias and Lost Utility in Multi-Dimensional Gaps
• Improved Exploration in Factored Average-Reward MDPs
• Optimistic Simulated Exploration as an Incentive for Real Exploration
• Stochastic Planning and Lifted Inference
• Feature Dynamic Bayesian Networks
• Online Planning in Uncertain and Dynamic Environment in the Presence of Multiple Mobile Vehicles
• Reasoning about Discrete and Continuous Noisy Sensors and Effectors in Dynamical Systems
• A compact, hierarchical Q-function decomposition
• Robby is Not a Robber (anymore): On the Use of Institutions for Learning Normative Behavior
• Solving Relational MDPs with Exogenous Events and Additive Rewards
• Kernel Taylor-Based Value Function Approximation for Continuous-State Markov Decision Processes
• Distributed Estimation using Bayesian Consensus Filtering
• Temporal plannability by variance of the episode length
• Bridging the Gap between Reinforcement Learning and Knowledge Representation: A Logical Off- and On-Policy Framework
• Optimal by Design: Model-Driven Synthesis of Adaptation Strategies for Autonomous Systems
• Solving Markov Decision Processes with Reachability Characterization from Mean First Passage Times
• A Prototype for Educational Planning Using Course Constraints to Simulate Student Populations