Qualitative Self-Localization using a Spatio-Temporal Ontology: A Preliminary Report Shyamanta M Hazarika Anthony G Cohn School of Computing University of Leeds, Leeds LS2 9JT United Kingdom e-mailfsmh,
[email protected] Abstract Self-localization - the correlation of current and former impressions of the world is an essential ability for most mobile agents. In an inhabited dynamic system, high precision metric approaches demand accurate sensor devices and large computational power. In contrast, during the last few years qualitative methods have been explored to overcome mainly problems regarding complexity and stability. This paper describes a qualitative approach to self-localization. With space-time as the ontological primitive and using distinct spatiotemporal patterns for categories of objects, selflocalization within an integrated spatio-temporal framework is investigated. Given a record of local surveys, we show how space-time history descriptions might be abduced from local surveys and spatio-temporal patterns. The qualitative mereotopological world model so constructed forms a basis for self-localization. keywords: spatio-temporal reasoning, localization, space-time.
1
self-
Introduction
In the field of robotic navigation, high precision metric approaches [Lozano-P´erez, 1983; Kuan et al., 1985] demand very reliable and accurate sensor devices. In contrast, over the last few years, qualitative approaches to robotic navigation have been proposed to overcome problems regarding complexity and stability. Qualitative modelling for selflocalization and navigation include the qualitative map approach [Kuipers and Byun, 1991; Levitt and Layto, 1990] and the adaptive topological models introduced by [Prescott, 1994]. Kurz’s ultrasonic clustering techniques [Kurz, 1993] and the approach based on typical sequences of local sensorreadings rather than on explicit topology [Tani and Fukumura, 1994] as well as robust world-modelling technique by Zimmer [Zimmer, 1996] are other qualitative approaches to self-localization and navigation. The above qualitative navigation approaches concern spatial learning and path planning in the absence of a single
global coordinate system for describing locations and position of landmarks. Further, they are based on a semantic hierarchy of descriptions for representation, with the most abstract level being that of the topological neighbourhood. These approaches though based on the basic mobile robot task: “Recognize places you have seen before!” do not exploit the notion of qualitative motion1 for navigation. Exploiting Qualitative Motion Under the purview of Qualitative Spatial Reasoning (QSR) (see [Cohn and Hazarika, 2001b] for an overview) navigation in true qualitative terms has been attempted by [Schlieder, 1993; Escrig and Toledo, 1998]. For many applications and especially in case of locomotion, it is not necessary to model position information but only positional change. Consequently, in [Freksa and Zimmermann, 1996] orientation knowledge is seen as dynamic path knowledge and the qualitative concept of motion is introduced. Further, a simple but effective means for representation of a course of motion allowing description at several levels of granularity, abstraction and accuracy suitable for compact storage of motion events as well as prediction of the future of a moving object was suggested by [Musto et al., 1998; Schmid and Wysotzki, 1998]. Elsewhere, QSR is seen as a constraint satisfaction problem. As a consequence of this, the treatment of several aspects of space (such as orientation following the Freksa and Zimmermann’s approach [Freksa and Zimmermann, 1996], cardinal directions following Frank’s approach [Frank, 1992] and qualitative named distances [Freksa and Zimmermann, 1996]) could be integrated into the same spatial model. Using Constraint Logic Programming over finite domains, a Qualitative Navigation Simulator for successful autonomous navigation of a simulated robot through an unknown structured environment has been built [Escrig and Toledo, 1998]. More recently Bennett et al. [Bennett et al., 2000a] explore the expressive power of a recently developed qualitative regionbased geometry [Bennett et al., 2000b] and apply it to the problem of representing and reasoning about the motion of rigid bodies within a confining environment. Exploiting the notion of qualitative change and spatiotemporal continuity, this paper presents a self-localization 1 Motion can be seen as a form of spatio-temporal change and is used in such an interpretation here.
formalism. We present a logic based framework in which a qualitative mereo-topological world model is constructed based on space-time histories obtained through an abductive process2 within an integrated space-time framework. The qualitative mereo-topological world model so constructed forms a basis for self-localization. The next section introduces the abductive process for generating the space-time histories. Thereafter in section 3 we introduce the spatiotemporal theory used in our formalization. Finally we present an outline for qualitative self-localization within a spatiotemporal framework.
2
3 Spatio-Temporal Theory ST Our basic entities are extended regions of space-time. This ontological shift is not entirely new. Objects and events in space can be considered as space-time volumes. Starting with [Russell, 1914] there are a few authors [Quine, 1960; Carnap, 1958] and more recently [Hayes, 1985; Vieu, 1991] who consider whole space-time histories. Similarly, Clarke’s [Clarke, 1981] intended interpretation of his region-based calculus was spatio-temporal. Recently, Muller [Muller, 1998] has proposed a mereo-topological spatio-temporal theory based on space-time as a primitive.
Generating Space-Time Histories
Getting a qualitative mereo-topological world model from a local survey3 is the basis for qualitative self-localization. With spatio-temporal primitives in an inhabited dynamic system4 the key idea is to generate space-time histories abductively. Given a temporally extended local survey, the abductive task is to hypothesize the space-time histories; which, given the spatio-temporal patterns, would explain the local surveys. In logical terms, if a local survey is represented as the conjunction of a set of spatial relationships, the task is to find an explanation of in form of a logical description (a mereotopological world model) H involving space-time histories, such that ST ^ P ^ H j where, ST is a spatio-temporal theory comprising axioms for space, time, change and continuity. P is a logical description of spatio-temporal patterns for objects and agents in the domain. The following sections deliberate on a possible form of the above components. We restrict discussion of the spatio-temporal theory ST here to pure space-time histories, change and continuity. However, it is worthwhile noting that we are developing a spatio-temporal theory of physical objects and preliminary work has been reported in [Cohn and Hazarika, 2000]. Use of a spatio-temporal theory of physical objects for (a full-blown account of) qualitative navigation is part of ongoing research and beyond the scope of the present paper.
=
2
As far we know [Shanahan, 1999] is the only work that uses a logic-based framework using abduction for sensor data assimilation. However it falls short of using a purely qualitative approach to spatial representation (such as the framework described by [Randell et al., 1992]). 3 A map emphasizes the illusion of seeing a spatial scene from above in an instant of time (a snapshot) which we refer to as global snapshot: the complete knowledge of the world at a time instant. In contrast, the knowledge of the world for an autonomous agent as it continuously explores is only partial and we refer to it as local survey: partial spatial knowledge of the world for an extended period. 4 Our interpretation of dynamical system is as in [Sandewall, 1994]. A dynamical system is one whose states changes over time and where effects flow forwards in time. A dynamical system is inhabited iff it contains one or more agents which can influence the system’s state at later times by performing actions.
time
time
time y
y x
space a.
y
x
x
space
space c.
b.
Figure 1: a. Spatial b. Temporal and c. Spatio-Temporal connection between two spatio-temporal entities x and y. We will use three connection relations Cst ; Csp and Ct for spatio-temporal, spatial and temporal connection respectively. The interpretation of these relations is as shown 5 in Fig 1. The spatio-temporal connection Cst xy x is spatiotemporally connected to y holds just in case the closures of x and y at least share a spatio-temporal point. Spatial connection for space-time entities is their connection in pure space. As shown in Fig. 1a connection under spatial projection is interpreted along the temporal axis i.e., spatial connection on projection to an infinitesimally thin temporal slice at right angles to the temporal axis. Such an interpretation of spatial connection intuitively assumes an underlying chequered space6 . Spatial connection is written as Cspxy x is spatially connected to y. Here x and y are spatio-temporal regions. Spatial connection in space-time is symmetric and reflexive. Fig. 1b shows temporal connection between spatio-temporal regions x and y. Temporal connection is written as Ctxy x is temporally connected to y. The axiomatisation of these connection relations are identical and follows [Cohn et al., 1997]. Note that in this theory the closure and the interior cannot be distinguished. We have the following axioms:
:
:
:
C xx: C xy ! C yx: 8z C zx $ C zy $ where 2 fst; sp; tg. A1. A2. A3.
5
[ (
) (x = y)℄
Space is shown as 1D in these illustrations and the others in Fig. 2, but this is simply for ease of drawing. The defined concepts are applicable to 2D and other higher dimensional space. 6 Note that under a space-time interpretation and a layered representation of snapshots spatially connected entities in the same layer are under spatio-temporal connection rather than spatial connection.
Mereo-Topological Relations From the connection relation C xy we define the mereological relation of parthood, P xy: x is a part of y.
(
(
)
( )
(
)
( + )
A4. A5.
8y9xNTPPstxy 9z 8u Cst uz $ Cst ux _ Cstuy
(
(
CON x def 8y; z
D4 states that a connection between two entities x and y is a firm-connection just in case some one-piece part of x (CONst x) and some one-piece part of y (CONst y) is interior connected (INCON x y ).
( + )
[
(
INCONx def 8y NTPPst yx ! 9z Pst yz ^ NTPPst zx ^ CONst z D4. FCONxy def 9u; v Pstux ^ Pst vy ^ CONst u ^ CONst v ^ INCON u v
D3.
)℄ ( + )℄
[
Temporal Relations At times for clarity we will write the temporal relations as infix operators. Therefore temporal connection Ct xy x is temporally connected to y is also written as x > < y. We will also write Ptxy; POt xy and EQt xy as x t y; x t y and x t y respectively. In order to introduce a spatio-temporal interpretation we must capture a notion of temporal order between the entities of the theory. For temporal order we write x < y the closure of x strictly precedes the closure of y in time. Axiom A6 establishes that temporal connection and temporal order are incompatible. Also temporal order is anti-symmetric (A7).
:
:
(
x 1t y
def ECt ^ :9v1 ; v2 v1 t x ^ v2 t y ^ v2 < v1 D6. x Ajt y def 8u x 1t u $ y 1t u D7. x jt y def 8u u 1t x $ u 1t y D8. x kt y z def y 1t x ^ x 1t z
D5.
(x = (y + z) ! C )
x> < y ! :x < y x < y ! :y < x (x < y ^ y >< z ^ z < w) ! x < w
Allen [Allen, 1984] and even before him Nicod [Nicod, 1924] pointed out that if time is totally ordered then there are 13 JEPD (jointly exhaustive and pairwise disjoint) relations in which one one-piece interval can stand to another which can be defined in terms of meets. We give the definition for meets (D5) which is a specialization of ECt and define relations that we will be using in subsequent formulations. D6 is the definition for one interval ending with another and D7 for one interval starting with another. D8 states interval x to be the interval between two distinct intervals y and z .
))
In order to differentiate between different spatio-temporal patterns and transition between histories we introduce the notion of firm connection. A firm-connection in n-D space is defined as a connection wherein an n-D worm can pass through the connection without becoming visible to the exterior. In other words, for two regions to be firmly-connected a direct conduit exists between the two [Cohn and Varzi, 1999]. In order to define firm-connection, we define one-piece or spatiotemporal connectedness. A spatio-temporal region is spatiotemporally one-piece CONst x just in case all parts of x are Cst connected. Similarly to represent that a certain temporal extent is one-piece we define temporal connectedness : spatio-temporal region x is temporally one-piece just in case all parts of x are temporally connected. We can also define spatial connectedness : spatio-temporal region x is spatially one-piece just in case all parts of x are Csp connected. We have the following definition. D2.
A6. A7. A8.
)
P xy def 8z C zx ! C zy The parthood relation P is used to define properpart PP , overlap O and disjoint DR . Further DC ; EC ; PO ; EQ ; TPP and NTPP i.e., disconnected, externally connected, partial overlap, equal, tangential proper part and non-tangential proper part respectively can also be defined. These relations along with the inverses for the last two viz. TPPi and NTPPi constitute the eight JEPD relations of RCC-8 (see [Cohn et al., 1997] for definitions). We introduce the following existential axioms. Axiom A4 ensures every region has a non-tangential part. In A5 the individual z is noted x y and represents the sum. D1.
Axiom A8 establishes the composition of temporal connection and temporal order.
(; )
( ( (
) ) )
)
Spatio-Temporal Relations A space-time connection implies a spatial connection as well as a temporal connection7 . Therefore we have the following axiom: A9.
(
Cstxy ! Ctxy ^ Csp xy
)
Further, to define relations between space-time regions that may vary through time, we introduce the notion of a ‘temporal slice’, i.e., the maximal component part corresponding to a certain time extent [Muller, 1998]. D9.
TSxy
def
((
) ! Pstzx)
Pstxy ^ 8z Pstzy ^ z t x
Henceforth, the notation wy denotes the part of y corresponding to the lifetime of w when it exists (i.e., when w t y)8 . We introduce relationships to refer to the initial and final parts of a history. D10 states that a part of a history y can be termed an initial part just in case it starts with y and ends before it. Conversely, x is a final part of a history y (D11) just in case x starts after y and ends with it.
y ^ 9z (z Ajt y ^ x 1t z ^ x + z = y ) Pstxy ^ x Ajt y ^ 9z (z jt y ^ z 1t x ^ x + z = y)
D10.
IPxy def Pstxy ^ x jt
D11.
FPxy def
Finally, models must not be spatio-temporal alone, so spatio-temporal connection Cst needs to be different from temporal as well as spatial connection. A10. A11.
9x9y 9x9y
Ctxy ^ :Cst xy Cspxy ^ :Cstxy
Space-Time Continuity We would like to define space-time continuity. Strong spatiotemporal continuity is ‘spatial’ and ‘temporal’ continuity si7
Though note that the converse is not necessarily true. y is purely syntactic sugar: for any atom The notation w could equivalently be replaced by x TSxy x t w 8
8(
(:: y ::)
w ^ ) ! (::x:: ).
Non-cyclicity: Non-cyclicity is the phenomenon of never taking the same path twice. Cyclicity: Cyclicity is the phenomenon of taking the same path more than once though not necessarily at the same speed11 .
multaneously. Intuitively this notion is same as Muller’s definition of continuity [Muller, 1998]: any space-time region is defined as qualitatively continuous just in case it is temporally self-connected and it doesn’t make any spatial leaps9 . D12.
CONTw
def
((
CONt w ^ 8x8u TSxw ^ x> < u ^ Pstuw
) ! Cstxu)
However this definition of continuity is unable to stop histories from “temporal pinching” – that is exclude histories that disappear and reappear again instantaneously at the same spatial location. With temporal pinching, we have weird transitions possible: transitions that do not adhere to the conceptual neighbourhood diagrams for binary topological relations such as RCC-8 [Cohn and Hazarika, 2001a]. In order to enforce a stronger notion of spatio-temporal continuity for histories we disallow temporal pinching and introduce the notion of firm-continuity. D13 is the definition of a non-pinched history w and D14 defines firm spatio-temporal continuity.
[
NPw def :9x9y Pst xw ^ Pstyw ^ x 1t y ^ :FCONxy D14. FCONTw def CONTw ^ NPw
D13.
(
℄ ( ; ))
)) [(
℄
time
x
x
x
NYC
IMB
space
CYC a.
P
The use of spatio-temporal patterns is based on the fact that autonomous agents make frequent use of knowledge in the form of categories. Categories often appear as abstractions of raw sensor readings that provide a means of recognizing circumstances and predicting effects of actions. In the literature there are attempts to learn such categories for themselves based on transforming raw sensor readings into clusters of time series that have predictive value to the agent [Rosenstein and Cohen, 1999; Fernyhough et al., 2000]. These learning algorithms could be augmented further based on distinct spatio-temporal patterns identifiable with different object categories. The following qualitative spatio-temporal patterns are identifiable with a single “one piece” spatial entity: Immobility: Immobility is the phenomenon of occupying the same space at all times. 9
Note that Muller uses a slightly different definition of onepiece/connectedness using closures. CONt w def x1 ; x 2 w x 1 x 2
x1 > < x2 where x is defined as the closure of x. His mereotopological theory follows [Clarke, 1981] in having topological functions and Cst xy interpreted as x and y share a point. 10 This idealization does not in any way changes the formalization presented here for higher dimensional space. However in higher dimensions and with flexible objects the spatio-temporal patterns would be more involved.
:9
℄
[(
time
The range of phenomena that can be described in a spatiotemporal theory of space is probably inexhaustible. Identifying a realistic corpus of spatio-temporal patterns involving one or more spatial entities is a complex task and one far beyond the scope of the present paper, as outlined in section 2. We restrict ourselves to 2-D Euclidean space populated with rigid objects10 and one or more autonomous agents all of which are shape invariant.
4.1 Spatio-Temporal Patterns
[
IMBx def CONst x ^ 8t t t x ! EQsp x xt NYCx def CONst x ^ 8u; v u t x ^ v t x ^ : u t v ! :EQsp ux xv 13 D17. CYCx def CONstx ^ 9u; v; w u t x ^ v t x ^ w t x ^ v kt u w ^ x ^ :EQ x x EQsp ux w sp u v
D15. D16.
℄
P and Self-Localization
4
From D15 to D17 we provide the object level definitions for the above three different patterns 12 .
( = + ^ :(
))
x y
x y
CLN
COL
x y SEP
x
y
DIS
x y ATT
space
b.
Figure 2: Spatio-Temporal Patterns for a. single entity and b. pair of entities. Fig. 2a shows the different spatio-temporal patterns identified above. When more than one spatial entity is involved the following are some distinct types of spatio-temporal patterns in 2-D space involving rigid objects (as shown in Fig. 2b). Coalescence: Coalescence is a coming together of two bodies for a period. Separation: Separation of two bodies that have previously behaved as a unit for a period. This is the dual of coalescence. Collision: A collision is a dynamic event when two bodies come into contact and separate again. A collision could be instantaneous or a coalescence followed 11
There are weaker and stronger versions of these predicates possible too: eg. of never taking an overlapping path or of taking an overlapping path more than once (which might then yield the kind of semantic region descriptions computed in [Fernyhough et al., 1996; 2000]). 12 We cannot distinguish rotation from cyclic mobility. Topologically, they both have the property that objects are in the same place twice. However, with an additional morphological primitive of congruence (as in [Bennett et al., 2000b]) we could make the distinction. 13 Note that this definition implies that the object is never stationary. Objects that are in non-cyclic motion and in rest intermittently would be a combination of IMB and NYC over different intervals of time.
by a separation. Disjointness: Two bodies remain disjoint for a period. Attachment: Two bodies remian attached for a period14. In [Cohn and Hazarika, 2001a] we have introduced three transition operators TransTo; TransFrom and InsRel3. The first two operators assume that the initial and/or the final relations hold over intervals15 and differ as to which of the two relations hold at the dividing instant. The third is for histories undergoing a transition between two relations with an instantaneous relation holding in between. Using these operators16, in D18 through D20 we provide the object level definitions for the first three spatio-temporal patterns respectively. D21 and D22 defines disjointness and attachment respectively.
COLxy def CONst x ^ CONst y ^ 9u; v TransTo d ; e ; x; y; u; v D19. SEPxy def CONst x ^ CONst y ^ 9u; v TransFrom e ; d ; x; y; u; v D20. CLNxy def CONst x ^ CONst y ^ 9u; v; w TransTo d ; e ; x; y; u; v ^ TransFrom e ; d ; x; y; v; w _ InsRel3 d ; e ; d ; x; y; u; v ^ v kt u w D21. DISxy def CONst x ^ CONst y ^ 8t t t x ^ t t y ! DCsp xt yt D22. ATTxy def CONst x ^ CONst y ^ 8t t t x ^ t t y ! ECsp xt yt The patterns stated in D18 through D20 can only hold when one or more of the entities involved is mobile. A pair of immobile objects will not have any of the above spatiotemporal patterns (A12). D18.
[
[ [[(
(
[( [(
A12.
( (
(
)℄ )℄
(
)℄
) )
) )) ( ; )℄ ℄ ℄
(IMBx ^ IMBy) ! [:CLNxy ^ :COLxy ^
:SEPxy
℄
Given the set of patterns P (definitions D15 through D22), for the abductive process to be able to exploit the spatio-temporal patterns, we need to add to P that all histories over a given period obey one of these patterns. We make the following definitions: D23. D24.
[
℄
Patx def IMBx _ NYCx _ CYCx Pat2xy def CLNxy _ COLxy _ SEPxy _ DISxy _ ATTxy
[
℄
We than assert Patx and Pat2xy for each observed pair of spatio-temporal histories x and y in the domain. Clearly, in 14
Note that we can have another pattern which is a combination of disjointness and attachment i.e. remains attached for a period than disjoint for some interval and attached again. 15 For defining transitions (see [Cohn and Hazarika, 2001a] for details) between RCC relations, we treat RCC relations as constant symbols rather than as predicates; thus we define a predicate r
; x;y : meaning holds between spatio-temporal regions x and y (where is the lowercase translation of the RCC relation ) i.e., r
; x; y x; y . The transition operators are defined with the final two arguments to the rcc predicate as always co-temporal, so these amount to just testing the spatial topology. 16 The three operators TransTo; TransFrom and InsRel3 can be defined from existing apparatus with no new primitives.
(
) (
) ( )
general, a much wide variety of patterns17 will be required, but this illustrates the general mechanism.
4.2 Self-Localization With a background spatio-temporal theory as developed in section 3 and the above logical descriptions of spatiotemporal patterns, we provide a logical account of selflocalization in this section. Referring back to the process of abduction in section 2, might comprise a set of conjunctions of RCC-8 relations between different objects, objects and agents as well as between agents in the domain.
An Illustrative Example Let us assume scenarios as shown in Fig. 3 for an autonomous agent with on-board vision in an inhabited environment. We
x
x b
a
z
y
b
a
z
y
b
a
Figure 3: Scenarios of an inhabited dynamic environment. assume the vision system to have a pan of 360 degrees and also that it can compute depth information accurately and can accurately locate objects in view. During an interval t, the robot a moves from its initial position (Fig. 3a) to its final position (Fig. 3b), recording spatial relationships of the objects it can see as it moves. Such knowledge as it continuously explores is only partial and we refer to it as local survey knowledge. There are two qualitatively different temporal parts to t: initially (during t1) a sees that:
fDC ta1 tx1 ; DC ta1 ty1 ; DC tx1 ty1 g
Then (during t2) it sees that
fDC ta2 tx2 ; DC ta2 ty2 ; DC ta2 tb2 ; DC tb2 tx2 ; DC tb2 ty2 ; DC tx2 ty2 g
It can also record the pure spatial relationships for any object between intervals t1 and t2, i.e.,
fEQsp tx1 tx2 ; EQsp ty1 ty2 ; POsp ta1 ta2 g
Based on the spatio-temporal patterns the following formula is one possible explanation of (i.e. abduction from) the local survey made by a during t
H = fIMBx ^ IMBy ^ IMBb ^ DCxy ^
DCxa ^ DCyb ^ DCxb ^ DCybg
17 For example the additional combination patterns described in footnotes [13 and 14]
However, based on above local survey and the spatiotemporal patterns we could have made other possible explanations as well. E.g. from a’s point of view it is also possible that b was initially hidden behind y and moved up as a also moved up, i.e.,
H = fIMBx ^ IMBy ^ NYCb ^ DCxy ^
DCxa ^ DCyb ^ DCxb ^ DCybg
This is one further possible explanation (as are several others e.g. that b suddenly comes into existence at the start of t )18 . Any abductive process will yield more than one possible answer in general. Under such circumstances we need to add certain heuristics for selecting the optimal one. A simple heuristic could be for the robot to proceed with the first valid explanation it finds. We conjecture that if the explanation is false, the processing of subsequent sequences of local surveys would be likely to reveal this. This requires further investigation. A more sophisticated approach would be to choose the explanation that minimizes the number of changes of state between different time intervals. E.g. if a observes that NYC tb2 then it might infer that NYCb. Similarly if a observes that IMB tb2 it might abduce that IMBb. This is somewhat akin to the non monotonic inference rule of circumscription [McCarthy, 1980b] which has a somewhat analagous minimization operator19.
2
5
Conclusion
We have provided an outline of a formalism with a spatiotemporal ontology as a framework for qualitative selflocalization. This is based on abductive reasoning. As stated above, the existence of multiple explanations is a general characteristic of abductive reasoning and the selection of “preferred” explanation is an important problem. It seems that in some common-sense arguments, more complicated preference relations on explanations are used. The discovery and investigation of such relations is an interesting topic for further research. Equally, it will be important to isolate and define other typical behaviour patterns other than those defined in section 4.1 in order to improve the granularity of the predictions possible. We also note that there are interesting issues in combining the local surveys made by two communicating agents (such as a and b in Fig. 3). At present we have only considered topological knowledge. If other qualitative knowledge such as distance or orientation information is available then this will globally extend the range of possible behaviours and patterns describable and will make much finer levels of explanation possible. Finally, we remark that in this paper we have addressed the issue of inferring complete spatio-temporal information given partial spatial knowledge over a complete time interval; the 18
The present example uses spatio-temporal patterns involving a single history. Abduction using patterns that involves two entites would be more involved and is part of ongoing research. 19 In fact there are clearly other relationships with the non monotonic reasoning literature which deserve to be explored. E.g. [Shanahan, 1995; Lang and Asher, 1995; Guesgen and Hertzberg, 1996 ]
dual problem of inferring complete spatio-temporal information from complete spatial knowledge at specific times only (such as from time-lapse photography, or annual geographic surveys for instance) also deserves investigation.
6 Acknowledgement The first author would like to acknowledge the Commonwealth Scholarship Commission, United Kingdom for financial assistance under reference INCS-1999-177. The second author gratefully acknowledges the financial assistance of the EPSRC under grant GR/M56807.
References [Allen, 1984] J F Allen. Towards a general theory of action and time. Artificial Intelligence, 23(2):123–154, 1984. [Bennett et al., 2000a] B. Bennett, A. G. Cohn, P. Torrini, and S. Hazarika. Describing rigid body motions in a qualitative theory of spatial regions. In Proceedings of the 17th National Conference on AI (AAAI-2000), Austin, Texas, 2000. [Bennett et al., 2000b] B. Bennett, A. G. Cohn, P. Torrini, and S. M. Hazarika. A foundation for region-based qualitative geometry. In Proceedings of 14th European Conference on AI (ECAI-2000)., 2000. [Carnap, 1958] R Carnap. Introduction to Symbolic Logic and its Applications. Dover Publications, Inc., New York, 1958. Translated by W H Meyer, Univ. of Chicago and J Wilkinson, Wesleyan Univ. [Clarke, 1981] B L Clarke. A calculus of individuals based on ‘connection’. Notre Dame Journal of Formal Logic, 22(3):204–218, July 1981. [Cohn and Hazarika, 2000] A. G. Cohn and S. M. Hazarika. A spatio-temporal theory of physical objects. In Working Notes of ECAI-2000 Workshop on Current Issues on Spatio-Temporal Reasoning, 2000. [Cohn and Hazarika, 2001a] A G Cohn and S M Hazarika. Continuous transitions in mereotopology. In Commonsense-2001: 5th Symposium on Logical Formalizations of Commonsense Reasoning, New York, 2001. [Cohn and Hazarika, 2001b] A G Cohn and S M Hazarika. Qualitative spatial representation and reasoning: An overview. Fundamenta Informaticae, 45:1–29, 2001. [Cohn and Varzi, 1999] A G Cohn and A Varzi. Modes of connection. In C. Freksa and D.M. Mark, editors, Proceedings of COSIT-99, Lecture Notes in Computer Science No. 1661, pages 299–314. Springer-Verlag, 1999. [Cohn et al., 1997] A G Cohn, B Bennett, J Gooday, and N Gotts. RCC: A calculus for region based qualitative spatial reasoning. GeoInformatica, 1:275–316, 1997. [Escrig and Toledo, 1998] M T Escrig and F Toledo. Qualitative Spatial Reasoning: Theory and Practice - Application to Robot Navigation, volume 47 of Frontiers in AI and applications. IOS Press, Amsterdam, 1998.
[Fernyhough et al., 1996] J. H. Fernyhough, A. G. Cohn, and D. C. Hogg. Generation of semantic regions from image sequences. In Fourth European Conference on Computer Vision. ECCV, Springer-Verlag, 1996. [Fernyhough et al., 2000] J. H. Fernyhough, A. G. Cohn, and D. C. Hogg. Constructing qualitative event models automatically from video input. Image and Vision Computing, 18:81–103, 2000. [Frank, 1992] A Frank. Qualitative spatial reasoning about distance and directions in geographic space. Journal of Visual Languages and Computing, 3:343–373, 1992. [Freksa and Zimmermann, 1996] C Freksa and K Zimmermann. Qualitative spatial reasoning using orientation, distance and path knowledge. Applied Intelligence, 6:49–58, 1996. [Guesgen and Hertzberg, 1996] H Guesgen and J Hertzberg. Spatial persistence. Applied Intelligence, 6:11–28, 1996. [Hayes, 1985] P. J. Hayes. Naive physics I: Ontology for liquids. In Jerry R. Hubbs and Robert C. Moore, editors, Formal Theories of the Commonsense World, pages 71– 89. Ablex Publishing Corporation, Norwood, NJ, 1985. [Kuan et al., 1985] D Kuan, J C Zamiska, and R A Brooks. Natural decomposition of free space for path planning. In IEEE International Conference on Robotics and Automation, pages 168–173, St. Louis, Missouri, 1985. [Kuipers and Byun, 1991] B J Kuipers and Y-T Byun. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 8:47–63, 1991. [Kurz, 1993] A Kurz. Building maps based on the learned classification of ultrasonic range data. In International Workshop on Intelligent Autonomous Vehicles (IAV) ’93, pages 193–198, University of Southampton, United Kingdom, 1993. [Lang and Asher, 1995] J Lang and N Asher. A nonmonotonic approach to spatial persistence based on distances and boundaries. In Proceedings of Time, Space and Movement, 1995. [Levitt and Layto, 1990] T S Levitt and D T Layto. Qualitative navigation for mobile robots. Artificial Intelligence, 44:305–360, 1990. [Lozano-P´erez, 1983] T Lozano-P´erez. Spatial planning: a configuration space approach. IEEE Transaction on Computers, C-32(2):108–120, 1983. [McCarthy, 1980a] J McCarthy. Circumscription — A form of non-monotonic reasoning. Artificial Intelligence, 13(1):27–39, 1980. [McCarthy, 1980b] J McCarthy. Circumscription and other non-monotonic formalisms. Artificial Intelligence, 13(2):171–172, 1980. Addendum to [McCarthy, 1980a]. [Muller, 1998] P. Muller. Space-time as a primitive for space and motion. In N. Guarino, editor, Formal ontology in Information Systems, volume 46 of Frontiers in Artificial Intelligence and Applications, pages 63–76, Trento, Italy, June 1998. IOS Press.
[Musto et al., 1998] A Musto, K Stein, A Eisenkolb, K Schill, and W. Brauer. Generalization, segmentation and classification of motion data. In Henri Prade, editor, Proceedings of 13th European Conference on Artificial Intelligence, pages 180–185. John Wiley & Sons, 1998. [Nicod, 1924] J. Nicod. Geometry in the Sensible World. Doctoral thesis, Sorbonne, 1924. English translation in Geometry and Induction, Routledge and Kegan Paul, 1969. [Prescott, 1994] A Prescott. Explorations in Reinforcements and Model-based Learning. PhD thesis, Department of Psychology, University of Sheffield, United Kingdom, 1994. [Quine, 1960] Quine. Word and Object. MIT Press, 1960. [Randell et al., 1992] D. A. Randell, Z. Cui, and A. G. Cohn. A spatial logic based on regions and connection. In Proceedings of 3rd International Conference on Knowledge Representation and Reasoning, pages 165–176, San Mateo, 1992. Morgan Kaufmann. [Rosenstein and Cohen, 1999] M T Rosenstein and P R Cohen. Continuous categories for a mobile robot. In Proceedings of the 16th National Conference on AI, pages 634– 640, 1999. [Russell, 1914] B. A. W. Russell. Our Knowledge of the External World. Routledge, 1914. [Sandewall, 1994] E Sandewall. Features and Fluents: The Representation of Knowledge about Dynamical Systems, volume I. Oxford University Press, 1994. [Schlieder, 1993] C Schlieder. Representing visible locations for qualitative navigation. In N Piera Carret´e and M G Singh, editors, Qualitative Reasoning and Decision Technologies, pages 523–532, Barcelona, 1993. CIMNE. [Schmid and Wysotzki, 1998] U Schmid and F Wysotzki. Qualitative and quantitative approaches to spatial inference and the analysis of movements. Technical Report 982, Fakult¨at f¨ur Informatik, Technische Universit¨at Berlin, 1998. [Shanahan, 1995] M Shanahan. Default reasoning about spatial occupancy. Artificial Intelligence, 74:147–163, 1995. [Shanahan, 1999] M Shanahan. A logical account of the common sense informatic situation for a mobile robot. Electronic Transactions on Artificial Intelligence, 1999. [Tani and Fukumura, 1994] J Tani and N Fukumura. Learning goal-directed sensory-based navigation of a mobile robot. Neural Networks, 7(3):553–563, 1994. [Vieu, 1991] L Vieu. S´emantique des relations spatiales et inf´erences spatio-temporelles: une contribution a´ l’´etude des structures formelles de l’espace en langage naturel. PhD thesis, Universit´e Paul Sabatier, Toulouse, 1991. [Zimmer, 1996] U R Zimmer. Robust world-modelling and navigation in a real world. Neurocomputing, 13(2-4):247– 260, 1996.
