15-887*/16-830: Planning, Execution, and Learning
Schedule, Notes, Readings
Fall 2008
- Monday, September 8: Introduction
- Lecture Notes
- Points to remember from the discussion in class:
- Planning is about states, goals, actions. Planning assumes a model of the world; Execution performs
the actions of a plan; Learning improves planning and execution through experience.
- Different planning problems require different assumptions
about state and actions, which can make a problem easier or harder to solve.
- No assigned readings besides lecture notes.
- Wednesday, September 10: Representation and Search
- Lecture Notes
- Points to remember from the discussion in class:
- State space grows exponentially in number of state variables
- Factoring / decomposing state space key to planning efficiency
- Strips-assumption (add/delete lists) deals with Frame Problem
- Writing a planning domain in terms of a set of predicates,
variables, and operators is a hard task.
- Planners characterized in terms of soundness, completeness,
optimality, and computational efficiency
- Many ways to find solutions to planning problems -- differ
in complexity and how well they scale with respect to size
of search space
- Search for solutions to planning problems can occur in
both state space and plan space
- No assigned readings besides lecture notes.
- Monday, September 15: Plan-Space Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Planning in place space: State space is space of partial
plans; search actions modify plans (refine them)
- Partial-Order planners work by adding causal links from effects
of one action to precondition of another, and then by eliminating
threats. Threats can be eliminated by promotion, demotion, or
separation. Backtracking occurs if a threat cannot be eliminated.
- Use of Least Commitment -- delaying choices of temporal
constraints and parameter bindings unless forced.
- Readings:
- Wednesday, September 17: State-space Non-linear Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Linear planning maintains state and a goal stack: it's efficient but can
generate unoptimal solutions, and it's incomplete.
- Nonlinear state-space planning uses a set of goals, backtracks over
plan orderings decisions. It's complete.
- State-space planning commits on plan step orderings
with the main goal of getting an updated state and hopefully
a "closer" state to the goal. Such commitments may lead to
backtracking, but may also lead to informed state-based choices
of actions.
- Plan-space planning does not commit on plan step orderings,
until it needs to solve threats. It
follows a least-commitment search
approach but only wrt step orderings.
- Plan-space planning commits to causal links
leading to linkability problems and to the need to backtrack
over linking commitments. In the linkability sense,
plan-space planning is a strong-commitment planner.
- Readings:
-
Integrating planning and learning: The Prodigy architecture, (Sections 1 and 2)
Manuela M. Veloso, Jaime Carbonell, M. Alicia P\'erez, Daniel Borrajo,
Eugene Fink, and Jim Blythe.
Journal of Experimental and Theoretical
Artificial Intelligence, 7(1):81--120, 1995.
-
Linkability: Examining causal link commitments in partial-order
planning,
Manuela M. Veloso and Jim Blythe.
In Proceedings of the Second International Conference on AI
Planning Systems, pages 170-175, June 1994.
- Monday, September 22: Graph-based Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, September 24: Heuristic Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Estimate cost of achieving conditions/goals using relaxed
form of problem
- Good heuristics make forward-progression state-space planners
very competitive
- Hard to find an informed, admissible heuristic for planning due
to positive and negative interactions
- Many heuristics for flaw selection -- no one is best
- Readings:
-
Planning as Heuristic Search, B. Bonet and H. Geffner. Artificial Intelligence, Special issue on Heuristic Search. Vol 129 (1-2) 2001.
-
Admissible Heuristics for Optimal Planning P. Haslum H. Geffner. Proc. 5th
Int. Conf. on AI Planning and Scheduling (AIPS 2000).
-
The FF Planning System: Fast Plan Generation Through Heuristic Search,
J. Hoffmann, B. Nebel. Journal of Artificial Intelligence Research,
vol 14, pp. 253-302, 2001
-
VHPOP: Versatile Heuristic Partial Order Planner,
H.L.S. Younes and R.G. Simmons. Journal of Artificial Intelligence
Research, vol 20, pp. 405-430, December 2003.
- Monday, September 29: Hierarchical Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Problem reduction search decomposes tasks into subtasks
- Take advantage of structure inherent in domain
- Domain definition -- "how" rather than "what"
- Works best when problem is complex, but few unintended
goal interactions
- Readings:
-
SHOP2: An HTN Planning System
Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Murdock, J.W., Wu, D. and
Yaman, F, Volume 20, pages 379-404, 2003.
-
O-Plan: the Open Planning Architecture,
Ken Currie and Austin Tate.
Artificial Intelligence Vol. 52, pp 49-86, 1991
-
HTN planning: Complexity and expressivity,
K Erol, J Hendler and D Nau. AAAI-94, 1994
- Wednesday, October 1: Classical Planning and Learning I
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 6: Classical Planning and Learning II
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 8: Conditional and Universal Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 13: Markov Decision Processes
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 15: Reinforcement Learning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 20: POMDPs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 22: POMDPs
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, October 27: Reactive Planning, Robot Execution
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, October 29: Path Planning
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 3: Execution architectures
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 5: Execution Monitoring and Diagnosis
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 10: Multi-agent Planning I
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 12: Multi-agent Planning II
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 17: Multi-agent Planning III
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 19: Multi-agent Robot Planning and Execution
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Monday, November 24: Planning for Heterogenous Multi-Robot Systems
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, November 26: Thanksgiving, No Class
- Monday, December 1: Learning to Coordinate
- Lecture Notes
- Points to remember from the discussion in class:
- Readings:
- Wednesday, December 3: Wrap Up
- Lecture Notes
- Points to remember from the discussion in class:
- Readings: