15-889 AI Planning and Learning
Syllabus - Course description and topics

SUMMARY:
In its essence, AI Planning involves the generation of sequences of actions that transform an initial situation into a desired configuration that satisfies a set of interacting goals.

Examples of planning problems include cargo transportation/logistics tasks, manufacturing production applications, robot navigation, and information navigation problems.

Questions of study in AI planning include: How to represent and change the planning action model? How to generate plans efficiently? How to produce plans of good quality? How to deal with the uncertainty of the world? How to dynamically combine planning, scheduling, and execution?

This course will cover in depth the main issues and algorithms in AI planning and learning, namely action and task modelling and representation, plan generation algorithms, heuristic learning and reuse of experience, and largely open research topics, such as dynamic integration of planning, scheduling, and execution, and multiagent planning.

Throughout the course we will address and use a variety of planning, and planning and learning systems, including Strips, Nonlin, Tweak, Prodigy, Snlp, Sipe, Flecs, GSAT, Graphplan, C-Buridan, Weaver, Prodigy/EBL, Static, Alpine, Chef, Debugger, Prodigy/Analogy, Priar, Hamlet, Quality, Observe, and Cassandra.

EVALUATION:

Students will study research papers. There will be homeworks, programming projects, and a final exam.

CONTENTS: (not necessarily in this strict order):

Part I: Deliberative planning

• Action and Task Representation
  • operators, inference rules
  • functions and variable constraints
  • abstraction hierachies
  • primary effects
  • ontological task knowledge
  • temporal and continuous data representation
• Planning algorithms
  • forward and backward search
  • linear planning
  • state-space search
  • situation calculus
  • nonlinear/least-commitment planning
  • regression planning
  • transformational planning
  • hierarchical task networks
  • graph and gsat planning
• Conditional and probabilistic planning
  • dealing with uncertainty
  • probabilistic representation
  • planning with Markov models and POMDPs
  • decision theory
  • probabilistic plan evaluation and refinement
• Heuristics and search control
  • means-ends analysis
  • efficiency, quality
  • change and selection of representation
  • statistical analysis and use of task features for heuristic and search strategy selection

• Learning opportunities
  • efficiency/domain/quality improvement
• Reuse of Experience
  • case-based planning
  • plan reuse, plan debugging
  • derivational replay of planning episodes
  • learning as the combination of interpreting, storing, and reusing experience
• Control knowledge for efficiency and quality
  • explanation-based learning
  • static analysis of domain knowledge
  • abstraction hierarchies
  • quality evaluation metrics
  • incorporation of quality feedback
  • active/autonomous exploration
  • inductive refinement of learned knowledge
• Acquiring task model
  • observation and practice
  • planning with incomplete or incorrect models
  • information gathering
  • execution and knowledge refinement

• reactive planning
• anytime algorithms / real-time search
• architectures for planning and execution
• TCA, 3T, Atlantis, RAP
• dynamic/continuous planning, scheduling, and execution
• planning to perceive

• planning and scheduling
• robot motion planning
• multiagent planning
• applications