Reasoning with non-convex time intervals
Lina Al-Khatib · 1995
This dissertation focuses on the representation and reasoning about qualitative temporal relations between intervals. Traditional interval-based time representations of events assume interval convexity, i.e., intervals are uninterrupted. This assumption makes it difficult to represent the common sense notion of events that are interrupted in time or are collections of sub-events. It also lacks the ability to handle recurring events. Having a representation of time without the convexity restriction enhances the ability to solve certain tasks, such as scheduling, planning, or database manipulation. In this dissertation we introduce a framework for reasoning about temporal non-convex intervals. We extend James Allen's interval-based calculus by relaxing the condition of convexity. This extension increases the expressive power and usefulness of the calculus while retaining its computational advantages. A matrix based model for representing binary relations between non-convex intervals is developed. Operations on matrix relations are defined to be used in the reasoning process for solving important tasks. One of the important tasks is finding the feasible relations between intervals in a network of non-convex intervals. For this specific task, we give an approximate solution (constraint propagation algorithm) that runs in polynomial-time. We define the canonical form for a matrix relation to be a reduced equivalent matrix relation that satisfies certain conditions. An arbitrary matrix relation can be converted into a canonical form by using efficient linear time algorithms. We also show that dealing with canonical matrix relations improves the speed of performing the operations required for reasoning tasks in networks of non-convex intervals. For the purpose of comparing our generalized model with the traditional convex interval model, we analyze their performances when running the constraint propagation algorithm (path-consistency) on the same data. The analysis shows that our model performs better than the traditional convex interval model in terms of space and time. The reason for this improvement is that when dealing with sequences of intervals certain assumptions about the domain (e.g. order) will be represented implicitly which results in a smaller knowledge base to be stored and better performance in terms of space. It also allows the temporal reasoner to internalize these assumptions, and not have to explicitly infer things about them during the reasoning process, which result in fewer operations to be performed and better time performance.