15-887*: Planning, Execution, and Learning
Schedule, Notes, Readings
Fall 2016
- Wednesday, September 7: (LV) Introduction
- Lecture Notes
- Points to remember from the discussion in class:
- No assigned readings besides lecture notes.
- Monday, September 12: (V) Representation for higher level planning
- Lecture Notes
- Points to remember from the discussion in class:
- Many ways to represent the states and actions of a problem,
significantly affecting the planning expressiveness and complexity.
- Closed-world assumption: What is not true in the state, is false.
- STRIPS action representation (add / delete lists).
- Many ways to find solutions to planning problems -- differ
in complexity and how well they scale with respect to size
of search space.
- Humans use real-world knowledge when they solve planning problems;
most planners do not have that luxury.
- Readings:
- Wednesday, September 14: (V) Algorithms for classical planning
- Lecture Notes
- Points to remember from the discussion in class:
- Planners are characterized in terms of soundness, completeness,
optimality, and computational efficiency.
- Linear Planning: Work on one goal until completely solved. Only then move to another goal.
- GPS Algorithm: Sound, Not Optimal, Not Complete
- Prodigy Algorithm: Nonlinear planner, Sound
- Readings:
- Monday, September 19: (L) Graph representation for lower level planning
- Lecture Notes
- Points to remember from the discussion in class:
- Interleaving of graph construction and search is critical.
- C-Space Transform: makes planning faster, but constructing C-space can be expensive.
- Multiple methods for constructing the graph of the planning problem.
- State discretization typically reduces computational complexity of motion planning at the expense of surrendering strict completeness.
- Readings:
- No assigned readings besides lecture notes.
- Wednesday, September 21: (V) Planning Graphs for Planning and Heuristic Search
- Lecture Notes
- Points to remember from the discussion in class:
- Graphplan has two phases: forward extension and backwards plan search.
- Exclusivity relations key to the efficiency of Graphplan.
- Graphplan is optimal in terms of number of time steps.
- Readings:
- Monday, September 26: (L) Heuristic A*; Weighted A*
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, September 28: (L) Heuristic functions, Multi-heuristic A*
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 3: (V) Planning under uncertainty, conditional and conformant
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 5: (V) Planning under uncertainty, re-planning and decision-theoretic planning, uncertainty of action
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 10: (L) Execution: heuristic search, anytime, re-planning, real-time heuristic search I
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 12: (L) Execution: heuristic search, anytime, re-planning, real-time heuristic search II
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 17: (V) Planning under uncertainty: MDPs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 19: (V) Planning under uncertainty: Reinforcement Learning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 24: (L) Learning in Planning: Experience graphs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 26: (L) Learning in Planning: ERRT, reuse of previous plans
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 31: (V) Learning in Planning: Explanation-based, Analogy-based
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 2: (L) Learning in Planning: learning a cost function
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 7: (V) Deep Learning and Deep Reinforcement Learning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 9: (L) Planning under uncertainty: POMDPs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 14: (V) Planning under uncertainty: Short-sighted probabilistic planning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 16: (V) Multi-agent planning and execution: DecSIMDPs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 21: (V) Multi-agent and human-agent planning and execution
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 23: THANKSGIVING - NO CLASS
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 28: (L) Application: planning for manipulation
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 30: (L) Application: planning for ground and aerial robots
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, December 5: (L) Application: planning for perception (MHA*, PERCH)
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, December 7: (LV) Review
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
mmv@cs.cmu.edu
July 23, 2016