CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Nov 20, 1998)

"Reasoning About Time"

Motivation: Handling Time Within the Predicate Calculus Alone Would be Awkward

It's a question both of clarity of representation and efficiency of inference.
 

Events as Points and Events as Intervals

While the simplest model for an event gives it a single point on the timeline, this slightly complicates the representation of happenings that have a beginning and an end.  They must be represented with a pair of events and some kind of link between them.

By treating events as intervals from the start, we are then inclined to think at a slightly higher level of abstraction.  Intervals become first-class objects and we can focus on the relationships between intervals instead of working only at the point level.

In a sense the two representations are equally powerful -- with a pair of points we can represent an interval, while with a degenerate interval of zero length, we can represent a point on the timeline.  So it's mainly a matter of how one chooses to think about the notion of event.
 

The 13 Primitive Interval Relationships of J. Allen

Consider two numbers x and y.  If we only regard the relative relationship for them, there are exactly three possibilities:  x < y,   x = y,   and x > y.

Now consider two intervals A and B.  Paying attention only to the relative values of the endpoints and not to the actual numbers, there are 13 distinct relationships that are possible for A and B.

Here they are.  Each of the first six have a distinct inverse, whereas "A equals B" is a symmetric relationship.

A precedes B:
      A
o----------o
                      B
                 o----------o
A meets B:
      A
o----------o
                 B
           o----------o
A overlaps B:
      A
o----------o
            B
       o----------o
A starts B:
   A
o------o
     B
o----------o
A finishes B:
        A
     o-----o
      B
o----------o
A equals B:
     A
o----------o
     B
o----------o

Computing With Interval Relationships

First let us consider how to take advantage of two relationships to constrain another.  Suppose that we know the relationship between A and B and we know the relationship between B and C, then we can often say something about the relationship between A and C the limits its possibilities.

For example, if A precedes B and B precedes C, then A precedes C.  This is because the 'precedes' relation is a transitive one.  However, most of the temporal interval relationships are not transitive in the standard sense.  For example, if A meets B and B meets C, we cannot conclude that A meets C.  It COULD meet C but only in the non-general situation that B is an interval of zero length.  By sitting down and drawing diagrams we can work out all the possible relationships among A and C for each pair of relationships between A and B, and B and C.  The result of this is shown in the "transitivity table" on page 401 of the text.

When we don't know precisely which of the 13 relationship between A and B is true, we may know that certain ones are ruled out.  In other words, we know a subset of the 13 possibilities that can hold for A and B.  If we also know a subset for B and C, then we can combine these two items of information to come up with a subset for A and C.  The algorithm for this is given in the text.  It makes use of the transitivity table repeatedly.

This technique can be applied to problems of working out the timing for a collection of events (represented as intervals without endpoint times) when the clues are given in a scattered, pairwise form.
 

An Example

The events...
A. Abigail was at home.
B. The bird was dead.
C. The cat was alone with the bird.
D. The dog was in the house.

The given relationships...
1. "The dog went out before Abigail did."
2. "The bird was alive when Abigail left."

What are the implications of this evidence?
Encoding of 1:    D ( < M S O D ) A
Encoding of 2:    A ( < ) B

In order to determine the subset of possible relationships that hold between D and B, we apply the transitivity table for each ordered pair consisting of a relationship in 1 and a relationship in 2.

The result is D ( < ) B.
 I.e., the event that the dog was in the house took place before the event that the bird was dead.
 


 

Last modified: November 20, 1998

Steve Tanimoto

tanimoto@cs.washington.edu