Optimizing Temporal Preferences

Contents

This paper focuses on problems where the objective is to maximize a set of local preferences for times at which events occur. Previous work by the authors and others has resulted in a formalization of a subclass of these problems into a generalization of Temporal Constraint Satisfaction Problems, using a semi-ring as the underlying structure for reasoning about preferences. A tractable strategy for combining and comparing preferences was proposed, wherein computing global preferences consists of taking the minimum of the component preference values. This strategy, which we here dub the "weakest link optimization" (WLO) strategy, is a coarse method for comparing solutions, and can easily be demonstrated to have drawbacks. To compensate for these limitations, we make WLO more robust by combining it with a process that involves iteratively committing to temporal values in the set of optimal solutions, and concomitantly fixing the preference value for the projection of the solution to the local preference. We prove the value of this strategy by showing that the resulting solutions are also Pareto optimal.