Low-cost Addition of Preferences to DTPs and TCSPs

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Uncertainty

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 previous algorithms for solving TCSPs and Simple Temporal Problems with Preferences (STPPs), in both cases using techniques for projecting and solving component sub-problems. We show that adding preferences to DTPs and TCSPs requires only slightly more time than corresponding algorithms for TCSPs and DTPs without preferences. Thus, for problems where DTPs and TCSPs make sense, adding preferences provides a substantial gain in expressiveness for a marginal cost.