Ontologies for time
What follows is our response to the arguments about the ontology of
time from Pat Hayes, Ray Reiter, and John McCarthy.
Response to John
The example of car accelerating demonstrates the need of time points
for time ontology.
A similar example is throwing a ball up into the air. The motion of
the ball can be modelled by a quantity space of three elements:
going-up, stationary, and going-down. Intuitively, there are
intervals for going up and going down. However, there is no interval,
no matter how small, over which the ball is neither going up nor going
down. The property of being stationary is naturally associated with a
point, rather than any interval (including Allen and Hayes' moment),
a "landmark" point which separates two other intervals.
Response to Ray
| During all the years that the debate has raged about time points vs
intervals, we devotees of the sitcalc have never seen it as an
issue.
| It has already been an issue of the sitcalc. For instance, in Pinto
and Reiter's 1995 paper, Reasoning about Time in the Situation Calculus,
[j-amai-14-251], the concept
of situation is extended to have a time span (an interval?) which is
characterised by a starting time and an ending time (two points?).
During the time span of a situation no fluents change truth value.
Also, an action with duration is modelled with two instantaneous
actions (start-action and end-action). So, all the debates about time
points vs intervals apply here, and the Dividing Instant Problem
still arises. In fact, all Ray's arguments show again, with his
revised formulation of the sitcalc to accommodate temporal reasoning,
either there is no way of expressing the claim that a proposition
(like Light is on) is true or false at some time points, or one has
to artificially take the unjustifiable semi-open interval solution.
This is not surprise at all and is what one would expect, since the
problem is actually there for the underlying time theory itself, and
therefore would be there for any formalism which wants to support
explicit time representation.
Response to Pat
| ...For example, the 1990 AIJ critique of Allen's account by Galton
(wrongly) assumes that Allen's intervals are sets of points on the
real line.
| After re-reading Galton's paper [j-aij-42-159], as we understand,
Galton's arguments are in general based on the assumption that Allen's
intervals are primitive, rather than sets of points on the real line.
In fact, the main revision Galton proposes to Allen's theory is a
diversification of the temporal ontology to include both intervals and
points. That is, in Galton's revised theory, intervals are still
taken as primitive. Having pointed out this, however, as shown in Ma,
Knight and Petrides' 1994 paper [j-cj-37-114], Galton's determination
to define
points in terms of the "meeting places" of intervals does not, as he
claims, axiomatise points on the same footing as intervals, and hence
that some problems still remain in these revisions.
| there does seem to be a simple, basic, account which can be
extended in various ways to produce all the other alternatives, and
this core theory is the one I was referring to.
| Does this core theory refer that one in which "intervals are uniquely
defined by their endpoints (which are also the points they fit
between) and two intervals meet just when the endpoint of the first is
the startpoint of the second"? Or Allen's one? - It seems the former
one.
Anyway, yes. There does seem to be such a simple, basic core theory.
For general treatments, in Ma and Knight's CJ 94 paper,[j-cj-37-114] a time theory
is proposed (as an extention to Allen and Hayes' interval-based
one) which takes both intervals and points as primitive on the same
footing - neither intervals have to be constructed out of points, nor
points have to be created as the places where intervals meet each
other, or as some limiting construction of intervals. The temporal
order is simply characterised in terms of a single relation "Meets"
between intervals/points. Some advantages of this time theory are:
(1) It retains Allen's appealing characteristics of treating
intervals as primitive which overcomes the Dividing Instant Problem.
(2) It includes time points into the temporal ontology and therefore
makes it possible to express some instantaneous phenomenon, and
adequate and convenient for reasoning correctly about continuous
change.
(3) It is so basic that it can be specified in various ways to
subsume others. For instance, one may simply take the set of points
as empty to get Allen's interval time theory, or specify each
interval, say T , as <T-left, T-right>
where T-left < T-right ,
to get that one Pat prefers.
|
The way I prefer, myself, is to say that propositions hold only
during intervals, so that it is simply ill-formed to assert a
proposition of a single point; but to allow the possibility of
pointlike intervals, of the form <t,t> , to be the temporal
durations of propositions which are (intuitively) thought of as
happening at a single 'point'. Or, put another way, some intervals
may consist of just a single point, and some points may completely
fill an interval. These pointlike intervals are the way that (this
version of) the theory encodes the times when instantaneous truths
hold. This doesnt require us to say that every point fills an
interval, notice: since 'interval' is a basic predicate, it is
perfectly consistent to say ¬ interval( <t, t> ) ; this would
entail, for example, that nothing changed at that particular time.
But it allows us to consider the proposition that a tossed ball's
vertical velocity is zero, and assert that it is true at a single
'point', ie formally, that its interval of truth was pointlike. And
since it is easy to characterise pointlike in the theory:
((pointlike i) iff ((begin i) = (end i)))
|
Yes, it's true. And, it seems that, all these can be reached
equivalently by simply taking pointlike interval <t,t> as identical
with point t in the case where both intervals and points are included
in the time ontology.
|
one can, for example, say something like
((illuminated i) or (dark i))) implies (not (pointlike i))
so that the light is neither on nor off at the switching point.
In this theory, every proposition has a 'reference interval' during
which it is true, and a proposition might not be true of
subintervals of its reference interval. (Though some propositions
might be. This kind of distinction has often been made in the
linguistic literature. Note however that this intuition is
basically incompatible with the idea that an interval is identical
to the set of the points it contains.)
|
This can be distinguished by applying Holds_In and
Holds_On (that is
Allen's Holds, see Galton's paper [j-aij-42-159].
Actually, as shown in Ma and Knight's 1996 paper [j-cj-37-114],
to characterise the intuitive relationship
between Holds_On and Holds_In ,
in the case where intervals are
allowed, some extra axiom is needed.
Also, it seems that, in Pat's formulation, for expressing that
interval <a,b> is a subinterval of interval <c,d> , one would have
c < a < b < d . In this case, we get that pointlike intervals
<a,a> and <b,b> (or equivalently, points a and b )
fall in interval <c,b> .
| We certainly need something corresponding to 'points', I agree. I
meant only that the formal theory can be crafted in the way Ive
outlined above, or alternatively by identifying the pointlike
intervals with their endpoints, and allowing a proposition to hold
at a single point. This is in many ways more intuitively
transparent but it is formally a bit more awkward, since pointlike
isnt definable any more, and one has to put in special axioms
forbidding points to meet each other. The 'reference interval' of a
proposition could now be a single point in the theory. This is
essentially the theory that Allen and I described in our 1985
paper [c-ijcai-85-528], though it takes a little work to see it.
| On the one hand, many cases suggest the need of allowing a proposition
to holds at a single point. For instance, see the example of throwing
a ball up into the air described earlier in the response to John
McCarthy.
On the other hand, allowing a proposition to holds at a single point
doesn't necessarily make pointlike un-definable. It depends on if one
would impose some extra constraints, such as
((illuminated i) or (dark i))) implies (not (pointlike i))
as introduced by Pat for the light switching example, which actually
leads to the assertion that the light is neither on nor off AT the
switching point.
Actually, in the later version of Allen and Hayes's theory that appears in
1989 [j-ci-5-225], an awkward axiom is proposed to
forbid moments to meet each other. It is interesting to note that,
although moments are quite like points (moments are non-decomposable),
they still have positive duration (they are not pointlike). Moments
are included in Allen and Hayes' time ontology, while points are not.
One of the reasons that such an axiom is awkward is that it doesn't
catch the intuition in common-sense usage of time. In fact, in many
applications, one would like to take some quantity as the basic unit
of time. E.g., we may take a second as the basic unit. In other words,
seconds are treated as moments - they cannot be decomposed into
smaller units. However, for a given second, we may still want to
express the next one, that is, a second can meet another second,
although they are both non-decomposable.
| True, and indeed the Allen relations only have their usual
transitivity properties when applied to intervals which are
nonpointlike and forward-oriented. Of course both these are
properties expressible in the theory, so that the Allen
transitivity relationships can be stated there, suitably qualified.
(When the alternative extension axioms are added, the
qualifications become tautologous.)
...BTW, the claim that "meets" and "before" being exclusive is
"intuitive" depends on how one's intuition is formed. Part of what
I learned by having to construct alternative formalisations is that
intuition is very malleable. Having gotten used to pointlike
intervals, I dont find this exclusivity condition at all intuitive.
| If the exclusivity condition is not intuitive at all, as Pat's claims,
then why is is proposed for Allen's relations applied to intervals? Is
it simply because they can be easily defined as exclusive when applied
to nonpointlike intervals? Why not when applied to pointlike ones?
(Simply because it cannot be conveniently defined?). Actually, in the
case where both intervals and points are treated as primitive on the
same footing, it is straightforward to extend Allen's 13 exclusive
temporal relations between intervals to govern both intervals and
points, while without losing the property of exclusivity. Vilain's
[c-aaai-82-197] and Ma and Knight's [j-cj-37-114] systems are
two examples.
| But these cases only make sense if one thinks of interval and
points in the usual mathematical way, which is exactly what Im
suggesting we don't need to do. We can get almost everything we
need just from the ordering structure: we don't need to get all
tied up in distinguishing cases which can only be formally stated
by using all the machinery of real analysis.
| The cases make sense not only if one thinks of intervals and points in
the usual mathematical way. In fact, all the three cases are
demonstrated under the assumption that both intervals and points are
treated as primitive, rather than in the usual mathematical way.
| Again I was careless in using the word "knowledge", sorry. I
should have said: in order to answer the question whether the light
is on or off, one has to specify the interval with respect to which
this question is posed. On this view, the truth or otherwise of a
proposition is only meaningful with respect to certain intervals. I
dont mean that the facts are determined by knowing more about the
details of the interval, but that the question is a different
question when asked about one interval than when asked about
another, and for some intervals in may be simply meaningless. Is
the light on or off at (exactly) 3.00 pm? The only way to answer
this is to find a suitable non-pointlike interval of light or
darkness completely surrounding 3.00 pm, because 'being on' is the
kind of proposition that requires a nonpointlike reference
interval.
| But it seems that there are also some other kind of proposition to
which one cannot assign any nonpointlike reference interval. For
instance, in the throwing ball up into the air example, proposition
"the ball is stationary" can only be true at points, and for any point
we cannot find any non-pointlike interval (completely) surrounding it
over which the ball is stationary.
| This has nothing to do with whether an interval is open or closed:
in fact, there is no such distinction in this theory. It only
arises in a much more complicated extension which includes set
theory and an extensionality axiom for intervals.
| In the time theory where both intervals and points are taken as
primitive, we can (if we like) talk about the open and closed nature
of intervals with some knowledge being available. This kind of knowledge
can be given in terms of the Meets relation, rather than some "much
more complicated extension which includes set theory and an
extensionality axiom for intervals". In fact, we can define that:
|
interval I is left-open at point P iff Meets(P, I)
interval I is right-open at point P iff Meets(I, P)
interval I is left-closed at point P iff there is
an interval I' such that Meets(I', I) ^ Meets(I', P)
interval I is right-closed at point P iff there is
an interval I' such that Meets(I, I') ^ Meets(P, I')
|
That's all, and it seems quite intuitive. For instance, with the
knowledge MEETS(P, I) which says that interval I is immediately after
point P , one can intuitively reach that point P is on the left of
interval I and P is not a part of I , and there is no other time
element standing between P and I . Therefore, we say interval I is
left-open at point P . Similarly, with knowledge
MEETS(I, I') ^ MEETS(P, I') ,
one can reach that point P is a part and the "finishing"
part of interval I , that is interval I is "right"-closed at P .
It is important to note that the above definition about the open and
closed nature of intervals is given in terms of only the knowledge of
the Meets relation. However, if one would like to specify intervals as
point-based ones, such a definition will be in agreement with the
conventional definition about the open and closed intervals.
Jixin
References:
c-aaai-82-197 | Marc Vilain.
A System for Reasoning about Time.
Proc. AAAI National Conference on Artificial Intelligence, 1982, pp. 197-201.
|
c-ijcai-85-528 | James Allen and Pat Hayes.
A Common-Sense Theory of Time.
Proc. International Joint Conference on Artificial Intelligence, 1985, pp. 528-531.
|
j-aij-42-159 | Anthony Galton.
A critical examination of Allen's theory of action and time.
Artificial Intelligence Journal, vol. 42 (1990), pp. 159-188. |
j-amai-14-251 | Javier Pinto and Ray Reiter.
Reasoning about Time in the Situation Calculus.
Annals of Mathematics and Artificial Intelligence, vol. 14 (1995), pp. 251-268. |
j-ci-5-225 | James F. Allen and Patrick J. Hayes.
Moments and points in an interval-based temporal logic.
Computational Intelligence, vol. 5, pp. 225-238. |
j-cj-37-114 | Jixin Ma and Brian Knight.
A General Temporal Theory.
Computer Journal, vol. 37 (1994), pp. 114-123. |
John McCarthy wrote:
| McCarthy and Hayes 1969 paper [n-mi-4-463] used time as a fluent
on situations, i.e. time(s). ...
| My chief motivation for this was the fact that the mapping from situations
to times is many-one, since the sitcalc can distinguish different
situations with the same clocktime. The differences between how precisely
times are known, etc., can be handled by making the set of "times" obey
different axioms. For example, in R-sitcalc the appropriate kind of time
for a situation would be an interval of clocktimes, presumably; something
like 'from 4.12 to 5.15'.
| My previous message gave a reason for including time points in a
theory of events and actions. The theory could be founded so as to
regard them as degenerate intervals, but I don't see any advantage in
that, although I suppose the idea stems from the fact that people and
robots can't measure time precisely.
| Actually no. The motivation for introducing 'pointlike intervals' was just
to maintain a certain expressive neatness, where all propositions, even
instantaneous ones, are asserted w.r.t. a reference interval.
That idea - that intervals are approximations to points, and the length of
an interval represents a degree of ignorance about the location of a point
- gives a rather different ontology. In that case, for example, it doesnt
really make sense to be able to refer to the precise endpoints or
meeting-points of intervals (since if one can, then absolute precision
about timepoints comes for free.) The Allen set of thirteen relations
reduces to just six (before, overlap, inside, and inverses) since those
that require endpoints to be exactly identified (meets, starts, ends,
equal, endby, startby, meetby) are undefinable (except in an infinite
limit.) This is the theory called 'approximate-point' in my time catalog.
There arent any points in this theory, of course, though they could be
defined if one added enough mathematical machinery to be able to talk about
limits of infinite sequences.
Pat Hayes
References:
n-mi-4-463 | John McCarthy and Pat Hayes.
Some Philosophical Problems from the Standpoint of Artificial Intelligence. [postscript]
Machine Intelligence, vol. 4 (1969), pp. 463-502. |
|