Lecturers & Course Abstracts


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

Dr. Hector Geffner

Depto de Computacion - Universidad Simon Bolivar
Caracas, Venezuela.

Hector Geffner got his Ph.D in UCLA with a dissertation that was co-winner of the 1990 Association for Computing Machinery (ACM) Dissertation Award. Then he worked as Staff Research Member at the IBM T.J. Watson Research Center in NY, USA, for two years before returning to the Universidad Simon Bolivar, in Caracas, Venezuela, where he currently teaches.
Hector Geffner has been a member of the editorial board of the Journal of Artificial  Intelligence Research, has given tutorials at AAAI and IJCAI, and has  served in the program committee of the major AI conferences. He is the  author of the book ``Default Reasoning: Causal and Conditional Theories''  published by MIT Press in 1992.
He is interested in models of reasoning,  action, and learning, and in the development of high level tools for  modeling and problem solving.

Heuristic Search Planning: Models, Heuristics, and Algorithms

We consider the problem of planning in a general setting where actions can be deterministic, non-deterministic, or probabilistic,  and their effects can be fully or partially observable. The task is to obtain  a  plan or closed-loop controller  given a suitable description  of the initial situation, actions, sensors,  and goals.
We approach this problem by distinguishing three elements:
- models (that help us to make the tasks mathematically precise)
- languages (that help us to state problems in a convenient way), and
- algorithms (that compute the desired solutions: plans, controllers, etc.)
We show that the models - State Models, Markov Decision Processes (MDPs) and Partially Observable MDPs - can be conveniently described using  suitable logical action languages, and in many cases can be solved  by search algorithms that combine ideas from heuristic search and  dynamic programming.
We make then particular emphasis on heuristic search planning in the "classical" setting (where information is complete and  actions are deterministic) and describe the ideas underlying some of the currently most  powerful domain-independent planners  such as Graphplan, HSP, and FF.

Relevant Papers

These and a few other relevant papers available at www.ldc.usb.ve/~hector

Slides of the course:        Part 1;       Part 2


 

Dr. Malik Ghallab

  LAAS-CNRS,
  France

Planning with time and resources

This course covers planning with explicit time  and resources. Possible representations for actions and domains  involving time and resources will be presented as well as specific  algorithms for handling them. They will be illustrated through few  planners that handle explicit time and or resources.

Slides of the course:        Ghallab.pdf


 

Prof. Subbarao Kambhampati

   Dept. of Computer Science,
   College of Engineering and Applied Sciences
   Arizona State University, Tempe Arizona  - USA

Subbarao Kambhampati is a Professor of Computer Science and Engineering at Arizona State University, where he directs the YOCHAN research group (rakaposhi.eas.asu.edu/yochan.html). After formative education at Peddapuram, he received his bachelors degree in electrical engineering from Indian Institute of Technology, Madras, and M.S. and Ph.D. degrees in Computer Science from University of Maryland, College Park. He has published over eighty technical articles on planning, learning, CSP, information integration and related areas of AI. He was a 1994 NSF Young Investigator and a 1996 AAAI invited speaker. He has taught courses and has published several tutorial articles on AI planning, and co-chaired the 2000 AI Planning and Scheduling conference.

A Unifying and Brand-Name-Free Introduction to Planning

Although planning is one of the oldest research areas of AI, recent years have brought many dramatic advances in both its theory and practice. On the theory side, we now understand the deep connections between AI planning, heuristic search, constraint satisfaction, logic and operations research. On the practical side, we have effective ways of capturing and using domain-specific control knowledge, and have planners that are capable of synthesizing plans with hundred or more actions in minutes. These are undoubtedly exciting times for planning research.  For newcomers to the field, however, all this excitement does present special problems of trying to figure out foundational ideas scattered among a welter of brand-name algorithms.
The aim of my lecture(s) will be to provide a comprehensive overview of the field, placing both the traditional ideas and the recent advances in a unified perspective. I will isolate and present a brandname-free collection of foundational ideas underlying the old and new crops of planning algorithms. I will then discuss how these can be mixed and matched to develop planning algorithms offering a broad spectrum of tradeoffs.
While my initial emphasis will be on planning algorithms for deterministic domains, I will also briefly discuss the extensions of the essential ideas to domains with metric and temporal constraints, partially observable states as well as stochastic dynamics.  The lectures should be accessible to anyone with basic computer science and AI background.

Preliminary material for the course will be available at URL rakaposhi.eas.asu.edu/planning-tutorial.

Supplementary material (roughly in order of importance):

Slides of the course:        Kambhampati.pdf


 

Dr. Derek Long

University of Durham, UK

Derek Long is lecturer in Computer Science at the University of Durham, UK. He  received his DPhil at the Programming Research Group, Oxford University, and  carried out research in reasoning in AI, planning and problem-solving as  lecturer in Computer Science at University College London before joining  Durham. He is co-founder, with Maria Fox, of the Durham Planning Group.
Together with Maria Fox he developed the STAN planning system and the TIM  domain analysis system, which have participated very successfully in two AIPS  Planning Competitions.

Pre-processing and Domain Analysis

Planning systems can be seen as specialised programming environments, intended  to support the solution of a particular class of problems. Seen in this light,  the task of building a planning domain description is equivalent to the task of writing a program. As with the other programming languages, it is the  abstractions supplied by the language as basic constructs from which to build  the programs that determines how powerful and how useful the language is.  The  more the language supports abstractions which emphasise domain-knowledge,  rather than planning and problem-solving knowledge, the easier it is likely to  be for domain-specialists to encode complex domains. Unfortunately, planners  need control knowledge which can often be tedious to encode, or alien to the  view that a domain-specialist has of a domain.
In order to simplify and enrich  the information available to a planning system, domain analysis and  pre-processing have been proposed and explored. These techniques are intended  to extract from a declarative and domain-oriented description forms of  control-knowledge which are appropriate to a domain. This ranges from  identification of the basic characteristics of the behaviours of objects in a  domain through to the identification of specialised sub-problems for which  specific control-knowledge or problem-solving behaviour might be appropriate.  In addition, domain-analysis can play a critical role in the development of a  complex domain-description, providing new insights into a domain encoding for  the programmer, allowing easier debugging and more accurate modelling. This  course will explore these roles and examine the directions in which this area  of planning research is developing.

Materials

A very useful collection of papers illustrating directions in this field can be found in the working notes of the AIPS2000 Workshop on Analysing and Exploiting Domain Knowledge for Efficient Planning:
http://www.dur.ac.uk/CompSci/research/EVENTS/workshop.html

Slides of the course:        Part 1;        Part 2;        Part 3.


 

Prof. Dana Nau

University of Maryland, USA.

Dana Nau is a professor at the University of Maryland, in the Department of Computer Science and the Institute for Systems  Research.  His research interests include AI planning and searching,  and computer-integrated design and manufacturing.
He received his  Ph.D. from Duke University in 1979, where he was a National Science  Foundation (NSF) graduate fellow.  He has more than 200 technical publications (for details, see http://www.cs.umd.edu/users/nau).  He  has received an NSF Presidential Young Investigator award, the ISR  Outstanding Faculty award, and several ``best paper'' awards.  He is co-author of the computer program that won the 1997 World Bridge  Computer Challenge, and he is a Fellow of the American Association  for Artificial Intelligence (AAAI).

Ordered Task Decomposition: Theory and Applications

AI planning is finally becoming powerful enough to be useful for a  variety of  real-world planning problems.  This creates a great  potential for synergy between theory and practice. By examining the requirements of real-world planning problems, we can develop better  theories of planning -- and from these improved theories of planning,  we can develop better planning systems for real-world applications.
One example of this is a new variant of HTN planning called Ordered  Task Decomposition.  I will  describe the basic principles of Ordered  Task Decomposition, including the SHOP planning algorithm.  I will  compare and contrast it to "classical" AI planning techniques, and  will describe several applications to complex real-world planning  domains, including computer bridge, automated manufacturing, and
evacuation planning.

Primary materials:

Related work: Slides of the course:        Part 1;       Part 2.


 

Prof. Bernhard Nebel

Albert-Ludwigs-Universitaet Freiburg, Germany.

Bernhard Nebel is professor in the Department of Computer Science at Albert-Ludwigs-University Freiburg, Germany, and director of the research lab on the foundations of AI. He received a Ph.D. degree (Dr. rer. nat) from the University of Saarland in 1989 for his work on knowledge representation and belief revision.
He is a member of the IJCAII board of trustees and a member of the graduate school of Human and Machine Intelligence at Albert-Ludwigs-University. Among other professional services, he served as the Program Co-chair for the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR'92) and will serve as the Program Chair for the 17th International Joint Conference on Artificial Intelligence (IJCAI'01). In addition, he is a member of the editorial boards of Artificial Intelligence and AI Communication.
His research interests include knowledge representation and reasoning with an emphasis on semantics, algorithms, and computational complexity, in particular in the areas of description logics, temporal and spatial reasoning, constraint-based reasoning, planning, belief revision, and robotics.

Computational Complexity of Planning and Expressiveness of Planning Formalisms

This course focuses on two important theoretical properties of planning, namely, on the computational complexity of the planning problem for particular formalisms and of the expressiveness of  planning formalisms. Action planning is a challenging combinatorial problem. Depending on the formalism, the problem of decidingplan existence can be undecidable, EXPSPACE-complete, PSPACE-complete, NP-complete, or even decidable in polynomial time.
The most common setting -- propositional STRIPS planning -- is PSPACE-complete for arbitrary long plans and NP-complete for `short' plans. Interestingly, this complexity result holds for a number of different planning formalisms, which seems counter-intuitive from an algorithmic point of view. For instance, existing planning algorithms can handle basic STRIPS quite well. However, generating plans for planning tasks with conditional effects, general logical formulas as preconditions, and partial state description seems to be much more difficult, despite the fact the plan existence is still PSPACE-complete .
In order to make distinctions between planning formalisms with different expressiveness but identical computational complexity, we will introduce the notion of `compilability' and prove that some  planning formalisms are indeed expressively more powerful than, e.g., basic STRIPS -- even if the complexity of the plan existence problem is identical. These resultsimply, e.g., that the transformation proposed by Knoblock and others is optimal -- provided plans may grow only linearly.
Prerequisites for this course are a basic understanding of action planning and some understanding of computational complexity, i.e., it should be clear what the term `NP-complete' means.

Literature:

Tom Bylander, The Computational Complexity of Propositional STRIPS Planning, Artificial Intelligence, Volume 69, 1994, pp. 165 - 204.
B. Nebel, On the Compilability and Expressive Power of Propositional Planning Formalisms, Technical Report No. 101, Institut für Informatik, Albert-Ludwigs-Universität Freiburg, 1998 (accepted for publication in JAIR).

Slides of the course:        Part 1;       Part 2;        Part 3.


 

Dr. Paolo Traverso

ITC-IRST  Trento, Italy.

Paolo Traverso is currently the Head of the Automated Reasoning Systems Division at ITC-IRST (Centro per la Ricerca Scientifica e Tecnologica),  Trento, Italy.
Since 1989, he is a researcher at IRST, where he has been working in  both research and technology transfer projects.  He has been involved in industrial projects aiming at the application  of Model Checking to the formal verification of software, especially  in the area of safety critical systems (such as railways interlocking  systems, automatic train protection systems, space applications, industrial  controllers).
His main research interests are "Planning as Model Checking",  and, more in general, conditional and iterative planning, planning under  partial observability, planning for extended goals, reactive planning,  and the integration of action, perception and reasoning.

Planning as Model Checking

The lecture will provide an introduction to the "Planing as Model Checking" paradigm. The idea underlying "Planning as Model Checking" is that planning problems can be solved model-theoretically. Planning domains are formalized as semantic models.
Properties of planning domains (e.g. goals as sets of states to be reached)  are formalized as temporal formulas. The most important features of the  proposed approach are: Some of the implementations of "Planning as Model Checking" rely heavily on existing work in the context of finite-state program verification and in particular on the work on Symbolic Model Checking. One of the most relevant features of Symbolic Model Checking is the use of symbolic data structures called "Ordered Binary Decision Diagrams" (OBDDs) to represent and manipulate efficiently sets of states and actions.
The lecture will be organized as follows:
  1. We start with a very brief introduction to Model Checking.
  2. We show how planning problems can be stated as Model Checking problems.
  3. We propose a formalization that can be used to tackle  various planning problems.
  4. We discuss how planning as model checking can be implemented  efficiently with OBDDs.
Basic Literature on Planning as Model Checking: Further readings: Basic Literature on Model Checking: Slides of the course:        Traverso.ps.gz