Towards an Integrated Logic of Space, Time and Motion

1 Introduction

Over the last ten years logical systems for handling time have become commonplace in AI. The interval-based system of Allen [1984] bas become widely adopted in this area. A number of authors have suggested enhancements or modifi­ cations to it. My own [Galton, 1990] is particularly relevant to the current paper, because it starts to take space, motion, and continuity seriously in a way that Allen did not. [Gal­ ton, 1991] suggests a reworking of the syntax (unreification), which however I shall not follow here: the reified system here can in principle be unreified as suggested in that paper, but this leads to less wieldy formulae on the whole.

In contrast to time, space has received much less attention. A spatial reasoning system comparable to Allen's temporal logic has, however, been proposed recently by [Randall et al., 1992a] and [Randall et al., 1992b]-henceforth designated individually as RCCa and RCCb respectively, and collectively asRCC.

In the present paper I combine the spatial logic of RCC with my own modification of Allen's temporal logic to give a logic of space, time, and continuous motion.

2 Spatial Regions

RCC derive a set of relations between spatial regions, taking the notion of 'connection' as a primitive. Two regions are regarded as connected to each other if their topological clo­ sures are not disjoint. Since I shall have no use for the notion of topological closure, I prefer to say simply that connected regions are those which either overlap or abut one another. In the axiomatic theory, connectedness is stipulated to be reflex­ ive and symmetric.

RCC go on to derive a set of other dyadic relations on regions, of which eight are singled out as constituting a mutu­ ally exhaustive and pairwise disjoint set (analogous to Allen's well-known 13 relations on temporal intervals). They are

DisConnected from (DC) Externally Connected (EC) Partially Overlaps (PO) Equals(=) Tangential Proper Part of (TPP) Non-Tangential Proper Part of (NTPP)

and the inverses of TPP and NTPP (see Figure 1). For the formal definition of each of these in terms of Connection (C), see the RCC papers.

The exhaustiveness and exclusiveness of the eight relations above can be expressed using the axiom

Vxlc/y(Region(x) /1. Region(y) -+ DC(x, y) V EC(x, y) V PO(x, y) V x = y V TPP(x, y) V NlPP(x, y)V TPP(y, X) v NlPP(y, X))

together with 28 axioms of the form

where R1 and R2 are two (different) relations from the eight.

3 Spatial points

RCCa only admit regions into their class of spatial entities, just as Allen only admits intervals into his class of tempo­ ral entities. I argued in [Galton, 1990] that he should have admitted points as well; here I argue analogously for the need for spatial points, a possibility explicitly considered, though not actually advocated, by RCCb. Points arise nat­ urally in a number of ways, for example where two regions abut one another (e.g., two mutually tangential spheres or circles), at corners, or where two linear boundaries meet. As I have stressed in the temporal case, it is important not to think of regions as sets of points. If one does, one be­ comes embroiled in empirically meaningless distinctions such as that between topologically closed and topologically open regions. (In mathematics, we can distinguish clearly between the open disc {( x, y) I x 2 + y 2 < 1} and the closed disc { ( x , y) I x 2 + y2 ~ 1}, but this distinction does not seem to have any application to physical space.)

There are just two relations between points comparable to the 8 region-region relations above: point x is either the same point as y, or a different one.

For relations between points and regions things are a little more interesting; we have, for point p and region r,

pis insider pbounds r

p is outside r.

We can take inside as primitive and define

4 Bodies in space

From the AI perspective, the point of talking about space is to enable us to talk about things in space: our space is populated by extended bodies. For some purposes, it might be convenient to refer to unextended bodies too, e.g., point masses. And in any case, we shall want to refer to things such as corners, which are distinguished points on the surfaces of extended bodies, or centres of gravity.

The RCC papers make no assumptions concerning the rigid­ ity or otherwise of bodies. The resulting highly general system is applicable equally to rigid and to non-rigid bodies. Many bodies featuring in everyday discourse, such as people and animals, are of course non-rigid. But equally, many of them, such as bricks, tables, and houses, are to all intents and pur­ poses rigid. And many objects which have internal moving parts, such as troHeys, toasters, and electric drills, are glob­ ally rigid in the sense that their overall shape, as viewed from outside, does not change. There is therefore good reason to investigate the effects of specialising the RCC treatment to rigid bodies. It turns out that the theory of the RCC relations exhibited by rigid bodies has a number of interesting features lacking from the more general account.

At any moment a body occupies a region of space, which we shall call its position at that time. By a position for a body I understand just the region of space it takes up, no more and no less 1 . The assumption of rigidity means that any two positions for a given body must be congruent. We shall write pos( b) to denote the position of body b. This is a fluent in the sense of the Situation Calculus [McCarthy and Hayes, 1969]: that is, it can take different values at different times.

In normal discourse, we do not often have cause to refer to the position of a body in this sense; it is more typical to describe a body as being located within a larger region (e.g., John is in the kitchen). In fact, any language has a range of spatial prepositions such as the English in, on, at, etc., whose exact usage is hard to describe formally. For that reason we shall not try to define predicates such as I n(b, r) or On(b, r ). Instead, we shall describe the position of a body in relation to a region of space using the RCC relations DC, EC, PO, =, TPP, NlPP, TPP-1 and NJPp-I.

This will also have the advantage that we can just as easily describe the spatial relationship between two bodies at a given time (as e.g., the ball is in the box).

Given a rigid body band a region r, the possible positions of b in relation to r are constrained by the particular size and shape of each. There are six possibilities to consider:

1. They are congruent: that is, r is a possible value of pos(b).
2. b can just fit inside r: that is, TPP(pos( b), r) is possi­ ble, but not NlPP(pas(b), r). An example would be a hemispherical body and a spherical region of the same radius.
3. b can just cover r : that is, TPP( r, pas( b)) is possible but not NlPP( r, pas( b)), e.g., a spherical body and a hemispherical region of the same radius.
4. b can fit right inside r: that is, NlPP(pas( b), r) is pos­ sible. Example: a spherical body and a spherical region of greater radius.
5. b can more than cover r: that is, NlPP(r,pos(b)) is possible. Example: a spherical body and a spherical region of smaller radius.
6. None of the above holds: we say b and r are incommen­ surate. Example: a pole 3 feet long and a cubical region measuring 1 foot along each side.

Each of these possibilities defines a subset of the eight RCC relations that can hold between pas( b) and r, as follows:

1. DC, EC, PO, =. 2. DC, EC, PO, TPP.

1. DC, EC, PO, TPP- 1

1 For a symmetrical body, the position, in the sense introduced here, is ambiguous, since symmetry allows a body to occupy a position in more than one orientation. For simplicity we ignore this issue here, but acknowledge that a fuller treatment would need to take account of it.

4. DC, EC, PO, TPP, NTPP. 5. DC, EC, PO, TPP-1, NfPp-1. 6. DC, EC, PO.

We mentioned above that we may want to refer to unex­ tended objects such as comers of extended bodies, or idealised point masses. These have positions too, the position pos(p) of a point being a spatial point. The relevant relations here are the point/region relations Inside, Outside and Bounds, and the point/point relations= and :j;.

5 Continuity

We are now in a position to present a qualitative character­ isation of continuity. RCCb introduces the notion of a 'di­ rect topological transition' between two RCC relations. No assumption is made concerning rigidity. They allow, for ex­ ample, that a body's position can be a tangential proper part of a region at one time, and equal to it at a later time. This can only happen if the body increases in size. In the present paper, we restrict RCC's more general notion to rigid bodies. By doing so we are able to exploit an interesting connection with some earlier work on continuity.

We shall say that an RCC relation R' is a perturbation of RCC relation R with respect to a given body/region pair (b, r) if either it is possible to have R(pos(b), r) holding at an instant t and R' (pos( b), r) holding throughout an interval that is bounded by t, or it is possible to have R(pos(b) , r) holding throughout an interval i and R' (pos( b) , r) holding at an instant which bounds i. We now characterize continuity of position for a body by defining the possible perturbations for each of the RCC relations in which it can stand to a given region.

For example, suppose that TPP(pos( b), r) holds at instant t . Then if position is a continuous function of time, it cannot be the case that over some interval (t, t') we have EC(pos(b) , r) . Intuitively, in order to get from being inside the region r to being outside it, b bas to pass through a position which is partly inside and partly outsider, i.e., ifTPP(pos(b ), r) holds at t and EC(pos(b), r) holds at a timet' later than t, then it must be that PO(pos(b), r) holds at some time within the interval (t, t'). Here the point is that with respect to a body b which fits inside a region r, PO is a perturbation of both EC and TPP. but EC and TPP are not perturbations of each other. Continuity demands that if a body/region pair stand in RCC relations R1, R2, R3, ... over time, then each R;+1 must be a perturbation of the corresponding R; .

For each type of body/region pair we can construct a pertur­ bation diagram which shows the perturbation relation on the set of RCC relations appropriate to that pair type, as follows.

For point bodies, the perturbation diagrams are much simpler:

1. p is a point body, q is a spatial point:

6 States of Position and States of Motion

In [Galton, 1990] I introduced a distinction between what I called states of position and states of motion. The defining characteristics of these two types of state are as follows:

• If s is a state of position, and s holds throughout the interval (t1, t 2), then s holds at t1 and at t2.
• If s is a state of motion, and s holds at the instant t, then there is an interval i containing t such that s holds throughout i.

I pointed out that Allen's interval calculus and the associ­ ated Holds predicate relating states to intervals over which they bold only works for states of motion; and I proposed an enrichment of the calculus to make it work for states of po­ sition too. The enrichment consisted of introducing instants on the same footing as intervals, and three Holds predicates Holds-on, Holds-in, and Holds-at, the first two relating states to intervals, the third relating them to instants.

Using inf( i) and sup( i) to denote the instants which bound the interval i, and writing Div( t, i) to mean that instant t falls within (and hence divides) the interval i, the characteristic properties of states of position and motion can be expressed as follows:

• For a state of positions,

• For a state of motion s,

The eight RCC relations neatly split into four states of position and four states of motion, as follows:

States of Position: EC, =, TPP, TPP-1 States of Motion: DC, PO, NTPP, NTPP-1

Comparing this with the perturbation diagrams above, we observe the following rule:

The Perturbation Principle. Every RCC relation is a perturbation of itself, but otherwise a state of position can only be a perturbation of a state of motion, and vice versa.

Note that the Perturbation Principle depends for its applica­ bility on the fact that we have restricted our attention to rigid bodies. For non-rigid bodies the classification of RCC rela­ tions into states of position and states of motion itself becomes problematic. For example, TPP behaves like a state of posi­ tion when it undergoes a perturbation to NTPP, but like a state of motion when it undergoes a perturbation to =, as it can in the non-rigid case.

A similar set of relationships bold for the point-body re­ lations. The states of position are= and Bounds; the states of motion are :j;, Outside and Inside, and the Perturbation Principle applies equally in these cases.

7 Axiomatizing perturbations

The perturbation relationships give rise to axioms as follows. Let R be one of the RCC relations, and let its possible pertur­ bations be R1, R2, .. . , Rn (one of these will be R itself, and in any case n = 2 or n = 3). Then we have

Note that these axioms are automatically satisfied if R is a state of position, since it is implied by the defining property of such states together with the fact that R is one of the Ri; for states of motion, though, they have to separately postulated.

A kind of converse of the above pair of axioms is

These axioms are automatically satisfied if R is a state of motion, and only need to be separately postulated for states of position.

A third pair of axioms is required to ensure that the set of temporal instants has the right order type. It would be sufficient here simply to stipulate that they are ordered like the real numbers, but this seems a bit heavy-handed. For what we are going to do below, it is enough to lay down the axioms

We now show that the Perturbation Principle follows from the axioms, together with the defining characteristics of states of motion and states of position.

Suppose we have Holds-at(R(pos(b) , r), t), where R is a state of motion. Then there is an interval (t, t') such that Holds-on( R(pos( b), r), ( t, t')). If R(pos( b), r) ever fails to hold after t', then by (AS) there is a latest time t' such that Holds-on(R(pos(b), r), (t, t')), in which case we must have, from (Al), Holds-at(R'(pos(b), r), t'), where R' is a perturbation of R. We cannot have R' = R, since this would imply that there is a still later time t" such that Holds-on( R(pos( b) , r), ( t, t")), contradicting the maximality oft'. So we see that if an RCC state of motion ceases to hold, it must be immediately followed by one of its perturbations.

Now suppose Holds-at( R(pos( b), r), t ), where R is a state of position. By (A3), there is an interval (t , t') such that Holds-on( R' (pos( b), r), ( t , t') ), where R' is a perturbation of R. If R' 'I R then when R ceases to hold it is immediately followed by one of its perturbations. If R' = R, then by (AS), if Rever ceases to hold there is a latest timet' such that Holds-on( R(pos( b), r), ( t, t')). Since R is a state of position, this implies Holds-at( R(pos( b), r), t'), and by (A3) there is a time t" and a perturbation R' of R such that

From the maximality oft', we know that in this case R' 'I R, and so once again we have that when an RCC state ceases to hold, it is immediately followed by one of its perturbations.

8 Reasoning with Perturbations

In principle we could use the axioms (Al)-(A6) to perform actual reasoning. However, it is much simpler to use the Per­ turbation Principle, which as we have seen is a consequence of the axioms.

For example, suppose we know that

Since PO is not a perturbation of DC, to get from DC to PO we have to pass through a sequence of states DC = Ro, R1. ... , Rn = PO, where each Ri+l is a perturbation of Ri. A suitable chain is DC, EC, PO, and it is easy to see that any other possible chain must contain this one as a subchain. Hence we know that

9 Events

So far, we have only talked about states. Many events can be defined in terms of state changes. This is especially obvious in the case of motion in space. As suggested in [Galton, 1990], we shall replace Allen's predicate Occurs by three predicates Occurs-on, Occurs-in, and Occurs-at. If e is an event type then Occurs-in( e, i) says that an event of type e occurs during the interval i. If the event takes time, and exactly takes up the whole interval i, then we can write Occurs-on(e, i). If, on the other hand, the event is instantaneous (a possibility not countenanced by Allen), and occurs at the instant t, we write Occurs-at( e, t).

We can specify event types in terms of changes in respect of the RCC relations. Consider for example the event of one body's coming into contact with another. Initially, the positions of the two bodies are disconnected (DC) from each other; after contact they are externally connected (EC). The event of making contact is instantaneous, so we define an instantaneous event type contact( b1, b2) by the rule

Another example is the event of a body's entering a region. There are a number of different events that may be being referred to here, depending on what we regard as the beginning and end points of the event. An obvious one to go for is that for a body to enter a region is for it to undergo a transition between being just outside (EC) it to being just inside (TPP) it; call this event-type enter(b, r ). While the event is actually happening, the body is partly in and partly out of the region (PO). Thus we have

Both of the event-types we have considered are examples of transitions2. If R1 and R2 are RCC relations involving the same body/region pair, we define trans( R1, R2) as the type of events in which initially R1 holds, and finally R2 holds. The detailed occurrence conditions depend on whether R1 and R2 are states of motion or position, and whether R2 is a perturbation of R 1 · These also determine whether the event is durative or instantaneous. An exhaustive list of possibilities is

2 See [Gooday and Galton, 1992], where however a somewhat different treatment is given of transitions in general.

1. R1 is a state of position, R2 is a state of motion, R2 is a perturbation of R1.
2. R1 is a state of motion, R2 is a state of position, R2 is a perturbation of R1.
3. R1 and R2 are distinct states of motion, and both have a common perturbation R3 (which must of course be a state of position).
4. R 1 and R2 are distinct states of motion without a common perturbation.
5. R1 and R2 are distinct states of position.
6. R1 is a state of position, R2 is a state of motion, and neither is a perturbation of the other.
7. R1 is a state of motion, R2 is a state of position, and neither is a perturbation of the other.

The occurrence conditions for each of these cases are as fol­ lows.

1. The event is instantaneous, with occurrence condition
2. This case is just the time reversal of Case 1; the occur­ rence condition is
3. The event may be instantaneous or durative, depending on whether the body spends more than an instant in the intermediate state of position. This gives us two occur­ rence conditions

Occurs-at(trans(R1, R2), t) = Holds-at(R1, t) 1\ 3t' Holds-on(R2, (t, t')).

Occurs-at(trans(R1, R2), t) = 3t' Holds-on(R1, (t', t)) 1\ Holds-at(R2, t).

Occurs-at(trans(R1, R2), t) = 3t'3t"(Holds-on(R1, (t', t)) 1\ Holds-on(R2, (t, t"))). Occurs-on(trans(R1, R2), i) = 3i'3i" (Meets( i', i) 1\ Meets( i, i") 1\ Holds-on(R1, i') 1\ Holds-on(R3, i) 1\ Holds-on( R2 , i"))

Note that in the first condition we need not include a con­ junct Holds-at(R3, t) since this follows from the other conjuncts by the perturbation principle (since a given pair of RCC relations has at most one common pertur­ bation). In the second condition we do need the extra conjunct, though by the perturbation principle we could replace it by ...,Holds-in(R1, i) 1\ -,Holds-in(R2, i), thus avoiding any explicit mention of R3.

1. The event must be durative; this case resembles the dura­ tive part of the previous case, except that now we cannot explicitly mention the intermediate states, since we do

not know how many there are or how often each oc­ curs (for example, to get from NTPP to DC, any of the sequences

NTPP, TPP, PO, EC, DC NTPP, TPP, PO, EC, PO, EC, DC NTPP, TPP, PO, TPP, PO, EC, DC NTPP, TPP, PO, TPP, PO, EC; PO, EC, DC

would do). The occurrence condition must therefore be given as

Occurs-on(trans(R1, R2), i) = -,Holds-in(R1, i) 1\ ...,Holds-in(R2, i) 1\ 3i'3i"(Meets( i', i) 1\ Meets( i, i") 1\ Holds-on(R1, i') 1\ Holds-on(R2, i")).

1. The event must be durative, since to get from R1 to R2 we have to pass through at least one intermediate state of motion, which cannot hold just for an isolated instant. The occurrence condition is
2. The event has to be durative, with occurrence condition
3. This is just a time-reversal of the previous case.

Occurs-on(trans(R1, R2), i) = Holds-at(R1, inf(i)) 1\ ...,Holds-in(R1, i) 1\ -,Holds-in(R2, i) 1\ Holds-at(R2, sup(i)).

Occurs-on(trans(R1, R2), i) = Holds-at( R 1 , inf( i)) 1\ ...,Holds-on(R1, i) 1\ ...,Holds-on(R2, i) 1\ 3i'(Meets(i, i') 1\ Holds-on(R2, i')).

Occurs-on(trans(R1, R2), i) = Holds-at( R2, sup( i)) 1\ -,Holds-on(R1, i) 1\ ...,Holds-on(R2, i) 1\ 3i'(Meets(i', i) 1\ Holds-on(R1, i')).

The above list does not exhaust all the kinds of events we will want to refer to; it only handles changes of position of one body with respect to one region. A common kind of event which does not fall under this description is when a body moves from one region to another, say b moves from r 1 to r2. Assuming that b is extended and fits inside both r1 and r2, and that r1 and r2 are disconnected from each other, the occurrence condition for this event-type could be given by

Occurs-on(move(b, r1, r2), i) = Holds-at(TPP(pos( b), r 1), inf( i)) 1\ Holds-at(TPP(pos( b), r2), sup( i)) 1\ -,Holds-in(TPP(pos( b), r 1), i) 1\ -,Holds-in(TPP(pos( b), r2), i).

Here the assumption is that for the event to occur, b must start inside r1 and end up inside r2; the relation TPP is required since this will hold when b has just entered or is just about to leave a region. One might instead suggest that the relation we should be considering is PO, or EC. For a point body the relation could be either Bounds or Inside. Only experience with applying the formalism to particular reasoning tasks will tell us what the most suitable events to define are: what matters is that our system provides a good basis for a wide range of possible definitions.

A final example is the event of a body b's passing through a region r. Our formalism allows us to consider various dif­ ferent ways of describing this event and to choose the one that best suits our purposes. In figure 2, three possible trajectories are shown. An obvious choice for 'passing through' is to allow trajectories of types A and B, but not of type C. This would give us the occurrence condition

Occurs-on(transit(b, r), i) = Holds-at(EC(pos(b), r), inf(i)) 1\ Holds-at(EC(pos( b), r), sup( i)) 1\ ...,Holds-in(EC(pos(b), r), i) 1\ Holds-in(TPP(pos( b), r), i)

This covers type B as well as type A since by the perturbation principle a body must pass through TPP in order to get from EC to NTPP. If we want to allow trajectories of type C too, then all we need to do is to replace the last conjunct of the occurrence condition by ...,Holds-in(DC(pos( b) , r) , i) .

For a point body p passing through a region r only one type of trajectory is possible, corresponding to the occurrence condition

Occurs-on(transit(p, r) , i) = Holds-at(Bounds(pos(p ), r ), inf( i)) 1\ Holds-at(Bounds(pos(p) , r), sup( i)) 1\ Holds-on( I nside(pos(p), r), i)

In general, events involving point bodies are simpler to de­ scribe than those involving extended bodies since there are fewer RCC-type relations to consider.

10 Conclusion

We took the temporal logic of [Allen, 1984], as modified by [Galton, 1990], and combined it with the spatial logic of [Randall et al., 1992a and 1992b] to produce a simple but expressive logic of space, time, and continuous motion for rigid bodies.

Continuity was ensured by means of the Perturbation Prin­ ciple, which makes use of the distinction between states of position and states of motion introduced in [Galton, 1990]. A

set of axioms was given from which the Perturbation Principle follows.

In addition we showed how we could use our system to define a variety of event -types by specifying their occurrence conditions in terms of the elementary positional relations on bodies and regions.

Acknowledgments

I am grateful to John Gooday for critically reading several drafts of this paper, and to the anonymous referees for anum­ ber of useful suggestions for improving it.