Juan Purcalla Arrufi

Alexandra Kirsch

Motion Categorisation: Representing Velocity Qualitatively

Categorising is arguably one of the first steps in cognition, because it enables high-level cognitive processing. For a similar reason, categorising is a first step-a preprocessing step-in artificial intelligence, specifically in decision-making, reasoning, and natural language processing. In this paper we categorise the motion of entities. Such categorisations, also known as qualitative representations, represent the preprocessing step for navigation problems with dynamical obstacles. As a central result, we present a general method to generate categorisations of motion based on categorisations of space. We assess its general validity by generating two categorisations of motion from two different spatial categorisations. We show examples of how the categorisations of motion describe and control trajectories. And we establish its soundness in cognitive and mathematical principles.

Introduction

Any sensor, either robotic or human, is inundated by data with no direct meaning in itself, but its numerical value. This requires simplification-reducing the amount and the degree of detail of the data-, and conceptualisation-endowing data with a more straightforward meaning. A meaningful categorisation provides both in one stroke.

This paper introduces a method for creating intuitive categorisations of motion. Its generality is the best asset: it can use any spatial categorisation to create new categorisations of motion. Moreover, our method is applicable in any spatial dimension; and it categorises motions even when one or both entities are motionless.

The method's effectiveness is validated by applying it, exemplary, to two very different spatial categorisations: one of them dealing with overlapping, RCC [START_REF] Randell | A Spatial Logic based on Regions and Connection[END_REF], and the other with orientation, OPRA 1 [START_REF] Moratz | Representing relative direction as a binary relation of oriented points[END_REF]. Thus, we obtain a novel categorisation of motion dealing with regions. In what follows, we show the meaningfulness of the generated categorisations: firstly, we practically show the application of the categorisations to describe trajectories qualitatively, and to control navigation; secondly, we advance cognitive and mathematical arguments.

We find categorisations of motion form a promising field, despite being few, they have already proved successful in several areas. They enhance the analysis of movements, such as pattern analysis of sport players' trajectories [START_REF] Delafontaine | Implementing a qualitative calculus to analyse moving point objects[END_REF], dancers' bodily movements [START_REF] Seyed Hossein Chavoshi | Exploring Dance Movement Data Using Sequence Alignment Methods[END_REF][START_REF] Chavoshi | A Qualitative Approach to the Identification, Visualisation and Interpretation of Repetitive Motion Patterns in Groups of Moving Point Objects[END_REF], or animals' trajectories [START_REF] Mavridis | QTC3D: Extending the qualitative trajectory calculus to three dimensions[END_REF]. They simplify the implementation of navigation routines, notably in human-robot interaction [START_REF] Hanheide | Analysis of humanrobot spatial behaviour applying a qualitative trajectory calculus[END_REF][START_REF] Lichtenthäler | Social navigation -Identifying robot navigation patterns in a path crossing scenario[END_REF][START_REF] Bellotto | Qualitative Design and Implementation of Human-Robot Spatial Interactions[END_REF], not only because they provide meaningful categories, but also by enabling decision-making [START_REF] Dylla | SailAway: Formalizing navigation rules[END_REF].

The difficulty of categorising motion is illustrated in Figure 1. Which attributes should we use-and how-in order to categorise the 4 motion scenarios A, B, C, D, in this figure? For example, the pair of scenarios (A, B) and (C, D) are almost identical, differing only in the speed of k. Consequently, each pair may build a category. However, if velocities are not modified, in scenarios A and C k would cross before l without colliding, while in scenario B the vehicles collide, and in D k crosses behind l. Are there then three categories (A, C), (B), and (D) more meaningful than the two previous, (A, B) and (C, D)?

The variety of possible motion categorisations originates in the variety of spatial categorisations; as we see in the example-we can differently categorise A and D, because of the spatial categories 'before' and 'behind'; we can categorise B alone, because of the spatial category 'overlap', i.e., collision. For that reason, we use spatial categorisations as the basis of our method to generate categorisations of motion from spatial categorisations; a method we presented in a preliminary version [START_REF] Purcalla | Using Stories to Create Qualitative Representations of Motion[END_REF].

Preliminaries on Motion Categorisation

In this section we clarify some aspects of the terminology used: the terms 'categorisation' and 'motion'. We also present the two spatial categorisations that we use as examples to create motion categorisations: RCC and OPRA 1 .

Categorisation, Qualitative Representation, and Related Terms

We used the term 'categorisation' in the introduction of this paper, because it is more readily understood than other similar terms. The use of these terms depends on the field of study, for example, 'categorisation' is mostly used in cognitive science, 'conceptualisation' in language, 'classification' in machine learning, and 'qualitative representation' in artificial intelligence.

A great variety of spatial categorisations has been presented in the literature as 'qualitative spatial representations', from which we generate our motion categorisations. Consequently, in the rest of the paper we mostly use the term 'qualitative representation' (equivalent to 'categorisation') and the term 'qualitative relation' (equivalent to 'category'). As a categorisation partitions a continuum into categories, so a qualitative representation partitions it into qualitative relations.

Qualitative representations are categorisations with extended mathematical properties, which allow, for example, reasoning [START_REF] Cohen | Handbook of Categorization in Cognitive Science[END_REF]. As much as our motion categorisations are obtained from qualitative spatial representations, they are also qualitative representations of motion, and could, eventually, be endowed with reasoning properties. However, this is beyond the scope of this paper.

x y k l v l v k A x v l v k y k l B x y l v l k v k C x y k l v k v l D

What we Categorise: Motion Scenarios

We categorise instantaneous motion scenarios of two entities, k and l (Fig. 2), i.e., a motion scenario that is determined by two real positions and two real velocities, thus, four vector values (x k , v k ; x l , v l ) in a certain instant t = t 0 .

The entities need not be punctual, but they are rigid regions and their only degrees of freedom are translation (no angular velocity allowed). Additional values are only needed if required by the spatial representation. For example, as we apply RCC to two-dimensional discs, we need their radii; in OPRA 1 we need the orientations, usually provided by the velocity vector.

We call K the set of all possible motion scenarios. By definition, to categorise a scenario (x k , v k ; x l , v l ) means to map it into a certain motion category, i.e., relation, q i , which belongs to the finite set of motion categories, i.e., relations, Q = {q 1 , q 2 , . . . , q n }. Consequently, a motion categorisation is simply a mapping, f q , that assigns a certain motion category to every motion scenario, i.e.,

f q : K -→ Q (x k , v k ; x l , v l ) -→ q i (1)
As illustration, in Section 5, we detail two qualitative representations of motion, i.e., categorisations, obtained by our generating method. The examples require the knowledge of two spatial representations, OPRA 1 and RCC, that are presented in the following section.

Used Spatial Categorisations

Here we present two qualitative spatial representations, i.e. spatial categorisations, RCC and OPRA 1 , that we use in the examples of our method (Sect. 5).

RCC: A Topological Spatial Categorisation

RCC [START_REF] Randell | A Spatial Logic based on Regions and Connection[END_REF] relates two finite regions in a topological space according to their connectedness. We apply RCC concretely to the two-dimensional euclidian space, where RCC can be seen as categorising the overlapping of regions (See Fig. 3). It, thus, yields 8 possible relations: DC, regions do not overlap; EC, regions are tangent non-overlapping; 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.

In order to ease the calculations, in our examples (Sects. 5.1, 6.1.2 and 6.1.3) we take two discs with different radii as moving entities, where the radius of entity x is larger than that of entity y, so that in our examples the relations TPPI, TNPPI, and EQ, are not mentioned. This figure depicts the 8 RCC relations: DC, EC, PO, TPP, NTPP, EQ, TPPI, and NTPPI as a conceptual neighbourhood graph [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF][START_REF] Dylla | Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control[END_REF]: the arrows connect relations that are conceptual neighbours-we switch between conceptual neighbours only by a continuous translation (no dilations allowed) and without going through any other relation.

OPRA 1 : A Directional Spatial Categorisation

OPRA 1 [START_REF] Moratz | Representing relative direction as a binary relation of oriented points[END_REF] relates two oriented entities according to the relative orientation between them, considering also if the entities are at the same point or not. A single oriented entity partitions the space into four regions (Fig. 4) that are numbered as following: '0' is the half line beginning at the entity and extending forwards in the orientation sense, '1' is the half plane at the left of the entity, '2' is the half line beginning at the entity and extending backwards opposite to the orientation sense, '3' is the half plane at the right of the entity. The regions that an oriented particle defines under OPRA 1 : '0' the frontal half line, '1' left half plane, '2' the back half line, '3' the right half plane. Now, the relation between two entities (Fig. 5) is expressed as the region that each entity occupies with respect to the other entity by using the symbol ∠ with the following syntax:

∠ k with respect to l l with respect to k For example, in Figure 5a, the second entity l is on region 3 of the first entity k, and k is on region 0 of l; accordingly, the relation between both entities is expressed as ∠ 0 3 . There is, though, the singular case in OPRA 1 , when the entities are at the same point (see Figure 6). In that case, we obtain new categories defined as ∠region of k to which l points

Related Work

In this section we present concepts, used in the paper, dealing with qualitative relations: conceptual neighbourhood diagrams and dominance theory. We also provide an overview of previous work in qualitative relations of motion.

Conceptual Neighbourhood Diagram

The 'Conceptual neighbourhood diagram', introduced by Freksa [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF], is one of the most elementary concepts concerning qualitative representations. A simple example is provided in Figure 3, the conceptual neighbourhood diagram connects the RCC relations that can be directly obtained by a continuous transformation, in this case a translation of the discs. We can obtain the conceptual neighbourhood diagram from any qualitative representation, particularly from the representations of motion (Fig. 13).

In this paper, the conceptual neighbourhood diagram is a ubiquitous concept. Firstly, the conceptual neighbourhood diagram is implicit, though not mentioned, in our foundational concept the 'story' (Sect. 4.1)-A story can be seen as a path, restricted to uniform motions, in the graph of the conceptual neighbourhood diagram of a spatial representation. Secondly, the conceptual neighbourhood diagram of the qualitative relations of motion, is the basic tool for implementation of decision-making and control algorithms-Qualitatively steering a moving entity consists on displacing between relations in the conceptual neighbourhood diagram (Sect. 6.1.3).

Dominance Theory

The dominance theory, introduced by Galton [START_REF] Galton | Dominance Diagrams: A Tool for Qualitative Reasoning About Continuous Systems[END_REF] is also foundational in qualitative motion: it studies the properties of the intervals involving relations in spatial representations. For example, some relations-called 'states of motion'can only occur in open time intervals, e.g., (t a , t b ), others called 'states of position' -can only occur in closed time intervals, e.g., [t a , t b ] or even an isolated instant t a .

As shown in Section 4.1.1, we use the distinction provided by the dominance theory to distinguish rigid stories, i.e., both entities have the same velocity, from singleton stories, i.e., the entities have different velocity.

Qualitative Representations of Motion

An overview of representations of motion is found in a survey by Dylla et al. [START_REF] Dylla | A Survey of Qualitative Spatial and Temporal Calculi -Algebraic and Computational Properties[END_REF]: in a total of 40 representations surveyed, they classify three as representations of motion: QRPC [START_REF] Francisco | QRPC: A new qualitative model for representing motion patterns[END_REF], RfDL-3-12 [START_REF] Kurata | Interpreting Motion Expressions in Route Instructions Using Two Projection-Based Spatial Models[END_REF], and, the most used, QTC [START_REF] Van De Weghe | Representing and Reasoning about Moving Objects: A Qualitative Approach[END_REF]. QTC refers to a varied family of representations characterised by suffix [START_REF] Delafontaine | Implementing a qualitative calculus to analyse moving point objects[END_REF], e.g., QTC C1 . Each particular QTC representation is formed by a n-tuple of three symbols {-, 0, +}, which are determined by certain kinematic features, e.g., moving towards or from, moving rightwards or leftwards, moving faster or slower.

The survey of spatial representations of Chen et al. [START_REF] Chen | A survey of qualitative spatial representations[END_REF] also mentions three motion representations: Dipole Calculus [START_REF] Moratz | Qualitative spatial reasoning about line segments[END_REF], DIA [START_REF] Renz | A spatial odyssey of the interval algebra: 1. Directed intervals[END_REF], and QTC. A particular representation of motion, given by Wu et al., is the only one, to our knowledge, that deals explicitly with regions-it is equivalent to a Cartesian product of the spatial representation RCC and the distance variation between regions.

Representations of orientation and relative direction, such as OPRA [START_REF] Moratz | Representing relative direction as a binary relation of oriented points[END_REF] or Dipole Calculus [START_REF] Moratz | Qualitative spatial reasoning about line segments[END_REF], are used to represent moving entities by equating orientation with velocity [START_REF] Dylla | SailAway: Formalizing navigation rules[END_REF]; nevertheless, they are not primarily intended for such a task.

All the aforementioned representations can be used to categorise motion scenarios, excepting RfDL-3-12, which categorises a straight segment of trajectorydescribing polygonal trajectories qualitatively we find [START_REF] Musto | Qualitative and quantitative representations of locomotion and their application in robot navigation[END_REF]. Most of the categorisations (QTC, OPRA, QRPC, DIA) are ill-defined when at least one of the velocity vectors is zero.

Generating Categorisations of Motion

In this section we present the core method of the paper: how to generate categorisations of motion for motion scenarios using a given spatial categorisation. We illustrate these explanations with two examples (Sections 5.1 and 5.2)-it is useful to parallel read this section along with the examples.

Based on the preliminaries, we have the following data as a starting point for our motion categorisation: i ) a 'motion scenario' of two entities, k and l, which is described by two instantaneous, in t = t 0 , position-velocity pairs of vectors-one pair for each entity:

(x k , v k ; x l , v l )
ii ) a 'spatial categorisation' R, which provides a mapping f ρ from the spatial data of both entities-positions, orientations-into a spatial relation, R i . Notice that, as all spatial data is also contained in the data of the motion scenario, f ρ can be seen as mapping a motion scenario (x k , v k ; x l , v l ) into the corresponding spatial relation.

f ρ : K -→ R (x k , v k ; x l , v l ) -→ R i (2)

Stories: a Step into Motion Categorisation

The motion categorisation of a scenario (x k , v k ; x l , v l ), at t = t 0 , originates by assuming uniform motion, i.e., unchanged velocities, of the entities both into the past and into the future. In that way we obtain a finite list of spatial relations between the entities: the past spatial relations which could have occurred (t < t 0 ), the current relation (t = t 0 ), and the future spatial relations which would follow (t > t 0 ), under the assumption of uniform motion. We call 'story' this full temporal (past, present, future) sequence of relations, (R i1 , R i2 , . . . , R im ), that originates from a certain motion scenario by assuming uniform motion [START_REF] Purcalla | Using Stories to Create Qualitative Representations of Motion[END_REF]. Notice that, even for entities not moving in uniform motion, we always enforce the assumption of uniform motion, when we generate a story.

We regard the assumption of uniform motion, by no means, as a limitation or a simplification, but rather a sound way to define in qualitative spaces a concept equivalent to the instantaneous velocity vector in quantitative spaces (See Section 6.2.3) Thus, stories are obtained by a mapping, f σ ,-every motion scenario generates a unique story, S i , under the assumption of uniform motion.

f σ : K -→ Σ (x k , v k ; x l , v l ) -→ S i = (R i1 , R i2 , . . . , R im ) (3)
We determine all possible stories, S i , that scenarios may yield for the given spatial categorisation R; this is always a finite set [START_REF] Purcalla | Using Stories to Create Qualitative Representations of Motion[END_REF]Math. Appendix] that we call 'stories set', and represent as Σ = {S 1 , S 2 , . . . , S n }.

Rigid and Singleton Stories

A 'rigid story' is the story of two entities that move with the same velocity, i.e., v k = v l . A 'singleton story' is a story consisting of a single spatial relation, where the velocities of the entities are different, i.e., v k = v l Both 'rigid' and 'singleton' stories have only one element, for example, the rigid story S 01 = (DC) and the singleton story S 11 = (DC), have the same one element (DC) (Fig. 7). They should be categorised as one single story. However, the dominance theory (Sect. 3.2) classifies the rigid story S 01 = (DC) differently as the singleton story S 11 = (DC). On this account, we are entitled to distinguish both stories.

Indeed, this distinction manifests in navigation control (Sect. 6.1.3). A rigid story can only occur in a closed time interval-also in an isolated instantwhereas a singleton story must always occur in an open interval and, thus, cannot occur at an isolated instant.

k l v k v l k v k l v l
Figure 7: Two motion scenarios that seemingly have the same story (DC), but are different classified according to the dominance theory. The first scenario can occur only in closed time intervals, both velocity vectors are equal, i.e., v k = v l ; such scenario belongs, therefore, to the rigid story S 01 , its category is S 01 (DC). The second scenario can only occur in opened time intervals, velocity vectors are different, i.e., v k = v l ; and it, therefore, belongs to a singleton story S 11 , its category is S 11 (DC).

Story-Based Method for Generating Categorisations of Motion

We describe the method to create a categorisation of motion, i.e., a qualitative representation of motion, from any given spatial representation-we illustrate the method with examples in Section 5.

The method is as follows:

1. We have a spatial categorisation R, which relates each motion scenario with its spatial relation through the mapping f ρ (Eq. ( 2))

2. We determine all possible stories, S i , that motion scenarios (x k , v k ; x l , v l ) may yield for the given spatial categorisation, i.e., the 'stories set' Σ = {S 1 , S 2 , . . . , S n } 3. We obtain the mapping f σ that maps every motion scenario into a story S i (Eq. ( 3)).

4. We can straightforwardly create a motion categorisation, f q as presented in Equation ( 1), if we combine both aforementioned mappings, f σ and f ρ , through the Cartesian product, i.e., f q := f σ × f ρ (Eq. ( 4)). Accordingly, a motion scenario (x k , v k ; x l , v l ) is mapped into a story S i and into a qualitative spatial relation R j . Thus, the motion category of the scenario is defined as S i (R j ), i.e., the story S i , at the spatial relation R j .

f q := f σ × f ρ : K -→ Σ × R (x k , v k ; x l , v l ) -→ S i (R j ) (4)

Examples of Story-Based Representations of Motion

We use the story-based method defined above to generate novel qualitative representations of motion, i.e., motion categorisations, 'Motion-RCC' and 'Motion-OPRA 1 ', based on qualitative spatial representations, RCC and OPRA 1 .

Motion-RCC

We illustrate the method above (Sect. 4) using the spatial categorisation RCC.

1. We have a spatial representation R = RCC, which provides a mapping f ρ that relates each motion scenario with a spatial relation R j .

2. We obtain the stories set Σ = Σ 0 ∪ Σ 1 ; where Σ 0 = {(DC), (EC), (PO), (TPP), (NTPP), (TPPI), (NTPPI), (EQ)} 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), (DC, EC, PO, TPPI, PO, EC, DC), (DC, EC, PO, TPPI, NTPPI, TPPI, PO, EC, DC), (DC, EC, PO, EQ, PO, EC, DC)} are the non-rigid stories (Fig. 8a). We rename the rigid stories into S 0i , Σ 0 = {S 01 , S 02 , S 03 , S 04 , S 05 , S 06 , S 07 , S 08 }, and the non-rigid stories into S 1i , Σ 1 = {S 11 , S 12 , S 13 , S 14 , S 15 , S 16 , S 17 , S 18 }, according to Fig. 8a.

3. We obtain the mapping f σ , which assigns to every motion scenario (x k , v k ;

x l , v l ) the corresponding story S i .

4. The representation of motion is then generated by assigning to each motion scenario the pair S i and R j , which we write in the form S i (R j ); they are obtained respectively by the mappings f σ and f ρ

We call this representation 'Motion-RCC'.

Motion-RCC

For example, the relation S 12 (EC) indicates that the entities are moving in the story S 12 at the moment of tangency, i.e., EC. If the spatial relation appears multiple times in the story, such as EC in S 3 , we distinguish between each appearance, for example, chronologically, S 13 (EC -) is the first EC, and S 13 (EC + ), the last EC.

Motion-OPRA 1

We illustrate the method above in Section 4 using the spatial categorisation OPRA 1 .

1. We have a spatial representation R = OPRA 1 , which provides a mapping f ρ that relates each motion scenario with a spatial relation R j .

2. We obtain the stories set Σ as the union of different meaningful subsets ( Table 1):

Σ = Σ C ∪ Σ B ∪ Σ T ∪ Σ P ∪ Σ E ∪ Σ R (6)
3. We obtain the mapping f σ , which assigns to every motion scenario (x k , v k ;

x l , v l ) the corresponding story S i .

4. The representation of motion is then generated by assigning to each motion scenario the pair S i and R j , which we write in the form S i (R j ); they are obtained respectively by the mappings f σ and f ρ

We call this representation 'Motion-OPRA 1 '. We obtain its qualitative relations by combining each story S i (Table 1) with its spatial relations R j = ∠ b a (Eq. ( 7)). Consequently, it has a total of 100 relations of motion.

Non-Parallel velocities v k ∦ v l Σ C        v k = 0, v l = 0 ∠ 3 1 ∠ 0 1 ∠ 1 1 ∠ 1 2 ∠ 1 3 S C1-1 ∠ 1 3 ∠ 0 3 ∠ 3 3 ∠ 3 2 ∠ 3 1 S C2-1 ∠ 3 1 ∠3 ∠ 1 3 S C10 ∠ 1 3 ∠1 ∠ 3 1 S C20 ∠ 3 1 ∠ 3 0 ∠ 3 3 ∠ 2 3 ∠ 1 3 S C11 ∠ 1 3 ∠ 1 0 ∠ 1 1 ∠ 2 1 ∠ 3 1 S C21 Σ B                          v k = 0, v l = 0 ∠ 3 1 ∠ 0 1 ∠ 1 1 S B1-1 ∠ 1 3 ∠ 1 0 ∠ 1 1 S B2-1 ∠ 3 0 ∠3 ∠ 1 2 S B10 ∠ 0 3 ∠1 ∠ 2 1 S B20 ∠ 3 3 ∠ 2 3 ∠ 1 3 S B11 ∠ 3 3 ∠ 3 2 ∠ 3 1 S B21 v k = 0, v l = 0 ∠ 1 3 ∠ 0 3 ∠ 3 3 S B3-1 ∠ 3 1 ∠ 3 0 ∠ 3 3 S B4-1 ∠ 1 0 ∠1 ∠ 3 2 S B30 ∠ 0 1 ∠3 ∠ 2 3 S B40 ∠ 1 1 ∠ 2 1 ∠ 3 1 S B31 ∠ 1 1 ∠ 1 2 ∠ 1 3 S B41 Parallel velocities v k v l Σ T       
The entities' trajectories are superposed

∠ 2 0 ∠0 ∠ 0 2 S T -1 ∠ 0 0 ∠2 ∠ 2 2 S T 0 ∠ 0 2 ∠0 ∠ 2 0 S T 1 Σ P       
The entities' trajectories are not superposed singleton stories

∠ 3 1 S P 11 ∠ 3 3 S P 21 ∠ 1 3 S P 12 ∠ 1 1 S P 22 Rigid stories v k = v l Σ E        v = 0 ∠ 2 0 S E-2 ∠ 0 2 S E2 ∠ 1 3 S E-1 ∠ 3 1 S E1 ∠0 S E0 Σ R                motionless entities, v = 0, equiv. to OPRA 1 ∠ 0 0 S R00 ∠ 0 1 S R10 ∠ 0 2 S R20 ∠ 0 3 S R30 ∠ 1 0 S R01 ∠ 1 1 S R11 ∠ 1 2 S R21 ∠ 1 3 S R31 ∠ 2 0 S R02 ∠ 2 1 S R12 ∠ 2 2 S R22 ∠ 2 3 S R32 ∠ 3 0 S R03 ∠ 3 1 S R13 ∠ 3 2 S R23 ∠ 3 3 S R33 ∠0 S R0 ∠1 S R1 ∠2 S R2 ∠3 S R3 Table 1: Stories set Σ of OPRA 1 , divided into meaningful subsets of stories: Σ C , Σ B , Σ T , Σ P , Σ E , Σ R Motion-OPRA 1 = {S C1-1 ( ∠ 3 1 ), S C1-1 ( ∠ 0 1 ), S C1-1 ( ∠ 1 1 ), S C1-1 ( ∠ 1 2 ), S C1-1 ( ∠ 1 3 ), S C10 ( ∠ 3 1 ), S C10 ( ∠3 ), S C10 ( ∠ 1
3 ), . . . , S R2 ( ∠2 ), S R3 ( ∠3 )} (7) In Figure 9 we show examples of stories, S P 21 and S C2-1 , and corresponding qualitative relations of motion, for example, S P 21 ( ∠ 3

3 ) and S C2-1 ( ∠ 1 1 ).

Story S P 21

l 0 1 3 2 k S C2-1 ( ∠ 1 3 ) S C2-1 ( ∠ 0 3 ) S C2-1 ( ∠ 3 3 ) S C2-1 ( ∠ 3 2 ) S C2-1 ( ∠ 3 1 )
Figure 9: Representation of two stories in Motion-OPRA 1 , S P 21 and S C2-1 , displaying each one's spatial relations (See Table 1). Grouping story and spatial relation, i.e., S i (R j ) we obtain the relation of motion, e.g., S C2-1 ( ∠ 1 1 ) at the third scenario in the story S C2-1 .

Discussion

In this section we display the features of the generated motion representations, i.e., story-based representations of motion, by applying them to the introductory example (Fig. 1). We also discuss some apparent limitations-simplifications originating from the underlying spatial representations-and how to overcome them.

Categorisation with Motion-RCC and Motion-OPRA 1

Using Motion-RCC the scenarios of Figure 1,A,B,C,D, have the following qualitative relations, i.e., categories: A, C, D form one category with the relation S 11 (DC), and B forms one category with the relation S 13 (DC -). This can be interpreted as A, C, D being scenarios that would not evolve into collision, while in B k and l would collide provided no action is taken.

Using Motion-OPRA 1 the scenarios of Figure 1 have the following qualitative relations: A, B, C form one category with the relation S C1-1 ( ∠ 3 1 ), and D forms one category with the relation S C11 ( ∠ 3 1 ). This indicates that, if the entities were punctual, in scenarios A, B, C, k crosses before l; and in D, k crosses behind l.

Disregarded Attributes

We see that each of the generated motion representations disregards some spatial attributes, because the underlying spatial representations, striving after simplicity, intentionally disregard them-Spatial representations focus on the few attributes that are deemed relevant and dispense with the rest.

Motion-OPRA 1 disregards distance, as OPRA 1 does. A, B, C belong to the category defined by the relation S C1-1 ( ∠ 3 1 ), but we cannot assert the distance at which they currently the entities are, nor the minimal distance at which they will cross. Indeed, in scenario B the vehicles collide because of their size, and in scenarios A, C they don't, but OPRA 1 cannot distinguish it. This is a consequence of the spatial relation OPRA 1 ; it considers directions, and disregards distances.

Motion-RCC disregards right-left relative motion, front-back, parallelism, and crossing, as RCC does. For example, we categorise A, C, D scenarios as S 11 (DC)-entities that are passing by-but we cannot assert which entity will cross before or after the other.

Extending Motion Representations: Combining Attributes

In order to solve the problem with disregarded attributes, we can create an extended motion representation by combining motion representations through Cartesian product. For instance, as Motion-RCC does not consider right-left, front-back, crossing, or parallelism, we can add the representation Motion-OPRA 1 , which provides categorisation of such attributes. Thus, we obtain a new motion representation 'Motion-RCC × Motion-OPRA 1 '.

In this new representation we combine the attributes of its original representations: we have information about the degree of collision, through Motion-RCC; and information about right-left, crossing, parallelism, and precedence, through Motion-OPRA 1 .

In the introductory example (Fig. 1) the Cartesian product would yield the following relations: scenario A is (S 11 (DC), S C1-

1 ( ∠ 3 1 )), B is (S 13 (DC -), S C1-1 ( ∠ 3 1 )), C is (S 11 (DC), S C1-1 ( ∠ 3 1 )
), and D is (S 11 (DC), S C11 ( ∠ 3 1 )). The derived categories are (A, C), (B), and (D).

Variety of Categorisations

Motion-RCC and Motion-OPRA 1 define 3 possible categorisations:

1. (A, C, D) and (B), which correspond to scenarios with or without collision risk. We categorised with Motion-RCC.

(A, B, C

) and (D), which correspond to scenarios where k arrives first to the intersection point, or l arrives first. We categorised with Motion-OPRA 1 .

(A,C), (B), and (D)

. This corresponds to scenarios with collision risk, (D), and those without collision risk, A, B, C, being subdivided according to the entity that crosses before the other: in (A,C) k crosses first, and in (B) l does. We categorised with Motion-RCC × Motion-OPRA 1 .

Further categorisations can be obtained, creating new representations of motion by means of spatial representations and by combining them through Cartesian product.

Validation of Story-Based Representations of Motion

The first part of this section shows the utility of the story-based qualitative representations of motion: first, to qualitatively describe any kind of trajectories; second, to plan and control the navigation of entities. We present practical reasons that motivate the use of story-based representations of motion in navigation and motion processing.

The second part presents a bundle of desirable cognitive and mathematic properties that these representations fulfil. On the one hand we show how the story-based representations contain meaningful motion concepts of our daily life. On the other hand we show how they are embedded in the body of science: how they relate to cognition and to the concept of derivative.

Description and Control

Classification of Motionless Entities

The story-based representations of motion classify motions when entitiesone or both entities-are motionless. As examples, see Figure 10, and also Figure 12 where the trajectory of entity k with respect to l is described by Motion-OPRA 1 ,though l is motionless.

Accordingly, these representations are not only valid for dynamic environments, but also valid for static ones. For example, if a robot navigates in a dynamic environment, and suddenly all objects are motionless, there is no need to switch representation-the story-based representation allows for further motion description and control of the robot.

k l v k v l k l v l v k =0
Figure 10: Two motion scenarios, both having the same category, i.e., S 14 (DC -), in the motion representation Motion-RCC. The fact that in the second scenario the entity k is motionless is not a hindrace for a scenario categorisation.

Qualitative Description of General Motions

A property of the story-based representations of motion-and of any categorisation of instantaneous scenarios-is the ability to qualitatively describe any kind of two-entities trajectories [START_REF] Van De Weghe | Representing moving objects in computer-based expert systems: The overtake event example[END_REF][START_REF] Van De Weghe | A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems[END_REF]. This is mainly used in recognition of trajectories (i.e., motion patterns)-a trajectory that is encoded through qualitative relations can be more easily categorised as a certain type of motion, e.g., an 'avoidance manoeuvre', and therefore facilitates the development of interactive navigation routines [START_REF] Delafontaine | Implementing a qualitative calculus to analyse moving point objects[END_REF][START_REF] Hanheide | Analysis of humanrobot spatial behaviour applying a qualitative trajectory calculus[END_REF].

We exemplify, by means of Motion-RCC, how the story-based representations effectively describe the trajectories of two entities. The trajectory description consists of a finite sequence of qualitative relations of the generated representation. As we see in Figure 11, the motion of k with respect to l is described as {S 15 (DC -), S 14 (DC -), S 13 (DC -), S 12 (DC -), S 11 (DC)}, while the motion of m with respect to l is described as {S 15 (DC -), S 15 (EC -), S 15 (PO -), S 15 (TPP -), S 15 (NTPP), S 15 (TPP + ), S 15 (PO + ), S 15 (EC + ), S 15 (DC + ), S 14 (DC + ), S 13 (DC + ), S 12 (DC + ), S 11 (DC)}.

One can argue that the trajectories in Figure 11 might be simply described through the list of spatial relations, that is, k's trajectory is {DC}, while m's is {DC, EC, PO, TPP, NTPP, TPP, PO, EC, DC}. However, in Figure 12, we give a counterexample of how the generated relations of motion resolve serious ambiguities that spatial relations cannot. The RCC description of both trajectories is the spatial relation {DC}, but the Motion-RCC description is the relations of motion {S 15 (DC -), S 14 (DC -), S 13 (DC -), S 12 (DC -), S 11 (DC)} for k's trajectory, and {S 11 (DC)} for m's trajectory. the motion of (k, l); or the motion of (m, l)

Using Conceptual Neighbourhoods for Decision-Making and Control

Beyond the qualitative description of trajectories, the story-based representations of motion can be used for decision-making and control of trajectories, as any representation of motion can [START_REF] Dylla | SailAway: Formalizing navigation rules[END_REF][START_REF] Bellotto | Qualitative Design and Implementation of Human-Robot Spatial Interactions[END_REF]. First of all, we want to distinguish 'decision-making' from 'reasoning'. In the field of qualitative relations 'reasoning' consists on determining the possible categories of a group of more than two entities under certain constraints [START_REF] Renz | Qualitative Spatial Reasoning Using Constraint Calculi[END_REF], while in this paper 'decision-making' refers to finding the actions to steer an entity, whose motion with respect to the motion of (k, l), i.e., k-trajectory; and the motion of (m, l), i.e., m-trajectory.

Both trajectories have a single qualitative spatial relation, namely, DC, but have different descriptions according to the qualitative relations of motion in Motion-RCC (Eq. ( 5)): k's trajectory is {S 15 (DC -), S 14 (DC -), S 13 (DC -), S 12 (DC -), S 11 (DC)}, while m's trajectory is {S 11 (DC)} .

other entities is described qualitatively. Thus, qualitative reasoning can empower decision-making, but decision-making is not restricted to qualitative reasoning.

We obtain two important tools for decision-making and control by building the conceptual neighbourhood diagram of our story-based representation, e.g., for Motion-RCC (Fig. 13):

1. We can predict how the current motion scenario evolves, if velocities remain the same-these are the '→' arrows in Figure 13.

2. We can find the control decisions to reach a certain motion scenario, by finding the path in the graph between the start and final scenario. As there are, usually, many paths connecting two scenarios, we can set conditions on the chosen path, for instance, the absence of collisions.

As an example, consider the initial motion of entity k with respect to entity l in Figure 12. It has the qualitative relation S 15 (DC -) (start relation in Figure 13). Now, by means of a conceptual neighbourhood diagram, we find the necessary dynamic actions to transition into the safe motion state, i.e., S 11 (DC)-the resultant trajectory should be equivalent to the k-trajectory in Figure 12.

Cognitive and Mathematical Properties

Formation of New Concepts

As we see in our generated representations of motion, Motion-RCC and Motion-OPRA 1 , the stories are at the base of our categorisation-any qualitative relation, e.g., S 15 (PO + ), is directly linked to the story to which it belongs, in this case S 15 . We, now, realise that stories relate to basic concepts of motion, for example, collision, parallelism, crossing precedence, by-passing, . . . The fact that stories relate to these concepts is remarkable in the measure that those concepts were not present in the original spatial relations. For example, the stories of Motion-RCC correspond to diverse degrees of collision: S 11 corresponds to tangential collisions; S 12 and S 13 to partial collisions; S 14 and S 15 to total collisions.

In Motion-OPRA 1 the number of concepts increases. We see that each subset of stories Σ corresponds to a simple motion concept.

• Σ C correspond to stories of both entities moving and crossing

• Σ B correspond to stories where one entity is still and the other crossing.

• Σ T corresponds to superposed trajectories.

• Σ P corresponds to parallel trajectories (not superposed)

• Σ E corresponds to trajectories of two entities moving in alignment and maintaining distance from one another.

• Σ R are still stories: both entities are still.

Within each subset Σ we find a further variety of concepts, for instance, the crossing stories Σ C are subcategorised according to which entity crosses first, i.e., reaches the crossing point first: in S C * -1 k crosses first, and in S C * 1 l crosses first.

Cognitive Adequacy

Besides the formation of concepts in the story-based representations, here, we present further cognitive arguments that support the story-based representations.

Relation to Optical Invariants An important step in cognition is to extract information from the sensory input. If we consider the visual stimuli of a moving human, it is known that we use optical invariants [START_REF] Waller | Handbook of spatial cognition[END_REF], i.e., an "optical variable whose values remains invariant whenever the actor is in a state that if maintained, will bring about a successful outcome". For example, if the relative angle between a human's direction and the direction of a moving entity remains constant, the human will-if nothing changes-collide with the moving entity.

Optical variables provide, therefore, information about the current future [START_REF] David N Lee | Lee's 1976 Paper[END_REF], that is, what will eventually happen if one's current state (deceleration, running speed) remains constant.

In a similar sense we claim that story-based relations provide this 'current future' information about a meaningful outcome in the future, as optical variables do. Indeed, each relation of motion of a story-based representation is linked to the corresponding story, and the story is per definition the 'current future' equivalent for qualitative relations. For example, consider these three motion scenarios described by three different Motion-OPRA 1 relations: S C1-1 ( ∠ 3 1 ), S C10 ( ∠ 3 1 ), S P 12 ( ∠ 3 1 ). All three motion relations describe two entities whose spatial OPRA 1 relation is ∠ 3 1 , but the story part of the motion relation, i.e., S C1-1 , S C10 , and S P 12 , shows clearly that the evolution in each case is differentin the first relation k crosses before l, in the second k and l cross and collide, in the third k and l move in parallel. Therefore, we see that each of the motion relations is providing information about what is about to happen if the velocities remain the same, i.e., they provide information about the current future.

Motion Encoding and Anticipatory Behaviour From a cognitive viewpoint, we can see the representations of motion as a way to encode sensory information of two entities instantaneously moving. In that sense, we would expect these encodings to validate the principle of anticipatory behaviour and the need to represent interaction goals; in the words of Butz and Kutter: "[...] the brain does not represent space for its own sake, but rather the internal representations develop to be able to convert sensory information in such a way that motor behaviour can be executed effectively." ([2, p. 236])

Certainly, as argued in Section 6.2.2, the story-based representations encode a motion scenario with information about the current future, which facilitate such anticipatory behaviour. As shown in Section 6.1.3, the conceptual neighbourhood diagram makes possible the reaching of the goal motion scenario.

Qualitative Generalisation of the Derivative:

A Qualitative Velocity

We can draw an analogy between story-based relations of motion in qualitative spaces, and the tangent line in quantitative spaces; between a story, qualitatively, and the trajectory derivative, i.e., the velocity, quantitatively. The tangent line of the trajectory γ(t) of an entity k is defined by the current position γ(t 0 ) and the derivative dγ dt (t) t=t0 , i.e., the velocity v k at t 0 .

Thus, the tangent line provides information about the past, present and future position of the entity k providing that it has moved and will keep moving in uniform motion (See Figure 14). In the same way a story-based relation, e.g., S 13 (DC -), provides information about the past, e.g., (DC), present, e.g., (DC), and future qualitative spatial relations, e.g., (DC,EC,PO,EC,DC) of the entity k with respect to entity l, providing that it has moved and will keep moving in uniform motion. Consequently, as the tangent line is analogous to a story-based relation of motion, i.e., S i (R j ), if we take further this analogy, the current spatial relation, R j can be related to the current point, and the story, S i , to the velocity vector.

This analogy is limited, because the tangent line, given the time instant, provides the expected position of the entity, while the story does not allow time calculations.

l k k S13(D C_ ) k k k v k EC P O D C E C D C γ(t)
Figure 14: This is an instant of k moving on the trajectory γ(t). The velocity vector v k provides the instantaneous slope of the tangent line, i.e., the expected positions, if the entity maintains the same velocity. The motion relation S 13 (DC -) provides the same information qualitatively, i.e., the expected qualitative relations (EC, PO, EC, DC), if the entity maintains the same velocity.

Future Work

In this section, we have a look at two topics to be developed in future work.

Three-Dimensional Categorisations of Motion

As we mentioned in the Introduction, the method is applicable in any spatial dimensions, particularly, in three dimensions, where little research is done-we only know of a three dimensional categorisation, a QTC variant [START_REF] Mavridis | QTC3D: Extending the qualitative trajectory calculus to three dimensions[END_REF].

To obtain a three-dimensional categorisation of motion, we need a threedimensional spatial categorisation. For example, RCC can be trivially extended to three-dimensional regions; the RCC qualitative relations (Fig. 3)-DC, EC, PO, TPP, NTPP, EQ, TPPI, NTPPI-are the same in three dimensions [START_REF] Zlatanova | On 3D topological relationships[END_REF]. Consequently, the stories are the same, and, therefore, the qualitative relations are the same than in two dimensions (Eq. ( 5)), but with a three-dimensional meaning. Thus, S 13 (DC -) corresponds to the scenario where two spheres are disconnected, but they move towards one another, so that their uniform trajectory goes through a partial overlapping (PO).

Motion

Motion Categorisation for Multiple Entities

'Multiple entities' refers to scenarios with more than two entities. Until now, we only considered two entities for the sake of simplicity, because qualitative relations are usually binary defined. Nevertheless, in this section we give a glimpse of the possibilities of story-based categorisations of three moving entities by means of an example (Fig. 15). In this example, we show how two scenarios, having the same OPRA 1 spatial relations, are categorised according to the storybased method (Sect. 4).

Conclusion

We have presented a method to generate qualitative representations of motion, i.e., motion categorisations, out of any spatial representation. The method is motions-we have used it with two spatial representations RCC and OPRA 1 .

The generated representations are, at a practical level, effective both to describe trajectories qualitatively and to implement decision-making and control in navigation, even when entities are motionless. Moreover, they manifest a variety of cognitive and conceptual properties that endorse its use: (i) the motion relations, i.e., the motion categories, are related to common navigation concepts, (ii) they follow principles similar to the cognitive encoding of motion stimuli, (iii) they can be seen as a qualitative generalisation to the tangent lines, i.e., the velocity, of a trajectory on real spaces.

Central points in future work will be experimentally checking the cognitive adequacy of story-based representations of motion in humans, automatising the generation of stories and their mappings (at the moment they are obtained manually), applying the method to create three-dimensional categorisations of motion, and categorising motions with more than two entities. Additional points for future work, are the reasoning capabilities with the story-based representations of motion, and how they are related to the reasoning capabilities in the generating spatial relations.

Figure 1 :Figure 2 :

 12 Figure 1: A challenge for motion categorisation: 4 scenarios (A,B,C,D) with two moving vehicles k and l, with velocity vectors v k and v l . Each pair (A,B) and (C,D) has identical positions, velocity angles, and fulfils v k > v l -each pair differs only in the speed of k.

Figure 3 :

 3 Figure3: The RCC qualitative relations depend on how two entities overlap. This figure depicts the 8 RCC relations: DC, EC, PO, TPP, NTPP, EQ, TPPI, and NTPPI as a conceptual neighbourhood graph[START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF][START_REF] Dylla | Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control[END_REF]: the arrows connect relations that are conceptual neighbours-we switch between conceptual neighbours only by a continuous translation (no dilations allowed) and without going through any other relation.

Figure 4 :

 4 Figure 4: The regions that an oriented particle defines under OPRA 1 : '0' the frontal half line, '1' left half plane, '2' the back half line, '3' the right half plane.

Figure 5 :

 5 Figure 5: Examples of OPRA 1 spatial relations, ∠ b a , between two entities k and l that are at different points. The syntax is ∠ k with respect to l l with respect to k

Figure 6 :

 6 Figure 6: Examples of OPRA 1 spatial relations, ∠a , between two entities k and l that are at the same point. The syntax is ∠region of k to which l points

11 (Figure 8 :

 118 Figure 8: Stories in RCC

Figure 11 :

 11 Figure 11: Two possible pairs of motion description are presented in this figure: the motion of (k, l); or the motion of (m, l)

Figure 12 :

 12 Figure 12: Two possible pairs of motion description are presented in this figure:the motion of (k, l), i.e., k-trajectory; and the motion of (m, l), i.e., m-trajectory. Both trajectories have a single qualitative spatial relation, namely, DC, but have different descriptions according to the qualitative relations of motion in Motion-RCC (Eq. (5)): k's trajectory is {S 15 (DC -), S 14 (DC -), S 13 (DC -), S 12 (DC -), S 11 (DC)}, while m's trajectory is {S 11 (DC)} .

Figure 13 :

 13 Figure 13: Part of the conceptual neighbourhood diagram for RCC-Motion. As an example, S 15 (DC -) (green ellipse) is the start situation and S 11 (DC) (green rectangle) is the desired safe situation. The only way through the diagram that reaches the desired safe state without colliding is marked with a green arrow. It corresponds to the trajectory of k in Figure 12: S 15 (DC -), S 14 (DC -), S 13 (DC -), S 12 (DC -), S 11 (DC).The diagram also provides the type of control action needed, either a change in the value of the vector v kv l , i.e., ⇒, or not, i.e., →. Further meaningful information present in the diagram is the expected evolution of the scenario: if velocities remain constant the motion relations evolve according to the '→'.

  -RCC-3d = { S 01 (DC), S 02 (EC), S 03 (PO), S 04 (TPP), S 05 (NTPP), S 06 (TPPI), S 07 (NTPPI), S 08 (EQ), S 11 (DC), S 12 (DC -), S 12 (EC), S 12 (DC + ), S 13 (DC -), S 13 (EC -), S 13 (PO), S 13 (EC + ), S 13 (DC + ), S 14 (DC -), S 14 (EC -), S 14 (PO -), S 14 (TPP), S 14 (PO + ), S 14 (EC + ), S 14 (DC + ), S 15 (DC -), S 15 (EC -), S 15 (PO -), S 15 (TPP -), S 15 (NTPP), S 15 (TPP + ), S 15 (PO + ), S 15 (EC + ), S 15 (DC + ) S 16 (DC -), S 16 (EC -), S 16 (PO -), S 16 (TPPI), S 16 (PO + ), S 16 (EC + ), S 16 (DC + ), S 17 (DC -), S 17 (EC -), S 17 (PO -), S 17 (TPPI -), S 17 (NTPPI), S 17 (TPPI + ), S 17 (PO + ), S 17 (EC + ), S 17 (DC + ), S 18 (DC -), S 18 (EC -), S 18 (PO -), S 18 (EQ), S 18 (PO + ), S 18 (EC + ), S 18 (DC + )} (8)

  = { S 01 (DC), S 02 (EC), S 03 (PO), S 04 (TPP), S 05 (NTPP), S 06 (TPPI), S 07 (NTPPI), S 08 (EQ), S 11 (DC), S 12 (DC -), S 12 (EC), S 12 (DC + ), S 13 (DC -), S 13 (EC -), S 13 (PO), S 13 (EC + ), S 13 (DC + ), S 14 (DC -), S 14 (EC -), S 14 (PO -), S 14 (TPP), S 14 (PO + ), S 14 (EC + ), S 14 (DC + ), S 15 (DC -), S 15 (EC -), S 15 (PO -), S 15 (TPP -), S 15 (NTPP), S 15 (TPP + ), S 15 (PO + ), S 15 (EC + ), S 15 (DC + ) S 16 (DC -), S 16 (EC -), S 16 (PO -), S 16 (TPPI),

S 16 (PO + ), S 16 (EC + ), S 16 (DC + ), S 17 (DC -), S 17 (EC -), S 17 (PO -), S 17 (TPPI -), S 17 (NTPPI), S 17 (TPPI + ), S 17 (PO + ), S 17 (EC + ), S 17 (DC + ), S 18 (DC -), S 18 (EC -), S 18 (PO -), S 18 (EQ), S 18 (PO + ), S 18 (EC + ), S 18 (DC + )}

Acknowledgements

Juan Purcalla Arrufi is grateful to Marcus Genkinger, CEO of STS Maschinenbau GmbH, for providing a job that can be flexibly adapted to his research activities. Thanks to Julia Paterson for kindly correcting and reviving the paper's English.

0 ) with some following relations of its story,

). We call this story SM , where the entity k goes between l and m.

0 ) with some following relations of its story, ( ∠ 2 1 , ∠ 2 1 , ∠ 2 0 ) and ( ∠ 3 1 , ∠ 3 1 , ∠ 2 0 ). We call this story SU , where the entity k goes behind l and m.

Figure 15: Two stories, S M (Fig. 15a) and S U (Fig. 15b), each with three moving entities, k, l, and m. The spatial relation for each scenario is given by a 3-tuple containing its three binary OPRA 1 qualitative relations. Both stories have initial motion scenarios with the same spatial relation, i.e., ( ∠ 1 3 , ∠ 1 1 , ∠ 2 0 ), though the stories are different. Therefore, the scenarios are differently categorised: the first motion scenario of Figure 15a is categorised as

), and the first motion scenario of Figure 15b is categorised as

story-based, and the created representations of motion inherit the properties of the used spatial representation, e.g., dimensions, or type of entities considered.

The method has shown its potential to generate qualitative representations of