From Images to Bodies: Modelling and Exploiting Spatial Occlusion and Motion Parallax

1 Introduction

Spatial occlusion (or interposition) arises when one object obscures the view of another. Spatial occlusion is one of several visual cues we exploit to build up our awareness of three-dimensional form and distance. Another is motion parallax, whereby a change in viewpoint causes relative displacements of objects at different distances in the visual field [Braddick and Atkinson, 1982]. Occlusion events help us determine where an object's boundary lies, or infer why an object cannot be seen, and what we need to do in order to render it visible.

For example, consider two objects A and B in an agent's visual field. Suppose the agent moves to its left, while keeping these objects in sight. If object A passes across B, or, when moving toward A, B becomes completely obscured, the agent can infer that A is in front of B. Similarly, if, when moving to the right, no relative change arises, the agent may infer that A and B are far away, or close by and possibly moving in the same direction as itself. Conversely, if A, when visible, always appears to be subtended by B, the agent may infer that A and B are physically connected. In each case, occlusion events and motion parallax are being used to derive an objective model of the world from a naturally restricted viewpoint (Figure 1).

While visual occlusion remains a topic of some interest in the machine vision literature [e.g., Plantinga and Dyer, 1990; Geiger, et al., 1995], an opportunity arises to investigate occlusion within the Qualitative Spatial Reasoning (QSR) domain. For example, Galton's [1994] Lines of Sight calculus outlines a theory of occlusion for modelling convex bodies using a discrete set of 14 occlusion relations. It is natural to take a topological approach to modelling occlusion, since occlusion events are very general, and apply to all objects irrespective of their size, shape and function. Petrov and Kuzmin [1996] provide an axiomatisation of spatial occlusion founded on a point-based ontology.

Randell, et al. [1992] develop a mereo-topological theory, RCC-8, used to describe spatial relationships between regions based on the primitive relation of connection. Cui, et al. [1992] use RCC-8 to develop a qualitative simulation program to model physical processes by specifying direct topological transitions between these relations over time. Their work is one example of using qualitative spatial representations to model continuous change [Cohn, 1997]. ROC-20 extends RCC-8 to reason about relative distances between bodies from occlusion events, and transitions between occlusion events to model the effects of motion parallax from both object motion and changing viewpoints.

2 The Formal Theory

Our universe of discourse includes bodies, regions and points, all forming pairwise disjoint sets. In terms of interpretation, bodies denote physical objects, while regions split into two further disjoint sets that denote either three-dimensional volumes (typically the spaces occupied by bodies) or twodimensional regions (typically projected images of bodies as seen from some viewpoint).

For the purposes of this paper, a set of sorts and a sorted logic are assumed. Within the sorted logic, possible values of variables in formulae are derived implicitly from the specified sort of the argument position in which it appears, allowing ad hoc polymorphic functions and predicates to be handled.

The notation and conventions used throughout this paper is as follows: type a(t1,.., tn): tn+1 means function symbol a is well sorted when its argument sorts are t1,.., tn with tn+1 as the result sort, and type a(t1,.., tn) means predicate a is well sorted when defined on argument sorts t1,.., tn. Axioms, definitions and theorems are respectively indicated in the text as follows: (A1,..,An), (D1,..,Dn), and (T1,..,Tn). Where axiom/definitional schema are used, the numbering in the parentheses reflects the number of object-level axioms and definitions generated, e.g. (A10-A15) would indicate that six axioms are defined.

2.1 RCC-8

The mereo-topological theory RCC-8 [Randell, et al., 1992] is embedded into ROC-20. As with RCC-8, the same primitive dyadic relation C/2 is used: 'C(x,y)' is read as "x is connected with y" and is interpreted to mean that the topological closures of regions x and y share a point in common. All the relations defined in RCC-8 are used, and all carry their usual readings: DC/2 (disconnected), P/2 (part), EQ/2 (equal), O/2 (overlaps), DR/2 (discrete) PO/2 (partial overlap), EC/2 (external connection), PP/2 (proper part), TPP/2 (tangential proper part), NTPP/2 (non-tangential proper part). PI/2, PPI/2, TPPI/2 and NTPI/2 are the inverse relations for P/2, PP/2, TPP/2 and NTPP/2, respectively. Of these relations, eight are provably Jointly Exhaustive and Pairwise Disjoint (JEPD) and can be singled out for reasoning about state-state topological changes [Cui, et al., 1992]. For brevity this set of relations is referred to as JEPD RCC-8 .

Axioms for C/2 and definitions for the dyadic relations of RCC-8 are as follows:

(A1) "x C(x,x) (A2) "x"y [C(x,y)fi C(y,x)] (D1) DC(x,y) "def. �C(x,y) (D2) P(x,y) "def. "z[C(z,x)fi C(z,y)] (D3) EQ(x,y) "def. P(x,y) & P(y,x) (D4) O(x,y) "def. $z[P(z,x) & P(z,y)] (D5) DR(x,y) "def. �O(x,y) (D6) PO(x,y) "def. O(x,y) & �P(x,y) & �P(y,x) (D7) EC(x,y)"def. C(x,y) & �O(x,y) (D8) PP(x,y)"def. P(x,y) & �P(y,x)

(D9) TPP(x,y) "def. PP(x,y) & $z[EC(z,x) & EC(z,y)] (D10) NTPP(x,y) "def. PP(x,y) & �$z[EC(z,x)) & EC(z,y)] (D11) PI(x,y) "def. P(y,x) (D12) PPI(x,y) "def. PP(y,x) (D13) TPPI(x,y) "def. TPP(y,x)

(D14) NTPPI(x,y) "def. NTPP(y,x) type F(Region,Region); where F ˛ {C,DC,P,EQ,DR,PO,EC,PP,TPP,NTPP,PI,PPI,

TPPI,NTPPI}

Not reproduced here, but assumed, is an axiom in RCC-8 that guarantees every region has a nontangential proper part (A3), and a set of axioms (A4-A9) introducing Boolean functions for the sum, complement, product, difference of regions, and the universal spatial region, and an axiom that introduces the sort Null enabling partial functions to be handled - see [Randell, et al., 1992].

2.2 Mapping Functions and Axioms

ROC-20 uses the set of dyadic relations from RCC-8 to model the spatial relationship between bodies, volumes, and images. The distinction between bodies and regions is maintained by introducing two functions: 'region(x)' read as "the region occupied by x" and 'image(x,v)' read as "the image of x with respect to viewpoint v". The function: region/1, maps a body to the volume of space its occupies, and image/2 maps a body and a viewpoint to its image; i.e. the region defined by the set of projected half-lines originating at the viewpoint and intersecting the body, so forming part of the surface of a sphere of infinite radius centred on the viewpoint. A set of axioms incorporating these functions are defined by the following axiom schema 1 :

(A10-A15) "x"y [F(region(x),region(y)) fi "v [F(image(x,v),image(y,v))]] type region(Body):Region 2 type image(Body,Point):Region type F(Region,Region) where F ˛ {C,O,P,PP,NTPP,EQ}

Not all of the defined RCC-8 relations are shown. For example, given DC(region(a),region(b)) all image relationships between the a and b are possible depending on the shape of the objects and the viewpoint assumed. This shows that these axioms function as a set of spatial constraints between bodies, a given viewpoint, and their corresponding images. This point is re-visited in section 6

1 Although not developed here, the distinction made between bodies and regions enables one to define the notion of free space and model spatial occupancy - see [Shanahan, 1996].

2 Sortal declarations given here are not as restricted as they could be, for example we could declare: type region(Body):3DRegion, and type image(Body,Point):2DRegion, where 2DRegion and 3DRegion are (disjoint) subsorts of the sort Region.

below, where a change in viewpoint, or a change in the relative positions of bodies with respect to a viewpoint, is discussed.

2.3 Occlusion Defined

A second primitive relation: 'TotallyOccludes(x,y,v)', read as "x totally occludes y with respect to viewpoint v", is now added, and is axiomatised to be irreflexive and transitive (and is, by implication, asymmetric):

(A16) "x"v �TotallyOccludes(x,x,v) (A17) "x"y"z"v [[TotallyOccludes(x,y,v) & TotallyOccludes(y,z,v)] fi TotallyOccludes(x,z,v)]

type TotallyOccludes(Body,Body,Point)

The intended geometric meaning of total occlusion is as follows. Let line(p1,p2,p3) mean that points p1, p2 and p3 fall on a straight line with p2 strictly between p1 and p3. Then, x totally occludes y from v iff for every point p in y, there exists a point q in x such that line(v,q,p), and there are no points p¢ in y, and q¢ in x, such that line(v,p¢,q¢). Given the transitivity of total occlusion, an object x can totally occlude an object y even if x itself is totally occluded by another object.

Several axioms are now introduced to embed RCC-8 into this theory:

(A18) "x"y"z"v [[TotallyOccludes(x,y,v) & P(region(z),region(y))] fi TotallyOccludes(x,z,v)]

i.e. if x totally occludes y, x totally occludes any part of y.

(A19) "x"y"v [TotallyOccludes(x,y,v) fi "z[P(region(z),region(y))] fi �TotallyOccludes(z,x,v)]

i.e. if x totally occludes y no part of y totally occludes x.

(A20) "x"y"v [TotallyOccludes(x,y,v) fi "z[[P(region(z),region(x)) & P(region(u),region(y))] fi �TotallyOccludes(u,z,v)]]

i.e. if x totally occludes y no part of y totally occludes part of x.

This latter axiom excludes cases where the occluding body has parts that wrap 'behind' the occluding object. That is to say, while some nested bodies satisfy this relation, not all do, as in the case where, for example, a body is totally enveloped by another. This particular model is an example of mutual occlusion, which is defined below in definition (D17).

(A21) "x"v$y$z[P(region(y),region(x)) & P(region(z),region(x)) & TotallyOccludes(y,z,v)]

i.e. every x has a part that totally occludes another part of x. This axiom guarantees that bodies have 'depth'.

(A22) "x"y"v [TotallyOccludes(x,y,v) fi P(image(y,v),image(x,v))]

i.e. if x totally occludes y, the image of x subtends the image of y. Note that (A22) is not a biconditional because the P/2 relation does not take account of relative distance, a topic to be considered shortly.

By separating out volumes and images, two non-identical bodies having identical images (as in the case where one body exactly occludes another) can be modelled without inconsistency. Spatial identity in terms of co-location still applies, but is restricted to the dimensionality of the regions being modelled.

Next, the relation of occlusion is weakened to include, for example, partial occlusion: 'Occludes(x,y,v)' is read as "x occludes y from viewpoint v":

(D15) Occludes(x,y,v) "def. $z$u[P(region(z),region(x)) & P(region(u),region(y)) & TotallyOccludes(z,u,v)]

type Occludes(Body,Body,Point)

i.e. x occludes y if a part of x totally occludes a part of y.

Total occlusion between two objects implies occlusion, which in turn implies region overlap between their corresponding images:

(T1) "x"y"v[TotallyOccludes(x,y,v) fi Occludes(x,y,v)] (T2) "x"y"v [Occludes(x,y,v) fi O(image(x,v),image(y,v))]

Occludes/3 is non-symmetrical. By contrast, the O/2 relation in RCC-8 is symmetrical, which renders it unsuitable for modelling occlusion relationships. Hence the need to augment RCC-8 with an additional primitive relation.

Other more specific occlusion relations may now be defined: partial, and mutual occlusion. An example of mutual occlusion is two interlinked rings. These relations will then be finessed further by combining them with the set of RCC-8 relations:

(D16) PartiallyOccludes(x,y,v) "def. Occludes(x,y,v) & �TotallyOccludes(x,y,v) & �Occludes(y,x,v)

type PartiallyOccludes(Body,Body,Point)

i.e. x occludes (but does not totally occlude) y, but y does not occlude x.

(D17) MutuallyOccludes(x,y,v) "def. Occludes(x,y,v) & Occludes(y,x,v) type MutuallyOccludes(Body,Body,Point)

i.e. x and y occlude each other.

For completeness (not listed here) inverse relations for Occludes/3, TotallyOccludes/3 and PartiallyOccludes/3 are defined (D18-D20); leaving the null case: NonOccludes/3, where no occlusion arises:

(D21) NonOccludes(x,y,v) "def. �Occludes(x,y,v) & �Occludes(y,x,v)

type NonOccludes(Body,Body,Point)

The six relations: NonOccludes/3, MutuallyOccludes/3; and TotallyOccludes/3, PartiallyOccludes/3, and their inverses are pairwise disjoint.

Finally, these new occlusion relations must be mapped to their RCC analogues:

• (A23) "x"y"v[NonOccludes(x,y,v) fi DR(image(x,v),image(y,v))]
• (A24) "x"y"v[PartiallyOccludes(x,y,v) fi [PO(image(x,v),image(y,v)) � PP(image(x,v),image(y,v))]] (A25) "x"y"v[MutuallyOccludes(x,y,v) fi [PO(image(x,v),image(y,v)) � P(image(x,v),image(y,v)) � PI(image(x,v),image(y,v))]]

2.4 Finessing the Occlusion Relations

Although a variety of occlusion relations have now been defined, they are still very general, as no spatial relation stronger than P/2 from RCC-8 is used. Total occlusion, for example, covers three cases: (i) where the image of the occluded body is a tangential proper part of that of the occluding body, (ii) where it is a nontangential proper part, or (iii) the images are identical because one body exactly occludes the other. By refining the existing set of occlusion relations in this manner, a total set of 20 JEPD relations become definable. These are generated using the following definitional schemas:

(D22-D33) FY(x,y,v) "def. F(x,y,v) & Y(image(x,v),image(y,v)) (D34-D41) CY -1 (x,y,v) "def. C(y,x,v) & Y(image(y,v),image(x,v)) type F(Body,Body,Point) where if: F = NonOccludes, then Y ˛ {DC,EC} F = TotallyOccludes, then Y ˛ {EQ,TPPI,NTPPI} F = PartiallyOccludes, then Y ˛ {PO,TPP,NTPP}

F = MutuallyOccludes, then Y ˛ {PO,EQ,TPP,NTPP}

and where if: C = TotallyOccludes, then Y ˛ {EQ,TPPI,NTPPI} C = PartiallyOccludes, then Y ˛{PO,TPP,NTPP} C = MutuallyOccludes, then Y ˛ {TPP,NTPP} e.g. TotallyOccludesEQ(x,y,v) "def. TotallyOccludes(x,y,v) & EQ(image(x,v),image(y,v)) TotallyOccludesEQ -1 (x,y,v) "def. TotallyOccludesEQ(y,x,v) & EQ(image(y,v),image(x,v))

type F(Body,Body,Point) where: F is an element from the set of all 20 occlusion relations.

It is this part of the Region Occlusion Calculus that is now referred to as ROC-20, and the set of 20 JEPD relations as JEPD ROC-20 .

3 Theory Comparisons

It is now possible to map out the relationship between RCC-8, Galton's [1994] Lines of Sight Calculus (LOS-14), and ROC20. Consider the JEPD RCC-8 overlap relations first, i.e. {PO, TPP, NTPP, EQ, TPPI, NTPPI}. These relations are indifferent to relative distance with respect to a viewpoint, and each conflates a pair of Galton's relations. For example, given only that x partially overlaps y, it is impossible to say whether x is in front of or behind y. In both LOS-14 and ROC-20, these two cases are distinguished.

This leaves two RCC-8 relations {DC, EC}. These map respectively to the LOS-14 relations C/2 (clears) and JC (just clears), and to the two ROC-20 relations: NonOccludesDC/3 and NonOccludesEC/3. The six remaining relations of ROC20 are precisely the cases where non-convex bodies (ruled out in LOS-14) are allowed into the modelled domain. These correspondences are illustrated in table 1.

In table 1 mutually occluding objects are shown thus, , indicating that the lighter coloured 'U'-shaped object both occludes and is occluded by the darker. In the special case of MutuallyOccludesEQ/3 part of the darker body lies behind the lighter body, and is exactly subtended by it, while a (visible) part of this, extends through a slot in the lighter body and occludes it.

The formal relationship between LOS-14 and ROC-20 is also illustrated by the following theorem:

(T3) "x"y"v [�MutuallyOccludes(x,y,v) « [NonOccludes(x,y,v) � TotallyOccludes(x,y,v) � PartiallyOccludes(x,y,v) � TotallyOccludes -1 (x,y,v) � PartiallyOccludes -1 (x,y,v)]]

where the five disjuncts are provably pairwise disjoint, and where each disjunct in turn respectively splits into 2+3+3+3+3 = 14 of the JEPD ROC-20 'base' relations.

4 Comparative Distance and Occlusion

While the notion of relative distance between bodies appears in this theory, it only forms part of the interpretation resulting from the model used, and is implicit. Made explicit, a robot, for example, can exploit this information to reason about partial orderings of radial distances between itself and bodies based on their observed or inferred occlusion properties. A reworked subset of comparative distance axioms originally proposed by van Benthem [1982] is embedded into the theory. The primitive relation: 'N(x,y,z)' used here, is read as "point x is nearer to body y than x is to body z", while 'E(x,y,z)' is read as "body y is as near to point x as is body z":

(A26) "x"y"z"u [[N(x,y,z) & N(x,z,u)] fi N(x,y,u)] (A27) "x"y �N(x,y,y) (A28) "x"y"z"u [N(x,y,z) fi [N(x,y,u) � N(x,u,z)]] (D42) E(x,y,z) "def. �N(x,y,z) & �N(x,z,y) type F(Point,Body,Body), where: F ˛ {N,E}

Comparative distance is related to occlusion, and is embedded into ROC-20, with the following axioms:

(A29) "x"y"v [TotallyOccludes(x,y,v) fi N(v,x,y)]

i.e. if x totally occludes y with respect to some viewpoint v, then x is nearer to v than y is to v.

(A30) "x"y"v [N(v,x,y) fi "z[P(region(z),region(y)) fi N(v,x,z)]]

i.e. if v is nearer to x than y, then v is nearer to x than any part of y.

Note that the named viewpoint is not necessarily identified with an agent, and intentionally so. For example, if the agent holds and aligns two objects (one in each hand) where the one totally occludes the other, it does not follow the agent is closer to the occluding object, than the one occluded. It is also because of the guiding projective geometry assumed here (and which interprets the image/2 function) that a viewpoint is identified with a point, and not an extended region in space.

5 Relative Orientation

If one body lies just to the left of another with respect to a line of sight, and is closer to the observer, movement to the right will typically increase the apparent separation between them. The relative left-right hand positions of the bodies will reverse as the line of sight intersects both bodies and passes to the left of that point. In order to be able to model and exploit this example of motion parallax, the ternary primitive relation: 'Left(x,y,v)', read as "x is to the left of y from viewpoint v", is added and axiomatized. Its dual (Right/3) is also defined: 3

(A31)"x"v�Left(x,x,v) (A32)"x"y"v [Left(x,y,v) fi �Left(y,x,v)] (A33)"x"y"z"v [[Left(x,y,v) & Left(y,z,v)] fi Left(x,z,v)]

(D43) Right(x,y,v) "def. Left(y,x,v)

type F(Body,Body,Point) where: F ˛ {Left,Right}

For completeness, the relation: 'NonLeftRight(x,y,v)' read as "x is neither to the left or right of y relative to viewpoint v", is added:

(D44) NonLeftRight(x,y,v) "def. �Left(x,y,v) & �Right(x,y,v)

type NonLeftRight(Body,Body,Point)

Here it is assumed that the observer's horizon is fixed, and that the field of view is restricted. Without these assumptions, the transitivity of Left/3, for example, would fail in the intended model. This would be the case if the agent were at the centre of a circular arrangement of objects (Stonehenge, for example), entailing each object could be both to the left and the right of itself.

3 Other spatial orientation duals with exactly the same properties (irreflexivity, etc.) are easily definable, e.g. forward/rearward, or above/below.

The primitive relation Left/3 is embedded into the theory using the following axioms:

(A34)"x"y"v [Left(x,y,v) fi [$z [P(region(z),region(x)) & Left(z,y,v)] & �$u [P(region(u),region(x)) & Left(y,u,v)]]]

(A35)"x"y"v [Left(x,y,v) fi �P(image(x,v),image(y,v))]

i.e. in the first case (A34) if from v, x is left of y, some part of x projects to the left of y, while no part of x projects to the right of y; while in the second case (A35), from v, if x is left of y then x is not subtended by y.

It is now straightforward to see how ROC-20 can be further developed. For example, where one object lies to the left of another and is disjoint, to the left and in boundary contact, and so on. All the distinct states depicted in figure 1 can then be modelled.

6 Relative Viewpoints

A change of viewpoint always carries the possibility of a change in the apparent spatial relationships holding between bodies in the domain (figure 1). If, for example, two bodies are physically separated, and an agent is allowed to freely move around, several apparent spatial relationships may be seen to apply. However, for two bodies forming a part-whole relation, no change in the viewpoint will coincide with both bodies separating. These and other configuration possibilities form the basis of the set of global spatial constraints introduced in section 2.2. There still remains the question of singling out additional dynamic spatial constraints, this time arising from instantaneous transitions between temporally ordered sequences of occlusion events.

As with many discrete based QSR theories, the set of JEPD ROC-20 relations can be worked into an envisionment, where a set of axioms lay out the dynamic possibilities and constraints of spatial relationships deemed to hold between bodies over consecutive moments in time [Cohn, 1997]. For ROC-20 this is represented as a table (table 2) where legal/illegal (instantaneous) transitions between spatial relationships are respectively denoted by "y" (yes) or "n" (no) entries mapping to pairs of named occlusion relations. A path formed by linking together pairs of nodes denotes a possible projected sequence of states from an initial state (at time t) via successor states (at times t+1 … t+n).

The symmetry about the highlighted diagonal indicates the symmetrical relationship between each pair of named nodes. For example, the relation NonOccludesEC/3 has five such legal transitions, as read across the named row or down the named column. This means the relation NonOccludesEC/3 from time t to the next instant t+1, now re-worked as an envisionment axiom (assuming a fixed viewpoint and the continued existence of the bodies from time t to t+1), has the following form:

"x"y"v"t [HoldsAt(NonOccludesEC(x,y,v),t) fi [HoldsAt(NonOccludesEC(x,y,v),t+1) � HoldsAt(NonOccludesDC(x,y,v),t+1) � HoldsAt(PartiallyOccludesPO(x,y,v),t+1) � HoldsAt(PartiallyOccludesPO -1 (x,y,v),t+1) � HoldsAt(MutuallyOccludesPO(x,y,v),t+1)]]

The envisionment table can be interpreted two ways: either in terms of the viewpoint changing, or where the positions of the bodies change. In the former case, an additional predicate is required: ChangePos(v1,v2), (meaning viewpoint v1 changes to viewpoint v2), which relates v1 at time t in the antecedent of the envisionment axiom to v2 at time t+1 in the consequent. These sequences of occlusion events can then be viewed as building the topology of motion parallax into the model. Obviously, where orientation information is added the number of relations and nodes increase, as does the overall complexity of the new set of permissible transitions between specified named occlusion relations.

7 Discussion and Conclusions

ROC-20 presents an axiomatisation of spatial occlusion. It assumes the region based ontology of RCC-8 [Randell, et al., 1992] and extends the work of Galton [1994] by allowing both convex and concave shaped bodies. It is this extension that describes occlusion events of mutually occluding bodies. The inclusion of van Benthem's [1982] notion of comparative nearness facilitates reasoning about relative distance between occluding bodies. An envisionment table models sequences of occlusion events to enable reasoning about objects and the images that may be formed in a visual field.

Several directions for future work are indicated. The axiomatisation of the primitive relation: TotallyOccludes/3, currently rules out models where the occluding body has a part that wraps behind the occluded body. In the theory this is a case of mutual occlusion. However, we can see potential gains by re-working the current axiomatisation (and relaxing this restriction) so that any degree of enclosure of one body by another (from some assumed viewpoint) could be a case of total occlusion.

Additional work is required to generate the composition table [see Cohn, 1997] for JEPD subsets of the defined occlusion relations. Also of note is the question whether there are any decidable and tractable subsystems of ROC-20, as has already been shown for RCC-8 [Bennett, 1994; Renz and Nebel, 1998]. Further computational gains may be made by adding information about the relative size of bodies or regions acting as additional constraints when checking for consistency of sets of these relations [c.f. Gerevini and Renz, 1998].

ROC-20 lays the theoretical foundations for further work in Cognitive Robotics, in which the images of objects are used to infer the spatial arrangement of objects in a robot's world - ultimately with map building and route planning in mind. We argue that the modelling of occlusion and motion parallax within a traditional QSR approach offers a uniform framework to achieve this. Galton [1994] has already shown these lines of sight relations can partition an idealized plan view of the embedding space into a set of polygonal regions. For each (view) point in that space exactly one of the JEPD line of sight relations holds. Where objects of varying shapes and sizes exist, many named sight lines that form tangents to objects naturally intersect at points. These correspond in this theory to a conjunction of atomic formulae drawn from the set of JEPD relations used. This gives rise to a set of extrinsic reference points determined completely by the objective spatial arrangement of the objects in the robot's world. With these points, localization becomes possible, while enabling qualitative and metric quantitative information to be combined. Spatial constraints and envisionment axioms now lead into map building and route planning. The robot then acquires the means to plan and execute moves [Levitt and Lawton, 1990; Schlieder, 1993] while constantly monitoring and relating its own direction of movement to the observed change and sequence of occlusion events in its visual field.

Acknowledgements

Work described here has been supported by EPSRC project GR/N13104, "Cognitive Robotics II". We wish to thank Paulo Santos, Brandon Bennett and Antony Galton for fruitful discussions during the development of ideas presented in this paper; and the comments given by the anonymous referees.