From: George Ferguson (ferguson@cs.rochester.edu)
Date: 04/26/02
Hmm. Adam tells me that the document came through without any line
breaks. It looks fine at my end. Probably a unix-mac-pc thing (isn't
it exciting to still be dealing with the end-of-line problems after
40+ years of computing?).
I will try to cut and paste it in rather than attaching it as a file.
In fact, I will mail it out of emacs to minimize the chances of any
mail app trying to be smart.
George
--------------------------------------------------------------------------
Overall, we like this initial formulation. It manages to capture
generalities without excluding different people's theories. We tested
the common ontology by seeing whether we could extend it with
additional axioms to produce the Interval Temporal Logic as described
in (Allen, 1984) and (allen & Hayes, 1989). This seems like a good
exercise not only because it is near and dear to our hearts, but also
because it's a widely-used and extensivley studied representation of
time.
Our comments in this note are divided into three sections: the first
addresses issues in the development of the temporal logic through
Section 2, the second notes a few fairly minor points that we came
across in later sections of the proposal, and, finally, we describe
our mapping or extension of the proposed logic into the Allen ITL.
--------------------------------------------------------------------------
Comments on Temporal Logic:
1. INTERVAL-BETWEEN ought more properly to be called
TEMPORAL-ENTITY-BETWEEN, given the definition near the end of 2.1.
2. Near the end of 2.1, you comment that "the ontology is silent about
whether intervals are uniquely determined by their starts and
ends." That is, INTERVAL-EQUALS is not (necessarily) true equality.
While this is certainly mathematically possible, it is different
from the standard use of equality in the interval algebra (which
uses only true equality). Also, in later examples you describe
intervals as, for example "[10:00, 11:00]". We suspect that most
people would expect that, for example, "Raining([10:00, 11:00])"
and "~Raining([10:00, 11:00])" was logically inconsistent, although
this would not necessarily be the case if intervals are not
uniquely determined by their endpoints. So we are in the camp that
would like to strengthen this.
3. In 2.3 on the interval relations, it would appear that several of
the definitions are counter-intuitive unless restricted to proper
intervals (those not of the form "[t,t]"). For example, a
degenerate interval [t,t] INT-EQUALS itself, INT-MEETS itself, and
is INT-MET-BY itself! Thus "Meets(X,Y) <-> ~MetBy(X,Y)" is not a
theorem of these axioms. In fact, unless restricted to proper
intervals, none of the standard antonyms of the interval algebra
are theorems. And of particular interest in planning (cf. Allen &
Koomen 1987), the degenerate interval is INT-DISJOINT from itself.
4. Regarding the axioms for DURING, AT-TIME, and HOLDS: Up to this
point, if we wanted to have a theory based solely on intervals, we
could simply ignore the point-oriented aspects of the proposed
ontology. However, with the proposed definitions for HOLDS, we are
forced to accept that eventualities occur/hold at points if they
hold over intervals.
Your axioms are (t is a point, T is an interval):
holds(e, T) <=> during(e, T)
holds(e, t) <=> at-time(e,t)
during(e, T) & inside(t,T) => at-time(e, t)
These imply:
holds(e,T) & inside(t, T) => holds(e, t)
Now you could say that we can just ignore this HOLDS predicate, and
define our own, and we won't get into trouble. This may be the
case, but we think this would be confusing. We think it would be a
better strategy to keep the DURING and AT-TIME definitions, and let
individual researchers define their own HOLDS and OCCURS predicates
however they wish. An example of this is given below, where we
remove the first two axioms above, and actually strengthen the
third.
--------------------------------------------------------------------------
Comments on Later Sections (dates, etc.):
These comments based on a quick overview of the later parts of the
document. I'm afraid we haven't had time to work through them in
detail yet (nor are we really experts on this apsect of temporal
representation anyway).
5. Section 3.2 on "Hath": saying that "x is composed of the disjoint
union of N intervals of type u" is speaking somewhat loosely, it
would seem. The meaning seems to be that x is "N unit intervals
with respect to the TemporalUnit u". That is, *Day* is not really a
"type".
Also here, the definition of Hath does not require that the
component intervals be contiguous. Perhaps this comes out in the
axioms and could be added to the english gloss along with the
previous change.
6. The axioms for Hath have a couple of typos (unless we're missing
something). The two that say that "every element of S has an
element that precedes and follows it" use "x" in their innermost
formula, when it seems "s" is intended: "there exists a y2 which is
a member of s (not x), for which int-meets(y1,y2)" (and similarly
for y1 in the second axiom.
7. The comment following this states that if time is linearly ordered,
the E quantifier can be replaced by E!. Isn't this only true if
intervals are uniquely determined by their endpoints?
8. The final axiom for Hath has "duration(y1,u)" as a conjunct, but
since DURATION is a function, it would seem that "= 1" is missing,
to make y1 a unit interval w.r.t. the TemporalUnit u (as in the
second axiom for Hath).
And regarding this axiom, it isn't clear to us how it helps with
the election example used as motivation for granularity.
--------------------------------------------------------------------------
Relationship between Proposed Ontology and Interval Temporal Logic:
As described at the outset, we tried to figure out how to extend the
proposed common ontology into the Interval Temporal Logic of (Allen,
1984) and (Allen & Hates, 1989). Our sense is that this serves both to
firm up our understanding of the proposed ontology, as well as being
potentially valuable in its own right as a mapping into a widely-known
formalism. We use the original proposal's conventions of implicit
quanitification and typing (T for intervals, t for points), and we
number our axioms "AF<n>".
First, per comment #2 above, we make intervals uniquely defined by
their endpoints (ie., INT-EQUALS is true equality):
AF1. int-equals(T, T') => T=T'
Second, per comment #3 above, we allow only true intervals:
AF2. interval(T) => proper-interval(T)
Per comment #4 above, we remove the common ontology axioms about
HOLDS. We can define our notion of HOLDS (and OCCURS) in our more
specialized ontology as implying DURING, with additional constraints
(HOLDS is homogenous, OCCURS is anti-homogeneous):
AF3. interval(T) & holds(e, T) => during(e, T)
AF4. holds(e, T1) & int-contains(T2, T1) => holds(e, T2)
AF5. interval(T) & occurs(e, T) => during(e, T)
AF6. occurs(e, T1) & int-contains(T2, T1) => ~occurs(e, T2)
Finally, we are left with specifying the relationship between
intervals and points (in particular, the relationship between
eventualities holding/occuring over intervals and at points). The
original axiom is:
during(e, T) & inside(t, T) => at-time(e,t)
We would in fact strengthen this to the following:
AF7. at-time(e,t) <=> Exists T' . inside(t,T') & during(e, T')
In other words, at-time(e,t) means that e is "in progress" at t (as in
the progressive aspect statement "He was running at 3:15"). Note that
this axiom entails the original, but we probably wouldn't want it in
the common ontology as it would interfere with what some point-based
theories might want to say about the relationship between points and
intervals. We believe that once the axioms about HOLDS are removed
from the common ontology, this axiom is not needed either (although it
wouldn't hurt our formulation to leave it there, since we will just
strengthen it).
--------------------------------------------------------------------------
References:
Allen, J.F. (1984). Towards a general theory of action and time.
Artificial Intelligence 23, pp. 123-154.
Allen, J.F. and P.J. Hayes (1989). Moments and points in an
interval-based temporal logic. Computational Intelligence 5, pp.
225-238.
Allen, J.F. and G. Ferguson (1997). Actions and events in interval
temporal logic. In Oliveiro Stock (ed.), Spatial and Temporal
Reasoning, Kluwer Academic Publishers, pp. 205-245.
--------------------------------------------------------------------------
This archive was generated by hypermail 2.1.4 : 04/26/02 EDT