Publication Details

Multi-Criteria Optimization of Temporal Preferences

by Moffitt, M. D. and Peintner, B. and Yorke-Smith, N

in Proceedings of CP’06 Workshop on Preferences and Soft Constraints pp. 79-93,

Abstract

We propose a new framework for multi-criteria optimization in constraint-based temporal reasoning. Motivated by a real-world domain, we augment one of the most expressive current formalisms, the Disjunctive Temporal Problem with Preferences (DTPP), in two crucial ways. First, we model optimality criteria as being attributed to subsets of soft constraints, in contrast to the direct mapping to individual constraints common in previous formulations. Second, using Multi-Attribute Utility Theory (MAUT) we construct an objective function that considers not only the individual values of these separate criteria, but also their mutual interactions. The increased expressive power of the Multi-Criteria DTPP (MC-DTPP) allows us to model a broad range of complex preferential optimization problems that existing Temporal Constraint Satisfaction Problems cannot (for instance, capturing the whole Pareto frontier). We propose two algorithms for finding optimal solutions to an MC-DTPP, and demonstrate the computational efficiency of reasoning with MC-DTPPs on a suite of randomized benchmarks and a new collection of real-world scheduling instances.

Electronic Copies

Adobe PDF

BibTeX

EndNote

Associated Projects

Cognitive Assistant that Learns and Organizes As part of DARPA’s Personalized Assistant that Learns (PAL) program, SRI and team members are working on developing a next-generation "Cognitive Agent that Learns and Organizes" (CALO).

AIC Personnel

	Name	Title	E-mail
	Moffitt, Michael D	Student Associate
	Peintner, Bart	Sr. Computer Scientist
	Yorke-Smith, Neil	Computer Scientist