Research On Spatio-Temporal Representation And Reasoning Based On RCC

Time and space belong to those few fundamental concepts that always puzzled scholars from almost all scientific disciplines and were of vital concern to our everyday life, and are very important concepts in everyday life and common-sence reasoning. In reality, when one solves many problems he will concern some space or time informations. In AI, there are many themes that concern spatio-temporal information. Spatio-temporal representation and reasoning is motivated by a wide variety of possible application areas including Geographic Information System (GIS), autonomous robotic navigation, understanding of natural languages, sptio-temporal database, computer vision, image understanding, CAD/CAM, common-sense reasoning about physical systems . Because sptio-temporal reasoning has a wide possible application in so many application fields, it has gradual became a very active branch in AI. There are two common methods for qualitative spatio-temporal representation and reasoning: one is to integrate the spatial model and the temporal model into a multi-dimensional spatio-temporal structure; another is to attempt to build a model that simultaneous has spatial and temporal attribute .This paper is based on the theory of Region Connection Calculus (RCC); reinpregrets the regions in the theory of RCC to be extended regions of space-time and builds a integrated model of spatio-temporal representation and reasoning; then addresses some notions of spatio-temporal continuity; finally proposes the notions of spatio-temporal patterns and uses them to constraint the spatio-temporal theory that builded above . The basic language of RCC contains only one primitive predicate C(X,Y), read as 'region X is connected with region Y'. The relation C is ensured to be reflexive and symmetric by the following two axionms. (1) ?x[C (x,x)] (2) ?x ? y[C (x,y)→C(y,x)] Using C(X,Y), a basic set of binary relations are defined: 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), x=y(x is identical with y), O(x,y)(x overlaps y), DR(x,y)(x is discrete from y), PO(x,y)(x partially 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 nontangential proper part of y). The relations: P, PP, TPP, NTPP are non-symmetrical and support inverses. For the inverses we use Pi, PPi, TPPi, NTPPi to represent. Of the defined relations, those in the set {DC, EC, PO, EQ, TPP, NTPP, TPPi, NTPPi} are provably jointly exhaustive and pairwise disjoint(JEPD). We refer to this set of eight relations as RCC-8. We can increase the expressive power by embedding one primitive conv(x) into RCC theory. So there are three new relations between two convex regions: INSIDE, P-INSIDE, OUTSIDE. These three relations also have inverses. By C and conv we can extent JEPD relations from 8 to 23,so these 23 relations are called RCC-23. Following Muller, spatio-temporal regions traced by objects over time are termed spatio-temporal histories. In a n-D space, the spatio-temporal history is a n+1 dimensional volume. Connection relation can be differentiated into spatio-temporal connection(Cst ), spatial connection (Csp )and temporal connection(Ct ). From the topological relation Cα(x,y), we can define the mereological relation of parthood as what was done in RCC theory; Pα(x,y): x is a part of y. Pα( x,y)≡?z(Cα(z,x)→Cα(z,y)) The parthood relation is used to define proper par(tPPα), overlap(O α)and discreteness(DRα). Disconnected(DCα),external connected(ECα), partial overlap(POα), equal(EQα), tangential proper part(TPP ) and non-tangential proper part(NTPPα) can be also defined. These relations, along with the inverses for the last two TPPiαand NTPPαconstitute the jointly exhaustive and pairwise disjoint (JEPG) relations of RCC-8. The axioms and theories of RCC are also used for our new spatio-temporal extended model. In order to introduce a spatio-temporal interpretation we must capture a notion of temporal order between the entities. For temporal order we write x y: the closure of x strictly precedes the closure of y in time. From temporal connection and temporal order we can give the definition of meets (p)and all the temporal relations of Allen . This includes relations such as starts with ( ), ends with ( ), temporal inclusion ( ) and temporal equivalence(|? ?| ?≡t). Further, we define a three place relation of temporal betweenness (z2||(z1;z3)meaning z2 is met by z1 and meets z3). We introduce relationships to refer to the initial and final parts of a history. IP(x,y) states that x is an initial part of history y just in case x starts with y and ends before it. Conversely, x is a final part of history y (FP(x,y)) just in case x starts after y and ends with it. To define relations between spatio-temporal regions that may vary through time, we introduce the notion of a temporal slice, TS(x,y), x is a maximal component part of y corresponding to a certain time extent. We use the notation wy to denote the part of y corresponding to the lifetime of w when it exists ( when w ?y). In this reformalized spatio-temporal frame, we specify various notions of spatio-temporal continuity. The notion of continuity should capture the intuitive notion of motion. We now define various notions of what it means for a history to be continuous. First of all consider the case of the history having but a single component. This is essentially the case considered by Muller who defines the notion of a history being continuous if it is temporally self-connected and it does not make any spatial leaps: CONT(w) ≡CON t ( w)∧?x,u((TS(x,w)∧xu ∧P(u ,w)→C(x,u)) However, this definition of continuity permits 'temporal pinching'of histories, We can define a stronger notion of continuity for histories anddisallow temporal pinching which we term firm continuity. A non pinched continuous spatio-temporal history is firmly continuous. If a history contains multiple components, then we can consider how these relate to each other over time. We primarily propose six common spatio-temporal continuity: StrCONT, MulCONT, ColCONT, WCONT, TCONT, SpCONT. Now we can define three different transition operators to express relation transition between spatio-temporal regions: TransTo (r1,r3,x,y, z1,z2), TransFrom (r1,r3,x,y,z1,z2), InsRel3(r1,r2,r3,x,y, z1,z2).The first two operators assume that the initial and/or the final relations hold over intervals 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. We can use these transition operators to capture the process that relations between spatio-temporal histories are transitting. Finally we address notion of spatio-temporal patterns in such spatio-temporal theory. This paper enumerates some common simple patterns for rigid (shape invariant) objects. In many fields of application what is studied are rigid objects but not non-rigid objects, so here we only give a set of typical spatio-temporal patterns for rigid objects. For only one spatio-temporal region, there are following spatio-temporal patterns: 1.Immobilty IMB(x), 2.Non-cyclicity NYC(x) 3.Cyclicity CYC(x). In our presentation of spatial behaviour patterns we only considered monadic patterns involving a single spatio-temporal history. However, in general one might consider patterns involving two or more histories and if such behaviour patterns can be preferentially associated with particular sorts of objects, then this will provide additional heuristic knowledge to constrain possible explanations. In the case of pairs of spatial entities,x, y,the followings are some possible patterns for rigid objects which do not interpenetrate each other. These are: 1.Coalescence COL(x,y), 2. Separation SEP(x,y), 3.Collision CLN(x,y), 4.Disjointness DIS(x,y), 5. Attachment ATT(x,y).