Planning Lectures for Huan Liu's CSE471 (Fall 09)

Lecture Notes for Fall 2009

• Planning lectures
  • Audio of [Nov 2, 2009] Review of the "Do the right thing" basis of AI; planning as the reasoning underlying that decision; distinctions between non-deterministic vs. stochastic dynamics; distinctions between full vs. partial satisfaction goals; difference between planning and search in terms of atomic vs. propositional models; the expressivenss roller-coaster in AI; discussion of why are expressive representations useful. Start of propositional/relational models for planning; state-variable based action representation; specification and progression and regression search over actions.
  • Audio of [Nov 4, 2009] Interactive discussion of tradeoffs between progression and regression (and the sherlock holmes joke); discussion of complexity of planning; short discussion of partial order planning; heursitics for planning; analysis of set-difference heuristic; discussion of tradeoffs between heuristic computation time and search time; motivating planning graph heuristic as a "relaxed"/"optimistic" version of projection; level-heuristic and its admissibility; generalizing level heuristic to sets in three ways based on the understanding of subgoal interactions (independent, positive, negative interactions); showing that both sum(indepdent) and level(max) heuristics can be bad (the former by being inadmissible and uninformed respectively); introduction of relaxed plan heuristic, which is the state of the art.

Homework

Here is a homework problem that you should try to make sure you understood what was taught. (Solution will be posted when Huan Liu gives the green signal).

• Solutions

Related Resources

Here is a link to CSE574 the graduate level course on automated planning that I teach

• Here are executables and domain files for a variety of planners in case you want to play with them.

Lecture Notes from Spring 2006

• Planning: The big picture. State variable models; classical planing rep; Progression, Regression
  • Planning Applications
  • Audio of today's lecture
• Planning: Reachability Heuristics
  • Audio of today's lecture
  • A survey paper on planning graph reachability heuristics. You should be able to understand upto (and possibly including) section 3. It also has good worked out examples on a problem

Lecture Notes from Fall 2005

• Planning: The big picture. State variable models; classical planing rep; Progression, Regression
  • Audio of lecture of [Nov 16, 2005] (Planning the big picture; State-variable models of the world; Classical Planning representation; progression and regression)

• Reachability Heuristics for Planning (the secret behind the scalability of modern planners)
  • Audio of lecture of [Nov 21, 2005] (Reachability heuristics; Planning Graphs; Relaxed plans; cost sensitive planning etc.)

• Oversubscription planning, General introduction to issues in planning under uncertainty and incomplete information
  • Audio of lecture of [Nov 23, 2005]