Computations on Metric Maps in Mammals: Getting Oriented and Choosing a Multi-Destination Route

Behavioral and electrophysiological data suggest that mammals locate themselves and their goals on a cognitive map (Cheng, 1986; Collett, 1987; Collett et al. 1986; Gallistel, 1990; Georgakopoulos and Etienne, 1994; Mizumori, 1994; Morris, 1981; Muller et al. 1987; O’Keefe and Conway, 1978; Poucet, 1993; Quirk et al. 1990; Tolman et al. 1947). A cognitive map is a representation of (at least some) geometric relationships among a home site, terrain surrounding the home site, goals to be visited and the terrain surrounding those goals – a representation used for navigation. If the map includes metric information – distances and directions – then it encodes the shape of the environment. To navigate, the animal locates itself and its goals within the coordinate framework established by the map. This location enables it to set a course for a goal that it cannot currently perceive by reference to the terrain it can perceive. The map gives the direction and distance of its goal relative to what it currently perceives.

In this review, we consider a hypothesis about the construction of the map, the nature of the computation by which the animal may use its current perception of the environment to determine its position and orientation on its map, and the nature of the computation by which it chooses a distance-minimizing route when visiting several different goals in one trip.

Because an animal cannot perceive more than a part of its environment from any one vantage point, the construction of a cognitive map requires the integration of positional information derived from different views of the environment made at different times. Gallistel (1990) suggested that animals may construct a map suitable for navigational use by combining two sorts of position vectors: egocentric vectors, which specify the locations of terrain features (landmarks) in a body-centered coordinate system, and geocentric vectors, which specify the position of the animal in an earth-centered coordinate system (see Fig. 1). This hypothesis grounds the construction of a cognitive map in established computational capacities of the nervous system, because insect nervous systems, at least, have been shown to compute both sorts of position vectors (Cartwright and Collett, 1983; Cheng et al. 1987; Gallistel, 1995b; Wehner, 1992; Zeil, 1993).

The geocentric coordinate system is created by dead reckoning, which is the process of continuously updating the animal’s position by adding up successive small changes in that position (Etienne et al. 1991; Gallistel, 1990; Loomis et al. 1993; Mittelstaedt and Mittelstaedt, 1980; Müller and Wehner, 1988; Séguinot et al. 1993; Wehner and Wehner, 1986). These changes in position are displacement vectors, so the process of adding them up is equivalent to vector addition. In the limit, summing successive displacements to get net displacement is equivalent to integrating the velocity vector with respect to time to get the position vector, which is why this process is also called path integration. The position vector thus computed is geocentric, because it specifies the animal’s position in a coordinate system anchored to the point on the earth from which the animal starts an excursion. For the sake of simplicity, all dead reckoning is assumed to start from a single home base, the position of which constitutes the origin of the geocentric coordinate system. However, it is easy to modify this model of the map-construction process to accommodate multiple starting points (multiple origins for the dead reckoning of geocentric position).

Perceptual systems compute the directions and distances of landmarks from the animal (e.g. Sobel, 1990). These directions and distances constitute position vectors in an egocentric coordinate system, a coordinate system defined by reference to the animal’s body. This framework moves with the animal, but dead reckoning continuously indicates the orientation and displacement of the egocentric framework relative to the geocentric framework. Gallistel (1990) suggested that brains construct terrain maps by rotating a landmark’s egocentric position vector by the animal’s geocentric orientation (its heading) and adding the rotated vector to the animal’s geocentric position vector (Fig. 1). This computation carries the positions of notable terrain features perceived at different times and from different points of view into a common coordinate framework, which is the same framework in which the animal’s dead reckoning of its position is represented. Because dead reckoning gives the animal’s position in this same framework, the animal’s dead reckoning tells it where it is on its map.

The coordinate transformation by which a map of the animal’s environment may be constructed parallels other experimentally demonstrated coordinate transformations in the nervous system. For example, the deep layers of the superior colliculus contain circuitry that combines the eye’s angular displacement vector (its rotation) with retinal and head-centered position vectors to map visual and auditory sources into a common gaze-centered coordinate system (Sparks and Mays, 1990; Sparks and Groh, 1995). The orientation of the gaze-centered framework with respect to the other coordinate frameworks is derived by integrating eye velocity commands with respect to time, just as dead reckoning integrates the animal’s velocity with respect to time to obtain its position in the geocentric framework. The ability to compute coordinate transformations that map between different positional frameworks may be among the primitive computational capacities that make directed action possible (Gallistel, 1994, 1995a).

Dead reckoning provides moment-to-moment information about where an animal is on its cognitive map (the geocentric position vector), but the position and orientation information thus derived have a cumulative error of integration. The animal must correct its representation of its position from time to time by taking what navigators call a positional fix. This computation is the inverse of the map-construction computation. It involves comparing two differently derived egocentric position vectors. One is the egocentric position of mapped terrain features computed from the reckoned position and heading on the map. This is the computation shown graphically in Fig. 1, but with the egocentric position vector of the terrain feature taken as the unknown (rather than the geocentric position of the landmark): from the animal’s presumed (dead-reckoned) position and heading together with the mapped geocentric position of the terrain feature, the presumed egocentric vector for that feature is computed. Comparing the presumed egocentric position with the directly perceived egocentric position of the same feature gives the error in the reckoning, the displacement and rotation of the egocentric coordinate framework required to position and orient the animal correctly on its map. When one’s dead reckoning indicates that one is headed north with a headland off to the right at a distance of 1 nautical mile, but one hears waves breaking against that headland dead ahead at no more than 200 m, there is a serious error in one’s reckoning. The direct perception of the headland’s location in the egocentric framework (dead ahead 200 m) enables one to compute the correct position and orientation of the egocentric framework relative to the map’s geocentric framework.

Until recently, the contribution of dead reckoning to an animal’s sense of its position and heading was not widely recognized. Consequently, experimenters seldom studied the process of becoming reoriented in an animal that was completely dependent on taking a fix in order to know how it was oriented with respect to the mapped environment. Double integration of the angular accelerations detected by the vestibular system enables a rat to maintain some sense of its orientation with respect to its surroundings while being passively rotated in the dark at 30 revs min^-1 for up to 10 complete revolutions (Matthews et al. 1988). Thus, an animal is not ordinarily completely disoriented with respect to its environment even when it is temporarily perceptually isolated from it. When an animal has maintained its representation of how it is oriented, it interprets gross changes in the positions of landmarks in inertial space as just that; it assumes that the landmarks themselves have moved and, consequently, it does not use those landmarks to correct its sense of its own geocentric orientation and position (Biegler and Morris, 1993). To study the reorienting mechanism, it is essential to disorient the animal inertially, by steady slow rotation in the dark, and then require it to become reoriented (take a fix) in a familiar environment. Experiments of this kind with rats (Cheng, 1986; Margules and Gallistel, 1988) yielded surprising data on (1) how rats become reoriented and (2) the effect of disorientation on their disposition to use distinctive markers (goal signs) to locate sought-for objects. Similar results have recently been obtained with human toddlers as subjects (Hermer and Spelke, 1995, 1994). Also, somewhat similar results were obtained years ago with chimpanzees and macaque monkeys (Tinkelpaugh, 1932), so these findings appear to have considerable generality.

In the basic experiment, the rat or child is shown a hiding place (of food in the case of the rat, of a toy in the case of a child) in a rectangular environment. Judged only by the shape of the environment, the two ends of the rectangular box or room are indistinguishable, because rotation carries one end of a rectangle into the other. Without something to mark which end is which, there is in principle no way of telling whether such a rotation has occurred. In these experiments, however, the two ends are distinguished by salient non-geometric features – surface markings and smells. For example, in one of the rat experiments, one wall of the rectangular enclosure was white Styrofoam, while the other three were black plywood, and one end of the enclosure smelled of anise, while the other end smelled of peppermint. In some of the experiments with toddlers, one end of a small white room was covered with a large blue cloth.

After being shown the position of the food or toy in the rectangular space, the subject is inertially disoriented (by slow rotation in the absence of visual input). Vision is restored with the subject facing in a direction that varies randomly from trial to trial. The orientation that subjects compute is indicated by where they look for the food or toy. If their computation ignores the distinguishing non-geometric features and reorients them simply by reference to the shape of the enclosure, then they will be misoriented on 50 % of the trials. When thus misoriented, they will look in the rotational equivalent of the true hiding place – the place where the food or toy would be if the floor plan were rotated 180 ° about the center of the enclosure. This is what both rats and human toddlers are in fact observed to do on 50 % of the trials.

A rat that has just observed food hidden in a corner where a white Styrofoam wall and a black plywood wall converge, near a piece of cotton impregnated with anise will, after inertial disorientation, search for that food half the time in the diagonally opposite corner, where two black plywood walls converge and the nearby cotton smells of peppermint (Fig. 2A). The corner where it searches on these occasions neither looks nor smells like the corner where it observed the hidden food, but it is invariably the diagonally opposite (thus, geometrically/rotationally equivalent) corner. Similarly, a 2-year-old child who has watched a toy being hidden in a corner at the end of the room marked by the blue cloth searches half the time at the diagonally opposite corner, at the end where there is no blue cloth (Hermer and Spelke, 1995). Like the rats, the toddlers almost never search in the other two corners, which are not geometrically equivalent to the correct corner. And, again like the rats, the direction in which they face at the end of the disorientation procedure has no effect on the corner in which they search.

The tendency to search in rotationally equivalent locations disappears when subjects are not inertially disoriented between the time when they see the hiding place and the time when they must search for the object. Thus, the confusion of geometrically equivalent locations is a consequence of the reorientation process. If we hypothesize that when it is inertially disoriented and must take a fix to become reoriented, the nervous system does so by comparing the shape of the currently perceived environment with the shape of a corresponding portion of the environment represented on its map, then we predict that in a rectangular space it will be misoriented by 180 °on half the trials. On those trials, it will locate the goal in the corner diagonally opposite the correct corner. Thus, these results suggest that the vertebrate brain computes position and orientation fixes by computing the rotation and displacement required to make the shape of the currently perceived environment congruent with the corresponding portion of its cognitive map. This computation corresponds to what Gallistel (1990, chapter 3) called a global fix, a computation that relies on the overall shape of the currently perceived environment rather than on individual terrain features. The characteristics of surfaces (e.g. color, roughness) and locales (odors) play no role in this computation; the fix is based on shape and shape alone because it is an inherently geometric computation, equivalent to computing principal axes.

It should also be noted that the fact that subjects in these experiments search only in geometrically equivalent corners is strong evidence that they represent the position of the sought-for object on a Euclidean (metric) sense-preserving cognitive map, because the corners on different diagonals of a rectangle are indistinguishable in any encoding of the enclosure’s geometry that does not preserve both metric properties (wall lengths) and sense (left–right relationships) – see Gallistel, 1990, chapter 6. Thus, if the animals relied on anything less than a metric, sense-preserving map, they would search in all four corners rather than only in the correct corner and its diagonal opposite.

Becoming reoriented within a familiar environment has a strong effect on the readiness with which rats and toddlers use goal signs to find hidden objects. A goal sign is not a landmark – a fixed feature of the terrain – because it has been observed to move with the goal, or because the sign is known to be found in conjunction with the goal in many different locations. A goal sign, unlike a landmark, may be a distinctive surface color or odor, rather than a feature of the terrain. Rats and pigeons readily learn to use distinctive signs such as smells and surface colors to find food or a resting spot when these signs consistently predict its location (e.g. Cheng, 1994; M’Harzi and Jarrard, 1992; McDonald and White, 1993; Morris et al. 1986; Rudy, 1991). However, rats use goal signs to direct their search only in environments where they have remained reliably oriented. If they must become reoriented before they search, then they search at the goal’s remembered position relative to the shape of the environment, even when the remembered relationship to a goal sign is a reliably better indicator of where to search (Cheng, 1986; Margules and Gallistel, 1988).

Hermer and Spelke (1995) showed that the same is true of toddlers. They placed two triangular boxes with distinctly different surface coloration in diagonally opposite corners of a rectangular room (Fig. 2B). Their toddler subjects watched while they hid a toy in one of them. After disorientation, their subjects searched half the time in the box in the diagonally opposite corner, even though this box differed strikingly in appearance from the box in which they had just seen the toy hidden. However, if the disoriented children and the two triangular boxes were taken out of the room before the children were asked to search for the toy, then they reliably searched in the correct box. Thus, different stimuli serve different search strategies. The macroscopic shape of the environment serves a strategy based on the remembered position of the target within that shape (the object’s mapped position). Goal signs serve a strategy based on searching in or near the signs, regardless of their geocentric position. The brain does not compute the animal’s position and orientation in the environment from goal signs, except perhaps when the shape of the environment and dead reckoning both fail to provide any indication of the animal’s orientation. Disorientation strongly biases both rats and young children towards search strategies based on the target’s remembered position in the global framework. The preferred search strategy of monkeys and chimpanzees, even when they have not been inertially disoriented, is also to rely on the remembered position of the object within the room, rather than on the distinctive characteristics of the container in which it is hidden (Tinkelpaugh, 1932; Yerkes and Yerkes, 1928). An appreciation of these two very different search strategies and the different stimuli on which they rely is likely to be important in understanding the neurobiology of structures such as the hippocampus, because both positional information and sign stimuli affect the firing of units in this structure (Quirk et al. 1990; Sharp et al. 1990).

Perhaps the most common use of the cognitive map is in the choice of foraging routes. Often, these routes visit more than one destination in a single excursion. Choosing an optimal route that visits many different locations – the so-called traveling salesman problem – has been intensively studied from a computational standpoint (Lawler et al. 1990) because the number of alternatives that must be considered grows as the factorial of the number of locations to be visited.

Menzel (1973) pioneered the study of this problem in primates. He carried young chimpanzees around while he hid pieces of fruit at 18 different sites in their enclosure. When he released them, they retrieved food from as many as 18 sites on a single rapid foraging expedition. Their route bore no relationship to the one on which the experimenter had taken them and it generally appeared to minimize the distance they traveled, although Menzel did not compute optimal routes.

Recently, one of us (Cramer, 1995) has repeated this experiment, but with vervet monkeys. Individual monkeys were carried around in a holding cage while the experimenter hid grapes in selected holes in a 5 ×5 gridwork of holes covering the monkey’s 9.15 m ×9.15 m outdoor enclosure; they were then released to collect the grapes, and their route was recorded on video tape. Because the grapes were not visible, the monkeys had to rely on their memory of their locations in computing a route. The first finding was a striking species difference: the vervet monkeys never remembered more than six locations, whereas Menzel’s chimpanzees often remembered 18.

Tinkelpaugh (1932) found the same limitation in rhesus macaques. He directly contrasted the rhesus macaque’s memory span in this sort of task with that of chimpanzees and humans. The macaque could remember a maximum of six locations, while chimpanzees and humans had much larger memory spans (16 or more). This suggests the possibility that the ability to remember and work with a large number of locations at once is a shared derived trait of the apes.

The focus of Cramer’s work was to determine properties of the mechanism or algorithm that determines the monkey’s choice of a route that visits all the goals to be visited on a given expedition. How far ahead does the route-finding computation look? When at most six destinations are entertained, the nearest-neighbor algorithm, which looks only for the nearest next destination, chooses the optimal route in the majority of cases. When it fails to do so, the route it chooses is rarely more than 25 % longer than the optimal route. Also, within the confines of the roughly 9 m square enclosure where these experiments were run, the energetic costs of the few extra paces required by a non-optimal route are a negligible fraction of the animal’s hourly energy expenditure for basal metabolism alone. For both these reasons, one might have expected the vervet monkeys to use a simple algorithm, which chose the route one segment at a time, considering at each goal only where the nearest subsequent goal was. However, two experiments showed that the choice of the next segment of the monkey’s route was determined by an algorithm or mechanism that considered at least two further destinations beyond the next destination (three-step look ahead).

The first experiment used a diamond configuration (Fig. 3A). If the monkey does not intend to return to the starting vertex, the shortest route is a thunderbolt (dashed route in Fig. 3A), but if it is to return to the starting point (to get a grape placed there after it reached its first destination), then the shortest route is the diamond route (solid route in Fig. 3A). Thus, where best to go once the first destination is reached, depends on where one will go after two further visits. If one’s route terminates with the second of two further visits or goes on to some goal beyond that destination (as in Fig. 3B), then the optimal thing to do is to cross over from the first to the second of the two close vertices before going to the far vertex. On five of the seven tests on which the vervet subjects failed to return to the release point, they used the thunderbolt route (and on only one of these seven did they use an aborted diamond route). Moreover, in other experiments with randomly chosen goal locations or destinations distributed in unequal groups, several configurations happened to involve an approximate diamond at the outset, with other locations found beyond the far apex of the diamond (for example, Fig. 3B). In such cases, the subjects generally chose the thunderbolt route. However, in 20 of the 26 trials on which they returned to the release point of the diamond configuration, they used the diamond route. The diamond route was 13.63 m, while the thunderbolt route with return was 15.42 m. Despite the modest savings in distance covered (<12 %) and the negligible energetic cost of covering the additional 179 cm necessitated by the non-optimal route, the monkeys reliably selected the optimal route.

The second experiment was still simpler. The baited locations were arranged in a group of four to one side and a group of two to the other, with the subject’s starting point equidistant from the nearest location in each group (Fig. 3B). A nearest-neighbor algorithm or an algorithm that considers only one visit beyond the next visit (one-or two-step look ahead) will not reliably choose to go to the richer side first. Nor will a simple exhaustive search algorithm or any mechanism that, like a simple exhaustive search, always finds an optimal route but does not deliver anything more, because an optimal route is the same length no matter in which direction one follows it. However, the vervets invariably went to the richer side first (on 43 out of 43 tests). Their route-finding mechanism clearly considered (or was affected by) not only where they would go first but where they would go after that and where they would go after the next visit but one (three-step look ahead).

The hypothesis that animals can construct and use a cognitive map has a long and controversial history (Tolman, 1948; Wehner and Menzel, 1990). The controversy stems in some measure from the fact that such an ability would seem to be evidence that the more advanced nervous systems are symbol-processing devices (Gallistel, 1995b). The cognitive map hypothesis presupposes that the nervous system contains such things as position vectors and that it can perform basic computations with these vectors, such as rotating them and adding them. In recent years, the preponderance of opinion has swung to the map hypothesis, at least for mammals, in part because of the discovery of neurons in the hippocampus that fire when the animal is in a given place regardless of its field of view and even in complete darkness (Mizumori, 1994; Muller et al. 1994; Quirk et al. 1990; Sharp et al. 1990). The more interesting questions now concern the kinds of computations that animals may perform using the geocentric position vectors they have stored (that is, their map). Recent experiments on how they become oriented and how they choose routes have revealed unexpected and surprisingly sophisticated computations.

A.E.C. was supported by a National Science Foundation Graduate Fellowship and University of California Office of the President Dissertation Year Fellowship. The work with vervet monkeys was conducted at the Non-Human Primate Research Laboratory, supported in part by The Research Service of the Veterans Administration Medical Center, Sepulveda, and by Grant DE-FC03-87-ER60615 from the Department of Energy.