Solving over-constrained Disjunctive Temporal problems with preferences
Bart Peintner, Michael D. Moffitt, Martha E. Pollack · 2005
We present an algorithm and pruning techniques for ef-ficiently finding optimal solutions to over-constrained in-stances of the Disjunctive Temporal Problem with Prefer-ences (DTPP). Our goal is to remove the burden from the knowledge engineer who normally must reason about an inherent trade-off: including more events and tighter con-straints in a DTP leads to higher-quality solutions, but de-creases the chances that a solution will exist. Our method solves a potentially over-constrained DTPP by searching through the space of induced DTPPs, which are DTPPs that include a subset of the events in the original problem. The method incrementally builds an induced DTPP and uses a known DTPP algorithm to find the value of its optimal so-lution. Optimality is defined using an objective function that combines the value of a set of included events with the value of a DTPP induced by those events. The key element in our approach is the use of powerful pruning techniques that dra-matically lower the time required to find an optimal solution. We present empirical results that show their effectiveness.