Lecturers and Courses

The Summer School Program features eight courses that explore evolving techniques on AI Planning. Each tutorial is taught by experienced scientists and practitioners in AI planning.


Michael Beetz
Plan-based Control of Autonomous Robots

In recent years, autonomous robots, including XAVIER, MARTHA [1], RHINO [3,2], MINERVA, and REMOTE AGENT, have shown impressive performance in longterm demonstrations. In NASA's Deep Space program, for example, an autonomous spacecraft controller, called the Remote Agent [5], has autonomously performed a scientific experiment in space. At Carnegie Mellon University XAVIER [6], another autonomous mobile robot, has navigated through an office environment for more than a year, allowing people to issue navigation commands and monitor their execution via the Internet. In 1998, MINERVA [7] acted for thirteen days as a museum tourguide in the Smithsonian Museum, and led several thousand people through an exhibition.

These autonomous robots have in common that they perform plan-based control in order to achieve better problem-solving competence. In the plan-based approach robots generate control actions by maintaining and executing a plan that is effective and has a high expected utility with respect to the robots' current goals and beliefs. Plans are robot control programs that a robot cannot only execute but also reason about and manipulate [4]. Thus a plan-based controller is able to manage and adapt the robot's intended course of action -- the plan -- while executing it and can thereby better achieve complex and changing tasks. The plans used for autonomous robot control are often reactive plans, that is they specify how the robots are to respond in terms of low-level control actions to continually arriving sensory data in order to accomplish their objectives. The use of plans enables these robots to flexibly interleave complex and interacting tasks, exploit opportunities, quickly plan their courses of action, and, if necessary, revise their intended activities.

In this course we present an overview of recent developments in the plan-based control of autonomous robots. We identify computational principles that enable autonomous robots to accomplish complex, diverse, and dynamically changing tasks in challenging environments. These principles include plan-based high-level control, probabilistic reasoning, plan transformation, and context and resource-adaptive reasoning. We will argue that the development of comprehensive and integrated computational models of plan-based control requires us to consider different aspects of plan-based control -- plan representation, reasoning, execution, and learning -- together and not in isolation. This integrated approach enables us to exploit synergies between the different aspects and thereby come up with simpler and more powerful computational models.

Bibliography

Course materials (Section 1, Postscript, 9MB) (Section 2, Postscript, 10MB) (Section 3, Postscript, 2MB) (Section 4, Postscript, 1MB)


Susanne Biundo
Planning history and Overview

The course gives a comprehensive introduction to the field of AI Planning. It reviews the various principal planning methods together with their underlying domain representations and outlines present and future application areas.

After that, developments towards a systematic combination and integration of different planning methods as well as the integration and use of techniques from related fields are presented. The course ends with a historical overview over this traditional yet rapidly developing and exciting sub-field of AI.

Course materials (revised - as delivered, not as in handout) (PDF, 1.5MB)


Craig Boutilier
Planning under Uncertainty with Markov Decision Processes

Markov decision processes (MDPs) have become standard models for sequential decision problems involving uncertainty within the planning and probabilistic reasoning communities. The aim of the course is:

  1. to provide a brief introduction to Markov decision processes;
  2. to survey some of the representational and computational methods for solving MDPs that have been developed in the AI community in recent years.

The focus will be on techniques that draw on or are related to planning methods in deterministic settings (as opposed to those based on machine learning). Representations to be discussed include propositional methods (e.g., probabilistic STRIPS, dynamic Bayesian networks) first-order representations, and computationally-motivated representations such as BDDs. Computational techniques include regression, abstraction, and decomposition methods that rely on these specific representations. The course will deal primarily with fully observable MDPs, though the extension to partially observable MDPs will be discussed briefly.

Course materials (part 1 Powerpoint, 0.6MB ) (part 2 Powerpoint, 0.9MB )


Brian Drabble
Scheduling and planning

Scheduling is the problem of assigning a set of actions/tasks to a set of resources (machines, workman, trucks) subject to a set of constraints. Examples of scheduling constraints include deadlines (e.g., job i must be completed by time t), resource capacities (e.g., there are only four drills), precedence constraints on the order of tasks (e.g., a piece must be sanded before it is painted), and priorities on tasks (e.g., finish job j as soon as possible while meeting the other deadlines). Planning is the problem of producing a sequence of actions (operator instances), each of which is legal in its starting world state, which takes the initial state to a goal state (or series of goal states). Traditionally, scheduling and planning are viewed as separate research areas. However, this is a rather simplistic view as many decisions in planning impact on scheduling and vice versa. For example, if a planner is faced with the choice of welding or gluing a series of components together, it would be useful to know that the welding machines are all currently unavailable due to maintenance. Alternatively, if scheduler losses all the the welding machines due to breakdowns, then knowing that the components could be glued together would help overcome the problem.

In this course we will present an overview of recent developments in intelligent scheduling and optimization and the ways in which these systems and algorithms can be integrated with planners to develop a comprehensive approach to the planning and scheduling problem. The overview will provide details of several scheduling techniques/systems and describe their advantages over existing approaches. These include the ability to reduce scheduling times from hours to minutes and to increase the size of the problem that can be handled by as much as 50 fold. Demonstrations of several constraint based systems will be provided together with case studies from areas including shipbuilding, aircraft assembly and CD manufacturing.

[PLANET has been requested to withdraw these materials]


Craig Knoblock
Planning and the Web

There are many interesting planning problems that arise in the context of gathering and integrating information from the Web. This course will cover a variety of planning techniques, systems, and applications that relate to this problem. These topics include query planning, planning for information gathering, interactive planning using contraint propagation, and the efficient execution of information gathering plans.

Course materials (part 1 PDF, 1.2 MB [ author's site]) (part 2 PDF, 1.5MB [ author's site])


Philippe Laborie
Planning with resources

Course outline | also as .doc

A resource can be defined as any substance or (set of) object(s) whose cost or available quantity induce some constraint on the operations that use it. A resource can for instance represent a machine which can only perform one operation at a time, the fuel contained in the tank of a plane or the workforce or the money available to perform a given project. In the context of planning with resources, a solution plan is defined as a plan that achieves the goals while allocating resources to operations in such a way that all resource constraints are satisfied. As in the real life resources often have a limited availability, it's not surprising that resource constraints play a key role in practical planning.

The first part of the course will provide a definition of resources in the context of planning and review the state of the art of planning with resources. The second part will focus on one of the most promising approach for dealing with resources in planning which relies on the application of constraint-based techniques in Partial-Order or Hierarchical Task Network planning.

Course materials (Powerpoint, 8MB)


Maria Fox
Planners Performance Evaluation

Planning systems can be evaluated in a number of different ways: by analysis of their formal properties, by empirical comparison with other similar systems, by consideration of their scaling behaviour, in terms of the time/quality trade-offs they make, by ablation studies to test the added value of a new technique or heuristic, and so on. Most conference and journal papers contain some such analysis in order to substantiate the authors' claims about the planning systems described.

Since the advent of the international planning competitions in 1998 there has been a considerable amount of data available for use in empirical comparisons. There is an increasing supply of benchmark problems and there are data sets available that enable comparisons to be made that are stable and can be repeated and verified.

It is nevertheless still rare to see evidence of a scientific approach to evaluation in the literature, and common to find conclusions drawn about the superiority of one system over another on the bases of differences that might be statistically insignificant. Often the data sets used to draw such conclusions consist of only a handful of problem instances from the ancient archives of planning (blocks world and rocket, for example). This seems disappointing when the scope for more meaningful analyses is increasing all the time.

This course will start by outlining the stages of a scientific approach to evaluation of a data set. We then proceed to examine a large collection of data - a subset of that obtained from the 2002 international planning competition. The course will introduce (or remind students about) some simple statistical tests that can be used to determine the significance of a feature of a data set. We will then proceed to apply some of these tests to the competition data and see what conclusions can justifiably be drawn.

Course materials (revised - as delivered, not as in handout) (Part 1) (Part 2)


Martha Pollack
Planning and execution

Plans are made to be executed, by an automated system, by a human being, or by a combination of a machine and a person. Moreover, most plans are executed in dynamic, uncertain environments, in which the beliefs and goals that motivated the original planning problem are subject to change. The techniques for planning and execution to be considered in this course include the following:

Course materials (revised - as delivered, not as in handout) (lecture 1. PDF, 0.4MB) (lecture 2. PDF, 0.4MB)