Adding Preferences to Temporal Constraint Satisfaction Problems

Recent planning and scheduling applications have successfully used the
Temporal Constraint Satisfaction Problem (TCSP) formalism for reasoning
about events and temporal constraints between them. Given a TCSP, the
task is to find a schedule or a set of schedules that satisfy all
constraints in the problem. In this talk, I will present our recent work
on addressing two limitations of TCSPs in the context of planning
applications: hard bounded constraints often do not match reality; and
it is difficult for a planning system to recover if any constraint is
violated during plan execution. To address both limitations, we extended
the TCSP to include preferences, which allow constraints to be satisfied
to different degrees. I will describe our Autominder planning
application, review the basics of TCSPs, show how to extend them with
preferences, and describe two of the algorithms we have developed to
find optimal schedules for a given TCSP with Preferences.