Exploration and Navigation Using
Hierarchical Cognitive Maps
Nestor Schmajuk & Horatiu Voicu
University & University of Memphis
We describe a spatial
navigation model that uses a hierarchical representation of space.
The model is able to explore exhaustively large environments and to
plan paths between distant places, even though it uses a working
memory with a limited capacity. By using a hierarchical structure,
an agent with a limited working memory capacity has (a) a comparable
performance to that of an agent with no working memory limitations,
(b) a reduced number of connection values and (c) a shorter decision
time. The model describes many properties of hierarchical spatial
behavior in humans and animals. Potentially, the approach can also
be applied to the design of robots able to navigate in large
Even if during a
purported trip from a house in one city in one continent to an
office in a different city in another continent we need to
traverse a large number of roads and streets, it is impossible
to keep all the locations simultaneously in working memory (WM).
Just looking at a map of the East Coast of the United States
with street resolution would be a daunting task. Therefore, the
trip should be planned first at a high level that tell us which
continents are to be examined, then at an intermediate level
showing what cities are to be called upon (road maps), and
finally at a low level that specifies which streets to take
(street maps). In all cases, it is possible that only a part of
each type of map can be processed at one time.
From a psychological
perspective, the problem is to explain how navigation is
accomplished by humans or animals in a large environment, i.e., one
that contains a large number of places. From a robotics
perspective, the question is how to build a robot that navigates in
such large environments. It has been suggested (McNamara, Hardy, & Hirtle, 1989) that humans solve the problem by building
a hierarchical cognitive
map that contains
multiple levels representing the same large environment at
different resolutions. In contrast, autonomous robots have
difficulty navigating in large environments because path
planning algorithms for large environments are slow for real
time applications (Nehmzow, 1995).
In this paper, we
introduce a neural network model of spatial navigation that
incorporates a hierarchical
cognitive map. First, we analyze the benefits of using
hierarchical spatial representations. Then, we describe the
model and present computer simulations that illustrate how it
builds and uses the hierarchical map. Finally, we discuss how
the model describes human and animal experimental data and
compare it to other models.
The need for hierarchical maps.
Voicu and Schmajuk (2002) described a model of spatial
navigation that uses a topological representation of the
environment structured as a grid (see Figure 1). The cells
of the grid represent unique places that the agent can
identify and are approximately the size of the agent.
Although cells in the grid are assumed to be square, any
shape that preserves the continuity of space can be used.
The location of the agent in the grid is determined by a
localization system which, by making use of the distance to
cues as coded by their visual angles (Schmajuk, 1990;
Zipser, 1985), determines the
agent's location in space. The model assumes that all cells
on the grid representing adjacent places are connected even
before the agent enters and explores the environment, i.e.,
it assumes the continuity of space.
The model shown in Figure 2 includes
a goal-seeking system with goals set by a motivational
system, a cognitive system that has the role of a long-term
memory and a WM that has the role of a short-term memory
(Atkinson & Shiffrin, 1968).
While the cognitive map represents the connectivity between
places, the connectivity between places and goals, and the
connectivity between goals and places, the WM is used for
path planning once the relevant information from the
cognitive maps has been stored in it. The information
stored in WM is used by the goal-seeking system to produce
motor action upon the environment. The model also includes a
localization system that tells where in the environment the
agent is located and a control system that has the role of
supervising the flow of information between the components
of the model. The control system can be viewed as an
executive system (Baddeley, 1974, 1986) that
allocates processing resources to different slave systems.
guides the exploration of an unknown environment by assuming
that, as suggested by Berlyne (1950), all unexamined places on
the grid are goals for the motivational system driven by
curiosity. In addition, as mentioned above, we assume that all
these points are connected. Therefore, the system will direct
the agent to visit all places connected to the exploration goal,
decreasing the connection between that goal and each place
whenever the place is examined and the agent is no longer
curious about it (see Figure 3). Thus the model can perform a
complete exploration of the environment.
unexamined places initially connected to the exploration goal
are examined, exploration ceases. Exploration also ceases when,
after certain time using the cognitive map (see below), the
system cannot decide how to approach an unexamined place. Voicu and Schmajuk
(2001a) showed that this curiosity-directed
exploration is more efficient, i.e., takes less movements, than
random exploration. The system represents the actual structure
of the environment by updating the connections between initially
connected places in the cognitive map whenever an obstacle is
The cognitive map
built by the network is a topological map, i.e., it represents
only the connectivity, not distance or direction, between
places. Associations between place i and place j, Vi,j,
are the elementary internal learned representations of the links
in the external world. These associations are stored in
modifiable synapses, indicated by open triangles in Figure 3.
Whereas a positive Vi,j association, means that place
j can be accessed from place i, a positive Vj,i
association, means that place i can be accessed from place j. In
both cases, Vi,j = Vj,i = 0 means that
each place cannot be accessed from the other. When the agent is
in place i, activation aj is given by aj =
piVi,j, and this activity indicates
whether place j is accessible from place i. When place j,
adjacent to place i currently occupied by the agent, is accessed
by the agent, then Vi,j and Vj,i are
incrementally increased to a asymptotic value larger than 1.
Therefore, in the cognitive map trodden (strengthen) links
between places are represented by stronger connections (Vi,j
= Vj,i > 1 ) than unexplored links (Vi,j =
Vj,i = 1) or links between places that have been
verified to be accessible (Vi,j = Vj,i =
1). A detailed description of the model is given in Voicu and
examined place is a goal for a motivation other than curiosity,
e.g., when the agent has already found an appetitive stimulus at
that location, the agent can use the cognitive map to navigate
from its present position to the goal. If the environment has
not been explored and mapped before navigation, the system will
use its a priori representation and assume that all adjacent
places are connected. If the agent does not find these
connections during navigation, the map is modified accordingly.
If the environment is known, the system will use the map
representing the actual structure of the environment.
exploration or navigation, the goal-seeking system will guide
the agent to approach a neighboring place in which a goal is
found. When the goal cannot be perceived from the current
location of the agent, the system will guide the agent to move
towards the goal using the cognitive map. There are two methods
of using the cognitive map.
One method, referred to as next-place activation
method (Voicu & Schmajuk, 2001a),
consists of briefly entering all neighboring places in
succession, thereby activating their representation in the
cognitive map, and spreading this activation forward until
the representation of the goal becomes active. In order to
make the activation of the goal proportional to the distance
(measured by the number of intermediate places from the
current position), we assume that this activation is
attenuated as it spreads from the representation of one
place to another. Therefore, neighboring places that are
closer to the goal will activate more strongly the
representation of the goal.
A second method, referred to as
(Staddon, 2001; Voicu & Schmajuk, 2002), consists of
activating the goal in the cognitive map, which will
activate the place where it is located, and spreading this
activation until the representation of the current location
of the agent becomes active. Again, because we assume that
this activation is attenuated as it spreads from one place
to another, places that are closer to the goal are more
active than places that are more removed from it.
goal activation procedures are similar in some aspects and
different in others. As mentioned, both methods measure the
distance between the current position of the agent and the goal
by attenuating an initial activation as it spreads over the
cognitive map. Therefore, if these two points are separated by a
very large number of intermediate places, the attenuated
activity will become too weak to be used in the decision
The next-place and
goal activation methods differ in speed. With the next-place
activation method, the system needs to repeat the activation of
the cognitive map at each location on its way to the goal, which
makes the total decision time proportional to the square of the
length of the path (the time required to compute all the moves
to the goal is proportional to l + (l - 1) + . .
. 2 + 1 = l (l
+ 1)/2, where l is the length of the path). Instead, with the goal-activation
method, the total decision time is proportional to the length of
the path. The information needed to generate the moves to the
goal is produced by spreading the activation
l times in the network,
where l is the length of
the path. The next-place and goal activation methods also
differ in their memory requirements. The WM required by the
next-place activation procedure can be either large or small.
The size is large if the WM stores the associations of every
place in the environment with the prediction of the goal
generated when the agent enters a given place. Alternatively,
this size can be relatively small if the WM stores only the
associations of (a) the alternative directions in which the
agent can move with (b) the prediction of the goal produced when
the agent moves in a given direction.
goal-activation method can plan a complete path between a goal
and the current place by storing the activation of all places in
the environment in WM and then choosing which place to move next
by performing gradient ascent on this activity surface. Once the
activation of all places is stored in WM, this information can
be used at every location on the way to the goal. Therefore, the
goal activation method, though faster and able to plan a
complete path from the current position of the agent to the
goal, always requires a WM of size equal to the number of places
in the environment.
two important advantages that a hierarchical structure
provides: (a) a reduced number of connection values and (b)
a shorter decision time. Both advantages are the result of
storing the same information at multiple scales. The number
of connections is reduced because there are no connections
between places that belong to different regions (except
adjacent places in adjacent regions), and decision time is
improved because coarser representations of the environment
involve fewer nodes and therefore faster decision times.
More details are presented in appendices A and B.
shows that the use of a hierarchical cognitive map reduces
the number of connection values in a nonhierarchical map.
Appendix B shows that the decision time is shorter in a
hierarchical than in a nonhierarchical cognitive map.
section we address the question of how path planning can be
accomplished in a large environment when two restricting
factors are considered: (a) a limited WM capacity and (b) an
adequate attenuation when a spreading activation method is
Figure 4. (A) Canvas for a two
level hierarchy. The environment is divided in 6
regions (A, B, C, D, E, and F) and each region is
divided in six places. The advantage of this
representation is that a WM of size 6 is enough for
planning paths in the environment. (B) Squares in
broken lines represent the regions to be explored.
Solid lines represent connections between regions.
With a WM of limited
As shown, the goal activation method, which is
relatively fast and able to plan a complete path to the
goal, always requires a WM of size equal to the number of
places in the environment. It has been suggested that WM
capacity is relatively small, ranging between five and nine items
in humans (Miller, 1956). Therefore, an important question
is how path planning in a large environment can be
accomplished using a limited WM capacity. McNamara, Hardy
and Hirtle (1989) suggested that organisms that move in
large-scale environments should have their spatial memory
structured in units compatible in size to that of the WM.
How does this idea apply to the system described above?
As mentioned, planning a complete path from the
current position of the agent to the goal can be achieved
using the goal-activation method, which requires a WM of
size W equal to the number of places N in the environment (W
= N). If the capacity of the WM is smaller than the number
of places N (W < N), path planning cannot be completed. This
happens because the goal-seeking mechanism needs the
activation of both the current place and the goal to be in
WM in order to produce motor actions. Consequently, one way
to achieve path planning between two places is by dividing
the environment in a number of regions n that is equal to or
smaller than W (W
³ n). Because n < N, the size s of each of the n
regions will be larger than the size S of each of the N
places (which are approximately the size of the agent),
that is, s > S. Finally, the number of places of size S in
each region of size s is given by m = s / S.
Even though it is possible to plan a path in an
environment divided in n = W regions, these regions are
larger than the size of the agent and therefore inadequate
to exactly define its spatial location. Consequently, once
the path through the n regions is defined, we need to define
the paths through the places inside each of these regions.
As described above,
planning a complete path between two points inside a region
requires a WM of size W equal to or greater than the number of
places m inside a region (W
³ m). If W < m,
then another division of each region will be necessary. If
the environment is represented by a hierarchy with L levels
then the total number of places covered is given by N = WL
Therefore, the number of levels L in which an environment of
N places should be divided in order to fit a WM of capacity
W, is given by L = log N/ log W = log 36 / log 6 = 2 (for an
example with W=6, N=36 see Appendix A
and Figure 4).
spreading activation method.
Even if there were
no potential limitations to WM capacity, the use of both the
goal activation and the next-place methods is still problematic.
Both methods are required to spread activation over a limited
number of places in order to avoid excessive attenuation of the
spreading activity, thereby restricting how far the goal can be
from the location of the agent. It can be argued that this
problem can be avoided if the attenuation rate, i.e., the
attenuation at each reinjection in the cognitive map, is small
enough. However, small attenuation rates can result in poor
discrimination between two alternative next places when the goal
is far from the location of the agent. This poor discrimination
might be caused by a baseline noise that is larger than the
difference between activities at adjacent places far removed
from the present position of the agent.
Figure 5. Memory modules used in the Hierarchical Cognitive
Map. The place-region,
place-goal, goal-place, and region-place connections
are stored in four associative networks. These
networks and the flow of information
among them are
manipulated by the control system. This figure shows
inputs and outputs of these memory modules.
Connections between modules are
shown in Figure 6.
Appendix C shows the equations used for updating the
associations and outputs in each of the blocks
Hierarchical cognitive map with two levels, lower
level map (LLM) and upper level map (ULM). This
figure shows the connections among the
modules that allow the control system to read the
structure and plan paths in the
environment. Connections related to the
the memories are not shown.
compromise should be reached by combining a minimum attenuation
rate with a maximum number of reinjections that still generates
a significant activity at the current location of the agent when
the goal is activated. Let this maximum number of reinjections
be A. Consequently, in order to obtain a useful activity from
the most distant confines of the environment, we should divide
the environment in such a way that in the worst case the agent
is A regions, and A reinjections, away from the goal.
Whereas A is
limited directly by the physical implementation of the spreading
activation process, the limited WM capacity could be either a
direct result of the limitation of A or a consequence of how the
agent is designed.
introduce a hierarchical version of the cognitive map
presented by Voicu and Schmajuk (2002)
and described in the section on The Need for Hierarchical
Maps. In the hierarchical version, spatial information is
structured on a two-level hierarchy (see Figures 5 and 6).
Each level is represented by an associative network (Kohonen,
1977; see Figure 3). The first
level, or lower level map (LLM), has a high resolution
(locations are relatively small), which permits the
representation of all environmental details (such as
obstacles). For each region, the LLM stores associations
between places and places, places and goals, and goals and
places. Associations between places represent possible
transitions between spatial locations, associations between
goals and places define where a given goal is located, and
associations between places and goals define what goals can
be found in a given location. This LLM is identical to the
nonhierarchical cognitive map described before except that
it has fewer connections due to the lack of interregional
connections (see Appendix A).
The second level, or
upper level map (ULM), has a
low resolution (relatively
large locations) that permits the
representation of the whole environment. The ULM stores
associations between regions and regions. Again,
associations between regions represent possible transitions
additional associative networks (see Figure 5) are needed to
represent the associations between places and regions
(defining the region where a place is located) and between
regions and places (defining the places contained in a given
system acts on the four associative networks (place-region,
place-place, region-region, and region-place) by directing
the flow of information between them and between the
networks and the goal-seeking system (see Figures 2 and 6).
This control system determines how the networks are used
during exploration and navigation.
Exploration and the updating of the hierarchical map.
As in the case of
nonhierarchical maps described in the section on
The Need for
Hierarchical Maps, in order to build a hierarchical map of the
environment the agent has to examine each place in the
environment and enter the result of the inspection in the
As shown in
Figure 4, the agent
is provided with a priori information. (1) The environment to be
explored contains a partition of disjoint (non overlapping)
regions that covers it completely. (2) These regions are
initially interconnected and preserve the continuity of space.
(3) In turn, each region contains a partition of disjoint places
that covers it completely. (4) These places are initially
interconnected and preserve the continuity of space. For
simplicity, it is assumed that regions and places are
rectangular; however, as in the nonhierarchical case, any type
of shape is suitable as long as it preserves the continuity of
space. In addition, it is assumed that any two adjacent place
fields are connected and any two adjacent regions are connected.
In order to
completely explore the environment, the motivational system
defines as goals for exploration all the unexamined regions in
which the environment is divided. Alternatively, one or a few
regions can be defined as goals. In turn, all the places in the
region(s) to be explored are goals for exploration. Because the
agent can be surrounded by unexplored regions or places, the
decision of which region or place to enter first is made
according to a set of priorities. In our case, these are North,
West, East, North-West, North-East, South, South-West, and
Figure 7. Exploration. The model can exhaustively explore a
by applying the exhaustive
exploration strategy at all levels of the hierarchy.
All places are equally attractive at the outset.
Path planning in a
known environment. Starting and ending positions
A1 and F4 respectively (black circles). Obstacles
are shown in gray.
The arrows show the trajectory of
the agent within each region.
Since the layout of
the environment is known the agent is building an
Click on image for
animation of process shown in Figures 8, 9, & 10.
Upper Level Map. (A)
Planning done at the ULM for traveling from region A
to region F with a priori connections. (B) New
planning once the connection between B and F has
Click on image for
animation of process shown in Figures 8, 9, & 10.
Figure 10. Path planning in an unknown
environment. The arrows show the trajectory of the
agent within each region. Since the layout of the
environment is not known the agent has to detour at
the border between region B and F.
Click on image for
animation of process shown in Figures 8, 9, & 10.
Exploration of a region.
If obstacles are found in the explored region, then the LLM that
represents the connectivity between places is updated according
to a Hebbian rule (see Appendix C). The control system knows
that a region has been completely explored, i.e., all places
have been examined, when all place-exploratory goal associations
are equal to 0. After exploration, a region is defined as
composed by all places in a region that can be examined without
leaving the original region.
Several examples of how different types of regions are
explored are described in Appendix
D. Appendix E
describes how the a priori shape of a region and its a
priori connections can be changed according to how obstacles
are positioned in the environment (region redefinition). If
an obstacle divides a region in two, then during the
exploration of that particular region the model creates two
smaller new regions and connects them to the hierarchical
structure. The regions created are disjointed and separated by
the obstacle. This division process can continue an
arbitrary number of times so that the map adapts to how
obstacles are positioned in the environment.
Exploration of the environment.
The ULM is updated only if the newly found obstacles prevent the
agent from reaching the next region to be explored. The same
Hebbian rule, described above, used for updating the connections
between places within a region in the LLM is used for updating
the connections between regions in the ULM (see
Connections between regions are assumed to be weaker than
connections between places within a region.
Figure 7 illustrates the case of an environment to be explored.
Exploration of the regions is done following the priorities
described before, so if the agent starts at place A1, it will
move to places A2, A3, A6, A5, and A4. From region A the agent
will move to regions B, C, F, E, and D, where it will attempt to
visit the places in the order followed when exploring region A.
Finding a path between two places in an explored
is complete, and both ULM and LLM accurately reflect the
structure of the environment, the agent is ready to navigate
between any two points in the environment. If the place where
the agent is currently located and the goal are in the same
region (a fact detected by spreading the activation from the
goal a fixed number of times and succeeding in activating the
current location of the agent), then only the LLM of that region
is used for path planning. Instead, if as illustrated in Figure
they are in different regions (a fact detected by spreading the
activation from the goal a number of times proportional to the
size of WM and failing to activate the current
location of the agent), then planning starts in the ULM.
8 illustrates the case in which the agent is initially located in
place A1 and the goal in place F4. As described below, the
execution of each step in ULM is accompanied by path planning at
LLM. Whenever a subgoal at the local level is reached the system
proceeds with the next step at the ULM.
Step 1. Lower Level Map. Because the starting place and the goal are not
in the same region the control system plans a path at the ULM.
Step 2. Upper Level Map. The agent combines the present region A with
the goal region F in the ULM and plans the upper level path
(ULP) between them, ULP = A, B, C, F, using the activity surface
in WM (see Figure 9B).
Step 3. Lower Level Map. Once the path is planned at the Upper Level, the
detailed navigation at the Lower Level is planned and achieved.
As before, starting at place A1, the goal for the agent is the
closest place that belongs to B, that is B1. This is
accomplished by activating all places in region B, and spreading
this activation over the network, including places A3 and A6.
Because the resulting activation surface shows similar activity
levels for places A3 and A6, the agent uses the above priorities
to determine lower-level path (LLP), LLP = A1, A2, A3, B1. This
path is stored in WM and is overwritten the next time the system
plans a lower level path.
Step 4. Lower Level Map. The agent is initially at place B1. In order to
move from region B to region C, the agent plans the LLP = B1,
B2, B3, C1.
Step 5. Lower Level Map. The agent is initially at place C1, and the
goal, defined by the next region in the upper level path B, C,
F, is the closest place that belongs to F, that is F3. Due to
its navigational priorities defined above, the agent will plan
the LLP = C1, C2, C3, C6, and F3, and move through it.
Lower Level Map. The agent is initially at place F3 and the goal
is F4. Because activation of the goal activates the
representation of the current place, the LLM is used. The LLP
planned and followed is LLP = F3, F5, F4. Because the last
region, F, has been reached, the task has been completed.
Finding a path between two places in an unexplored
The agent can
navigate between any two points in the environment even when
exploration has not been completed and both ULM and LLM just
reflect the a priori assumptions about the structure of the
environment. Figure 9A illustrates the ULM with six
regions. As in the previous case, the agent has to move from
place A1 in region A to place F4 in region F.
illustrates the representation of the complete environment, gray
squares indicating obstacles, showing place 1 in region A (place
A1) and place 4 in region F (place F4). Unlike the previous
case, the model plans the following path at the ULM: A, B and F
(see Figure 9A). Once the agent is in place B5
it updates the LLM and the ULM, and path planning starts again.
The agent moves from B5 to C1, then from C1 to B3 and finally
In the case of navigation
between two points in the environment, the continuity of each
region is not critical. If a region is actually composed of two
or more subregions, the agent will find that the predicted path
is not executable, disconnect the regions in the ULM, and plan
an alternative path.
simulations, we assumed that the capacity of the WM is W= 1120
and the environment is divided into 30 regions. Therefore, the
agent navigates in an environment that contains N = 33,600
places. All places are of approximately the size of the agent.
The simulated environment is based on the topography of the Duke
University West Campus. It includes 12 buildings and their
surrounding areas. All buildings have their entrances open and no
details about the inside structure is included. Only the outside
walls of the buildings appear as obstacles in the simulated
First, we let the
agent perform a complete exploration of the environment and then
plan paths between different locations in the environment.
Figure 11 shows the result
of a complete exploration of the environment. The grid shown in
thin black lines illustrates the initial division of the
environment. Regions created during exploration contain dotted
lines and are delineated by gridlines and obstacles.
One important aspect of
exhaustive exploration is the inability to examine all places in
one sweep. This is most likely to happen in environments that
contain many cul de sacs. In the case of an agent that does not
use a hierarchical representation of space this problem is acute
since the agent has no means of detecting if there are
unexamined cul de sacs close to its current position. This
happens because the agent always moves towards the closest
unexamined place with respect to the whole environment. In
contrast, an agent that uses a hierarchical representation of
space always moves to the closest unexamined place with respect
to the current region. Therefore, unvisited cul de sacs that are
in the current region will be visited even if they are further
away than unexamined places located in an adjacent region. In
the computer simulations shown in Figure 11,
with few exceptions, all cul de sacs (i.e., all buildings) are
completely visited in one sweep.
Figure 11. Exhaustive exploration. Gray lines represent
either obstacles or building contours. The grid
represents the initial division of space. The map
shows a schematic representation of Duke West
Campus. Regions that contain dotted lines are
created during exploration.
Click on image for
animation of process shown in Figures 11, 12, & 13.
After performing a complete exploration of the
environment we let the model plan paths between different
locations. Figure 12 shows the path between two places that
belong to regions created during exploration. The starting
place is located in the Psychology building and the goal is
located in Bryan Center. Figure 13 shows two paths between
places that belong to regions defined a priori. The first
path Start1-Goal1 crosses the campus from North-West to
South-East and the second path crosses the campus from
South-West to North-East. It can be noticed that the agent
takes advantage of shortcuts contained inside regions.
Figure 12. Path planning. Gray lines represent obstacles.
The grid represents the initial division of space.
The map shows a schematic representation of Duke
West Campus. Dotted line represents the path planned
by the agent between Psychology building and Bryan
Click on image for
animation of process shown in Figures 11, 12, & 13.
Path planning. Gray
lines represent obstacles. The grid represents the
initial division of space. Dotted lines represent
paths between pairs of places Start1-Goal1 and
Click on image for
animation of process shown in Figures 11, 12, & 13.
This chapter shows
that agents with a limited WM capacity and that use a
hierarchical representation of space, can plan navigation and
exploration of large environments. Agents plan navigation by
spreading activation between the representations of two places
in the cognitive map and storing the resulting activities in a
WM. Then, they perform gradient ascent on the activity surface
stored in WM. Agents explore the environment by setting as goals
places that have not been examined before. During exploration
agents update their internal representation (all levels of the
hierarchy) to reflect the spatial layout of the environment.
Computer simulations show how the model is applied to an
environment with 33,600 places.
Comparison with other spatial representations.
Our model represents a given environment by determining
the occupancy at points equally spaced on a grid. The space
between points is equal to the size of the agent or that of the
smallest object in the environment. This approach has been used
both in building robots (e.g., Schultz et al., 1999) and
developing models of animal navigation (e.g., Reid & Staddon, 1998; Trullier
& Meyer, 1998). If, instead of being equally spaced, the
points on the grid are unequally separated, then the
resulting spatial structure can take advantage of the size
of the occupied or unoccupied areas. Unequally spaced grid
structures save memory when large, either occupied or
unoccupied regions are present (Samet, 1980; Hirtle, 1995).
These type of structures have also been used in robots (e.g., Arleo, Millan, & Floreano, 1999).
Another type of spatial representation results from
partitioning the environment into disjoint parcels. The
shape and the location of each partition are determined by
the angles and distances from the agent to salient features
of the environment. Experimental data shows that place cells
in the rat hippocampus provide a partition of the
environment that has fields approximately two and a half
times larger than the size of the animal (O'Keefe & Dostrovsky, 1971). The
firing pattern of the place cells seems to be modulated in
part by the positions of cues and landmarks external to the
maze in which the subjects perform. When compared to the
grid methods defined above, the partition method lacks rules
to generate a unique division of space. This method has been
used both in robots (Bachelder & Waxman, 1994) and models
of animal navigation (Sharp, 1991). Vectorial
representations describe the environment by making use of
geometric objects, such as points, circles or polygons (Latombe,
1991). Each of these objects contains a vector that defines
its position and a set of mathematical equations that define
its shape. The most important advantage of this type of
representations is the ability to use a variety of
geometrical operators, such as magnification, rotation, and
translation, to manipulate the spatial representation. Its
most important drawback is the difficulty of constructing
the objects directly from sensory data (Dudek & Jenkin,
2000). These methods have been used in robots (Latombe, 1991)
and models of animal navigation (Cartwritght & Collet,
representations are better suited than vectorial
representations for exhaustive explorations of an
environment. If an agent uses the second approach, then only
salient objects would be coded and the space between objects
would not have an internal representation. Therefore, the
agent will probably fail to explore some part of the space
between objects. On the other hand, if the agent uses a
grid, every place the size of the footprint of the agent or
of a small object would have an internal representation.
to the metric representations (grid, partition, or vectorial)
mentioned above, topological representations describe only
the connectivity, not direction and distance, between
places. Since path planning on a topological structure is
efficient, many models use this type of representation (Chown, Kaplan, & Kortenkamp,
1991; Schmajuk & Thieme, 1992).
model describes space by the occupancy of points on a grid
and, in addition, defines the connectivity between these
points, it provides information about the topological
aspects of the environment. Furthermore, as shown by Voicu
and Schmajuk (2002), even if metric data are not
explicit in the topological representation of our model, the
representation contains implicit metric information because
nodes that are further away in its structure are also
further away in the real environment. Other models also
combine metric and topological information (e.g., Kuipers,
How the model explains experimental data.
the idea that humans use hierarchical spatial
representations, Stevens and Coupe (1978) reported that
people misjudge the relationship between geographical
locations or artificial stimuli based on super-ordinate
spatial relations. For example, because most of the US is
south of Canada, Seattle is usually judged to be south (and
west) of Montreal even though it is actually north (and
west). According to our model, in the absence of information
about the relationship between two places that belong to two
different regions (e.g., Seattle and Montreal), the agent
relies on the relation between the regions where those
places are located (e.g., US and Canada). The latter
relation, however, might contain inadequate information
since the relationship between regions might be different
from the relationship between places. For example, in Figure
7, place A1 is north
of place B4. However, in the absence of information about
their relative location and based on the location of regions
A and B, A1 and B4 are judged to be at the same latitude.
the ordered-tree algorithm
(Reitman & Rueter, 1980) to detect underlying organization
of spatial memory, Hirtle and Jonides (1985) showed that the
spatial representation in humans is organized
hierarchically (see Taylor,
for more information on human spatial memory). Their subjects were tested on free recall,
map drawing and relative distance judgment regarding a
region in which subjects have been living for at least 2
years. The study shows that, when the points belong to
different clusters, physical distances tend to be estimated
as longer than that estimated when the points belong to the
same cluster [Figure 5 in Hirtle and Jonides (1985)].
present form our model can eventually explain Hirtle and
Jonides's results by assuming that associations between
places within a region are stronger than those between
places located in different regions. For example, if there
are three places (two located in the same region and one
located in a different region) that have the same physical
distance between them, the activity that spreads between the
places that belong to the same region is attenuated less
than the activity that goes between two places that belong
to different regions. Since, as mentioned in the section on
The Need for Hierarchical Maps, our model evaluates the
distance between two places by the level of activation of
one place after activity is spread in the network from the
other place, places within one region will be judged to be
closer than places across regions. [For a different approach,
see Voicu (2003).]
Still another study, conducted by McNamara et al.
(1989) using human subjects, showed that spatial memory is
hierarchically structured even when objects are uniformly
distributed on a map (see
Taylor, this volume, for more information on human spatial memory). The study suggests that hierarchies
are present even when there are no physical and perceptual
boundaries in the layout of the environment. This
hierarchical organization might be implicit in the structure
of the human visual system, where external images are
represented in a number of different resolutions (Watson & Robson, 1981). This
evidence might supports our assumption that the environment
is partitioned a priori in a hierarchical structure that has
different resolutions at different levels.
evidence for a hierarchical representation of spatial
information has been provided by Holding (1994). Subjects
learned an imaginary map that contains houses, streets and
towns. An analysis using the ordered-tree algorithm shows
that the hierarchical structure groups houses together and
streets together. Similarly, in our model streets could be
represented at the same level in the hierarchical map.
Moreover, the experimental results suggest that these
hierarchical spatial representations support semantic
priming. Our model can explain priming in terms of one item
activating the representation of a second one in the
cognitive map and, therefore, decreasing response time to
the second item.
literature also provides evidence that suggests that spatial
memory in animals uses multiple representations with
different resolutions. For example, Cartwritght and Collet
(1983) concluded that bees
navigate using both contours of objects (located within tens
of meters) and tree lines (located within hundred of
meters). It is unclear, however, if these representations
are combined in a hierarchical way or if, instead, bees use
the objects when close to them and the tree lines when far
from the objects.
Other experimental studies (Dallal & Meck, 1990;
Fountain & Rowan, 1995; Macuda & Roberts, 1995;
Meck & Williams, 1997;
Roberts, 1979; Terrace, 1991) suggest that
animals chunk information and form hierarchical
representations to facilitate learning. For example,
experimental data (Roberts, 1979) suggest that when rats are tested in a hierarchical radial
arm maze (a regular radial arm maze that has three additional small aisles
at the end of each arm), they use separate
memories for primary and secondary alley choices. In our
model, the secondary alleys and the central platform can be
seen as regions, each one represented by its own LLM. In
turn, regions are connected by the primary alleys, and this
spatial structure is represented by a ULM. (See
Mizumori, this volume, for
possible novel representations.)
Comparison with other hierarchical cognitive maps.
model presented in this paper, several approaches to spatial
navigation take advantage of hierarchical spatial
representations for planning action in a given environment.
Niizuma et al. (1992) proposed a hierarchical system in
which each control level uses its own map of the
environment. The hierarchical structure contains a
connection map, a geometrical map, a local map and a sensing
map. Only one level of the hierarchy is active at one time
and, when one level fails to accomplish the navigational
task, the control is passed to a higher level. Whereas in
the Niizuma et al. (1992) model each control level uses its
own map of the environment, in our model the control system
has access to all levels in the hierarchical structure.
approach to hierarchical mapping has been proposed by
Donnart and Meyer (1996). Their model uses a production rule
system to build a hierarchical map of the environment that
includes not only spatial information, but also information
related to spatial tasks. The model learns a hierarchical
organization of landmarks that helps in landmark
recognition. The main benefit of using this type of
hierarchy is that the localization system is more robust by
having additional contextual information. Issues related to
the size of the explored environment are not addressed by
proposed an approach to hierarchical mapping that describes
a method for finding a minimum path between places in a
large environment using a hierarchical structure. In this
hierarchical structure, the environment is divided in
regions that contain exit and entry points. These points are
used as goals when moving from one region to another. The
method first determines the level of the hierarchy that
includes both the goal and the current position. For this
upper level, the method finds the shortest path using
Dijkstra's (1959) algorithm. Then, using the same algorithm
at the lower level, the method finds paths between the
current position and the exit point in the first region, the
entry point and the exit point in the second region, and so
forth. Because the method uses fixed entry and exit points,
the path generated combining the upper and lower levels is
seldom identical to the shortest path generated when
Dijkstra's algorithm is directly applied to the lower level.
However, these results are improved when several adjacent
regions are collapsed into a single one.
approach is similar to ours in the way spatial information
is represented and used; however, there are two important
differences. First, our approach addresses the issue of how
the hierarchical map is updated. Second, because in our
method any point on the border between regions can be an
exit or an entry point, the path generated combining the
upper and lower levels better approximates the path
generated when path planning is directly applied to the
another approach that uses hierarchical structures is the
Spatial Semantic Hierarchy (SSH) proposed by Kuipers (2000).
The SSH comprises five levels, including sensory, control,
causal, topological, and metric. The
provides the sensory information in a readable form for all
the other levels. Basically, variables like distance,
intensity of light and sound are converted in an appropriate
format. The control level
describes the environment by using control laws that are
associated with conditions for their utilization. A
particular law (e.g., follow wall, approach landmark) is used
within a segment of the environment. The causal level
summarizes the environment as a discrete model in terms of
sensory views and actions
and causal relations among them. The
contains the connections among places, paths and regions in
the environment. Finally, the
contains a geometrical map of the environment using a single
frame of reference. This type of information is seldom
useful but it can prove essential in certain scenarios.
(2000) argues for the advantage
of a hierarchical representation of the topological level
versus a linear representation. One concern is, as mentioned
before, that a hierarchical representation usually produces
a path that is far from the optimal solution. However, even
if hierarchical representations are not able to provide the
optimal path, they can save time by providing a
computationally inexpensive suboptimal path, which sometimes
is more important than traveling on the shortest path.
hierarchical structure has also been used by Graham, Joshi,
and Pizlo (2000) to build a model that solves the traveling
salesman problem (TSP). The TSP is the problem of finding
the shortest tour that connects a number of cities that a
salesman is interested in visiting.
Graham et al. (2000) compared the performance of human
subjects, their model and well-known algorithms in the
artificial intelligence (AI) literature on TSP. Their
results showed that, unlike the AI algorithms, human
subjects and the hierarchical model show a linear dependency
between the size of the problem, i.e. number of cities, and
the error of the solution, that is the difference between the
solution found by the human subject or the computational
model and the actual optimal solution (the shortest tour).
al. (2000) represent the TSP as a high-resolution
grid where cells that encode cities have values greater than
zero whereas all other cells have a value of zero. By using
a process of filtering and compression a succession of
smaller grids are produced. Each grid looks like the initial
grid only it has a different resolution. All these
grids are used to build step by step a solution to the TSP.
First, a partial solution of the problem is produced at the
grid with the lowest resolution. Then, this solution is
expanded by including partial solutions taken from the grids
with higher resolutions.
although the representation used by Graham et al. (2000) is
very similar to ours, the information stored in it is used
for different purposes. Whereas their representation builds to solve a particular problem, namely the TSP, our
representation is used to explore and navigate large
Schmajuk (2001a) presented a neural network model of spatial
navigation that includes an action system and a cognitive
map. By spreading activation between the representations of
two places in the cognitive map and storing the resulting
activities in a WM, the action system can plan the shortest
path between those places. However, the capacity of the WM
might be too small to store the activity of all intermediate
places or the attenuation might be too large to be used in
the decision process when navigating in a large environment.
These restriction call for the use of a hierarchical
the hierarchical map, the environment is represented at
multiple levels. At the highest level, the environment is
divided in a number of parts equal to the size of WM. At the
lowest level, each part of the previous level is divided in
parts equal to the size of the agent.
Between the highest and the lowest level, each part of the
previous level is divided in a number of parts equal to the
size of the WM. Path planning starts at the level that
contains the points between which navigation is desired, and
ends at the lowest level, at which motion is produced.
Computer simulations show that a model, with a WM capacity
smaller than the total number of places in the environment,
explores, creates new regions and navigates between places
in the environment. The model describes some, but not all,
of the properties of hierarchical spatial behavior in humans
and animals. Potentially, the approach can also be applied
to the design of robots able to navigate in large
A., Millan, J., & Floreano, D. (1999). Efficient learning of
variable-resolution cognitive maps for autonomous indoor navigation.
IEEE Transactions on Robotics and Automation, 15, 990-1001.
Atkinson, R.C., & Shiffrin, R.M. (1968). Human memory: A proposed
system and its control processes. In K.W. Spence and J.T. Spence
(Eds.), The psychology of learning and motivation: Advances in
research and theory (Vol. 2, pp. 89-195). New York: Academic
Bachelder, I.A., & Waxman, A.M. (1994). Mobile robot visual mapping
and localization: A view based neurocomputational architecture that
emulates hippocampal place learning, Neural Networks, 7,
Baddeley, A. (1986). Working memory. Oxford: Clarendon Press.
Berlyne, D.E. (1950). Novelty and curiosity as determinants of
exploratory behavior. British Journal of Psychology, 41,
A. (1998). Hierarchical spatial reasoning: A geocomputation method.
Proceedings of the 3rd International Conference on GeoComputation,
17-19 September, Bristol.
Cartwright, B.A, & Collett, T.S. (1983). Landmark
learning in bees: Experiments and models. Journal of Comparative
Physiology, 151, 521-543.
E., Kaplan, S., & Kortenkamp, D. (1995). Prototypes, location, and
associative networks (PLAN): Toward a unified theory of cognitive
mapping. Cognitive Science, 19, 1-51.
Dallal, N.L., & Meck, W.H. (1990). Hierarchical
structures: Chunking by food type facilitates spatial memory.
Journal of Experimental Psychology: Animal Behavior Processes, 16,
Dijkstra, E.W. (1959). A note on two problems in
connection with graphs. Numeriske Mathematik, 1, 269-271.
Donnart, J.Y., & Meyer, J.A. (1996).
Hierarchical-map building and self-positioning with MonaLysa.
Adaptive Behavior, 5(1) 29-74.
Dudek, G., & Jenkin, M. (2000). Computational
principles of mobile robotics. Cambridge University Press.
Fountain, S.B., & Rowan, J.D. (1995). Coding for
hierarchical versus linear pattern structure in rats and humans.
Journal of Experimental Psychology: Animal Behavior
Processes, 21, 187-202.
Graham, S.M., Joshi, A., & Pizlo, Z. (2000). The
travelling salesman problem: A hierarchical model. Memory and
Cognition. 28(7), 1191-1204.
Hirtle, S.C. (1995). Representational structures
for cognitive space: Trees, ordered trees and semi-lattices.
Lecture Notes in Computer Science, 988, 327-340.
Hirtle, S.C., & Jonides, J. (1985). Evidence of
hierarchies in cognitive maps. Memory and Cognition, 13(3),
Holding, C.S. (1994). Further evidence for the
hierarchical representation of spatial information. Journal of
Environmental Psychology, 14(2), 137-147.
Kohonen, T. (1977). Associative memory.
Berlin, Germany: Springer Verlag.
Kuipers, B. (2000). The spatial semantic
hierarchy. Artificial Intelligence, 119, 191-233.
Latombe, J.C. (1991). Robot motion planning,
Kluwer Academic Publishers.
Macuda, T., & Roberts, W.A. (1995). Further evidence for
hierarchical chunking in rat spatial memory. Journal of
Experimental Psychology: Animal Behavior Processes, 21,
Mataric, M.J. (1991). Navigating with a rat brain: A
neurobiologically-inspired model of robot spatial representation.
In From Animals to animats (Vol. 1, pp. 169-175).
Cambridge, MA: MIT Press.
McNamara, T.P., Hardy, J.K., & Hirtle, S.C. (1989). Subjective
hierarchies in spatial memory. Journal of Experimental
Psychology: Learning, Memory, and Cognition, 15, 211-227.
W.H., & Williams C.L. (1997). Perinatal choline supplementation
increases the threshold for chunking in spatial memory,
Neuroreport, 8(14), 3053-3059.
Miller, G.A. (1956). The magical number seven, plus or minus two:
Some limits on our capacity for processing information.
Psychological Review, 63, 81-97.
Miller, G.A., Galanter, E., & Pribram, K.H. (1960). Plans and the
structure of behavior. New York: Holt.
Nehmzow, U. (1995). Animal and robot navigation. Robotics and
Autonomous Systems, 15, 71-81.
Niizuma, M., Kawano, Y., Tomizawa, M., Sugiyama, M., & Degawa, S.
(1992). Flexible control of autonomous vehicle utilizing
hierarchical map and planning, Proceedings of the IMACS/SICE
International Symposium on Robotics, Mechatronics and Manufacturing
O'Keefe, J., & Dostrovsky, J. (1971). The hippocampus as a spatial
map. Preliminary evidence from unit activity in the freely moving
rat. Brain Research, 34, 171-175.
O‘Keefe, J., & Nadel, L. (1978). The
hippocampus as a cognitive map. Oxford: Oxford University Press.
A.K., & Staddon, J.E.R. (1998). A dynamic route finder for the
cognitive map. Psychological Review, 105, 585-601.
Reitman, J.S., & Rueter, HR. (1980). Organization revealed by recall
orders and confirmed by pauses. Cognitive Psychology, 12,
Roberts, W.A. (1979). Spatial memory in the rat on a hierarchical
maze. Learning and Motivation, 10, 117-140.
H. (1980). Region representation: Quadtrees from boundary codes.
Communications of the ACM, 23(2), 163-170.
Schmajuk, N.A. (1990). Role of the hippocampus in temporal and
spatial navigation: An adaptive neural network. Behavioural Brain
Research, 39(3), 205-229.
Schmajuk, N.A., & Thieme A.D. (1992). Purposive behavior and
cognitive mapping: An adaptive neural network. Biological
Cybernetics, 67, 165-174.
Schultz, A.C., Adams, W., & Yamauchi B. (1999). Integrating
exploration localization and planning with a common representation.
Autonomous Robots, 6, 293-308.
Sharp, P.E. (1991). Computer-simulation of hippocampal place cells.
Psychobiology, 19(2), 103-115.
Staddon, J.E.R. (2001). Adaptive dynamics: The theoretical
analysis of behavior. Cambridge, MA: MIT Press.
Stevens, A., & Coupe, P. (1978). Distortions in judged spatial
relations, Cognitive Psychology, 10(4), 422-437.
Terrace, H.S. (1991). Chunking during serial-learning by a pigeon.
Journal of Experimental Psychology: Animal Behavior Processes, 17(1),
Trullier, O., & Meyer, J.A. (1998). Animat navigation using a
cognitive graph. In Blumberg et al. (Eds.). From animals to
animats 5: Proceedings of the fifth international conference on
simulation of adaptive behavior. Cambridge, MA: MIT Press.
H. (2003). Hierarchical cognitive maps. Neural Networks, 16,
H., & Schmajuk, N.A. (2001a). Three-dimensional cognitive mapping
with a neural network. Robotics and Autonomous Systems, 35,
H., & Schmajuk, N.A. (2001b). Hierarchical cognitive maps. Fifth
international conference on cognitive and neural systems, ICCNS '01,
H., & Schmajuk, N.A. (2002). Exploration, navigation and cognitive
mapping. Adaptive Behavior, 8(3-4), 207-223.
Watson, A. B., & Robson, J.G. (1981). Discrimination at threshold:
Labeled detectors in human vision. Vision Research, 21,
Zipser, D. (1985). A computational model of hippocampal place
fields. Behavioral Neuroscience, 99, 1006-1018.
The authors would like to thank Jose Larrauri, Matt Serra and
Ron Parr for comments and suggestions of previous versions of
copyrights for the individual chapters are retained by the authors.
All other material in this book is copyrighted by the editor, unless
noted otherwise. If there has been an error with regards to
unacknowledged copyrighted material, please contact the editor
immediately so that this can be corrected. Permissions for using
material in this book should be sent to the editor.