ABSTRACT continuous from discretized spaces and
In the current research, navigational describes procedures applicable when the
execution of a plan fails. It insists on the need
path analysis of mobile robots will be carried for an integrated conception of such procedures,
out using embedded intelligent techniques. At which must be tightly tailored to the specific
the beginning literature will be reviewed in robot that is used, notably to the capacities and
regard to current research problem as stated limitations of its sensory-motor equipment, and
to the specific environment that is experienced.
above. During literature review suitable
A hierarchy of navigation strategies is outlined
methodologies adopted by various researchers in the discussion, together with the sort of
will be reviewed and analyzed. Analysis of adaptive capacities each affords to cope with
genetic technique will be done for path unexpected obstacles or dangers encountered on
planning of mobile robots in clustered an animat or robot’s way to its goal.
environments. Subsequently, hybrid techniques
In a recent review, Guillot and Meyer
will be developed and analyzed for path (2001) emphasized the animat contribution to
optimization of mobile robots. At the end, cognitive systems research. In particular, they
results obtained from the analysis will be stressed the capacity of this approach to
discussed and conclusion will be drawn. integrate both the body and the control in the
quest for understanding intelligence in living
systems, a discourse that a steadily growing
number of researchers elaborate according to
INTRODUCTION various modalities(Brooks, 1991a,b; Clark,
For a robot, an animal, and even for 1999; Hara & Pfeifer, 2000; Pfeifer & Scheier,
man, to be able to use an internal representation 1999; Varela & Rosch, 1991).
of the spatial layout of its environment to
position itself is a very complex task, which
raises numerous issues of perception, An animat is a simulated animal or a
categorization and motor control that must all be real robot that permanently interacts with its
solved in an integrated manner to promote environment through its sensors, its body and its
survival. This point is illustrated here, within the actuators, and that must continuously cope with
framework of a review of localization strategies many concurrent, and possibly contradictory,
in mobile robots. The allothetic and idiothetic needs and goals (Meyer & Wilson, 1991; Meyer,
sensors that may be used by these robots to build Roitblat, & Wilson, 1993; Cliff, Husbands,
internal representations of their environment, Meyer, & Wilson, 1994; Maes Mataric, Meyer,
and the maps in which these representations may Pollack, & Wilson, 1996; Pfeifer, Blumberg,
be instantiated, are first described. Then map- Meyer, & Wilson, 1998; Meyer, Berthoz,
based navigation systems are categorized Floreano, Roitblat, & Wilson, 2000; Hallam,
according to a three-level hierarchy of Floreano, Hallam, Hayes, & Meyer, 2002).
localization strategies, which respectively call Animat designers, wishing to contribute to our
upon direct position inference, single-hypothesis understanding of human intelligence and
tracking, and multiple hypothesis tracking. The cognition, approach such endeavors in an
advantages and drawbacks of these strategies, evolutionary perspective—according to which
notably with respect to the limitations of the intelligence and cognition are supposed to be
sensors on which they rely, are discussed rooted in basic adaptive capacities inherited
throughout the text. from animals. Therefore, their effort to
Concerning map-learning, it investigate the interactions between an animat
distinguishes metric maps from topological and its environment particularly focuses on the
maps and describes procedures that help animat’s aptitude to survive in unexpected
maintain the coherency of these maps. environmental circumstances.
Concerning path-planning, it distinguishes
The capacity to navigate is obviously navigation strategies would afford planning
a major requirement for an animal striving capacities to the animal or the robot. In this
to survive in a given environment, or for an case, survival depends on actions that are
autonomous robot trying to fulfill its not only determined by current perceptions
mission, because it affords the possibility of and memorized events, but also by their
finding energy sources while avoiding expected consequences.
dangerous hazards. The most primitive
navigation strategy that might help the Map-based navigation seems quite
animal or the robot Halsucceed in such tasks natural to humans because using a map is a
consists of relying on mere chance and of very convenient way to describe an
moving randomly. As shown by environment and to share it with other
Todd,Wilson, Somayaji, & Yanco (1994), people. However, the human use of a map
evolutionaryshaped blind action may suffice requires a lot of high-level cognitive
to keep a population of animats, i.e. of processes in order to interpret the map and
simulated animals or real robots (Meyer & to establish the correspondence with the real
Wilson, 1991; Meyer, Roitblat, & world. Often, this correspondence is made
Wilson,1993; Cliff, Husbands, Meyer, & easier by modifying the environment, for
Wilson, 1994;Maes, Mataric, Meyer, example, by writing names on posts
Pollack, & Wilson, 1996;Pfeifer, Blumberg, indicating subway stations.
Meyer, & Wilson, 1998; Meyer,Berthoz,
Floreano, Roitblat, & Wilson, 2000;lam, The first research efforts in robotic
Floreano, Hallam, Hayes, & Meyer, 2002), map-based navigation were mainly inspired
alive and reproducing. However, the by these cognitive processes, assuming that
adaptive capacities of the animal or the errors in sensing and acting may be detected
robot would be dramatically enhanced if and corrected by a high-level cognitive
they used a slightly more elaborate). process, or using some sort of
navigation strategy, which would call upon environmenttal modification to make the
some fr sensor to detect objects in the navigation process easier. However, some
environment and on some reflex action to ethological studies suggested that animals
either pursue or avoid such objects. also made use of maps for navigation (for
Additional adaptive capacities would be example the cognitive map hypothesized by
afforded to an animal or a robot able to turn Tolman, 1948). Such hypotheses gained
to still more elaborate navigation strategies support with the identification of place cells
making it possible to elaborate and in rodent brains (O’Keefe & Dostrovsky,
memorize a so-called cognitive map 1971). These place cells are neurons, found
(Tolman, 1948), i.e. an internal notably in a part of the brain called the
representation of the environment. Survival hippocampus, that have an activity
in such case would depend not only on correlated with the rat’s position in its
immediate perceptions and reflexes, but also environment. This kind of map-based
on the recall of objects or events navigation is a much more appealing
experienced in specific places in the past. paradigm for robot map based navigation, as
Finally, because implementation of such it does not presuppose high level cognitive
internal representations would allow the processes and is able to work in natural and
animal or the robot to take into account that unmodified environments. Because sev-eral
a given move from a given place would lead robotic navigation models inspired by these
to another specific place, still more elaborate biological examples have been designed.
source, which provides external information
about the environment.
Idiothetic information may concern
PROCESSES OF NAVIGATION
speed, acceleration, leg movement for
Basically, map-based navigation
animals, or wheel rotation for robots. A
calls upon three processes (Levitt & Lawton,
straightforward integration of these data
1990; Balakrishnan, Bousquet, & Honavar,
results in a position estimate for the robot in
1999).
a 2D space. This process is referred to as
Map-learning, the process of dead-reckoning or path-integration. The
memorizing the data acquired by the term idiothetic data used is borrowed from
robot during exploration in a suitable biological literature. It corresponds to what
representation. is called odometry in robotics.
Localization, the process of deriving Allothetic information may be
the current position of the robot derived from vision, odor, or touch, for
within the map. animals, and laser range finder, sonars or
Path planning, the process of vision, for robots. Here again, the word
choosing a course of action to reach allothetic is borrowed from biology; it
a goal, given the current position. corresponds to expressions like observation,
The third process is simply dependent on the perception or sensor data in robotics
first two, as the current position and the map literature. There are two main uses of this
of the environment between this position information source are:-
and the goal are required to plan actions Data may be used to directly
toward this goal. The first two processes are recognize a place or a situation. In
also closely related. The chicken-and-egg this case, any cue—such as sonars
nature of their relation (Yamauchi, Schultz, time-of-flight, color or odor—may
& Adams, 1999; Kurz, 1995) arises from the be used.
fact that the map is needed to estimate the A metric model may be used to
position and that, conversely, the position is convert raw allothetic data into
needed in order to build the map. This information expressed in the 2D
relation makes the problem of simultaneous space related to the idiothetic data. In
localization and map-learning very difficult. this case, geometric properties of the
To solve this chicken-and-egg environment, such as object
[Link] have chosen to limit the scope positions, are inferred (Fig. 1). This
of this article to localization strategies that may be straightforward, as is the
rely on a fully-known map of the case for laser-range finders or sonars,
environment. The issues that arise when or more complicated, as for stereo-
localization and map-learning are tackled vision.
simultaneously, together with a survey of The drawbacks and advantages of these two
planning methods. sources of information are complementary.
Indeed, the main issue raised by idiothetic
SOURCES OF INFORMATION information is that, because it involves an
Two distinct sources of information integration process, it is subject to
may be used for map navigation. The first is cumulative error. This leads to a continuous
the idiothetic source, which provides decrease in quality, and therefore such
internal information about the robot’s information cannot be trusted over long
movements. The second is the allothetic periods of time. In contrast, the quality of
allothetic information is stationary over
time, but it suffers from the perceptual
aliasing problem, i.e. the fact that, for a
given sensory system, two distinct places in
the environment may appear the same.
Consequently, in order to build
reliable maps and to navigate for long
periods of time, the two sources must be
combined in a given animat (Cox, 1991). In
other words, allothetic information must
compensate for idiothetic information drift,
while idiothetic information must allow
perceptually aliased allothetic information to
be disambiguated.
MAP REPRESENTATION
When both allothetic and idiothetic
sources of information are available, there
are many ways to integrate them in a
representation useful for animat navigation.
Classically, the corresponding models are
classified in two categories resorting to
either metric or topological maps. In metric
maps, the positions of some objects, mainly
the obstacles that the animat may encounter,
are stored in a common reference frame. In
contrast, within topological maps, it is the
allothetic characterizations of places that the
animat can reach that are stored, along with
some information about their relative
positions (Fig. 1). Additional details about
the advantages and drawbacks of these
representations can be found in (Filliat &
Meyer, 2003).