Graphplan

• A. Blum & M. Furst Fast Planning through Graph Analysis(IJCAI95 and AIJ 1997). [Paper] [Review]

  Additional, optional background material:

  • C. Anderson and D. Smith and D. Weld Conditional Effects in Graphplan (AIPS-98, June 1998)

Compilation to SAT

• M. Ernst and T. Millstein and D. Weld Automatic SAT-Compilation of Planning Problems (IJCAI-97, August 1997) [Paper] [Review]

  Additional, optional background material:

  • Kautz, H. and Selman, B.Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search AAAI-96, 1996. [Paper]
  • S. Wolfman and D. Weld The LPSAT Engine and its Application to Resource Planning [Paper]
  • Henry Kautz and Joachim P. Walser.State-space Planning by Integer OptimizationAAAI-99, Orlando, FL, 1999 [Paper]

Heuristic State-Space Search

• B. Bonet and H. Geffner Planning as Search: New Results ECP, 1999). [Paper] [Review]

  Additional, optional background material:

  • Jorg Hoffman's FF planner
  • XuanLong Nguyen, and Subbarao Kambhampati Extracting effective and admissible heuristics from the Planning Graph Proc. AAAI-00, 2000.

Refinement Planning

• S. Kambhampati, Refinement planning as a unifying framework for plan synthesis AI Magazine, Vol 18. No. 2, Summer, 1997 [Paper] [Review]

  Additional, optional background material:

Markov Decision Processes

• Boutilier, C., Dean, T. and Hanks, S. (1999) Decision-Theoretic Planning: Structural Assumptions and Computational Leverage, JAIR, Volume 11. [Paper] Just read the first 30 pages. [No review necessary].

  Additional, optional background material:

  • Geoffrey Gordon, Background on Markov Decision processes.Unpublished [Paper] This is a shorter introduction which has less on the overall problem and more on policy construction methods. Also discusses the linear programming solution.

Search in Belief Space

• B. Bonet and H. Geffner. Planning with Incomplete Information as Heuristic Search in Belief Space Proc. 5th Int. Conf. on AI Planning and Scheduling (AIPS 2000), Colorado, 4/2000, AAAI Press [Paper] [Review]

  Additional, optional background material:

  • B. Bonet and H. Geffner. Faster Heuristic Search Algorithms for Planning with Uncertainty and Full Feedback Int. Joint Conference on Artificial Intelligence (IJCAI-2003), Acapulco, Mexico, August 2003 [paper]

Robot Localization?

• Hugh F Durrant-Whyte will give a guest lecture; for this it would be great if you got some background on Kalman filters. Please read and review (focus on pages 19-29) the following: Welch and Bishop An Introduction to the Kalman Filter Siggraph Tutorial notes, 2001. [Paper] [Review]

  Additional, optional background material:

  • Hugh F Durrant-Whyte's home page.

Probabilistic Graphplan

• Avrim L. Blum and John C. Langford Probabilistic Planning in the Graphplan Framework ECP-98 (1998). [Paper] [Review]

  Additional, optional background material:

  • Craig Boutilier, Ronen I. Brafman and Christopher Geib Structured Reachability Analysis for Markov Decision Processes Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), 1998. [Paper]

Stochastic Planning using Decision Diagrams

• Jesse Hoey, Robert St-Aubin, Alan Hu and Craig Boutilier SPUDD: Stochastic Planning using Decision Diagrams Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI 99), Stockholm, Sweden. [Paper] [Review]

  Additional, optional background material:

  • Z. Feng and E. Hansen. Symbolic Heuristic Search for Factored Markov Decision Processes, Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, Alberta, Canada, July 2002. [Paper]

Continuous Time and Resource Uncertainty

• Dearden et al. Incremental Contingency Planning ICAPS-03 Workshop on Planning Under Uncertainty [Paper] [Review]

  Additional, optional background material:

  Slides from a presentation by Dave SMith on parts of this material.

Partially Observable MDPs

• Anthony Cassandra, Michael L. Littman, Nevin L. Zhang Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI--97) 1997. [Paper] [Review]

  Additional, optional background material:

  • Kevin Murphy wrote a good survey [Paper]
  • Andrew Y. Ng and Michael Jordan. PEGASUS: A policy search method for large MDPs and POMDPs, Uncertainty in Artificial Intelligence, Proceedings of the Sixteenth Conference, 2000. [Paper]

Interleaved Planning and Execution

• Sven Koenig Agent-Centered Search AI Magazine 2001. [Paper] [Review]

  Additional, optional background material:

  • This is a survey paper, so there are many references to track; pick your favorite algorithm and read the primary source.
  • One especially important connection is to Real-time dynamic programming (RTDP) as sketched briefly on this page.

Planning for Softbots

• Keith Golden Leap before you look: Information Gathering in the PUCCINI planner, AIPS-98, 1998 [Paper] [Review]

  Additional, optional background material:

  • For those of you without background in partial-order (causal link) planning, you'll probably need to read section4 (and maybe 5 and 6) of my "An Introduction to Least Commitment Planning," AI Magazine, 15(4), pages 27-61, Winter 1994. Ignore the subsections on implementation details.
  • See related papers for the Pettrick and Bacchus paper below.
  • Many background and followup papers available here
  • The recent latest papers on the subject from the 2003 ICAPS workshop on planning for web services (to appear June 2003).

Contingent Approach to Information Gathering

• R. Petrick and F. Bacchus A Knowledge-Based Approach to Planning with Incomplete Information and Sensing, AI Planning and Scheduling (AIPS2002), 2002. [Paper] [Review]

  Additional, optional background material:

  • Oren Etzioni, K. Golden and D. Weld Tractable Closed World Reasoning with Updates, Proceedings of KR-94, May 1994. [Paper]
  • Alon Y. Levy , Obtaining Complete Answers from Incomplete Databases Proceedings of the 22nd VLDB Conference, Bombay, India. 1996 [Paper]
  • F. Bacchus and R. Petrick, Modeling an Agent's Incomplete Knowledge during Planning and Execution, Knowledge Represention and Reasoning, pages 432-443. 1998. (If you have questions on their KR scheme).

The Partial-Order Approach

• J.S. Penberthy and D. Weld Temporal Planning with Continuous Change, AAAI-94, Seattle, WA, July 1994. [Paper] [Review]

  Additional, optional background material:

  • For those of you without background in partial-order (causal link) planning, you'll probably need to read section4 (and maybe 5 and 6) of my "An Introduction to Least Commitment Planning," AI Magazine, 15(4), pages 27-61, Winter 1994. Ignore the subsections on implementation details.
  • D. Long and M. Fox Exploiting a Graphplan Framework in Temporal Planning [Paper]
  • Ghallab and Laruelle Representation and Control in IxTeT, AIPS94, 1994.

Temporal Graphplan

• D. Smith and D. Weld, Temporal Planning with Mutual Exclusion Reasoning IJCAI-99, 1999. [Paper] [Review]

  Additional, optional background material:

  • J. Koehler, Planning under Resource Constraints, ECAI-98, pages 489-493, 1998.[Paper]

Forward-Chaining Search

• Minh B. Do and Subbarao Kambhampati, Sapa: A Domain-Independent Heuristic Metric Temporal Planner ECP 2001. [Paper] [Review]

  Additional, optional background material:

  • P. Haslum and H. Geffner, Heuristic Planning with Time and Resources,, Proceedings ECP-2001. [paper]

Stochastic Search of Planning Graphs

• Alfonso Gerevini , Ivan Serina, Alessandro Saetti, Sergio Spinoni "Local Search Techniques for Temporal Planning in LPG", to appear in ICAPS03. [Paper] [Review]

  Additional, optional background material:

  • Alfonso Gerevini and Ivan Serina "Fast Planning through Greedy Action Graphs", in Proceedings of Sixteenth National Conference of Artificial Intelligence (AAAI-99), Orlando Florida July 1999. AAAI-MIT Press. This and other papers available here

Explanation-based learning and dependency-directed backtracking

• S. Kambhampati, Improving Graphplan's search with EBL and DDB techniques. IJCAI-1999 [Paper]

  Additional, optional background material:

  • Fox and Long: STAN TIM analysis

Heuristics for Partial-Order Planning

• XuanLong Nguyen & Subbarao Kambhampati, Reviving Partial Order Planning Proc. IJCAI-01, 2001. [Paper]

  Additional, optional background material:

  • D. Weld, An Introduction to Least Commitment Planning, AI Magazine, 15(4), pages 27-61, Winter 1994. [Paper]

Spacecraft and NASA Domains

• S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt, D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins, D. Tran , "ASPEN--Automating Space Mission Operations using Automated Planning and Scheduling," SpaceOps 2000, Toulouse, France, June 2000.
• G. Rabideau, S. Chien, J. Willis, T. Mann, "Using Iterative Repair to Automate Planning and Scheduling of Shuttle Payload Operations," Innovative Applications of Artificial Intelligence (IAAI), Orlando, Florida, July 1999.
• Jonsson, Morris, Muscettola, Rajan, and Smith, "Planning in Interplanetary Space: Theory and Practice" in Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, Breckenridge, CO, April 2000.

Training, simulation & Games

• John Laird and Michael van Lent Interactive Computer Games: Human-level AI's Killer Application [Paper]. This was presented as an invited talk at AAAI on August 2, 2000 - it's "A general, over-the-top paper attempting to rally people to work on artificial intelligence and computer games" More detailed papers on Larid's website
• Planning in training simulation environments (Nov 27) Jonathan Gratch "Emile" Proc Autonomous Agents 2000
• Jeff Rickel and Lewis Johnson "Virtual Humans for Team Training in VR" Proc AI in Education, 1999

Computer Science & Engineering Department
University of Washington
PO Box 352350
Seattle, WA 98195-2350 USA