CS 541 (AI Planning) Syllabus

CS 541: AI Planning

Fall 2000

Instructors: Jim Blythe, Yolanda Gil, and Jon Gratch

blythe@isi.edu, gil@isi.edu, gratch@ict.usc.edu

http://www.isi.edu/~blythe/cs541

Syllabus and Tentative Schedule

Introduction to AI planning

Action and plan representations, historical overview, STRIPS (Aug 28)
class notes

Planning approaches

Plan generation and causal-link planning (Aug 30 & Sep 6)
Reading: "An Introduction to Least-Commitment Planning", Dan Weld, AI Magazine 1994
(With thanks to Hyuckchul Jung for the PDF version.)

Class notes 1 (powerpoint) (With a couple of corrections made after the class.)

Class notes 2 (powerpoint)
Hierarchical task network (HTN) planning (Sep 11)
Reading: Qiang Yang, "Formalizing Planning Knowledge for Hierarchical Planning." Computational Intelligence Journal, 6(2), (1990), pp. 12-24. NOTE: ONLY SECTIONS 1 & 2

Reading: Austin Tate, "Generating project networks", James Allen, James Hendler, and Austin Tate, editors. Readings in Planning. Morgan Kaufmann, 1990.

class notes
Plan graph search (Sep 13)
Reading: Avrim Blum and Merrick Furst. "Fast planning through planning graph analysis", Artificial Intelligence, 1997. (postscript version)

Reading: Jana Koehler, Bernhard Nebel, Jorg Hoffman and Yannis Dimopoulos. "Extending planning graphs to an ADL subset", European Conference on Planning (ECP) 1997. (postscript version)

class notes (powerpoint)

For more information, you can check out the Graphplan home page
Skeletal planning, case based planning (Sep 18)
Reading: Peter E. Friedland and Yumi Iwasaki. The concept and implementation of skeletal plans. Journal of Automated Reasoning, 1:161-208, 1985. NOTE: ONLY SECTIONS 4, 5.1, 5.2, 5.3.

Reading: Manuela Veloso. "Flexible Strategy Learning: Analogical Replay of Problem Solving Episodes." In Proceedings of AAAI-94. Postscript

class notes
Planning as constraint satisfaction, planning as satisfiability (Sep 20)
Reading: Henry Kautz and Bart Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In AAAI 96. (Postscript version) Blackbox home page

Reading: Minh Binh Do & Subbarao Kambhampati. Solving planning-graph by compiling it into CSP. AIPS 2000. (postscript version). GP-CSP home page

Class notes, ( powerpoint file). See also the slides about GP-CSP.
Planning using temporal logics (Sep 25)
Reading: Fahiem Bacchus and Froduald Kabanza. Using temporal logic to control search in a forward-chaining planner. EWSP 95 (postscript version)

Reading: Fahiem Bacchus and Yee Whye Teh. Making forward chaining relevant. AIPS 98 (postscript version)

You can also check out the TLPlan home page
Heuristic search planning (Sep 27)
Reading: Blai Bonet and Hector Geffner. "Planning as heuristic search: New results" Proceedings of the 1999 European Conference on Planning (ECP-99). (postscript version)

class notes
Reactive systems (Oct 2)
Reading: Michael Georgeff and Amy Lansky. "Reactive Reasoning and Planning". Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87), 1987.

class notes

Plan Representations

Knowledge representation for planning, ontologies, description logics (Oct 4)
Reading: Yolanda Gil. "Plan Representation and Reasoning with Description Logics". (postscript version)

Reading: A Brief introduction to description logics. (postscript version)

Class notes (powerpoint presentation)
Reasoning about time: temporal reasoning and scheduling (Oct 11)
Reading: David Smith, et al. "Bridging the Gap Between Planning and Scheduling." (postscript version)

Class notes (powerpoint)

Controlling Search

Complexity of planning problems (Oct 9)
Reading: Kutluhan Erol et al. "Complexity, decidability and undecidability results for domain-independent planning", AIJ 1994 (postscript version).

class notes (powerpoint)
Abstraction, macros, hierarchical planning (Oct 16)
Craig A. Knoblock, Josh D. Tenenberg, and Qiang Yang. "Characterizing abstraction hierarchies for planning". In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), Anaheim, CA, 1991. (postscript version).

Class notes
Learning search control knowledge (Oct 18)
Reading: Jonathan Gratch and Gerald DeJong, "A decision-theoretic approach to adaptive problem solving," Artificial Intelligence, (88) 1-2, 1996, pp. 365-396. (postscript version)
Class notes (powerpoint)

Agent-Based Planning

Multi-agent planning architectures (Oct 23)
desJardins, M., Durfee, E., Ortiz, C., and Wolverton, M., "A Survey of Research in Distributed, Continual Planning", AI Magazine, Volume 20, Number 4, Winter 1999. (PDF version)
desJardins, M. and Wolverton, M., "Coordinating Planning Activity and Information Flow in a Distributed Planning System", AI Magazine, Volume 20, Number 4, Winter 1999. (postscript version)
Class notes (powerpoint)
Reasoning about other agents (Oct 25)
Gratch, J., "How to make your planner rude: and other issues in multi-agent planning," draft article (postscript)
Class notes (powerpoint)
MIDTERM: (Oct 30)
Learning from an external environment (Nov 1)
Gil, Y., "Learning by Experimentation: Incremental Refinement of Incomplete Planning Domains", Proceedings of the Eleventh International Conference on Machine Learning (ICML-94) (pdf file).

Class notes
Planning within a team, by Milind Tambe (USC ISI) (Nov 20)

Planning under Uncertainty

Probabilistic planning (Nov 6 and Nov 8)

Blythe, J., "Decision-Theoretic Planning", AI Magazine, Volume 20, Number 2, Summer 1999, pages 1 to 15 only (PDF version)

class notes (powerpoint)
Exogenous events (Nov 8)
Blythe, J., "Event-based decompositions for reasoning about external change in planners", AIPS 1996 (postscript version)

class notes (powerpoint)
Decision theory, Markov decision processes (Nov 13)
Boutilier, Dean and Hanks, "Planning under uncertainty: structural assumptions and computational leverage", European Workshop on Planning, 1995. (Postscript version)

Also, pages 15 to 19 of decision-theoretic planning, from the Nov 6 class.

Further reading: Boutilier, Dean and Hanks, "Decision-theoretic planning: structural assumptions and computational leverage", JAIR 1 (1999) (postscript). This is a more detailed and up to date version of the EWSP 95 paper, but it's nearly 100 pages long.

Planning Applications

Planning in space, by Ben Smith (JPL, NASA) (Nov 15)
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. (PDF version)

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. (PDF version)

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. (PDF version)

Mixed-initiative planning (Nov 22)
"Strategic Advice for Hierarchical Planners", K. L. Myers, in Principles of Knowledge Representation and Reasoning: Proceedings of the Fifth International Conference (KR '96), Morgan Kaufmann Publishers, San Francisco, CA, 1996. (PDF version)

George Ferguson, James Allen, and Brad Miller, ``TRAINS-95: Towards a Mixed-Initiative Planning Assistant,'' Proc. Third Conference on Artificial Intelligence Planning Systems (AIPS-96), Edinburgh, Scotland, 29-31 May, 1996, 70-77. (postscript version)
Planning in training simulation environments (Nov 27)
Jonathan Gratch "Emile" Proc Autonomous Agents 2000 (PDF version)

Jeff Rickel and Lewis Johnson "Virtual Humans for Team Training in VR" Proc AI in Education, 1999 (postscript version)

Project Descriptions

Student presentations of course projects (Nov 29 & Dec 4)

Final Review

(Dec 6)