On the modelling and optimization of preferences in constraint-based temporal reasoning

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.