Temporal Preference Optimization as Weighted Constraint Satisfaction

Michael D. Moffitt, Martha E. PollackAAAI 2006

Optimizing schedules where preferences exist on a spectrum—rather than as simple binary constraints—presents a significant computational challenge. This paper, originally presented at AAAI 2006, addresses this by reframing temporal preference problems as weighted constraint satisfaction tasks. The authors introduce the WeightWatcher algorithm, which leverages specialized temporal reasoning to achieve speedups of up to three orders of magnitude over previous SAT-based state-of-the-art methods.

The Problem: Beyond Binary Constraints

In automated planning and scheduling, Disjunctive Temporal Problems (DTPs) involve constraints such as "Activity A must occur 5–10 minutes after B" OR "Activity C must occur 2–4 minutes after B." Adding preferences (DTPPs) transforms this into a utilitarian optimization problem: finding the schedule that maximizes overall satisfaction.

Previous approaches, such as the ARIO system, converted these problems into SAT (Satisfiability) formulas. While SAT solvers are highly efficient for general logic, the authors argue that this encoding discards the inherent temporal structure of the problem. The goal was to develop a solver capable of handling preference complexity while utilizing specialized temporal reasoning techniques.

The WeightWatcher Algorithm and VDTP Formalism

The authors propose two primary innovations to solve these complex scheduling tasks:

  1. The Valued DTP (VDTP) Formalism: Traditionally, preferences were attached to specific time intervals. The authors demonstrate that assigning "elementary costs" to the constraints themselves is mathematically equivalent for utilitarian optimization but significantly simplifies the underlying calculus.
  2. The WeightWatcher Algorithm: Instead of a general-purpose SAT solver, WeightWatcher uses a specialized branch-and-bound algorithm operating in a meta-CSP search space. In this space, variables represent the constraints, and values represent the methods of satisfying them.
The Solve-VDTP algorithm, the core of the WeightWatcher system, utilizes branch-and-bound search with specialized temporal heuristics.

A key feature of the algorithm is the $ε$ assignment, which allows the solver to explicitly choose to violate a constraint at a specific cost. This enables the branch-and-bound search to prune expensive paths early. Furthermore, by remaining in the temporal domain, the solver can employ techniques like conflict-directed backjumping and incremental forward checking specifically tuned for time-based constraints.

Experimental Results

To evaluate performance, the authors used a standard Random DTPP Generator to control problem size, preference levels, and constraint density. The results demonstrated a dramatic improvement over ARIO (the SAT-based leader) and GAPD (a greedy approach).

Performance comparison showing WeightWatcher's scalability relative to ARIO and GAPD as the number of constraints increases.

As shown in the performance data, WeightWatcher (Iterative version) maintained high efficiency even as problem complexity scaled. On problems with 50 constraints, WeightWatcher took approximately 0.025 seconds, while ARIO required 23.8 seconds—a nearly 1,000x improvement. Additionally, WeightWatcher's performance remained relatively flat as the number of preference levels increased, whereas ARIO's performance degraded significantly.

Conclusion and Key Insights

The primary takeaway is that structure matters. While SAT solvers are powerful, they are often "blind" to the underlying geometry of time. By maintaining the problem in a meta-CSP format, WeightWatcher uses the distance graph of the schedule to prune massive sections of the search tree that a SAT solver would otherwise have to process.

Future work may involve extending this weighted approach to integrate other constraint types, such as finite-domain or conditional constraints, to address even more complex real-world scheduling scenarios.

Summary updated

BibTeX
@inproceedings{moffitt2006temporal,
  author = {Michael D. Moffitt and Martha E. Pollack},
  title = {{Temporal Preference Optimization as Weighted Constraint Satisfaction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure