ICAPS 2005 tutorial
Hard and soft temporal constraint techniques for
scheduling problems with preferences and uncertainty
Tutorialists:
Francesca Rossi, University of Padova, Italy
K. Brent Venable, University of Padova, Italy
Goals:
This tutorial is intended to describe the main
approaches to soft constraints, and how to use
such techniques to model and solve scheduling problems.
In particular, we will focus on the presence of preferences
and uncontrollable events in such scheduling problems.
Intended audience:
Researchers in the area of planning and scheduling
who desire to know more about how soft constraint
techniques can be useful in their context.
Contents:
1. Hard and soft constraints:
-- main concepts
-- semiring-based approach to soft constraints
-- properties of classes of soft constraints
-- main solving techniques
2. Temporal constraints with preferences
-- addition of preferences to temporal constraints
-- tractable classes and polynomial solving algorithms
-- disjunctive constraints
3. Preferences and uncertainty in temporal constraints
-- optimal controllability notions
-- checking algorithms and complexity
-- execution algorithm
Resumes:
Francesca Rossi is currently a full professor at the Department of
Pure and Applied Mathematics of the University of Padova, Italy.
Her main research interests are in the areas of
constraint reasoning and constraint programming, with
particular interest on preferences, soft constraints,
preference aggregation, and uncertainty. In the past,
she has also worked on logic programming, Petri nets, concurrency
and parallelism, semantics, hypergraph grammars.
She has published about 80 papers in international
conferences and journals, and she has edited five books.
She has given tutorials on soft constraints at AAAI 2000, ECAI 2000,
HICSS 34 in 2000, and CP 2001.
K. Brent Venable is currently a Ph.D. student at the University of Padova
in Italy. Her main research interests are in the area of
soft constraints and temporal reasoning, preference aggregation,
and uncertainty. She has published 7 articles in international
conferences. Her Ph.D. is supervised by F. Rossi and
it is cheduled to finish in the first months of 2005.
Summary:
This tutorial will describe the main approaches to modelling
and solving soft constraints, and will show how to use
soft constraint techniques to model and solve scheduling problems with
preferences and uncertainty.
In particular, we will focus on scheduling problems that can be described
by quantitative temporal constraints where each event duration
can be associated to a level of preferences, and where
some events may be uncontrollable.
Then we will introduce preferences in uncertain scenarios,
we will define suitable notions of optimal controllability
and corresponding checking algorithms,
and we will show that the addition of preferences does not make the
problems more difficult.
The tutorial is intended for
researchers in the area of planning and scheduling
who desire to know more about how soft constraint
techniques can be useful in their context.
Although the tutorial is self-contained,
the attendance of the tutorial by N. Muscettola and M. Pollack
is encouraged to get a more complete description of
the current activitiees in the area of temporal
constraints reasoning for planning and scheduling.