OSB > Neil Yorke-Smith > Research > Publications

Controllability of Soft Temporal Constraint Problems

Rossi, F., Venable, K. B., and Yorke-Smith, N. Controllability of Soft Temporal Constraint Problems. Proceedings of CP'04, Toronto, Canada, September 2004. LNCS 3258, pp. 588-603, Springer, 2004.

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.

This paper is a revised version of that at CP'03 Online'03 Workshop, which extends the STPPU framework introduced at IJCAI'03.

Postscript (67K) | PDF (188K) | Bibtex entry

©2004 Springer-Verlag

Conference homepage



Research | Home