# Reasoning On Interval And Point-Based Disjunctive Metric Constraints In Temporal Contexts

Federico Barber FBARBER@DSIC.UPV.ES
Dpto. de Sistemas Informáticos y Computación Universidad Politécnica de Valencia Camino de Vera s/n, 46022 Valencia, Spain

## Abstract

We introduce a temporal model for reasoning on disjunctive metric constraints on intervals and time points in temporal contexts. This temporal model is composed of a labeled temporal algebra and its reasoning algorithms. The labeled temporal algebra defines *labeled* disjunctive metric pointbased constraints, where each disjunct in each input disjunctive constraint is univocally associated to a label. Reasoning algorithms manage labeled constraints, associated label lists, and sets of mutually inconsistent disjuncts. These algorithms guarantee consistency and obtain a minimal network. Additionally, constraints can be organized in a hierarchy of alternative temporal contexts. Therefore, we can reason on context-dependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent non-binary constraints, such that logical dependencies on disjuncts in constraints can be handled. The computational cost of reasoning algorithms is exponential in accordance with the underlying problem complexity, although some improvements are proposed.

## 1. Introduction

Two main lines of research are commonly recognized in the temporal reasoning area. The first approach deals with reasoning about temporal constraints on time-dependent entities. The goal is to determine what consequences (T) follow from a set of temporal constraints, "{TemporalConstraints}|=T?", or to determine whether a set of temporal constraints is consistent, with no assumptions about properties of temporal facts. The second approach deals with reasoning about change, events, actions and causality. Here, the goal is to obtain the consequent state from a set of actions or events which are performed on an initial state: "[Si, {A1, A2*, ..., A*n}]|= Sj?". Both these approaches constitute active fields of research with applications in several artificial intelligence areas such as reasoning about change, scheduling, temporal planning, knowledge-based systems, natural language understanding, etc. In these areas, time plays a crucial role, problems have a dynamic behavior, and it is necessary to represent and reason about the temporal dimension of information.

In this paper, we deal with the first of these approaches. Our goal is reasoning on qualitative and quantitative constraints between intervals or time-points in temporal contexts. Moreover, special cases of non-binary constraints are also managed. These tasks are pending issues in the temporal reasoning area, as well as important features to facilitate modeling of relevant problems in this area
(including planning, scheduling, causal or hypothetical reasoning, etc.).

Several temporal reasoning models have been defined in the literature, with a clear trade-off between representation expressiveness and complexity of reasoning algorithms. *Qualitative Point* Algebra (PA) (Vilain, Kautz & Van Beek, 1986) is a limited subset of interval-based models. Interval