CS 541: Artificial Intelligence Planning

Instructors: Yolanda Gil and Craig Knoblock

Meeting Days: Tuesday and Thursdays

Meeting Time: 3:30-4:50pm

Meeting Location: GFS 108

Planning has been an area of research in Artificial Intelligence for over two decades. It is concerned with the synthesis of sequences of actions (plans) that can be used by agents to achieve their desired goals. Planning involves the representation of actions and world models, reasoning about the effects of actions, and techniques for efficiently searching the space of possible plans. Planning has been used to automate a variety of tasks including robotic control, process planning, information gathering, transportation planning, experiment planning in molecular genetics, and spacecraft mission sequencing.

This will be an exciting and challenging course that will focus on the basic foundations and techniques in planning and survey a wide variety of planning systems. The class will be run as a lecture course with lots of student participation. The topics covered in the course will include:

 
		Action and Plan Representation

		Generative Planning

		Reactive Systems

		Abstraction and Hierarchical Planning

		Case-based Planning

		Machine Learning in Planning

		Extended Plan Representations

		Real-World Planning Applications

Prerequisites: CS561 - Introduction to AI

Grading: Grades will be based on homeworks, quizes, a course project, class presentation, and class participation.

Textbook: ``Readings in Planning'' by Allen, Hendler, and Tate [Allen et al. 1990].

Office Hours: immediately after class or by appointment, contact Craig Knoblock at knoblock@isi.edu or Yolanda Gil at gil@isi.edu

Student responsibilities in the class will consist of the following:

1. Presentations and Class Participation[20% of final grade]
   Class presentations that provide a detailed analysis of one of the articles listed below or other related papers. The presenter will hand out a 1-2 page analysis of the papers describing: the principal contributions of the paper, the principal weaknesses of the paper, and suggested extensions to the work.
2. Homework assignments. [20% of final grade]
3. Final exam and short quizes given in class. [30% of final grade]
4. A course project. [30% of final grade]
   A project includes any of the following:
   1. Implementing an extension to an existing planning system to enhance its capabilities.
   2. Building a new planning system.
   3. Writing a new domain for an existing planner.
   4. Anything else that you can convince us would make an interesting project.

Course Syllabus

1. • Real-World Planning Problems
   • Action and Plan Representation
   • Historical Overview (GPS, STRIPS, etc.) [Cohen and Feigenbaum1982], chapter 15,

2. • Generative Planning
     • MTC Planners
       • NOAH (Sacerdoti) [Allen et al. 1990], pages 162-170,
       • TWEAK (Chapman) [Allen et al. 1990], pages 537-558,
       • SIPE (Wilkins) [Allen et al. 1990], pages 319-335,
     • Causal-Link Planning
       • SNLP (McAllester and Rosenblitt) [McAllester and Rosenblitt1991]
       • UCPOP (Weld) [Weld1994]
     • Unified Framework
       • Planning as Refinement Search [Kambhampati et al. 1995]
   • Reactive Systems
     • Anytime Algorithms (Dean and Boddy) [Dean and Boddy1988]
     • PRS (Georgeff and Lansky) [Allen et al. 1990], pages 729-734,
   • Case-based Planning
     • CHEF (Hammond) [Allen et al. 1990], pages 655-659,
   • New Approaches
     • Approximate Planning [Ginsberg1994]
     • Planning as Constraint Satisfaction [Joslin and Pollack1996]
     • Planning by Graph Analysis [Blum and Furst1995]
     • Planning as Stochastic Search [Kautz and Selman1996]

3. • Planning Complexity
     • Joslin and Roach [Joslin and Roach1989]
     • Bylander [Bylander1992]
   • Abstraction
     • ALPINE [Knoblock1994]
     • Planning as Search [Allen et al. 1990], pages 566-578,
   • Hierarchical Planning
     • (Knoblock) [Knoblock1991]
     • (Barrett and Weld)[Barrett and Weld1994]
   • Skeletal Planning
     • Molgen [Friedland and Iwasaki1985], pages 161-180,
   • Learning Control Rules
     • SOAR [Rosenbloom et al. 1992]
     • PRODIGY [Minton and Carbonell1987], [Etzioni1990]
   • Postponing Interactions
     • Postponing Threats[Smith and Peot1993]

4. • Sensing and Incomplete Information
     • UWL [Etzioni et al. 1992]
     • (Owalski and Gini) [Olawsky and Gini1990]
   • Planning and Execution
     • IPEM, [Allen et al. 1990], pages 735-740,
     • Sage [Knoblock1995]
   • Learning from the Environment
     • Reinforcement Learning [Sutton1990]
     • Learning Action Models [Gil1994]

5. • Temporal Planning
     • DEVISER [Allen et al. 1990], pages 297-318,
     • Zeno [Penberthy and Weld1994]
   • Probabilistic Planning
     • Buridan [Kushmerick et al. 1994]
   • Decision Theory
     • Feldman and Sproull [Allen et al. 1990], pages 207-224,

6. • Planning in the Physical World
     • Robotics [Simmons1994]
     • Process Planning [Nau et al. 1995]
   • Planning for Software Agents
     • Softbots [Etzioni and Weld1994]
     • Information Gathering [Knoblock1995]
7. Project Presentations

 
• References
• About this document ...