Controllability of Soft Temporal Constraint Problems

In real-life temporal scenarios, uncertainty and preferences are often essential, coexisting aspects. We present a formalism where temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (strong, weak and dynamic), which have been developed for uncertain temporal problems, can be generalised to handle also preferences. We then propose algorithms that check the presence of these properties and we prove that, in general, dealing simultaneously with preferences and uncertainty does not increase the complexity beyond that of the separate cases. In particular, we develop a dynamic execution algorithm, of polynomial complexity, that produces plans under uncertainty that are optimal w.r.t. preference.