15-887*/16-830: Planning, Execution, and Learning
Schedule, Notes, Readings
Spring 2007
- Tuesday, January 16: Introduction
- Lecture Notes
- Points to remember from the discussion in class:
- Different planning problems require different assumptions
about state and actions; can make problem easier or harder
- Planning is usually done in service of execution; learning makes
everything work better/more accurately
- No assigned readings besides lecture notes.
- Thursday, January 18: 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.
- Tuesday, January 23: Classical Planning
(state-space, linear, non-linear)
- Lecture Notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Conjunctive goals can create problems for linear planning
using a stack of goals.
- Goal interactions affect planning efficiency.
- 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.
-
FLECS: Planning with a flexible commitment strategy,
Manuela M. Veloso and Peter Stone.
Journal of Artificial Intelligence Research, 3:25-52, 1995.
- Thursday, January 25: Classical Planning
(plan-space, partial-order)
- Lecture Notes
(six-to-a-page)
- 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:
- Tuesday, January 30: Classical Planning (graph-based)
- Lecture Notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Search space is graph of factored state representation
- Uses approximate reachability analysis, along with exclusivity
relationships, to constrain search.
- Forward/backward search
- Readings:
- Thursday, February 1: Heuristic Planning
- Lecture Notes
(six-to-a-page)
- Homework 1 OUT
- 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.
- Tuesday, February 6: Hierarchical Planning
- Lecture Notes
(six-to-a-page)
- 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
- Thursday, February 8: Temporal Planning
- Lecture Notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Time can be represented using points or intervals, relational
(qualitative) or metric (quantitative)
- Use of temporal constraint networks or simple temporal networks to
make temporal inferences
- Extend action representation to detail when (and for how long)
preconditions are needed and effects occur
- Readings:
-
Integrating Planning and Temporal Reasoning for Domains with Durations and
Time Windows A. Gerevini, A. Saetti, I. Serina, Proceedings of
IJCAI-05, Edinburgh, Scotland, 2005.
-
Temporal Constraint Networks
R. Dechter, I. Meiri, J. Pearl, Artificial Intelligence,
49:61-95, 1991
-
Temporal Planning with Continuous Change
J.S. Penberthy and D.S. Weld, Proceedings of AAAI-94, Seattle WA, July 1994.
- Tuesday, February 13: Discussion on Classical Planning
- No lecture notes
- No assigned readings
- Thursday, February 15: Conformant and Conditional Planning
- Lecture Notes
(six-to-a-page)
- Homework 1 DUE
- Points to remember from the discussion in class:
- Conformant planning produces non-branching plans that deal with
uncertainty by forcing the world into known states
- Conditional planning produces branching plans that use sensing actions
during execution to determine which branch to take
- Classical planning can be extended to deal with disjunctive
uncertainty by using approaches based on "possible worlds"
- Readings:
-
Conformant Graphplan, D. Weld and D. Smith, Proceedings of AAAI, July 1998.
-
Conformant Planning via Symbolic Model Checking
A. Cimatti and M. Roveri, Journal of Artificial Intelligence Research,
13:305-338, 2000.
-
Conditional Nonlinear Planning,
Mark Peot and David Smith
Proceedings of the First International Conference on AI Planning
Systems, College Park, Maryland, 1992
-
Extending Graphplan to Handle Uncertainty and Sensing Actions,
D. Weld, C. Andersonand D. Smith, Proceedings of AAAI, July 1998.
- Tuesday, February 20: Universal Plans
- Lecture Notes
(six-to-a-page)
- Homework 2 OUT
- Points to remember from the discussion in class:
- Universal plans (policies) can be represented and generated in
different ways (tables, decision trees, BDDs).
- Tree-based policies can be generated incrementally.
- BDD-based planning proceeds by computing "preimages"
backwards from the goal state. A preimage of a state is
the set of states that can transition to that state.
- There are three BDD-based planning algorithms to
know: strong, strong cyclic, and optimistic.
- Readings:
- Thursday, February 22: Probabilistic and Decision Theoretic Planning
- Lecture Notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Preference models include maximizing probability of goal achievement
and maximizing expected reward and/or utility
- Probabilistic planners add actions to increase likelihood of success
- Decision-theoretic planners use ranges on expected value/utility to
prune dominated plans
- Readings:
-
An Algorithm for Probabilistic Least-Commitment Planning
Nicolas Kushmerick, Steve Hanks and Daniel Weld,
Proceedings of AAAI-94, Seattle, WA, July 1994
-
Optimal Planning with a Goal-Directed Utility Model
Mike Williamson and Steve Hanks, Proceedings of AIPS 94.
-
Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis,
Peter Haddawy, AnHai Doan and Richard Goodwin ,
In Proceedings of the Eleventh Conference on Uncertainty in Artificial
Intelligence, (UAI-95), Montreal Canada, Aug. 1995
- Tuesday, February 27: MDPs and Reinforcement Learning
- Thursday, March 1: POMDPs
- Tuesday, March 6: POMDPs
- Lecture Notes
(six-to-a-page)
- Homework 2 DUE
- Points to remember from the discussion in class:
- Readings:
-
An Improved Grid-Based Approximation Algorithm for POMDPs
R. Zhou and E. Hanse. In Proceedings of IJCAI, Seattle Washington,
August 2001.
-
Point-based value iteration: An anytime algorithm for POMDPs.
J. Pineau, G. Gordon, and S. Thrun. In Proceedings IJCAI-03,
Acapulco, Mexico. August 2003.
-
Heuristic Search Value Iteration for POMDPs
T. Smith and R. Simmons. In Proceedings of UAI, July 2004.
-
Acting optimally in partially observable stochastic domains
A. Cassandra, L.P. Kaelbling, M. Littman. In Proceedings AAAI-94
Seattle WA, 1994.
- Thursday, March 8: Planning and Learning (Laura)
- Lecture notes
(six-to-a-page)
- Homework 3 OUT
- Points to remember from the discussion in class:
- Readings:
-
Learning-Assisted Automated Planning, Terry Zimmerman and SUbbarao Kambhampati,
AI Magazine, Volume 24, Summer 2003.
-
Nogood Learning for Classical Planning, Igor Razgon,
ICAPS '03 Doctoral Consortium.
-
Integrating planning and learning: The Prodigy architecture, (Sections 3 and 4)
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.
-
Learning Planning Operators in Real-World, Partially Observable Environments,
Matthew D. Schmill, Tim Oates and Paul R. Cohen,
In Proceedings of the 5th Int'l Conf. on AI Planning and Scheduling (AIPS'00), 2000.
- Tuesday, March 13: Spring Break
- Thursday, March 15: Spring Break
- Tuesday, March 20: POMDPs III
- Thursday, March 22: Path Planning (deterministic)
- Tuesday, March 27: Path Planning (randomized)
- Lecture notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
- Probabilistic Roadmaps for Robot Path Planning, Lydia Kavraki and
Jean-Claude Latombe. In Practical Motion Planning in Robotics,
1998.
- Randomized Kinodynamic Planning, Steven LaValle and James Kuffner.
In Proceedings International Conference on Robotics and Automation,
1999.
- Approaches for Heuristically Biasing RRT Growth, Chris Urmson and Reid
Simmons, in Proceedings International Conference on Intelligent Robots
and Systems, 2003
-
Particle RRT for Path Planning with Uncertainty,
N. Melchior and R. Simmons.
To appear in Proceedings of the IEEE International Conference on
Robotics and Automation (ICRA), Rome, 2007.
- Thursday, March 29: Execution Architectures (Laura)
- Lecture notes
(six-to-a-page)
- Homework 3 DUE
- Homework 4 OUT
- Points to remember from the discussion in class:
- Readings:
-
Experiences with an Architecture for Intelligent, Reactive Agents,
R. P. Bonasso, R. J. Firby, E. Gat, D. Kortenkamp, D. Miller and M. Slack
Journal of Experimental and Theoretical Artificial Intelligence, 9(2),
1997.
-
Remote Agent: To Boldly Go Where No AI System Has Gone Before,
Nicola Muscettola, P. Pandurang Nayak, Barney Pell, and Brian Williams
Artificial Intelligence 103(1-2):5-48, August 1998.
-
A Task Description Language for Robot Control,
R. Simmons and D. Apfelbaum,
In Proceedings of Conference on Intelligent Robotics and Systems, Vancouver Canada, October 1998.
- Tuesday, April 3: Monitoring and Diagnosis
- Thursday, April 5: Reactive Planning
- Lecture Notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
-
Integrating planning and learning: The Prodigy architecture,
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.
- The Effect of Representation on Goal-Directed Reinforcement
Learning Algorithms,
S. Koenig and R. Simmons, Machine Learning, Machine Learning
Journal, vol. 22, pp. 227-250, 1996.
- Tuesday, April 10 : Execution and Learning
- Thursday, April 12: Scheduling (classical) (Steve Smith)
- Lecture notes
- Points to remember from the discussion in class:
- Readings:
- Tuesday, April 17 : Scheduling (distributed) (Steve Smith)
- Lecture notes
- Points to remember from the discussion in class:
- Readings:
- Thursday, April 19: No class
- Tuesday, April 24 : Multi-Agent Planning I
- Lecture notes
(six-to-a-page)
- Homework 4 DUE
- Points to remember from the discussion in class:
- Readings:
- Social Potentials for Scalable Multirobot Formations,
T. Balch and M. Hybinette, in Proceedings IEEE International Conference
on Robotics and Automation, San Francisco CA, 2000.
- Coordination for Multi-Robot Exploration and Mapping
,
R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, H. Younes.
In Proceedings National Conference on Artificial Intelligence,
Austin TX, August 2000.
-
A Layered Architecture for Coordination of Mobile Robots,
R. Simmons, T. Smith, M. B. Dias, D. Goldberg, D. Hershberger,
A. Stentz, R. Zlot, in Multi-Robot Systems: From
Swarms to Intelligent Automata,
A. Schultz and L. Parker (eds.), Kluwer, 2002.
-
Hoplites: A Market-Based Framework for Planned Tight
Coordination in Multirobot Teams,
N. Kalra, D. Ferguson, and A. Stentz, in Proceedings of the International
Conference on Robotics and Automation, April, 2005.
- Thursday, April 26: Multi-Agent Planning II
- Lecture notes
(six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
-
Taming Decentralized POMDPs: Towards Efficient Policy Computation for
Multiagent Settings.
Ranjit Nair, David Pynadath, Makoto Yokoo, Milind Tambe and Stacy Marsella.
In Proceedings of the International Joint Conference on Artificial
Intelligence (IJCAI-03), 2003.
-
Communication for Improving Policy Computation in Distributed POMDPs
Ranjit Nair, Maayan Roth, Makoto Yokoo and Milind Tambe.
In Proceedings of Conference on Autonomous Agents and Multiagent Systems
(AAMAS-04), 2004.
-
Decentralized Communication Strategies for Coordinated Multi-Agent
Policies, M. Roth, R. Simmons and M. Veloso. In
Multi-Robot Systems: From Swarms to Intelligent Automata, A. Schultz, L.
Parker, and F. Schneider (eds.), Volume IV, Kluwer Avademic Publishers, 2005.
-
What to Communicate? Execution-Time Decision in Multi-Agent POMDPs,
M. Roth, R. Simmons and M. Veloso.
In Proceedings of the International
Symposium on Distributed Autonomous Robotic Systems (DARS),
Minneapolis MN, July 2006.
-
Dynamic multi-robot coordination,
Douglas Vail and Manuela Veloso,
In Multi-Robot Systems: From Swarms to Intelligent Automata,
A. Schultz, L. Parker, and F. Schneider (eds.),
Volume II, pages 87--100. Kluwer Academic Publishers, 2003.
-
Plays as team plans for coordination and adaptation,
Michael Bowling, Brett Browning, and Manuela Veloso.
In Proceedings of the 14th International Conference on Automated
Planning and Scheduling (ICAPS-04), Vancouver, June 2004.
- Tuesday, May 1 : Multi-Robot Planning and Execution (Laura)
- Thursday, May 3: Review
- No lecture notes
- No assigned readings
- Friday May 4 - Monday May 7: Final Exam Available