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:
  - 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:
  - An introduction to least-commitment planning, (pdf version)
    Daniel Weld. Artificial Intelligence Magazine, 27--61, Winter 1994.
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:
  - Fast planning through planning graph analysis,
    Avrim Blum and Merrick Furst.
    Artificial Intelligence, 90:281--300, 1997.
  - Conditional Effects in Graphplan Corin R. Anderson, David E. Smith, Daniel S. Weld, In Proceedings of the 4th International Conference of AI Planning Systems, 1998
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:
  - Universal Plans for Reactive Robots in Unpredictable Environments, MJ Schoppers. In Proceedings IJCAI 1987.
  - Strong Planning in Non-Deterministic Domains via Model Checking, A. Cimatti, M. Rovero, P. Traverso. In Proceedings of AIPS-98.
  - Automatic OBDD-based Generation of Universal Plans in Non-Deterministic Domains, A. Cimatti, M. Rovero, P. Traverso. In Proceedings of AAAI-98.
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
- Lecture Notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
Thursday, March 1: POMDPs
- Lecture Notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
  - POMDPs for Dummies.
  - Planning and Acting in Partially Observable Stochastic Domains. L.P. Kaelbling, M.L. Littman, and A.R. Cassandra, Artificial Intelligence, Vol 101, 1998.
  - Synthesis of Hierarchical Finite-State Controllers for POMDPs. E. Hansen and R. Zhou. Thirteenth International Conference on Automated Planning and Scheduling (ICAPS-03), Trento, Italy, June 2003.
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)
- Lecture notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
  - Robot Motion Planning. J.C. Latombe. Kluwer, 1991.
  - Planning Algorithms. S. LaValle, Draft: to be published by Cambridge University Press, 2006.
  - The Focussed D* Algorithm for Real-Time Replanning. A. Stentz, IJCAI 1995.
  - D* Lite. S. Koenig and M. Likhachev. AAAI 2002.
  - Experience with Rover Navigation for Lunar-Like Terrains. R. Simmons, et.al., IROS 1995.
  - Traveling Salesman Page
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
- Lecture Notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
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
- Lecture notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
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)
- Lecture notes (six-to-a-page)
- Points to remember from the discussion in class:
- Readings:
Thursday, May 3: Review
- No lecture notes
- No assigned readings
Friday May 4 - Monday May 7: Final Exam Available

reids@cs.cmu.edu
February 1, 2007

15-887*/16-830: Planning, Execution, and LearningSchedule, Notes, Readings Spring 2007

15-887*/16-830: Planning, Execution, and Learning
Schedule, Notes, Readings
Spring 2007