(PDF)
Peter van Beek.
Exact and approximate reasoning about qualitative temporal relations.
PhD thesis,
University of Waterloo, Department of Computer Science,
1990.
Much temporal information is qualitative information such as
``The Cuban Missile crisis took place during Kennedy's
presidency,'' where only the ordering of the end points of the
two events is specified. A point and an interval algebra have
been proposed for representing qualitative temporal information
about the relationships between pairs of intervals and pairs of
points, respectively. In this thesis, we address two fundamental
reasoning tasks that arise in these algebras: Given (possibly
indefinite) knowledge of the relationships between some intervals
or points, (i) find a scenario that is consistent with the
information provided, and (ii) find the feasible relationships
between some or all pairs of intervals or points. Solutions to
these tasks have applications in natural language processing,
planning, plan recognition, diagnosis, and knowledge-based
systems.
For the task of finding consistent scenarios the main results are as
follows. For the point algebra, we develop an O(n^2) time
algorithm that is an O(n) improvement over the previously known
algorithm, where n is the number of points. For the interval
algebra, finding a consistent scenario has been shown to be (almost
assuredly) intractable in the worst case. We show how the results for
the point algebra aid in the design of a backtracking algorithm. The
algorithm is shown to be useful in practice for planning problems.
For the task of finding the feasible relationships the main
results are as follows. For the point algebra, we develop the
first exact algorithm for finding all the feasible
relationships that takes O(n^4) time, where n is
the number of points, and show that a previously known
algorithm is exact for a subset of the point algebra. For the
interval algebra, finding the feasible relationships is again
(almost assuredly) intractable. The intractability of finding
exact solutions leads us to develop new algorithms that find
approximate solutions. We examine the effectiveness of the
approximation algorithms through computational experiments and
determine under what conditions the algorithms are exact. We
also give a simple test for predicting when the approximation
algorithms will and will not produce good quality
approximations.
Finally, we survey example applications chosen from the literature to
show where the results of this thesis are useful.