Dagstuhl Seminar 05241:
Synthesis and Planning
June 12 - June 17, 2005.
Schloss Dagstuhl, Germany
The goal of this seminar is to bring together researchers working in two
This combines a strong thread of current research in automata theory
with an area of possible but so far unexplored applications.
- (1) algorithmic techniques for the synthesis of discrete control
- (2) advanced planning algorithms in artificial intelligence.
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
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.
The list of participants can be found
Last modified: April 27, 2005
Moshe Y. Vardi