page 1  (1 pages)

1 2
This paper appeared in `Recent Advances in Qualitative Physics' ed. P Struss and B Faltings, MIT Press, 1992

Naive Topology: modelling the force pump

D. A. Randell, A. G. Cohn and Z. Cui

12.1 Introduction

AI has long sought computationally efficient and expressive ways to represent non-trivial domain knowledge within a formal framework. One clear example of this can be found in the Naive Physics programme [HAYE85a]. In the spirit of this programme, we outline a concise and rigorous formalism being developed [RACO89, RACO90] that is being used to reason about space and time. We illustrate this with a partial axiomatisation of a force pump. While we note the controversy Hayes' programme has generated [LEVE87], we are encouraged that our approach actually bodes well for the central ideas Hayes advocated.

We use our formalism to exploit topological and geometrical information inherent in descriptions and explanations that appear in everyday discourse about the physical world. Much of this information appears to be used unconsciously; however a little reflection on our use of language soon reveals how important this information is e.g. in the use given to prepositions or prepositional phrases. While we do not assume that our informal linguistic descriptions necessarily reveal those entities represented and exploited by the brain in all such activity (e.g. in the encoding of perceptual information), it is interesting to see that many of the underlying concepts expressed in our formalism are surprisingly intuitive. We do not give much emphasis to `naive' notions supposedly underlying our conceptual framework; instead we seek to build a rigorous formal theory that gives rise to these intuitive notions.

The structure of the rest of this paper is as follows. Section 1.2 discusses related work. Section 1.3 is a synopsis of the formalism (covered in more detail in [RACO90]). Section 1.3.1 develops the temporal parts of the formalism, and section 1.4 illustrates the use of the formalism with a partial axiomatisation of a force pump.

4 Chapter 12

12.2 Related work

Hayes [HAYE85a] and Welham and Hayes [WEHA84] discuss the importance of building large scale formalisms encoding topological information. Part of the motivation is centred on the assumption that experiential knowledge needs to be exploited if AI is to be able to tackle non-trivial domain problems. A clean semantics is secured by the preferred use of first order predicate logic both as a representation language into which theories should be capable of being translated and as a reference language by which competing formalisms and theories can be compared. Ontology for Liquids [HAYE85b] still stands as Hayes' main contribution to applied Naive Physics.

A collection of papers dealing with commonsense knowledge and reasoning appears in [HOMO85] and [HOBB85]. Many of these papers suffer to some extent from the free use of axioms without demonstrating the worth of their respective formalisms and theories in terms of interesting deductions. Leyton's [LEYT88] process grammar represents an alternative approach. Changes in measures of curvature extrema are exploited and provide the basic geometry by which processes can be modelled. Transformation of shape is covered but the modelling is restricted to capturing geometrical properties of homogeneous entities. Allen and Hayes [ALHA85, ALHA87a, ALHA87b] develop a theory of time that exploits topological information, but do not consider the possibility of a unitary formalism that captures both spatial and temporal topological information. Davis [DAVI88] describes a very expressive first order formalism for reasoning about solid object behaviour; the whole being illustrated by modelling the possibility and passage of a die passing through a funnel. Davis exploits several concepts that also appear in our formalism although the basic set of primitives in the two formalisms differ. Other related work can be found in [KULE88, FNF87, BLIZ90].

12.3 The formalism

The formalism [RACO90] is expressed in a many sorted logic allowing arbitrary ad hoc polymorphism on predicates and functions [COHN89] and is rooted in a calculus of individuals developed by Clarke[CLAR81, CLAR85]. It should be noted that variables in formulae derive their sortal restrictions implicitly from the argument positions they occur in.

5

Space does not allow a detailed description of the logic or the sortal apparatus used, but important sortal restrictions will be highlighted.

The domain of discourse includes regions as a primitive sort upon which the bulk of the formalism is built. Regions may either be spatial or temporal. Informally these regions may be thought to be potentially infinite in number, and any degree of connection between them is allowed.

Two primitive relations: `C(x; y)' read as `x is connected with y' and `B(x; y)' (`x is (temporally) before y') are used to define a set of dyadic relations defined on regions. Regions that connect cover all cases from external connection to identity. A subset of the relations defined using `C(x; y)' as the sole primitive include: `DC(x; y)' (`x is disconnected from y'), `P(x; y)' (`x is a part of y'), `PP(x; y) (`x is a proper part of y'), `O(x; y)' (`x overlaps y'), `EC(x; y)' (`x is externally connected with y)', `TPP(x; y)' (`x is a tangential proper part of y') and `NTPP(x; y)' (`x is a nontangental proper part of y'). Definitions for the complete set of dyadic relations based on `C(x; y)' and all the undefined constants, functions, predicates and relations referred to in the text can be found in [RACO89, RACO90].

We add a primitive function `conv(x)' (`the convex-hull of x') defined on spatial regions only. Intuitively, this function returns the region of space that would arise by completely enclosing a body in a taught cling film membrane. We use this function in a set of defined relations used to describe regions being inside, partially inside and outside, e.g. `P- Inside(x; y)' (`x is partially inside y') and `J-Outside(x; y)' (`x is just outside y'). Here we also define two related functions: `inside(x)' (`the inside of x') and `outside(x)' (`the outside of x') 1.

inside(x) =def ?y[8z[C(z; y) $ 9w[Inside(w; x) _ C(z; w)]]]

outside(x) =def ?y[8z[C(z; y) $ 9w[Outside(w; x) _ C(z; w)]]]

Additional functions supported by the formalism include a standard set of Booleans e.g. `sum(x; y)' (`the sum of x and y') , `prod(x; y)' (`the product of x and y'), `diff(x; y)' (`the difference between x and y'), and a further set of topological operators, e.g. `int(x)' (`the interior of x') and `cl(x)' (`the closure of x'). Partial functions e.g. `prod(x; y)' which

1With respect to defined functions, when we write ff(x) =def: ?y[?(y)] we mean 8x?[ff(x)] { this convention clarifies the ambiguity inherent in the notation used in [RACO89]

6 Chapter 12

does not return a region when :O(x; y) are made total by returning an object of sort Region t Null, where Null is a new sort which is disjoint from Region 2. We also introduce atomic regions (`Atom(x)' (`x is an atom')) being regions with no sub-parts, and closed atoms (`C-Atom(x)' (`x is a closed atom')) being their closures. The proper part relations are complemented with a set of `surround' relations, e.g. the relation `NTS(x; y)' (`x is nontangentially surrounded by y') is the surround analogue of the relation `NTPP(x; y)', where in the surround case both x and y are discrete and y wraps around x instead of x being a part of y in the `NTPP(x; y) case. Among the many concepts expressed in this formalism, only a few others are mentioned here: individual connected and disconnected regions (`Con(x)' and `Discon(x)'), simply connected regions (`S-Con(x)') and a quasi-manifold (`Manifold(x)'). Individual disconnected regions are regions that are not in one piece, whereas simply connected regions are regions without `holes'. The latter concept appears as a primitive predicate in the formalism, and is used to define multiply connected (M-Con(x))(i.e. `holed') regions. Finally, a quasimanifold is defined as a region that has a connected (i.e. one piece) interior. Given two regions that are externally connected, the composite region is a quasi-manifold if (for bodies) they share a `fused' surface, i.e. the degree of connection is not restricted to points or edges.

Manifold(x) ?def Con(int(x))

12.3.1 The Temporal Formalism

We now give a brief summary of the temporal ontology used. Temporal regions are called periods and are open. We define moments to be periods that have no parts such that one part is before the other. Moments are temporal atoms and are totally ordered. Intervals are periods that are not moments.

A set of dyadic relations are then defined on periods using the primitive relation `B(x; y)'. Although we can define analogues of all the 13 mutually exclusive and exhaustive3 dyadic relations common to interval logics e.g.[ALHA85], in fact all we shall need here is the relation

2The many sorted logic we use allows the sorts of terms to more general than the argument positions they occupy. This allows formulae such as `O(x, prod(x;x))' to be well sorted { see [COHN89].
3In fact there are more than 13 possible relations between periods if we also consider disconnected periods.

7

`Meets(x; y)' which is irreflexive, asymmetric and transitive.

Meets(t1; t2) ?def :9t3[B(t1; t3) ^ B(t3; t2)]

Descriptions of the world over time are expressed in terms of either states or events using Galton's [GALT84] characterisation. By a state we mean some description of the world that remains true over some specified period of time, which also applies to any sub-period of that specified period. In contrast, an event is taken to entail a change in truth value for the period it endures for. Processes are simply viewed as specified sequences of temporally linked states or events. While we recognise that some processes do not have either an identifiable initial or final moment over which they endure, here we assume all our processes to be bounded with an initial and final moment of existence.

Our ontology of time is similar to that expounded by Allen and Hayes [ALHA85, ALHA87a] although we here initially used material from [CARN58] when developing this part of the formalism. One difference between our axiomatisation and Allen and Hayes', is that we explicitly axiomatise periods as open regions and moments as atomic. There is also a difference between the interpretations given to both formalisms, e.g. while Allen and Hayes consider beginnings and ending of moments, we say that beginnings and endings of periods are moments.

We add three temporal functions to the theory, `initial(t)' (`the initial moment of t'), `final(t)' (`the final moment of t') and `next(t)' (`the next moment after t'). Sortal restrictions are required for these functions, e.g. final(t) is only well sorted for periods bounded above. We abbreviate

initial(t) as t and final(t) as
!
t .

initial(t1) =def ?t2[Interval(t1) ^Moment(t2) ^ PP(t2; t1) ^

:9t3[Moment(t3) ^ PP(t3; t1) ^B(t3; t2)]]

final(t1) =def ?t2[Interval(t1) ^ Moment(t2) ^ PP(t2; t1) ^

:9t3[Moment(t3) ^ PP(t3; t1) ^B(t2; t3)]]

next(t1) =def ?t2[Moment(t2) ^ Meets(t1; t2)]

Increasing, decreasing and constancy measures over time are treated as follows. The metalogical n-ary function `OE(x)' used below is to be understood as being replaced with appropriate functions, eg. `pressure(x)' read as `the pressure of x', `volume(x)' read as the volume of x' and `distance(x; y)' read as `the distance between x and y'. The function

8 Chapter 12

`at(OE(x; t)' read as `OE(x) at t' has the intended meaning that OE(x) holds at the moment t. The symbols `<',`>',` <=',` >=', and `=' carry their standard meaning. The relation `Increase(x; t)' is read as `x increases over t',`Decrease(x; t)' as `x decreases over t' and Constant(x; t)' as `x is constant over t': A metalogical function OE(x) maps a physical body to its OE-history, e.g., the function temp(x) maps x to the range of temperatures x undergoes throughout its entire history. One can think of this function has generating a temperature/time curve for x. The instantiated term at(temp(x); t) then maps the temperature history of x, at a moment in time t to a number. For each case of OE(x), some unit of measure is assumed, e.g., temp(x) returns the temperature history of x in degrees Celsius; hence at(OE(x; t) is a pure number4.

Increase(OE(x); t1) ?def at(OE(x); t1) < at(OE(x);
!
t1) ^ 8t2t3

[[P (t2; t1) ^ P (t3; t1) ^ B(t2; t3)] ! at(OE(x); t2) <= at(OE(x); t3))]

Decrease(OE(x); t1) ?def at(OE(x); t1) > at(OE(x);
!
t1) ^ 8t2t3

[[P (t2; t1) ^ P (t3; t1) ^ B(t2; t3)] ! at(OE(x); t2) >= at(OE(x); t3))]

Constant(OE(x); t1) ?def 8t2t3[[P (t2; t1) ^ P (t3; t1)] !

(at(OE(x); t2) = at(OE(x); t3))]

We distinguish between a physical object and the space it occupies: a two place function (cf Hayes' one place space function[HAYE85b]) space(x; t) yields the spatial region occupied by x at the moment t, or is of sort Null if x does not exist at t. For brevity we will write xjt instead of space(x; t).

12.4 Modelling the force pump.

A force pump is illustrated in Figure 1. For simplicity, we assume the pump is primed and that the reservoir feeding the inlet pipe is always full of liquid. The pump has two valves, valve1 and valve2 which open by door1 and door2. The doors are hinged to the pump body closing

4Three additional primitive sorts supported by the many sorted logic are being used here: Physical-Object, Measure and Number. The function OE(x) takes an argument of sort Physical-Object and returns a value of sort Measure (the OE-history). The function at(OE(x); t) has Measure and Moment as argument sorts, and returns a value of sort Number.

9

portals portal1 and portal2 respectively.5

top-chamber
J
J
J J

portal3
S
S
plunger
? ?
pump-body

? ? piston

?
?
? ? outlet-pipe

door2
`
`

portal5
@
@@

portal2

T
T T
door1

e
e e

inlet-pipe
HH

portal4

portal1
?
? ?
main-chamber
<=
<=
<= <=

..................................................
..................................................
............
..........
?
? ?
........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
........................................................................................................................................................................................................

..............................................................................................................................................................................................
..................................................

..................................................

..........
............. ......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.................................................................................................................................................................................................................................................................................................................................................................................. ..........................................................................................................................................................................
..............................................................................................................................................................................................

8t[M-con(pump-bodyjt)]
8t[PP(portal1; inside(pump-bodyjt))]
8t[PP(portal2; inside(pump-bodyjt))]
8t[PP(portal3; inside(pump-bodyjt))]
8t[Inside(pistonjt; pump-bodyjt)]
8t[EC(plungerjt; pump-bodyjt)]
8t[P-Inside(plungerjt; pump-bodyjt)]
8t[:Con(diff(inside(pump-bodyjt); pistonjt))]
[DC(sum(top-chamber,portal3);
sum(portal1; portal2; main-chamber))]
8t[J-Outside(inlet-pipejt; pump-bodyjt)]
8t[EC(inlet-pipejt; pump-bodyjt)]
8t[J-Outside(outlet-pipejt; pump-bodyjt)]
8t[EC(outlet-pipejt; pump-bodyjt)]
8t[Shut(valve1; t) ^ Shut(valve2; t)] !
[NTS(main-chamber;
sum(pistonjt; pump-bodyjt; door1jt; door2jt))]]
valve1 = valve(portal1; door1jt)
valve2 = valve(portal2; door2jt)

Figure 1: A force pump

.................................................. ..................................................
......
.....
? ? ........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
........................................................................................................................................................................................................
..............................................................................................................................................................................................
..................................................
..................................................
........

.................................................. ..................................................
.....
..................................................
..................................................
........

.................................................. ..................................................
.....
..................................................
..................................................
............ ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... .................................................................................................................................................................................................................................................................................................................................................................................. ..........................................................................................................................................................................
..............................................................................................................................................................................................

.................................................. ..................................................
.....
..................................................
..................................................
........

Figure 2: Cycle of the force pump

oe

oe

oe

-

5Portals are of course pure spatial regions rather than physical objects. In this paper we will just name portals, though they are definable (within the formalism) in terms of the space occupied by physical objects that they are portals of.

10 Chapter 12

On the upstroke, valve1 is not shut, while valve2 is shut. This arises because the upthrust pressure of the liquid acting upon door1 is greater than the downthrust forces acting on that door. The pressure difference opens the valve door and allows the liquid to pass from the inlet pipe into the main chamber. During this process the door of valve2 remains closed, sealing valve2. In this case atmospheric pressure acting on the door plus that arising from any liquid in the outlet pipe, thrusts the door into the portal effecting a seal. A similar chain of processes arise with the downstroke of the piston. In this instance valve1 shuts and valve2 opens and the liquid passes from inside the pump body out into the outlet pipe. The cycle is then repeated.

Figure 2 represents a pictorial series of topological state descriptions coinciding with one cycle of the operation of the pump. For simplicity we have assumed that when the piston is either at the nadir of its upward or downward motion, the next moment in time coincides with both valves being shut. In actual fact this would not arise in a primed and working force pump, e.g. valve1 would remain open for a few moments as the piston travelled on its downward path. Other strong assumptions implicit in the description of the working pump are covered below.

First of all we build up the pump from a library of component parts. In Figure 1 we list some formulae which describe the components of the pump and their topological relationships; space precludes a complete listing. The pump body is a multiply connected object with three portals, portal1, portal2 and portal3 which are proper parts of its inside. Note that the portals are represented as membrane like regions inside the pump body whose outer surface typically coincides with the exterior surface of the pump body. This makes a portal distinct from any passageway that might link the outside of a body from some inner chamber that might exist (as in our example). Portals are specifically defined not to be surface only or having zero-thickness.

The definition of a portal is as follows. A portal x of a region y is defined as a part of the inside of y and composed of the sum fusion of the closed atoms forming part of the inside of y and connecting with the outside of y. `Portal(x; y)' is read as `region x is a portal of region y' and `Portal(x)' as `x is a portal' and Portal(p; x; t) as p is a portal of physical object x at moment t or throughout interval t.

11

Portal(x; y) ?def P(x; inside(y)) ^

8z[C(z; x) $ 9w[C-atom(w) ^ P(w; inside(x)) ^

C(w; outside(x)) ^ C(z; w)]] ^ Manifold(sum(x; outside(y)))

8x[9y[Portal(x; y) $ Portal(x)]]

Portal(p; x; t) ?def 8t1P(t1; t) ! Portal(p; xjt1)

By making portals regions and not parts of the boundary interface between the inside and outside of bodies, properties that can be ascribed to regions can be ascribed to portals. In particular, if the space taken up by a portal's door seals a passageway between the interior (in the non-topological sense) of a pump body and its outside (hence filling in the portal), we can infer that the portal is sealed.

A piston with plunger attached and two pipes, an inlet and outlet pipe, are added. Since the piston always forms a seal with the inner wall of the pump body, adding the piston means that two disconnected chambers are created, the main and top chamber. It is worth pointing out that our formalism can make this relationship explicit.

It would be useful to be able to pick out that region of the pump that functions as the main chamber. Given our model, this can be done as follows. First we take the sum region of the pump body and its inside, and then we take the difference between this composite region and the piston. The resulting region is disconnected and yields the topchamber, the main-chamber and passageways linking these chambers to the outside of the pump body. The main-chamber is now picked out by taking that region connected to portal1, and then taking the maximal convex region that is part of it. It should be noted that we do not explicitly name and define these passageways and all of their portals, but a complete description of the pump at the level of detail we are considering would include these.

Valves are created by adding hinged doors to the pump body which can seal their respective portals. We represent valves as a two place functor valve(x; y) whose argument sorts are Portal, Door.

The axioms given below establish a relationship between the pump's valves, the regions that straddle them and the possibility of liquid flow through the valves. The first axiom states that a valve is shut iff the valve's portal is filled by (part of) the (solid) valve door. The predicate

12 Chapter 12

`Shut(x; t)' read as `x is shut throughout or at t' has the obvious intended meaning that x has a sealed aperture; while `Solid(x)' read as `x is solid' denotes the empirical notion of solidity or inpenetrability.6 The definition of Sealed(p,t) states that a portal is sealed iff it is part of anything solid.

8pyt[Shut(valve(p; y); t) $ 8t1[P(t1; t) ! P(p; yjt1)]

Sealed(p; t) ?def 8t1P(t1; t) ! 9x[P(p; xjt1) ^ Solid(x)]

8x[Door(x) ! Solid(x)]

For example, given that valve1 = valve(portal1; door1) we can see that if for some moment in time t, valve1 is shut, door1 seals portal1 making it a solid region and hence `Sealed(portal1; t)'; and that conversely if valve1 is not shut, portal1 is not sealed by door1 and hence (by a closed world assumption) valve1 is open.

Additional axioms give functional definitions of liquid outflowing, inflowing and being static with respect to a portal. Note the use put to

the part-whole relation P(wj t1; xj t1,)". Here we use the relation to capture the idea of some quantity of a liquid body moving e.g. outside the portal over time.

Outflowing(x; p; t1) ?def Liquid(x) ^ 9zw[Portal(p; z; t1) ^

:Sealed(p; t1) ^P(wj t1; xj t1) ^P(wj t1; inside(zj t1)) ^

O(wj t1; p) ^ J-Outside(wj
!
t1; z) ^ C(wj
!
t1; p)]

For example, if we know that Outflowing(liquid1, portal4; t1) then we can see that during this outflowing of liquid from portal4 i.e. out from the portal of the inlet pipe (and into portal1) at time t1, a quantity of liquid overlapping portal4 moves to be just outside the inlet-pipe and (with the last condition) just outside portal4.

Inflowing(x; p; t1) ?def Liquid(x) ^

9zw[Portal(p; z; t1) ^ :Sealed(p; t1) ^P(wj t1; xj t1) ^

J-Outside(wj t1; zj t1) ^ C(wj t1; p) ^

P(wj
!
t1; inside(zj
!
t1)) ^ O(wj
!
t1; p)]

Static(x; y; t1) ?def 8t2[P(t2; t1) !

[:Outflowing(x; y; t2) ^ :Inflowing(x; y; t2)]]

6Here we assume that being solid is not a fluent.

13

The processes just defined are non-dissective: if ` Outflowing(x; y; t)' is true it is not necessarily true that `Outflowing(x; y; t0)' where t0 is a subinterval of t. We can easily define dissective versions of these processes if desired; for example here is a dissective Outflowing:

Dissective-Outflowing(x; p; t) ?def 8t1[Moment(t1) ^

B( t ; next(t1)) ^ B(t1;
!
t ) ! Outflowing(x; p; sum(t1; next(t1)))]

A relation for connected portals, where `Connected-Portal(x; y)' is read as `x and y are connected (i.e. adjacent) portals' is defined;7 and an axiom that states that for any two connected portals, outflow from one coincides with an inflow into the other is given. With the modelled pump we can then assert that Connected-Portal(portal1, portal4) and Connected-Portal(portal2, portal5). The definition of connected portals ensures that the connection between them is not point-like and that they are totally aligned.

Connected-Portal(x; y) ?def Portal(x) ^ Portal(y) ^

Manifold(sum(x; y)) ^ 8z[[P(z; x) ^ C-Atom(z)] ! C(z; y)] ^

8w[[P(w; y) ^ C-Atom(w)] ! C(w; x)]

8xyt[Connected-Portal(x; y) !

[Outflowing(z; x; t) $ Inflowing(z; y; t)]]

The axioms and definitions given above are sufficient to make the following deductions. Suppose valve1 is shut. We can then infer that since portal1 is part of door1 (ie. occupied by the door), the portal is not open. We can then deduce that no inflowing or outflowing can arise through the portal (or between the connected portals). Hence the liquid within the pump is static with respect to portal1. With the converse case when valve1 is not shut either an inflowing or outflowing may arise across the connected portals.

Directionality of liquid flow through the valves in the example pump is fixed (eschewing the realistic case where e.g. portal1 would actually experience bi-directionality of flow over time as the piston commenced on its downstroke and the valve was closing). Appropriate axioms fixing

7Note that the definition for connected portals requires that both portals are the same size assuming atoms are all the same size. It is possible to weaken the definition so as to include the case where, for example, portal4 is larger than portal1.

14 Chapter 12

the directionality of the flow could be formulated as follows:

In-valve(valve(x; y)) ?def 8t1f:Outflowing(f; x; t1)

Out-valve(valve(x; y)) ?def 8t1f:Inflowing(f; x; t1)

In-valve(valve1) ^ Out-valve(valve2)

We recognise some strong assumptions underlying the use of these biconditionals used in the axiomatisation, e.g. that at all times no foreign body blocks the valve (even though the door may remain open) and that the liquid does not undergo any change of state. This has been done to simplify the example, but we see no indication that such restrictions are a by-product of the formalism and its underlying ontology.

As yet, no information has been given covering either causal factors or the initial conditions required for fluid to flow through the pump. But it is not that difficult to see what could be added and exploited. For example we could state that the inlet pipe must be filled with liquid in order for the liquid to pass into the pump body on the upstroke of the piston. Given the simple case of a primed pump this fact is easily expressed in the formalism:

9x8t[Liquid(x) ^ P(inside(inlet-pipejt); xjt)]

i.e. that the inside of the inlet pipe is part of a liquid body - which is to say the pipe is (in this instance always) full of liquid! The fact that liquid can be drawn up into the inlet pipe and into the pump body ie. that the condition given above need not hold to get liquid into the pump could be expressed in the formalism reasonably easily. In this case it would be useful to add an axiom abstracting out the direction of inequalities expressed by Boyle's Law which states that at constant temperature the pressure of a given mass of gas is inversely proportional to its volume.

8xt[[Gas(x) ^ Constant(temp(x); t)] !

[Increase(pressure(x); t) $ Decrease(vol(x); t)]]

Given this information we could reason that when the pump is started (and with the inlet pipe placed in a reservoir filled with liquid) the act of pulling up the piston would coincide with the trapped air in the pump (constant mass) increasing in volume. Assuming portal1 was not sealed this would mean that forces arising from the atmospheric pressure acting on the reservoir fluid would propagate through the liquid. This would

15

force the liquid into the inlet pipe and eventually into the pump body. Indeed we could adopt a rather naive view of suction by stipulating that at all times a pocket of air exists between the bottom face of the piston and the liquid in the pump body; and that when the piston moves upward, the volume of the air pocket increases, its pressure drops, and the liquid fills the vacuum formed. In the downstroke process the trapped air would decrease in volume resulting in its internal pressure increasing which would force the liquid down and through the outlet pipe.

12.5 Further Work

A complete axiomatisation of the pump has yet to be done. However we outline how this could be tackled. Firstly, it would be useful to be able to pick out those surfaces of the liquid that come into contact with the surfaces of the valve doors, the piston and the air/liquid interface (known as the free surface). By doing this the action of an external force on such bodies (or impressed force of liquid on an object) could be set up using an appropriate function. We already have definitions that pick out the region that may be construed as the outside `surface' or `skin' of an object. Below we give the definition for the skin of a closed region8.

The skin of a region x is the sum fusion of all those atoms that are tangential proper parts of x". Given this function it is possible to define the free surface of a liquid body.

skin(x) =def ?y[8z[C(z; y) $

9w[C-Atom(w) ^ TPP(w;x) ^ C(z; w)]]]

free-surface(xjt) =def ?y[8z[C-Atom(z) ! [P(z; y) $

Liquid(x) ^ P(z; skin(xjt)) ^ 9v[(Air(v) ^ C(z; v)]]]]

With the free-surface defined, and an adequate characterisation of one region being above (or below) another, we could reason that if the free surface of the liquid did not overlap the bottom portal of the inlet pipe, no additional water from the reservoir could be pumped through the pump. We could link the varying volume of liquid in the pump body to the position of the piston in the chamber. To do this requires some

8We are particularly indebted to Ian Gent whose insight led to the definition given here.

16 Chapter 12

means to pick out e.g. surfaces of component parts of the pump and parts of the surface of the pump body. The formalism has a primitive distance function `d(x; y)' (`the distance between x and y') which could be used here, e.g. we could simply say the piston moves up in the pump if the distance between it and portal1 increases (assuming rigidity of the component parts!). In turn this would be linked with differences in pressure between bodies of liquid and whether or not valves were shut. We need to be able to reason that when the piston is drawn up, the downthrust force of the piston acting on the contained fluid is less than the atmospheric pressure acting on the free surface of the fluid in the reservoir. The downthrust force of the atmospheric pressure propagating a force through the liquid results in an upthrust force on the piston/liquid surface interface (if we assume no pocket of air between the two, or between the liquid/air and air/piston surface interfaces if we do). Pressure differences serve to force the liquid through the inlet pipe and into the main chamber; valve1 opens because the external force of the liquid impressed on its underside is less than the sum of the forces acting on the other side of the door.

Additional empirical information can be added and exploited in the formalism. For example, rigidity in a body would mean that deformability could not arise, physical solid objects would not overlap if originally discrete. Liquids could be construed as incompressible (having constant volume with respect to compressive forces) connected regions which can deform (changing their convex hull) and pass into and fill insides of regions. In contrast gaseous objects would have the property of filling and occupying the inside of some sealed container; below we define the relation of being sealed within and the property of being a container. We recognise that the latter definition is for a generalised container and that containers vary according to the material being considered is to be contained, question of gravity and orientation and so on.

Sealed-Inside(x; y; t) ?def Container(y; t) ^ 9z[P(z; yjt) ^

Inside(xjt; z) ^ 8p[Portal(p; z) ! Sealed(p; t)]

Container(x; t) ?def [Solid(x) ^ Hollow(x)] _ 9p[Portal(p; xjt)]

One final point worth making is that we have blurred two separate notions of `part' in the above. The predicate symbol `P' of the topological logic is not the same as a component part (e.g. when we talk of the valve being part of the pump). The former is defined only on

17

regions whilst the latter is only defined on physical objects. We can now attribute characteristics to component parts which might not be true of a topological part.

8x[Force-pump(x) ! 8y[Component-part(y; x) ! Rigid(x)]]

8xyt[Component-part(x,y) ! P(xjt; yjt)]

12.6 Final Comments

We have concentrated upon spatial topological descriptions to illustrate the descriptive power of the formalism though we have started to develop the temporal and process related aspects of the formalism (which had been ignored in [RACO89]). Our approach is that certain processes can be adequately modelled by linking and ordering appropriate state descriptions over which some topological or metrical property remains invariant. Although not exploited in this paper, continuity constraints on the transformation of regions over time can be defined. Re-description of asymmetrical part/whole relations is also allowed so that a region can either be described as a part of a whole or as being surrounded by another region. This feature is used in our work modelling phagocytosis [RACO89] where a food particle can either be regarded as a part of a cell or surrounded by a cell but forming no part of it.

We are confident that the underlying richness of the concepts captured in this formalism makes it especially attractive as a representation language where topological and geometrical information is in abundance.

12.7 Acknowledgements

The financial support of the SERC on a studentship and on grant GR/G 36852 is gratefully acknowledged. In the preparation of this paper we have benefited from discussions with many people, and in particular with Ian Gent, Felix Hovsepian, Guy Saward and David Mond.

Bibliography

[ALHA85] J. F. Allen, P. J. Hayes: A Common Sense Theory of Time," in Proc. IJCAI, Morgan Kaufmann, Los Altos., 1985

[ALHA87a] J. F. Allen, P. J. Hayes: Moments and Points in an Interval-Based Temporal Logic," (TR180), Rochester, NY, Depts of Comp. Sci. and Phil., 1987

[ALHA87b] J. F. Allen, P. J. Hayes: Short time periods," Proc IJCAI, Morgan Kaufmann, Los Altos., 1987

[BLIZ90] W. D. Blizard: A Formal Theory of Objects, Space and Time," J. of Symbolic Logic, Vol. 55 No. 1, 1990

[CARN58] R. Carnap: Introduction to Symbolic Logic and its Applications," translated by H. Meyer and J. Wilkinson, Dover, NY, 1958

[CLAR81] B. L. Clarke: A Calculus of Individuals Based on Connection," Notre Dame Journal of Formal Logic, Vol. 2, No. 3., 1981

[CLAR85] B. L. Clarke: Individuals and Points," Notre Dame Journal of Formal Logic Vol. 26, No. 1, 1985

[COHN89] A. G. Cohn: On the Appearance of Sort Literals: a non-substutional framework for hybrid reasoning," in Principles of Representational Reasoning ed. R. J. Brachman et al, Morgan Kaufmann, Los Altos, 1989.

[DAVI88] E. Davis: A logical framework for commonsense predictions of solid object behaviour," AI in Engineering vol. 3(3), pp 125-138. 1988

[FNF87] K. D. Forbus, P. Nielsen, B. Faltings: Qualitative Kinematics: a Framework," Proc IJCAI, Morgan Kaufmann, Los Altos, 1987

[GALT84] A. Galton: The Logic of Aspect," Clarendon Press, Oxford., 1984

[HAYE85a] P. J. Hayes: The Second Naive Physics Manifesto," in [HOMO85]

[HAYE85b] P. J. Hayes: Ontology for Liquids," ibid.

[HOBB85] J. R. Hobbs et al: Commonsense Summer: Final Report," Stanford University, Report No. CSLI-85-35 1985

[HOMO85] J. R. Hobbs, R. C. Moore:(eds.) , Formal Theories of the Common Sense World," Ablex: Norwood.,1985

[KULE88] B. Kuipers, T. S. Levitt: Navigating and Mapping in Large-Scale Space," AI Magazine., Vol. 9(2), pp. 25{43, 1988

[LEVE87] H. Levesque et al: Taking Issue/Forum: A Critique of Pure Reason,"Comp. Intel. vol. 3, No. 3. 1987

[LEYT88] M. Leyton: A Process Grammar for Shape," AI, Vol. 34. 1988

[RACO89] D. Randell, A. G. Cohn: Modelling Topological and Metrical Properties in Physical Processes," in Principles of Knowledge Representation and Reasoning, ed. R. J. Brachman, H. Levesque and R. Reiter, Morgan Kaufmann, Los Altos. 1989

[RACO90] D. A. Randell, A. G. Cohn: Exploiting Lattice in a Theory of Space and Time," Computers and Mathematics with Applications, to appear.

[WEHA84] B. Welham, P. J. Hayes: Notes on Naive Geometry," HP Labs Bristol and Schlumberger Palo Alto research Labs. 1984