Publication Details

Controllability of Soft Temporal Constraint Problems

by Rossi, F. and Venable, K. B. and Yorke-Smith, N.

in Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP’04) pp. 588–603,

Abstract

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.

Electronic Copies

Adobe PDF

BibTeX

EndNote

AIC Personnel

	Name	Title	E-mail
	Yorke-Smith, Neil	Computer Scientist