Temporal Preference Optimization as Weighted Constraint Satisfaction

Abstract

We present a new efficient algorithm for obtaining utili-tarian optimal solutions to Disjunctive Temporal Problems with Preferences (DTPPs). The previous state-of-the-art system achieves temporal preference optimization using a SAT formulation, with its creators attributing its performance to advances in SAT solving techniques. We depart from the SAT encoding and instead introduce the Valued DTP (VDTP). In contrast to the traditional semiring-based formal-ism that annotates legal tuples of a constraint with prefer-ences, our framework instead assigns elementary costs to the constraints themselves. After proving that the VDTP can ex-press the same set of utilitarian optimal solutions as the DTPP with piecewise-constant preference functions, we develop a method for achieving weighted constraint satisfaction within a meta-CSP search space that has traditionally been used to solve DTPs without preferences. This allows us to directly in-corporate several powerful techniques developed in previous decision-based DTP literature. Finally, we present empirical results demonstrating that an implementation of our approach consistently outperforms the SAT-based solver by orders of magnitude.