Use and interaction of navigation strategies in regionalized environments

https://doi.org/10.1016/j.jenvp.2004.09.006Get rights and content

Abstract

In this work, three experiments are reported that studied the use and interaction of navigation strategies both during the learning of a virtual environment and during subsequent route planning tasks. Special interest concerned the role of regions within the environments. Results from Experiment 1 suggest that the regions are perceived and encoded in spatial memory very early during the process of learning an environment. During navigation such regional information could be used to overcome missing or imprecise spatial information on the detailed level. Experiments 2 and 3 studied the use and interaction of route planning strategies that are applied after an environment has been learned. Results suggest (i) that human route planning takes into account region-connectivity and is not based on place-connectivity alone, (ii) that route planning takes into account the distribution of multiple target locations and (iii) that route planning takes into account the complexity of alternative paths.

Introduction

“Traditionally, the path selection problem has been ignored or assumed to be the result of minimizing procedures such as selecting the shortest path, the quickest path or the least costly path.” This statement by Golledge (1995) is still true today. Very little work has been attributed to the question which mechanisms, strategies and heuristics are applied during route planning that allow to derive the shortest path, the quickest path or the least costly path from spatial memory. In this work three navigation experiments in virtual environments are reported that studied the use and the interaction of different navigation strategies that are applied during the exploration and learning of an environment and during subsequent route planning tasks.

Wayfinding and navigation behavior have been mainly used as a tool to study the underlying representation of space. Aginsky, Harris, Rensink, and Beusmans (1997), e.g. monitored subjects spatial knowledge of a virtual environment during the learning of a route through that environment. They found that only relevant spatial information, i.e. information in the vicinity of choice points, was retained. In navigation experiments in virtual reality, Gillner and Mallot (1998) showed that subjects store local elements (i.e. places or views associated with movement instructions and expected outcomes) in spatial memory. These local elements did not have to be globally consistent, suggesting that representations of space are graph-like structures rather than map-like structures (see Schölkopf & Mallot, 1995). Supporting evidence for graph-like representations of space also comes from navigation experiments in virtual environments, containing both global and local landmark information (Steck & Mallot, 2000). Global landmarks were distant landmarks such as towers and mountains that were visible from a large area, thus providing a global reference frame. Local landmarks, on the other hand, were objects at decision points and were visible only from a small distance. After learning the virtual environment, the global and local landmark information was set in conflict by rotating the global landmarks while keeping local landmarks stable. Surprisingly, subjects did not perceive nor report this conflict. Moreover, subjects who relied on global landmark information in the conflict situation showed good wayfinding performance if only local landmark information was provided and vice versa. Geographical slant has been shown to improve navigation and wayfinding performance as well as directional judgments in a virtual environment setup, suggesting that slant or height information is integrated in spatial memory (Steck, Mochnatzki, & Mallot, 2003; Restat, Steck, Mochnatzki, & Mallot, 2004).

Navigation and wayfinding procedures have also been used to evaluate the navigability of architectural spaces. O’Neill (1992) demonstrated that wayfinding performance decreased with increasing plan complexity (for measures of floor plan complexity see O’Neill, 1991; Raubal & Egenhofer, 1998). Furthermore, Werner and Long (2003) have shown that the misalignment of local reference systems impairs the user's ability to integrate spatial information across multiple places, suggesting that reference axes should be consistent throughout a building in order to support navigability. Janzen, Herrmann, Katz, and Schweizer (2000) investigated the influence of oblique angled intersections within an environment on wayfinding performance. When navigating arrow-fork intersections, subjects error rate depended on which branch they entered the intersection (see also Janzen, Schade, Katz, & Herrmann, 2001).

Numerous navigation experiments studied gender differences in spatial cognition, which are supposed to be one of the most reliable of all cognitive gender differences in humans (Moffat, Hampson, & Hatzipentalis, 1998). Astur, Ortiz, and Sutherland (1998), e.g. have developed a virtual version of the Morris water maze task for humans. Subjects were placed in a virtual pool that was surrounded by distal cues and were instructed to escape from the water as quickly as possible by navigating towards a hidden platform. Results revealed a gender effect: males swam for shorter time to find the platform, and after removing the platform males spent more time in the quadrant where the platform has previously been. While this study suggested a gender difference favoring males in spatial performance, other studies have reported the use of different aspects of the environment (e.g. global and local landmarks) and the use of different orientation and navigation strategies between subjects (e.g. Lawton (1994), Lawton (1996); Sandstrom, Kaufman, & Huettel, 1998; Lawton & Kallai, 2002), rather than fundamental performance differences. Basically, these studies state that male subjects rely more on global landmark configurations or global reference systems, while female subjects tend to rely on local landmark information and route information. In a neuroimaging study, Grön, Wunderlich, Spitzer, Tomczak, and Riepe (2000) have reported gender differences in brain activation as subjects searched their way out of a virtual maze. While there was as great overlap of brain area activation between genders, including the right hippocampus, Grön et al. report specific activation of the left hippocampus in males, and specific activation of right parietal and right prefrontal cortex for females.

Only few navigation experiments aimed at understanding the mechanisms and strategies that underlie route planning and navigation behavior. Gärling and Gärling (1988), e.g. investigated pedestrian shopping behavior with respect to distance minimization in multi-stop shopping routes. Most shoppers that minimized the distance of their shopping routes, first chose the location farthest away, most probably to minimize effort to carry bought goods, and then minimized distances locally between shopping locations (see also Gärling, Säisä, Böök, & Lindberg, 1986). This so called locally minimizing-distance (LMD) heuristics, also often referred to as the nearest neighbor (NN) heuristic in artificial intelligence approaches (e.g. Golden, Bodin, Doyle, & Stewart, 1980), is known to generally lead to optimal or near optimal solutions in traveling salesman problems of small sizes.

Insights into navigation strategies also come from the animal literature. For example, Gallistel and Cramer (1996) studied vervet monkeys’ ability to navigate the shortest route connecting multiple locations, by arranging baited locations in a group of four to one side and a group of two to the other side (see Fig. 1a). Note that the nearest baited location of both food patches were equidistant from the starting point. An algorithm like the NN predicts that monkeys choose to first visit both of the food patches equally often. However, the vervet monkeys first visited the richer food patch in all trials. Below we refer to this strategy as the cluster-strategy. In a second experiment Gallistel and Cramer (1996) arranged baited locations in a diamond shape. If the monkeys intended to return to the starting position, because it was baited after the monkey left it, the monkeys generally chose the shortest route in this traveling salesman task (see solid route in Fig. 1b). Here an NN strategy would predict that the monkeys followed a different nonoptimal route (see dashed route in Fig. 1b) for the first steps. Gallistel and Cramer (1996) concluded that the vervet monkeys’ route planning not only takes the first step into account (as predicted by the NN), but is indeed planning three steps ahead (see also Menzel, 1973).

Christenfeld (1995) studied human subjects’ preference to choose a certain route from a series of almost identical routes. In all conditions (route choice from artificial maps, from street maps or in real-world environments) subjects had the choice between a number of routes that were identical with respect to metric length, target point and the number of turns. The only difference between the routes was when along the route subjects had to make a turn. In all conditions, subjects delayed the turning decision as long as possible (see Fig. 1c). Christenfeld speculated that this effect resulted from subjects tendency to minimize mental effort, that is to say, subjects did not worry about where to turn until they had to turn. This strategy offers a possible explanation for the fact that people's route choices are often asymmetric; i.e. subjects choose different routes from A to B than from B to A (e.g. Stern & Leiser, 1988). On the basis of results from route planning from maps, Bailenson, Shum, & Uttal (1998), Bailenson, Shum, & Uttal (2000) extended Christenfeld's findings and suggested that subjects, when choosing between alternative routes from maps, prefer routes with the longest initial straight segment (Initial segment strategy—ISS), in order to leave the starting region as fast as possible (Route climbing principle).

In this work, route planning is defined as the process of selecting and navigating a path from a given starting location to a single or to multiple target locations that are beyond the sensory horizon of the agent. The spatial information needed to plan the route therefore has to be retrieved from spatial memory.

Human spatial memory has a certain property, namely its hierarchical organization that lately has been shown to influence route planning and navigation behavior (Wiener & Mallot, 2003). Hierarchical theories of spatial representations state that spatial memory contains nested levels of detail. Such a memory structure can be expressed in graph like representations of space in which locations are grouped together and form super-ordinate nodes. For example, places are grouped together and form regions. Spatial relations among regions can then be represented at the region level. Supporting evidence for the hierarchical theories came from distance- and directional-judgments, spatial priming, and memory recall procedures. Stevens and Coupe (1978), e.g. have shown that directional judgments between locations are distorted towards the spatial relations of the states they reside in. Wilton (1979) has shown faster directional judgments between locations that reside in different regions, as compared to locations that reside in the same region. In a speeded recognition task McNamara (1986) revealed stronger priming, that is faster recognition times, when prime and target were objects from the same region of a previously learned layout than when prime and target were objects from different region of the same layout (see also McNamara, Ratcliff, & McKoon, 1984; McNamara & LeSueur, 1989; McNamara, Hardy, & Hirtle, 1989). Hirtle and Jonides (1985) have shown that subjects underestimated relative distances between landmarks from the same subjective region, while they overestimated absolute distances between landmarks from different subjective regions. Among others, these results have led to the hierarchical theories of spatial representations.

Wiener and Mallot (2003) studied the influence of regions within an environment on human route planning behavior. In a virtual reality setup subjects learned environments that were divided into different regions by active navigation. After learning the environments subjects were asked to either find the shortest route to a single target-place or to find the shortest route for visiting three places within the environment. Subjects minimized the number of region boundaries they crossed during navigation and subjects preferred paths that allowed for fastest access to the region containing the target. These findings suggest that human route planning takes into account region-connectivity and is not based on place-connectivity alone. Wiener and Mallot proposed the fine-to-coarse planning heuristic, a cognitive model that describes this simultaneous use of spatial information at different levels of detail during route planning. The core of this fine-to-coarse heuristic is the ‘focal representation’ that is generated from the hierarchical reference memory of space by using fine space information (place-connectivity) exclusively for the current location and the close surrounding and coarse space information (regions-connectivity) exclusively for distant locations. In this focal representation, the shortest path to the next target (target-place or target-region) is planned. Planning a route in such a focal representation results in a detailed plan for the close surrounding, allowing for immediate movement decisions, while only coarse spatial information is available for distant locations. The route plan therefore has to be refined during navigation. By updating the focal representation and by re-planning the route, a detailed plan for the next movement decisions is available at all times along the route. By using spatial information at different levels of detail for close and distant location not only memory load is reduced, but also the complexity of the planning task itself. Additionally memory load for the route plan is minimized, since steps are planned only one at a time.

Other route planning schemes that make use of hierarchical representations of space have been suggested in computational models of spatial cognition. Chown, Kaplan, and Kortenkamp (1995), e.g. suggested that higher abstraction levels of the representation are used to first generate coarse route plans. Such plans are simple, easy to compute, and rule out a large number of suboptimal paths. However, in order to allow for actual movement decision at choice points these plans have to be broken down and fine route plans have to be generated. Usually, such planning schemes, in which first a coarse route plan is generated that is then successively refined, are referred to as coarse-to-fine planning schemes.

This work aims at further investigating mechanisms and strategies that underlie human route planning by the means of navigation experiments in virtual environments. In the first part of this work one experiment is presented that studied the formation of hierarchical components, i.e. regional information, in human spatial memory. It will be argued that regional information is formed early during the cognitive mapping process and that this information is used in simple search tasks. In the second part, two experiments are presented that studied navigation- and route planning-strategies employed after learning a regionalized environment. The focus of this part concerns the use and interaction of three navigation strategies: (i) it will be tested whether the cluster-strategy (explained above, Gallistel & Cramer, 1996) is also used by human navigators, (ii) the use of the fine-to-coarse planning heuristic is further investigated (Wiener & Mallot, 2003), (iii) the influence of the complexity of alternative paths on human route planning and navigation behavior is studied. It is proposed that human navigators plan their routes in order to minimize the complexity of the planned path; this strategy is referred to as the least-decision-load strategy. It will be argued that all three navigation strategies are applied by human navigators, and that subjects’ path choice behavior in these experiments can be predicted by a simple linear combination of the three navigation strategies.

Section snippets

General material and methods

All experiments presented in this work were conducted using virtual reality technology. Subjects actively navigated through virtual environments in the ego perspective and executed a series of navigation tasks. The use of virtual reality technology for navigation experiments has two major advantages as compared to real world experiments. First, it allows for exact control of the visual stimuli presented and second, one can carry out the experiments in environments created to exactly match the

Purpose

As stated in the introduction, there is convincing evidence that human spatial memory is hierarchically structured. Here a navigation experiment is reported that studied the perception and encoding of environmental regions, i.e. the formation of hierarchical components in spatial memory, during the learning of an environment. The experiment was motivated by the assumption that regional knowledge that arose early during the process of learning an environment, provided additional information

Purpose

In Experiment 1, the formation of hierarchical components, i.e. regional information, in human spatial memory was studied by simple search tasks in a regionalized environment. Here the use and interaction of different navigation- and route planning strategies that are applied after learning a regionalized environment are studied. It is proposed that in complex route planning tasks with multiple targets, comparable to shopping routes, different navigation- and route planning-strategies interact.

Purpose

In Experiment 2, a systematic effect in subjects’ navigation behavior for routes of type C was revealed. Two navigation strategies have been described that could have accounted for the observed effect. This experiment is a modification of Experiment 2. By changing the shape of the islands while keeping the absolute positions of the start-and target places of the test routes constant, the influence of the fine-to-coarse planning heuristic and the least-decision-load-strategy could be studied

Conclusions

In this work, 3 navigation experiments were presented that investigated the use of navigation strategies both during the learning of an environment (Experiment 1) and during subsequent route planning tasks (Experiments 2 and 3). Special interest in all of the experiments concerned the role of environmental regions for human navigation.

The results of Experiment 1 suggest that environmental regions were perceived and encoded very early during the process of learning an environment. This result is

Acknowledgements

This study was supported by the DFG (Deutsche Forschungsgemeinschaft)—MA 1038/9-1.

References (39)

  • H. van Veen et al.

    Navigating through a virtual cityusing virtual reality technology to study human action and perception

    Future Generation Computer Systems

    (1998)
  • J.N. Bailenson et al.

    The initial segment strategya heuristic for route selection

    Memory & Cognition

    (2000)
  • E. Chown et al.

    Prototypes, location and associative networks (plan)towards a unified theory of cognitive mapping

    Journal of Cognitive Science

    (1995)
  • N. Christenfeld

    Choices from identical options

    Psychological Science

    (1995)
  • C. Gallistel et al.

    Computations on metric maps in mammalsgetting oriented and choosing a multi-destination

    Journal of Experimental Biology

    (1996)
  • T. Gärling et al.

    Distance minimization in downtown pedestrian shopping

    Environment and Planning A

    (1988)
  • S. Gillner et al.

    Navigation and acquisition of spatial knowledge in a virtual maze

    Journal of Cognitive Neuroscience

    (1998)
  • B. Golden et al.

    Approximate traveling salesman algorithms

    Operations Research

    (1980)
  • R. Golledge

    Path selection and route preference in human navigationa progress report

  • Cited by (0)

    View full text