Temporal Reasoning with Layered Preferences

Temporal representation and temporal reasoning is a central in Artificial Intelligence. The literature is moving to the treatment of "non-crisp" temporal constraints, in which also preferences or probabilities are considered. However, most approaches only support numeric preferences, while, in many domain applications, users naturally operate on "layered" scales of values (e.g., Low, Medium, High), which are domain- and task-dependent. For many tasks, including decision support, the evaluation of the minimal network of the constraints (i.e., the tightest constraints) is of primary importance. We propose the first approach in the literature coping with layered preferences on quantitative temporal constraints. We extend the widely used simple temporal problem (STP) framework to consider layered user-defined preferences, proposing (i) a formal representation of quantitative constraints with layered preferences, and (ii) a temporal reasoning algorithm, based on the general algorithm Compute-Summaries, for the propagation of such temporal constraints. We also prove that our temporal reasoning algorithm evaluates the minimal network.