Algorithms for constraint-based temporal reasoning with preferences.

Abstract

Recent planning and scheduling applications have successfully used the Temporal Constraint Satisfaction Problem (TCSP) to model events and temporal constraints between them. Given a TCSP, the task is to find a schedule or a set of schedules that satisfy all constraints in the problem. A key limitation of TCSPs and related formulations is that they only represent hard constraints---constraints that are either satisfied or not. Many real-world situations are better modeled with soft constraints---constraints that are satisfied to a particular degree. Soft constraints allow knowledge engineers to express that some situations are preferable to others. This dissertation augments TCSPs with soft constraints and presents algorithms that find optimal solutions. We represent soft constraints by augmenting hard constraints with a preference function that maps every valid solution to a local preference value that describes how well the constraint is satisfied. We then aggregate the local preference values to attain the value of the entire solution. We studied two aggregation functions, the <italic>sum</italic> and <italic> minimum</italic> functions. We developed a set of algorithms that optimize with respect to both aggregation functions when preferences are added to each of two common TCSP subproblems: the Simple Temporal Problem (STP) and the Disjunctive Temporal Problem (DTP). We analyzed each algorithm experimentally on random problems and showed that the algorithms for DTPs with preferences integrate practically into a planning and scheduling application called Autominder. Before integration, we modified the algorithms to handle <italic>dynamic</italic> DTPs with preferences, equipping them to solve a series of related DTPs with preferences faster than solving them individually. In many real-world problems, finding the optimal solution is not necessary---it is more important to find near-optimal solutions quickly. Consequently, our focus was on maximizing anytime performance. We achieved this goal, showing empirically that our algorithms quickly found high-quality solutions even for large problems. For all algorithms, we showed that the cost of adding preferences was minimal, achieving our overall goal of making the use of TCSPs with preferences practical in all situations where hard-constraint TCSPs apply.