Framework for Route Following

Theory of Wayfinding Choremes

The theory of wayfinding choremes contributes to the cognitively adequate characterization of routes and the visualization of route information. One central goal is the identification of primitive route elements from the perspective of cognitive science. These conceptual primitives are coined wayfinding choremes. They are defined as mental conceptualizations of primitive functional wayfinding and route direction elements. The term choreme is derived from a theory by Roger Brunet, chorematic modeling (modelisation chorematique). Choreme is a made-up word taken from the Greek term for space, chorus, and the suffix -eme. By this combination Brunet indicates his goal: the creation of a language for space.

Wayfinding choremes are abstract mental concepts that are accessible by externalizations. For this work two kinds of externalizations are pertinent: verbalization and graphicalization (sketch maps).

In the behavioral-experimental part of this work evidence for the following aspects of wayfinding choremes was found:

• Mental conceptualizations of route parts are based on behavioral patterns. This means that in the context of wayfinding and the communication of route information functional rather than structural concepts predominate.
• Wayfinding choremes are conceptual spatial primitives of routes. They can be combined to route elements of higher order.
• The chunking principles of wayfinding choremes are influenced by the structure into which a route is embedded and the existence of additional route information such as landmarks.
• There are prototypical graphical instantiations of wayfinding choremes.

The original intention of Brunet to develop a language for spatial phenomena is realized in the present work for the domain of route information from a cognitive scientific perspective. The model of wayfinding choremes, which can be understood as terminals, comprises two central parts. First, a grammatical notation is used to organize route information on the basis of wayfinding choremes that allow for the specification of chunking principles. Second, the wayfinding choremes are employed to construct maps. As wayfinding choremes originate in abstract mental concepts this approach is termed cognitive conceptual. In contrast to other approaches that can be termed bottom-up, the wayfinding choreme approach is top-down. The rationale behind this procedure is that it can be assumed that a correspondence between internal and external representations has positive effects on map-wayfinder interaction.

Main publications:
Alexander Klippel (2003). Wayfinding choremes. Conceptualizing wayfinding and route direction elements. Universität Bremen.

Alexander Klippel (2003). Wayfinding Choremes. In W. Kuhn, M.F. Worboys, S. Timpf (Eds.), Spatial Information Theory: Foundations of Geographic Information Science. Conference on Spatial Information Theory (COSIT), pp. 320-334, Lecture Notes in Computer Science. Springer, Berlin.

Alexander Klippel, Heike Tappe, Lars Kulik, Paul U. Lee (2005). Wayfinding Choremes - A Language for Modeling Conceptual Route Knowledge. In Journal of Visual Languages and Computing, 16 (4), pp. 311-329.

Alexander Klippel, Kai-Florian Richter, Stefan Hansen (2005). Wayfinding Choreme Maps. In Stephane Bres, Robert Laurini (Eds.), Visual Information and Information Systems. 8th International Conference, VISUAL 2005, pp. 94-108. Springer, Berlin.

Context-Specific Route Directions

In our research on route directions, we focus on people's conceptualization of routes and the actions necessary to (successfully) follow them. We define conceptualization to be the (process of forming a) mental representation of a route. A route is represented as a sequence of decision point / action pairs. Hence, more precisely, conceptualization is (the process of forming a) mental representation of an (expected) decision point sequence with their accompanying actions. We have developed a process that aims at creating route directions supporting this conceptualization. The generated route directions are easy to process, i.e. they support forming and processing a representation of the corresponding route.

We coin the route directions generated by our model context-specific route directions. We use this term to emphasize that our process explicitly adapts the resulting route directions to the situation at hand, i.e. to the current action to take in the current surrounding environment. This reflects Dey's definition of context: "[...] any information that can be used to characterize the situation of an entity". For this adaptation, we need to account for the characteristics (the structure) of the environment in which route following takes place. The structure of an environment strongly influences the kind of instruction that can be given. The embedding of the route in the spatial structure surrounding it, the structure of that route itself, path annotations, and landmarks that are visible along the route all contribute to this influence. Furthermore, different reference systems provide alternatives to describe necessary actions to follow a route. An analysis of routes and route directions as well as the spatial knowledge required to determine and interpret them results in a systematics of elements that may be used in route directions. Based on this systematics, we developed and implemented GUARD, a process for the generation of context-specific route directions. GUARD stands for Generation of Unambiguous, Adapted Route Directions. It consists of four steps: in an initial step, every possible description of the action to be performed at each decision point is generated. These descriptions are represented in a relational statement termed abstract turn instruction. The next step combines abstract turn instructions of consecutive decision points into a single instruction, performing so called spatial chunking. As this initial chunking is simply syntax based, in the next step the generated chunks are checked against cognitive and representation-theoretic principles defining valid chunks. Finally, the fourth step generates the route directions in an optimization process. The combination of chunks producing the best route directions is determined. 'Best' here depends on the chosen optimization criterion.

GUARD is flexible with respect to the applied route direction principles. It is possible to combine different principles of chunking with different optimziation criteria, this way testing their appropriateness and performance.

Main publications:
Kai-Florian Richter (2007). A Uniform Handling of Different Landmark Types in Route Directions. In Stephan Winter, Matt Duckham, Lars Kulik, Benjamin Kuipers (Eds.), Stephan Winter, Matt Duckham, Lars Kulik, Benjamin Kuipers Spatial Information Theory. LNCS 4736, pp. 373-389. Springer, Berlin. International Conference COSIT

Kai-Florian Richter, Alexander Klippel (2007). Before or After: Prepositions in Spatially Constrained Systems. Thomas Barkowsky, Markus Knauff, Gérard Ligozat, Daniel R. Montello Spatial Cognition V - Reasoning, Action, Interaction. LNAI 4387, pp. 453-469. Springer, Berlin.

Kai-Florian Richter, Alexander Klippel (2005). A Model for Context-Specific Route Directions. In Christian Freksa, Markus Knauff, Bernd Krieg-Brückner, Bernhard Nebel, Thomas Barkowsky (Eds.), Spatial Cognition IV. Reasoning, Action, Interaction: International Conference Spatial Cognition 2004, pp. 58-78. Springer, Berlin.

Kai-Florian Richter, Alexander Klippel, Christian Freksa (2004). Shortest, Fastest, - but what Next? A Different Approach to Route Directions. In Martin Raubal, Adam Sliwinski, Werner Kuhn (Eds.), Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung. Beiträge zu den Münsteraner GI-Tagen 2004, pp. 205-217, IfGIprints. Institut für Geoinformatik, Münster.

Cognitive OpenLS

Research on wayfinding and route directions in psychology, linguistics, and cognitive science provides ample evidence for principles of good route directions. By analyzing human route directions those principles can be extracted that are most successful, in opposition to simply mimic human route direction. In this report we combine existing approaches and our own research. We identified the following three principles that we consider essential for cognitively ergonomic route directions:

• Making direction concepts more precise:
  Depending on the spatial structure of a decision point, describing the action to be performed may differ. For example, a change in direction usually described as "veer right" might turn to "fork right" given that the road ahead forks to the left and right (i.e. there are two possible branches to take, one heading off to the left, one to the right at approximately 45 degrees).
• References to landmarks:
  Landmarks are crucial for good route directions. They are used, among others, to identify decision points, to link actions to be performed to decision points, and to provide confirmation information that the correct route is still followed.
• Subsuming route directions:
  Subsuming several directions for individual decision points into one higher order direction covering a sequence of decision points with a single instruction is the third important principle of cognitive ergonomic route directions. Examples of instructions employing this spatial chunking are "turn left at the third intersection" and "follow the river until the gas station."

These principles need to be transformed into an adequate data structure to be able to represent the required information for automatically generating cognitively ergonomic route directions. With the Navigation Service the OpenLS specification developed by the Open Geospatial Consortium offers exactly the functionality required for this purpose. This service provides a client with the data necessary to generate route directions. We developed Cognitive OpenLS, a data structure that captures these principles, which is based on the OpenLS specification. It is defined as a XML schema that reflects the principles listed above. Cognitive OpenLS encompasses our other research, especially results of the theory of wayfinding choremes and of the model for context-specific route directions.

Main publications:
Alexander Klippel, Stefan Hansen, Kai-Florian Richter, Stephan Winter (2009). Urban Granularities - A Data Structure for Cognitively Ergonomic Route Directions. In GeoInformatica (Volume 13 , Number 2, pp. 223-247).

Stefan Hansen, Kai-Florian Richter, Alexander Klippel (2006). Landmarks in OpenLS - A Data Structure for Cognitive Ergonomic Route Directions. In M. Raubal, H. Miller, A. U. Frank, M. F. Goodchild (Eds.), Geographic Information Science - Fourth International Conference, GIScience 2006, pp. 128-144. Springer, Berlin.

Stefan Hansen, Alexander Klippel, Kai-Florian Richter (2006). Cognitive OpenLS Specification. SFB/TR 8 Spatial Cognition. Technical report No. 012-10/2006.