Introduction

How can we characterize movement patterns? We can, for example, adopt a formal approach and characterize movement patterns on the basis of manifold spatial calculi that capture static and dynamic spatial relations (e.g., van der Weghe, Billen, Kuijpers, & Bogaert, 2008). We can also investigate how humans make sense of movement patterns or how they perceive and structure movement events. Although many formal approaches are inspired by general results from cognitive studies, it is still an open question if they adequately bridge the gap between cognitive and formal characterizations. While we will not close this gap completely with this contribution, we do hope to make it a little less wide. To do so, we extend our approach to characterizing movement patterns on the basis of conceptual primitives that are termed here: movement choremes ( ). In the following, we first offer an early taxonomy to characterize movement patterns from the perspective of conceptual primitives. We then discuss examples how to formally ground conceptual primitives in current frameworks of topology and how topological formalisms might benefit from adopting a perspective of conceptual primitives.

Theoretical underpinning: Conceptual primitives and the relation between spatial representation and conceptual structure

What does it mean to be a (cognitive) conceptual primitive? Due to the flexible nature of the human mind, this question on conceptual primitives may have more than one answer. In general, though, we follow the approach outlined by Mandler (Mandler, 1992), who states that conceptual primitives are not to be interpreted as primitives in an atomic sense (i.e., their descriptions may be divided or compartmentalized further). Rather, they are foundational; foundational to the cognitive system. They are what allow us to create concepts about the things we encounter in our environments, which in turn allow us to communicate events as we meaningfully segment the potentially continuous stream of information into these foundational concepts. An example would be the understanding of direction changes of moving agents whether in constraining networks (such as streets) or differently structures spaces (e.g., deserts). Instead of using 360 degrees (or even decimals) we can expect that a cognitive system uses a much smaller number of qualitative equivalence classes. The following aspects should be kept in mind:

• The number of equivalence classes is not cast in stone, that is, there can be flexibility regarding the level of granularity. • Equivalent classes do not segmenting space homogenously. It is sensible to assume that they differ in size and extent. This fact is reflected in behavioral research, linguistic expressions, and formal characterizations. • There may even be a modality specific difference, for example, comparing the linguistic and non-linguistic conceptualization of direction information. To which extent this can be modeled is an open question.

Toward a taxonomy for single agent movement patterns from a chorematic perspective

We present a first draft of a movement patterns taxonomy for single agents/entities. This taxonomy is organized according to critical cognitive concepts of movement patterns. It is a work in progress and meant as a guideline for structuring ideas and discussions from a cognitive perspective2 .

The first level in the taxonomy (see Figure 1) distinguishes whether the trajectory (also referred to as path or trace) of a moving agent is of interest, or, whether the spatial relations bet the environm trajectory its We will focu seems to be characteristic [417][418] of primitive shapes. The third and final approach, which used term writing in combination with a formal grammar, has been adopted in the wayfinding choreme theory. Wayfinding choremes are conceptual primitives (Brunet, 1987;Klippel, Tappe, Kulik, & Lee, 2005) used to model route knowledge. Instead of focusing on all aspects of a complete route (i.e., the complete trajectory of a moving agent), critical points along the route are used to characterize routes with a limited set of direction primitives, called wayfinding choremes (Klippel et al., 2005). Wayfinding choremes can be combined into more complex sequences of movement patterns to reflect cognitive conceptualizations such as follow the road to the dead end and turn right. This last approach will be used as a basis for developing a cognitively unifying framework for the characterization of movement patterns. All of these approaches are well developed and allow for characterizing trajectories. The wayfinding choreme theory is particularly useful because these characterizations can include important contextual factors, such as landmarks3 .

Another way to conceptualize movement patterns is by characterizing changing spatial relations between the moving agent/entity and other features or entities in the environment (see Figure 1). One such related distinction (and the one that we will explore in greater depth here) is attributed to the importance of topology. We distinguish movement patterns that involve a change in the topological relationship between the moving agent/entity and other entities and those where the topological relations stay constant. The next distinction in the taxonomy important for movement patterns that involve topological changes is the spatial dimensionality of the moving object-point versus spatially extended entity. This in itself is an interesting question from a cognitive conceptual perspective and dependent on the granularity applied to characterize and interpret a movement pattern. It is important to note that no physical entity is a point in a formal sense. However, to characterize a movement pattern as a trajectory, we do have to assume that the moving entity is indeed a point. We will discuss the implications of this distinction in the light of recent research on directed lines, called Dlines (Kurata, 2008;Kurata & Egenhofer, 2008) and the conceptualization of movement patterns at the geographic scale (Klippel & Li, 2009).

It is important to note that the role that conceptual neighborhood graphs (Freksa, 1992a;Egenhofer & Al-Taha, 1992) play in movement pattern characterizations differs according to the dimensionality of the moving entity. As a reminder, conceptual neighborhood graphs are a form of organizing sets of topological relations (see left side of Figure 2) in a way that most similar topological relations (there may be differences in defining similarity that we will ignore here) become conceptual neighbors, that is, they are directly connected by edges in the conceptual neighborhood graph.

If we conceptualize the moving agent as a spatially extended entity, we can use the conceptual neighborhood graph that is established on the basis of topological relations distinguished by the region connection calculus (e.g., Randell, Cui, & Cohn, 1992) or by different levels of granularity in Egenhofer's intersection models (Egenhofer & Franzosa, 1991). To model a movement pattern in this way, the conceptual primitives (the movement choremes,

) are the topological equivalence classes assuming that the agent is moving. Extending our previous research on wayfinding choremes to , we can, for example, differentiate eight topological relations that constitute the conceptual neighborhood graph in Figure 2 4 (DC -disconnected, EC -externally connected, PO -partial overlap , TPP -tangential proper part, NTPP -non-tangential proper part, and two inverse relations for TPP and NTPP, TPPi and NTPPi, respectively). It is possible to define a formal language based on these relations. We will not go into detail here, but we will provide some examples (see also Egenhofer and Al-Taha, 1992):

• Consider the moving entity is a hurricane and our reference entity is a peninsula (for the moment we ignore the fact that the hurricane is 'in' the ocean while it is approaching the peninsula, see Stewart Hornsby & Cole, 2007). Critical stages of the hurricane's movement pattern are associated with changes in the topological relation between the hurricane and the peninsula. • A hurricane that never makes landfall has a very short conceptual path. It exists only of the relation DC ( ) • For a hurricane that does make landfall and, let's say, dies over land, the conceptual path gets longer:

• For hurricanes that completely cross the peninsula (assuming the hurricane is smaller than the peninsula), the path through the conceptual neighborhood graph looks like this:

It is important to keep in mind that the eight primitives (MCs) can be used as a basic characterization -like letters in the alphabet -and that combinations of these primitives can be used to characterize more complex movement patterns. An example would be hurricane Ivan in 2004, which crossed the Southwest of the United States, went back out into the Atlantic and came back to cross the southern tip of Florida.

Another important aspect is to make a connection to externalizations, such as linguistics or graphics. To model, for example, the semantics of the verb cross or the preposition across (as in the hurricane crossed / went across the peninsula), we can apply the combination of term rewriting rules and a formal grammar (MCGmovement choreme grammar) to identify (i.e., rewrite) movement characterization. For example, the complete conceptual path of hurricane Ivan (as briefly characterized in the preceding paragraph) would look like this: Within this string of movement concepts, we can identify sub-strings that are meaningful in their own right (e.g., the sub-string where the hurricane makes landfall or where its trajectory/path crosses the mainland for the first time). We have not specified a full grammar on the basis of movement concepts (MCG) yet, but a valid expression for the concept of across would look like this: This valid expression in the MCG can be used as a basis for defining term rewriting rules to process strings of movement concepts into meaningful parts (Klippel et al., 2005, see also Galton, 1993;Dershowitz, 1993).

One critical question we need to answer is: what constitutes valid expressions in this formal language. This, of course, is not trivial, as many combinations would be possible from a formal perspective (as we will see in the next section). The first constraint comes from the organization of the topological relations as conceptual neighbors into the conceptual neighborhood graph. Obviously, not all topological relations can be neighbors with all other topological relations; they are constrained through the movement patterns of the agent/entity. Consider the example of the hurricane crossing the peninsula. Assuming that there are no holes in the conceptualization of the hurricane (i.e., ignoring the eye of the hurricane), its movement can be conceptualized as translation which results in the path given above (e.g., . These constraints ensure the validity of the sequence of topological relations. The hurricane cannot jump from to without going through . While there may be other scenarios where jumping is possible (e.g., a tornado), for the moment we will stay, for now, in this more constrained domain (see Worboys & Duckham, 2006 for a discussion of more flexible options).

An additional observation is important to make: Humans have a tendency to pay particular attention to the ending relation of a movement patterns (or events). This phenomenon is referred to as the endpoint hypothesis (Regier & Zheng, 2007). To be able to identify potential segments, that is, sequences of MC (both in the conceptual path as well as in the actual trajectory) on cognitive grounds, the question we have to answer is which topological relations are good candidates for defining cognitively salient ending relations and which ones are not. In other words, while the movement choremes and the order of movement choremes are constrained by the conceptual neighborhood graph, the endings (or beginnings, see below) could be arbitrary and potentially all MC could be equally salient from a formal perspective. While equal salience of topological relations has been used in recent approaches on similarity measures (e.g., Schwering & Kuhn, to appear), our own research (Klippel & Li, 2009), results by Shariff et al. (1998), behavioral assessments of Allen's temporal calculus (Lu & Harter, 2006), and various formal approaches (e.g., Camara & Jungert, 2007) propose that topological (or corresponding temporal) relations do not have the same cognitive saliency 5 . For example, while it would be possible to allow for the following combination of MCs:

, it is questionable whether this should constitute a salient term in the MCG (the grammar of movement concepts).

Figure 3. A dendrogram that shows the result of a cluster analysis (Ward's method). Participants saw animated icons similar to the ones in Figure 2. Their task was to create groups out of these icons that they considered as being similar to each other. The movement patterns that the icons depicted were distinguished on the basis of topologically defined ending relations. The difference between DC1 and DC2, for example, is that DC1 are hurricanes that never made landfall while DC2 characterizes hurricanes that completely cross the peninsula (see Figure 2). The results show clearly that not all topologically defined ending relations are equally salient from a cognitive conceptual perspective (from Klippel & Li, 2009).

Figure 3 shows the result of an experiment on the salience of topologically defined ending relations. We used animated hurricane icons as shown in Figure 2. It is clear, that certain topological relations form conceptual groups and are more similar to each other than to members of other groups. One striking result is that concepts that exhibit some kind of overlap (PO, TPP, NTPP) are separated from those that do not overlap (DC, EC). This conceptual differentiation is also reflected in a linguistic analysis of labels that participants provided for these groups (see Klippel & Li, 2009 for details) and strikingly similar to an analysis by Lu and Harter (2006) on the cognitive saliency of Allen's intervals (Allen, 1993).

This is an important question if we want to break down a characterization of a movement pattern into meaningful subparts. While research has been conducted on these questions, we still need more behavioral validation to guide the way we assign saliency to the primitives of the MCG and what role they might play in defining meaningful sub-events. However, the combination of the MCG and term rewriting offers manifold possibilities to account for differently salient combinations. Comparable to the case of wayfinding choremes and their processing, the order in which term rewriting rules are applied allows for specifying more salient (rules that are applied first) and less salient (rules that are applied last) combinations.

So far we have talked only about the case in which both the moving agent/entity and the reference entity are spatially extended. Now we are turning to the case in which the moving entity can be conceptualized as a point while the reference entity (ground) is considered to be spatially extended. In this case we can build on the well explored framework of the 9-intersection model (Egenhofer & Mark, 1995) that allows for specifying the relationship between a line, which in this case would be the trajectory, and a spatially extended entity. A more elaborate framework is proposed by Kurata and Egenhofer (Kurata & Egenhofer, 2007) in which a non-directed line is replaced by a directed line (Dline), a model referred to as 9+ intersection. In this case, the number of possible relations between the line and the region increases from 19 to 26. The 9+ intersection approach is intended to model human concepts of motion and is the most elaborate topological approach to characterize single agent movement patterns. We briefly explore here how this approach could be realized within our framework of MC and the MCG (see also Kurata & Egenhofer, in press). We start by characterizing only three basic relations between the moving agent/entity and the spatially extended entity. The agent/entity can be either in the exterior (EX), on the boundary (BO), or in the interior (IN). Additionally, we need to distinguish whether the movement 'on' the boundary occurs only in one point, such as the start and end point, or whether it is an extended movement along the boundary. In the case where the movement on the boundary is taking place only in a single point we write (bo) instead of (BO). Please note that this distinction is also useful in characterizing different forms of crossing from the interior to the exterior. While this information is beyond a purely topological characterization, it has received some attention in modeling relationships between two lines (Xu, 2007). We will not discuss this aspect here in detail. We applied our characterization of movement patterns based on movement choremes to the examples of the 26 Dline relations we found in Kurata and Egenhofer's work (Kurata & Egenhofer, in press, see Figure 4). A movement pattern corresponding to an agent crossing the spatially extended entity would correspond to the following sequence:

To further demonstrate the feasibility of our approach based on only 4 conceptual movement primitives (in case of conceptualizing the moving agent/entity as a point), we show in Figure 4 how all 26 Dline relations could be characterized on the basis of MC. Once the grammatical foundations are laid, further processing could be applied. The combination could be defined as a valid expression in the MCG and could be simplified to a concept that could be referred to as 'enter'

(see also Mark & Egenhofer; Kurata & Egenhofer, in press).

These are just examples of how a characterization of movement patterns on the basis of movement choremes (that is, conceptual movement primitives) could be established. We will provide an outlook of ongoing work in the next Section. Please note that we modeled the relations given in the original icons by Kurata and Egenhofer (Kurata & Egenhofer, in press). To this end we distinguished between movement patterns on the boundary that occur only in one point (start, end, and crossing) and movement patterns that are extendedly taking place on the boundary (bo and BO, respectively). Please also note that we left out the MC and simply used the subscript to safe space. The power of this approach lies in its potential to identify meaningful substrings. For example, in case of IN-bo-EX we can summarize the movement patterns to INEX and associate a semantic (linguistic) concept with it.

Summary, conclusions and outlook

This paper presented a short overview of a developing theory for the characterization of movement patterns. The core notion of this theory are movement choremes, MC. A movement choreme is a conceptual primitive in the sense that it is foundational for the cognitive understanding of movement patterns. We are currently restricting ourselves to the characterization of movement patterns of individual entities. While MCs are primitives they unfold their full potential through grammatical rules that combine MCs into chunks (words to use a linguistic metaphor). These chunks are the basis for term rewriting rules that can be used to meaningfully segment long strings of MCs that characterize continuous movement patterns.

While we have not combined all aspects discussed such as the characterization of trajectories and the characterization of topologically changing relations between a moving agent/entity and entities in its environment, we did show that both aspect can be characterized using conceptual movement primitives. In a future step we are planning to fully specify this framework establishing a formal, conceptual language for movement patterns. One possibility of combining different aspects of movement patterns into a single notation has been discussed by Steward Hornsby and Cole (2007). We will follow their approach and we will combine a specification of shape characteristics of a trajectory with changing spatial relations. For example, using either Freeman chaining or wayfinding choremes, we could model direction changes of a hurricane even if, for example, topological relations do not change. We would need to specify a direction model for example cardinal directions for the geographic scale. Additionally we need a spatial unit that would allow us to specify individual steps. A hurricane going West for a while and then turning North toward the main land could be specified as:

Just like before, we could specify valid expression in the MCG that would allow us to chunk a sequence of . This valid expression (and others) could be used to process long strings of MCs.

The other aspect we left out of the specification here is the whole area of changing spatial relations between a moving agent/entity and entities in the environment that do not involve changing topological relations. These changes could be specified by using ordering information (Schlieder, 1995) or other qualitative specification of spatial relations such as the double cross calculus (Freksa, 1992b). The number of existing calculi is large and it may be necessary to use different calculi for different spatial environments and purposes.

One main aspect though in further specifying the MCG is the behavioral validation and the grounding of formal characterization on a cognitive assessment. For this purpose we have set up an experimental framework that will extensively assess, first, the role of topology across different domains and across different topological transformations. We consider this approach an essential step in tailoring existing formal specifications toward cognitive adequacy. Second, we will be addressing the question of different granularities and the scale dependency of conceptualizing moving entities either as points or as extended spatial entities.