Dagstuhl Seminar 05241:

Synthesis and Planning

June 12 - June 17, 2005.
Schloss Dagstuhl, Germany

[ Organizers ] [ Description ] [ Keynote Speakers ] [ Participants ]
[ Program ]

Organizers:

Henry Kautz (University of Washington)
Wolfgang Thomas (RWTH Aachen)
Moshe Y. Vardi (Rice University)

Description:

The goal of this seminar is to bring together researchers working in two complementary fields:

(1) algorithmic techniques for the synthesis of discrete control programs, and
(2) advanced planning algorithms in artificial intelligence.

This combines a strong thread of current research in automata theory with an area of possible but so far unexplored applications.

The paradigm of two-player games (with or without termination) captures a basic situation in reactive systems: A system (control component) "plays against nature": it performs actions in an arbitrary or even hostile environment and has to guarantee certain properties of the evolving sequence of moves, carried out in alternation between system and environment.

Results of the 1960's (of Büchi, McNaughton, Rabin, and others) created a methodology for automatically synthesizing control programs from specifications of the desired global behaviour. In recent years, this algorithmic theory of infinite games produced efficient procedures for strategy construction, opened applications in model-checking, and obtained progress in generalizing the framework to infinite-state, stochastic, and timed systems.

Classical AI planning refers to single-agent deterministic domains. Currently, a more general view is being developed, covering universal planning, extension by nondeterminism and probability distributions (decision-theoretic planning), planning under sources of uncertainty, and the integration of planning and learning. In these topics, AI planning shows close links to the synthesis of reactive control programs - in fact, one can argue that the two fields have the same subject matter and are distinct only by historic conditions.

In this seminar, an attempt will be made to merge the two fields: to apply algorithmic synthesis in AI planning, and at the same time to single out interesting scenarios for further developing the automata theoretic framework. We expect that the workshop will help to increase the interaction and collaboration of the two fields, and the transfer of methodologies from one field to another.

Keynote Speakers:

Henry kautz (University of Washington)
AI Planning Tutorial
Robert Givan (Purdue University)
MDP Tutorial
John G. Thistle (University of Waterloo)
Supervisory Control Tutorial
Wolfgang Thomas (RWTH Aachen)
Synthesis Tutorial

Participants:

The list of participants can be found here.

Program:

[ Monday, June 13, 2005 ]
[ Tuesday, June 14, 2005 ]
[ Wednesday, June 14, 2005 ]
[ Thursday, June 16, 2005 ]
[ Friday, June 17, 2005 ]

Last modified: April 27, 2005

Moshe Y. Vardi (vardi@cs.rice.edu)