Temporal Constraint Reasoning With Preferences

Abstract

A number of reasoning problems involving the manipulation of temporal information can be viewed as implicitly inducing an ordering of decisions involving time (associated with durations or orderings of events) on the basis of preferences. For example, a pair of events might be constrained to occur in a certain order, and, in addition, it might be preferable that the delay between them be as large, or as small, as possible. This paper explores problems in which a set of temporal constraints is specified, each with preference criteria for making local decisions about the events involved in the constraint. A reasoner must infer a complete solution to the problem such that, to the extent possible, these local preferences are met in the best way. Constraint-based temporal reasoning is generalized to allow for reasoning about temporal preferences, and the complexity of the resulting formalism is examined. While in general such problems are NP-complete, some restrictions on the shape of the preference functions, and on the structure of the set of preference values, can be enforced to achieve tractability. In these cases, a generalization of a single-source shortest path algorithm can be used to compute a globally preferred solution in polynomial time.