Next:
Overview of Part III:
Up:
Planning Algorithms
Previous:
Exercises
III
. Decision-Theoretic Planning
Subsections
Overview of Part III:
Decision-Theoretic Planning
Planning Under Uncertainty
9
. Basic Decision Theory
9
.
1
Preliminary Concepts
9
.
1
.
1
Optimization
9
.
1
.
1
.
1
Optimizing a single objective
9
.
1
.
1
.
2
Multiobjective optimization
9
.
1
.
2
Probability Theory Review
9
.
1
.
3
Randomized Strategies
9
.
2
A Game Against Nature
9
.
2
.
1
Modeling Nature
9
.
2
.
2
Nondeterministic vs. Probabilistic Models
9
.
2
.
3
Making Use of Observations
9
.
2
.
4
Examples of Optimal Decision Making
9
.
2
.
4
.
1
Pattern classification
9
.
2
.
4
.
2
Parameter estimation
9
.
3
Two-Player Zero-Sum Games
9
.
3
.
1
Game Formulation
9
.
3
.
2
Deterministic Strategies
9
.
3
.
3
Randomized Strategies
9
.
3
.
3
.
1
Extending the formulation
9
.
3
.
3
.
2
Computation of randomized saddle points
9
.
4
Nonzero-Sum Games
9
.
4
.
1
Two-Player Games
9
.
4
.
1
.
1
Dealing with multiple Nash equilibria
9
.
4
.
1
.
2
Randomized Nash equilibria
9
.
4
.
2
More Than Two Players
9
.
5
Decision Theory Under Scrutiny
9
.
5
.
1
Utility Theory and Rationality
9
.
5
.
1
.
1
Comparing rewards
9
.
5
.
1
.
2
Axioms of rationality
9
.
5
.
1
.
3
Constructing a utility function
9
.
5
.
2
Concerns Regarding the Probabilistic Model
9
.
5
.
2
.
1
Bayesians vs. frequentists
9
.
5
.
2
.
2
The source of prior distributions
9
.
5
.
2
.
3
Incorrect assumptions on conditional distributions
9
.
5
.
3
Concerns Regarding the Nondeterministic Model
9
.
5
.
4
Concerns Regarding Game Theory
Further Reading
Exercises
10
. Sequential Decision Theory
10
.
1
Introducing Sequential Games Against Nature
10
.
1
.
1
Model Definition
10
.
1
.
2
Forward Projections and Backprojections
10
.
1
.
3
A Plan and Its Execution
10
.
2
Algorithms for Computing Feedback Plans
10
.
2
.
1
Value Iteration
10
.
2
.
2
Policy Iteration
10
.
2
.
3
Graph Search Methods
10
.
3
Infinite-Horizon Problems
10
.
3
.
1
Problem Formulation
10
.
3
.
2
Solution Techniques
10
.
4
Reinforcement Learning
10
.
4
.
1
The General Philosophy
10
.
4
.
2
Evaluating a Plan via Simulation
10
.
4
.
3
Q-Learning: Computing an Optimal Plan
10
.
5
Sequential Game Theory
10
.
5
.
1
Game Trees
10
.
5
.
1
.
1
Determining a security plan
10
.
5
.
1
.
2
Computing a saddle point
10
.
5
.
1
.
3
Converting the tree to a single-stage game
10
.
5
.
2
Sequential Games on State Spaces
10
.
5
.
3
Other Sequential Games
10
.
6
Continuous State Spaces
10
.
6
.
1
Extending the value-iteration method
10
.
6
.
2
Motion planning with nature
Further Reading
Exercises
11
. Sensors and Information Spaces
11
.
1
Discrete State Spaces
11
.
1
.
1
Sensors
11
.
1
.
2
Defining the History Information Space
11
.
1
.
3
Defining a Planning Problem
11
.
2
Derived Information Spaces
11
.
2
.
1
Information Mappings
11
.
2
.
2
Nondeterministic Information Spaces
11
.
2
.
3
Probabilistic Information Spaces
11
.
2
.
4
Limited-Memory Information Spaces
11
.
3
Examples for Discrete State Spaces
11
.
3
.
1
Basic Nondeterministic Examples
11
.
3
.
2
Nondeterministic Finite Automata
11
.
3
.
3
The Probabilistic Case: POMDPs
11
.
4
Continuous State Spaces
11
.
4
.
1
Discrete-Stage Information Spaces
11
.
4
.
2
Continuous-Time Information Spaces
11
.
4
.
3
Derived Information Spaces
11
.
4
.
3
.
1
Nondeterministic and probabilistic I-spaces for discrete stages
11
.
4
.
3
.
2
Approximating nondeterministic and probabilistic I-spaces
11
.
4
.
3
.
3
Derived I-spaces for continuous time
11
.
5
Examples for Continuous State Spaces
11
.
5
.
1
Sensor Models
11
.
5
.
2
Simple Projection Examples
11
.
5
.
3
Examples with Nature Sensing Actions
11
.
5
.
4
Gaining Information Without Sensors
11
.
6
Computing Probabilistic Information States
11
.
6
.
1
Kalman Filtering
11
.
6
.
2
Sampling-Based Approaches
11
.
7
Information Spaces in Game Theory
11
.
7
.
1
Information States in Game Trees
11
.
7
.
2
Information Spaces for Games on State Spaces
Further Reading
Exercises
12
. Planning Under Sensing Uncertainty
12
.
1
General Methods
12
.
1
.
1
The Information Space as a Big State Space
12
.
1
.
2
Algorithms for Nondeterministic I-Spaces
12
.
1
.
3
Algorithms for Probabilistic I-Spaces (POMDPs)
12
.
2
Localization
12
.
2
.
1
Discrete Localization
12
.
2
.
2
Combinatorial Methods for Continuous Localization
12
.
2
.
3
Probabilistic Methods for Localization
12
.
3
Environment Uncertainty and Mapping
12
.
3
.
1
Grid Problems
12
.
3
.
2
Stentz's Algorithm (D
)
12
.
3
.
3
Planning in Unknown Continuous Environments
12
.
3
.
4
Optimal Navigation Without a Geometric Model
12
.
3
.
5
Probabilistic Localization and Mapping
12
.
4
Visibility-Based Pursuit-Evasion
12
.
4
.
1
Problem Formulation
12
.
4
.
2
A Complete Algorithm
12
.
4
.
3
Other Variations
12
.
5
Manipulation Planning with Sensing Uncertainty
12
.
5
.
1
Preimage Planning
12
.
5
.
2
Nonprehensile Manipulation
Further Reading
Exercises
Steve M LaValle 2008-06-13
