Partial Constraint Satisfaction of Disjunctive Temporal Problems.
Michael D. Moffitt, Martha E. Pollack · 2005
We present a method for finding optimal partial solutions to overconstrained instances of the Disjunctive Temporal Prob-lems (DTP). The solutions are optimal in that they satisfy a maximal number of constraints. While partial constraint sat-isfaction (PCS) has been commonly applied to finite-domain CSPs, its application in this setting is of particular interest, as temporal problems are traditionally solved using a meta-CSP approach, in which the constraints of the original problem be-come the variables of the meta-level problem. We show how to adopt nearly all previous pruning techniques in DTP solv-ing for use with PCS, and provide results demonstrating their effectiveness. We also introduce an incremental technique that leads to substantially improved performance.