Low-cost addition of preferences to DTPs and TCSPs
Bart Peintner, Martha E. Pollack · 2004
We present an efficient approach to adding soft constraints, in the form of preferences, to Disjunctive Temporal Problems (DTPs) and their subclass Temporal Constraint Satisfaction Problems (TCSPs). Specifically, we describe an algorithm for checking the consistency of and finding optimal solutions to such problems. The algorithm borrows concepts from pre-vious algorithms for solving TCSPs and Simple Temporal Problems with Preferences (STPPs), in both cases using tech-niques for projecting and solving component sub-problems. We show that adding preferences to DTPs and TCSPs re-quires only slightly more time than corresponding algorithms for TCSPs and DTPs without preferences. Thus, for problems where DTPs and TCSPs make sense, adding preferences pro-vides a substantial gain in expressiveness for a marginal cost.