Thumbnail
Access Restriction
Open

Author Khatib, Lina ♦ Morris, Robert ♦ Rossi, Francesca
Source CiteSeerX
Content type Text
Publisher Morgan Kaufmann
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Local Preference ♦ Temporal Constraint Reasoning ♦ Temporal Preference ♦ Single-source Shortest Path Algorithm ♦ Preference Function ♦ Local Decision ♦ Certain Order ♦ Preference Value ♦ Preferred Solution ♦ Preference Criterion ♦ Temporal Constraint ♦ Temporal Information ♦ General Problem ♦ Complete Solution ♦ Constraint-based Temporal Reasoning ♦ Polynomial Time
Description 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2001-01-01