Constraint Graph for my Morning Schedule
This thing all things devours:
Birds, beasts, trees, flowers;
Gnaws iron, bites steel,
Grinds hard stones to meal;
Slays king, ruins town,
And beats high mountain down.
J.R.R. Tolkien, The Hobbit
PDF Version: http://www.cs.brandeis.edu/~cs112/newReadings/allen-time-again.pdf
The Issues
According to Allen, the most important issue in temporal reasoning is the degree of certainty one can assume when dealing with time. This applies to whether the exact times the events took place is known, or whether the full order of the events is known. Moreover, an important factor in temporal reasoning is whether to deal with time as discreet points or as intervals. If dealing with time as intervals, whether the duration of each time interval is known or even required of if it is not that relevant.
Dating Scheme Approaches
The most intuitive way of dealing with computers is by using numbers. So representing time as simple timestamps comes quiet naturally to computers especially if we are dealing with time as discrete points. Using this approach, comparing different times would be easy since all it involves is comparing two numbers. Calculation of durations is is just subtracting two timestamps from each other. Finally, the space required to store time is linear in proportion to the time span we want to cover and can be known in advance.
On the other hand, information about time has to be fully known - there is no room for uncertainty. Moreover, such representations are counter-intuitive for us as human beings. For example, if someone were to ask me when I quit my job, my answer would most probably be, "Just before I came to Auckland" rather than "On the 14th of February 2005, at 17:46".
If exact information on time is not available , a method Allen calls Pseudo-Dates could be employed. That method works by assigning a symbolic timestamp for each event. i.e. Waking up would have a timestamp 1, having breakfast would get a timestamp of 2, watching the news would be 3, etc... For this to work the events have to be fully ordered and that order has to be known. One has to keep in mind that these Pseudo-Dates do not actually correspond to any specific dates or timestamps.
Even though Pseudo-Dates relieves us from the requirement of needing full knowledge of the times of the events, it has drawbacks such as calculation of duration is not possible since the difference between two Pseudo-Dates has no significant meaning. Moreover, insertion of new events in such a scheme would be limited by the machine's precision, and the space requirement is not linear to the time span and cannot be known in advance. Finally Pseudo-Dates cannot handle disjunctive events, i.e. events that are not related to each other.
Points Vs. Intervals
Allen raises the issue whether time be dealt with as a group of discreet points or as intervals. In spoken language both are actually used. E.g. I had lunch at 12. or I had lunch during the break between my classes. In practice though, looking at time as discrete points could be problematic since almost any event can in theory be subdivided into smaller events. So if we deal with time as discrete points then subdividing it would not be possible. Thus Allen chooses to consider time intervals rather than points.
Constraint Propagation Approaches
In this part Allen discusses the method he is most famous for. This approach involves representing time intervals as a graph where each interval is connected to the other intervals with an arc labelled with all possible temporal relationships between them (see figure below).
Constraint Graph for my Morning Schedule
One of the more useful aspects of this method is that relations can be deduced by the propagation of constrains using Allen's algorithm which is sound and complete for all cases that are intuitive for humans - though it is sound yet incomplete for cases that are not intuitive for humans, such as puzzles and the like. Moreover, disjunctive relations can finally be represented using this approach. Unfortunately though, this method of representing time does not convey duration information, nor is it possible to represent disjunctions between more than two points.
Duration-Based Approaches
Fortunately, graphs that represent durations are available. One of the first to work on this kind of graphs was the US Department of Defense when they developed PERT networks, which mainly used for project management. The way this kind of network works is that the arcs represent durations, while the nodes represent the earliest and latest times possible for the start of the event whereby the sequence of events can finish in the least possible time (see figure below).
PERT Network (modeled after the one in Figure 9 in the paper)
This method of representing time is good for scheduling since it minimizes the time required for a certain sequence of related events. Moreover, it allows for the representation of durations without the need for any timestamps. Unfortunately, this method does not allow for the handling of unknown durations - there is no way to represent them and keep the network in tact. Adding new events is computationally expensive since it might require the re-computation of the whole network. Dean and McDermott, two AI researchers came up with other Duration-Based approaches that do address the problem of having unknown durations.
Conclusion
Allen concludes that time representation is quiet important in many different areas, a point which we can all agree on. He also concludes that none of the temporal representations available in the world of AI now is perfect, each has its strengths and weaknesses and is useful under certain conditions. Finally, he concludes that this field is still in its infancy and a lot of work has to be done in order for it to mature.
All in all, I think that this was a good paper. Allen presents the different methods of representing time quiet clearly and in a straight forward manner. I think that he managed to cover all his bases and to give the reader a good idea on the issues involved in each of the approaches for representing time. Moreover, one point which impressed me was that he didn't devote more time than needed for the Constraint-Propagation Approaches or his own algorithm - he was not advocating them but he was impartial and objective when talking about them. After reading this paper I felt that I had a better grasp of what's involved in representing time.
That being said, one of the issues I had with Allen's paper was that he seems to assume that the reader is familiar with his 1983 paper on temporal reasoning - so I would recommend that anyone read that paper first before attempting to read this one (it is available in the references). For example, even though the issue of whether to represent time as discreet points or intervals is quiet important, he does not elaborate much on this topic in this paper - but it is covered quiet well in the other paper. Allen does sometimes tend to jump from one topic to another without proper introductions, but that's not that big of a problem.
In my opinion, this paper as well as his 1983 paper on temporal intervals are a must-read for anyone interested in temporal reasoning.
What is time? If nobody asks me, I know; but if I were desirous to explain it to one that should ask me, plainly I know not.
Augustine of Hippo