Qualitative representations of motion transform kinematic floating point data into a finite set of concepts. Their main advantage is that they usually reflect a human understanding of the moving system, so we can more straightforwardly implement human-like navigation rules; in addition, they reduce the overhead of floating point computations. Therefore, they are an asset for mobile robots or unmanned vehiclesboth terrestrial and aerial-especially those that interact with humans. In this paper we provide a method to create new qualitative representations of motion from any qualitative spatial representation by using a story-based approach.
Description and interpretation of moving entities (humans, animals, robots, or inert objects) are at the core of many disciplines such as mobile robotics, human-robot interaction, geographic information systems, animal behaviour, high-level computer vision, and knowledge representation, among others. Qualitative representations transform the mass of quantitative data (positions and velocities) into a reduced group of concepts. Therefore, they simplify data so that these are easier to understand and to process (e.g. in modelling, planning, learning, or control).
Nonetheless, the work in qualitative representations of motion is still reduced in number, when compared to
spatial representations1 [6, p. 16 ][7, p. 5187], and mostly restricted to point-like entities moving in one or two
dimensions [
To fill the gap, in this paper we profit from the available spatial representations to systematically increase the number of representations of motion: we introduce a method that creates qualitative representations of motion given any qualitative spatial representation.
This has direct applications, for example, we may create a representation of motion using Hall’s spatial
categorisation, proxemics [
Our method centres on the concept of ’stories’ which, we believe, opens a new perspective in dealing with representations. A spatial representation can classify two static entities, or equivalently, each snapshot of two moving entities. If we therefore consider the complete sequence of snapshots—what we call the ‘story’ (Def. 2)—, we have a qualitative description of the motion.
An overview of representations is found in a survey by Dylla et al. [
Representations of orientation and relative direction, such as OPRA [
All the aforementioned representations are limited to point-like entities moving in one or two dimensions.
There is, however, a particular qualitative relation of motion for regions [
Continuous sequences of qualitative relations, such as the temporal sequences of Def. 1 (p. 4), are based on
Freska’s foundational concept conceptual neighbourhood [
Sequences of relations are used to analyse real data by Delafontaine et al. [
In this section, we define and illustrate the key concepts—stories and stories set —that we use to create qualitative representations of motion (Sect. 5). But first of all we define the underlying concept: temporal sequence of relations. DC x x x vk t =
1.2s t = 0.20s
TPP
y t = 2.00s
DC
k
Definition 1. A Temporal Sequence of Relations [
The time interval (ta, tb) can be freely chosen, e.g., it can be totally unbounded, i.e., extend to the whole time (1 , 1 ), be half-bounded (1 , tb), or bounded (ta, tb).
We obtain the temporal sequence of relations of two entities in a certain time interval by mapping their trajectories ~xk(t) and ~xl(t) into the qualitative relations of the representation we are using. We describe a sequence of relations as a list in parenthesis: (R1, R2, . . . , Ri, . . . ). We say a temporal sequence of relations is finite, if it has a finite number of relations, or infinite, if it has an infinite number. Notice that even though the entities’ motion occurs in a continuous space throughout a continuous time interval, the temporal sequences are finite, when the trajectories have a finite number of transitions between qualitative relations; this happens in Fig. 1, the sequence is finite, (DC, EC, DC), because we have only two transitions: DC ! EC and EC ! DC.
Now, based on the temporal sequences, we define the stories.
Definition 2. A Story is a temporal sequence of relations of two entities that is defined over the whole unbounded time interval (1 , 1 ).
A story describes the qualitative relation of two moving entities at any instant of time. Thus, any temporal sequence of relations is a substring of a certain story. We can see each story as a complete qualitative description of the motion of a two-entities system. We characterise stories with the letter S and, if necessary, an appropriate subscript.
Example 1. The temporal sequence S =(DC, EC, DC) in Fig. 1 is a story. Any proper substring is not a story, but just a temporal sequence of relations, because it does not happen in the whole unbounded interval (1 , 1 ). For instance, the substring (EC,DC) is not a story, because it happens on [0, +1 ).
Example 2. The temporal sequence (DC, EC, PO, TPP, NTPP, TPP, PO, EC, DC) in Fig. 2 is a story. Substrings, such as (PO, TPP, NTPP, TPP) or (DC, EC, PO), are not stories, but just temporal sequence of relations.
Definition 3. The Stories Set is the set of all possible stories of two entities.
If there is no constraint on the stories, the stories set contains an infinite number of stories. We refer to the stories set with the letter ⌃ (see Sect. 5); we add a subscript, e.g., ⌃ 0, when we deal with a set of stories that is not the stories set, but a subset thereof. 4
The central idea of this paper is to classify motions through stories: we assign the same category to the motions that belong to the same story. (Sect. 5). Thus, the total number of categories in our novel motion representation is the cardinality of the stories set, i.e., its number of elements. However, an awkward situation arises: the cardinality of the stories set is infinite—some stories are also infinite—, if we do not restrict the motions that create the stories.
Consequently, we suggest restricting the type of motions considered in order to obtain a tractable motion representation. We choose to restrict the stories by considering, from now on, only uniform motion, i.e., the velocity vectors are constant. This has two desirable properties: i. Each story in uniform motion is finite, i.e., has a finite number of relations (See Prop. 1 in Appendix A). ii. The set of all possible stories in uniform motion, i.e., the stories set (Def. 3), is finite (See Prop. 2 in in Appendix A). Consequently it partitions the whole phase space, i.e., the coordinates space of the positions and velocities of the two entities (~xk, ~vk; ~xl, ~vl).
The restriction to uniform motion stories is a standard assumption, if we classify motion situations that
are specified only by the current position and velocity of two entities, i.e., (~xk, ~vk; ~xl, ~vl)—the acceleration is
disregarded, as in QTC [
Rigid stories play a special role in uniform motion: each of them is a singleton—it has a single element, a constant spatial relation. But not all singleton stories are rigid, e.g., the story S11 = (DC) is not rigid but is a singleton (Fig. 4). x
y x y y
x
x y y x
We describe the method to create a representation of motion from any given spatial representation. In practice, our method yields always two representations of motion: the simple one, which is just formed by the stories, and the augmented variant, which is refined by adding the spatial relations to each story—we combine the power of ‘story‘ and ‘snapshots‘. We illustrate the method in the example below using the spatial representation RCC (Fig. 3), and thus, the two new generated representations of motion are Motion-RCC (Eq. (1) on page 6, and Fig. 4), and its augmented variant Augmented-Motion-RCC (Eq. (2) on page 6).
The method is as follows: 1. We have a spatial representation. 2. We calculate the stories set, ⌃, for the given spatial representation. In case it is a finite set, e.g., when restricted to uniform motion, we can work out a method to calculate it. 3. The obtained stories set is a novel representation of motion, where each story is a qualitative relation—every motion state is classified according to the story it belongs to. 4. (optional) We can create the augmented representation of motion from the first one by specifying the spatial relations in each story.
We illustrate the method above using the spatial representation RCC. (Fig. 3). RCC relates two regions according to their overlapping. So it yields 8 possible relations: DC, regions do not overlap; EC, regions are tangent nonoverlapping; PO, regions overlap in the interior but none is contained in the other; TPP, region x is contained in y and is tangent to the border; TPPI, region y is contained in x and is tangent to the border; EQ, both regions overlap completely; NTPP, x is contained in y and does not overlap the border of y; NTPPI, y is contained in x and does not overlap the border of x.
1. We have the spatial representation RCC 2. We calculate the RCC stories set restricted to uniform motion as ⌃ = ⌃ 0 [ ⌃ 1. ⌃ 0 = {(DC), (EC), (PO), (TPP), (NTPP)} are the rigid stories and ⌃ 1 ={(DC), (DC, EC, DC), (DC, EC, PO, EC, DC), (DC, EC, PO, TPP, PO, EC, DC), (DC, EC, PO, TPP, NTPP, TPP, PO, EC, DC)} are the non-rigid stories. We rename the rigid stories into S0i, ⌃ 0 = {S01, S02, S03, S04, S05}, and the non-rigid which we rename into S1i, ⌃ 1 = {S11, S12, S13, S14, S15} according to Fig. 4. 3. The stories set ⌃ is the qualitative representation of motion—note, though, that that story S01 and S11 are equal to (DC) therefore S01 drops to avoid repetition. We call this representation ‘Motion-RCC’:
Motion-RCC = {S02, S03, S04, S05, S11, S12, S13, S14, S15} This representation assigns to every motion state (~xk, ~vk; ~xl, ~vl) the corresponding story Si, i.e., the corresponding relation of motion. 4. (optional) We can augment the resolution of the representation of motion Motion-RCC by specifying the spatial relations in each story—for the singleton stories this process is redundant, as they have a single spatial relation. So we obtain the representation of motion ‘Augmented-Motion-RCC’. (1) (2) Augmented-Motion-RCC = { S02(EC), S03(PO), S04(TPP), S05(NTPP), S11(DC), S12(DC ), S12(EC), S12(DC+), S13(DC ), S13(EC ), S13(PO), S13(EC+), S13(DC+), S14(DC ), S14(EC ), S14(PO ), S14(TPP), S14(PO+), S14(EC+), S14(DC+), S15(DC ), S15(EC ), S15(PO ), S15(TPP ), S15(NTPP),
S15(TPP+), S15(PO+), S15(EC+), S15(DC+)} For example, the relation S12(EC) indicates that the entities are moving in the story S12 at the moment of tangency, i.e., EC. If the spatial relation appears multiple times in the story, such as EC in S3, we distinguish each appearance, for example, S13(EC ) is chronologically the first EC, and S13(EC+), the last EC. 6
We outline two possible applications of qualitative representations • Recognition of trajectories (i.e., motion patterns)
Through the qualitative relations in the new representation of motion, we can characterise and therefore
recognise certain types of motion [
S15(DC ) ! S14(DC ) ! S13(DC ) ! S12(DC ) ! S11(DC) (3) • Trajectory control
We can use the conceptual neighbourhood graph of our new representation of motion to take decisions in order
to control trajectories [
We have presented a a story-based method (Sect. 5) that should be able to generate qualitative representations of motion out of any spatial representation. The created representation of motion inherits the properties of the used spatial representation, e.g., dimensions, or type of entities considered. The method has proven to be e↵ective to generate meaningful qualitative representations of motions for the representation RCC (Sect. 5). With our generated motion representation, Augmented-Motion-RCC, we have outlined two applications of motion representations: recognition of trajectories, i.e., motion patterns; and control of trajectories.
Our generating method is most e↵ective, when we restrict the trajectories of the entities, e.g., setting velocity constant, so that our stories set is finite. This can be seen as a limitation or as the advantage to tailor the generated representation of motion to the features of our trajectories. We have restricted the trajectories to have uniform motion. S12
S13 S14 S14
S13
S15
We argue that the use of ‘stories’ to classify motions borrows from a cognitive idea: we can better recall a series of items, when they are linked by way of a story—Stories seem quite a natural way for humans to relate, connect, or classify items.
The next step are to test the e↵ectiveness of this method with other spatial representations, for instance,
three dimensional [
A
Proposition 1. Finitude of the Stories in Uniform Motion We can reasonably show that for two regular enough2 entities the stories in uniform motion are finite.
We build the proof on two properties: first, stories in uniform motion have extreme relations (Lemma 1); second, temporal sequences of relations in uniform motion are finite over a finite time interval (Lemma 2). Proof. According to Lemma 1 two regular enough entities in uniform motion have extreme relations. That is, we can find two time instants ta and tb, with ta < tb, so that in the time interval (1 , ta) the entities’ relation remains constant—we call it ra—and in the time interval (tb, +1 ) the entities’ relation remains constant.—we call it rb.
Now, According to Lemma 2, these regular enough entities moving in uniform motion have a finite temporal sequence of relations in the interval [ta, tb], say (r1, . . . , rn).
Consequently the story of the two entities, i.e., the temporal sequence of relations in the interval (1 , ta) S [ta, tb] S (tb, 1 ), would be finite, as it is obtained by concatenating the two extreme relations and the temporal sequence: (ra, r1, . . . , rn, rb). In case any extreme relation coincides with its border relation, i.e., ra = r1 or rb = rn, we exclude the repeated ones.
The extreme relations are those relations of a story that remain unchanged when t ! 1 or t ! +1 . That is, a relation ra is extreme in t ! 1 , if and only if 9 ta, so that in the time interval (1 , ta) the relation between entities is ra. Analogously, a relation rb is extreme in t ! +1 if and only if 9 tb, so that in the time interval (tb, +1 ) the relation between entities is rb.
Lemma 1. Existence of extreme relations for two entities in uniform motion.
Two regular enough2 entities that move in uniform motion and are described by a qualitative representation based on overlapping, intersection, or orientation, have a story with extreme relations both for t ! 1 and t ! +1 . Proof. We name the entities k and l and they have constant velocities ~vk and ~vl.
1. In the case ~vk = ~vl the relation between both entities, ri, remains constant — this relation is the whole
story —, therefore, trivially, ri is the extreme relation for both t ! 1 and t ! +1 .
2. In the case ~vk 6= ~vl we distinguish two subcases regarding what feature the representation bases on:
overlapping-intersection of entities, or relative orientation.
(a) Representations based on overlapping-intersection of finite entities have either one or two qualitative
relations for the case of ‘no overlapping-intersection’, e.g., the relation DC in RCC (Fig. 3); the relation
disjoint in 9-Int [
lim t! +1 k~ˆl(t) = ~vl k~vl ~vk ~vkk (4a)
lim k~ˆl(t) = t!1
lim t! +1 k~ˆl(t) (4b) 2Enough regular entities are those finite in size with a finite number of features, i.e., a finite number of vertices, edges, concavities, holes, . . . Because both limits for the connecting vector exist, the extreme relations of any story exist; they are the relations neighbouring each limit.
Lemma 2. Finitude of the Temporal Sequences of Relations in Finite Time Intervals In uniform motion, for regular enough2 entities, a temporal sequence of relations in a finite time interval is also finite.
Proof. A qualitative representation partitions the phase space of two regular enough finite entities in a finite number of regions, i.e., the qualitative relations. Therefore by moving in uniform motion in a finite time interval the system goes through a finite number of such regions, i.e., the resultant temporal sequence of relations must be finite.
Proposition 2. Finitude of the Stories Set The set of stories in uniform motion, i.e., the stories set, is finite.
Proof. We cannot rigorously prove that the stories set is finite, but Lemma 3 gives an equivalent condition that help us to see that the number of possible stories must be finite in most qualitative representations: if we prove that there is a story with more or an equal number of relations than any other, then the stories set must be finite. This is the case in RCC (Fig. 4), where the longest story is S5.
Lemma 3. The longest story The stories set is finite, if and only if it exists a longest story, i.e., a story that has more or equal relations than any other.