Publication Details

A Variable Elimination Approach for Optimal Scheduling with Linear Preferences

by Meuleau, N., Morris, R. A., and Yorke-Smith, N.

in Proceedings of CP/ICAPS'08 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems

Abstract

In many practical scheduling problems, feasible solutions can be partially ordered according to differences between the temporal objects in each solution. Often, these orderings can be computed from a compact value function that combines the local preference values of the temporal objects. However, in part because it is natural to view temporal domains as continuous, finding complete, preferred solutions to these problems is a challenging optimization task. Previous work achieves tractability by making restrictions on the model of temporal preferences, including limiting representations to binary and convex preferences. We propose an application of Bucket Elimination (BE) to solve problems with piecewise linear constraints on temporal preferences with continuous domains. The key technical hurdle is developing a tractable elimination function for such constraints. This proof of concept takes a step toward an ability to solve scheduling problems with richer models of preference than previously entertained. Further, it provides a complementary approach to existing techniques for restricted models, because the complexity of BE, while exponential in the treewidth of the problem, is polynomial in its size.

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
	Yorke-Smith, Neil	Computer Scientist