Evolutionary Design of Mobile Robot Behaviors
for Action-Based Environment Modeling
YAMADA Seiji
CISS, IGSSE, Tokyo Institute of Technology
4259 Nagatsuta, Midori, Yokohama 226-8502, Japan
E-mail: yamada@ymd.dis.titech.ac.jp
URL: http://www.ymd.dis.titech.ac.jp/~yamada/index-e.html

Abstract. This paper describes an evolutionary way to design behaviors of a mobile robot for recognizing environments. We have proposed
an action-based approach (called AEM) for a mobile robot to recognize environments. In AEM, a behavior-based mobile robot acts in eachenvironments and action sequences are obtained. The action sequences
are transformed into vectors characterizing the environments, and therobot identiﬁes the environments with the vectors. The design of suitable behaviors for AEM is very diﬃcult for human because the search
space is huge and intuitive understanding is hard. Thus we develop theevolutionary design of such behaviors using genetic algorithm.

1Introduction

The most studies to recognize environments have tried to build a precise geometric map using a robot with high-sensitive and global sensors. However,just to recognize environments, such a strict map may be unnecessary. Thus
we have tried to build a mobile robot which recognizes environments only withlow-sensitive and local sensors, and proposed approach that a mobile robot canrecognize the environment with action sequences. We call this approach AEM(Action-based Environment Modeling) [5]. In AEM, a mobile robot acts using
given suitable behaviors like wall-following in environments. Then the action
sequences executed in each environment are obtained, and transformed into environment vectors. A robot identiﬁes the environments by comparing them.
Through the research on AEM, we recognized a signiﬁcant problem: where
the suitable behaviors come from? . An easy solution is that human designs thebehaviors. However the task becomes quite diﬃcult for a human designer as
the variety of environments increases. In this paper, we propose the evolutionary design method of such behaviors using GA (Genetic Algorithm) and makeexperiments for evaluation.
In the similar approach to AEM, several studies have been done in robotics[2] and artiﬁcial life [4]. In most researches, wall-following has been used as
suitable behaviors in [2][4][5]. Unfortunately the behaviors were described byhuman designers, and ﬁxed.

55mm

A robot acts inan environment

A robot acts inan environment

Testenv.

Training
env.

Actionsequence

Actionsequence
Chain coding
transformation

32mm

Chain coding
transformation

Fig. 2. Khepera

Environment
vectorEnvironment
vector21

Storing
instances(a) Training phase

5DC motor
Infraredproximity sensor
76

Comparing withstored instances(b) Test phaseFig. 1. Overview of AEM

2340Fig. 3. Sensor positionsTask: Action-based Environment Modeling

In AEM [5], a mobile robot is designed in a behavior-based approach [1]. Thebehavior means mapping from states to actions. An AEM procedure consistsof two stages: a training phase and a test phase (Fig.1). In the training phase,training environments having a class are given to a robot. The class means acategory in which the environment should be included. The mobile robot actsin the environments using given behaviors and obtains sequences of executedactions (called action sequence) for each of them. They are transformed into realvalued vectors (called environment vectors) using a chain coding-like method.
The environment vectors are stored as instances, and the training phase ﬁnishes.
In the test phase, a robot is placed in a test environment which is one oftraining environments. The robot tries to identify the test environment with oneof training environments. The identiﬁcation is done using 1-Nearest Neighbormethod, i.e. the robot selects the most similar instance to the test environment,and considers that the class of the instance is that of the test environment. The
similarity is evaluated with Euclidean distance between environment vectors.
Since the suitable behaviors depend on environment structure which a robot
should recognize, they have been described by human designers thus far. However
the task is very diﬃcult because of a huge search space.

3

States, actions and environment vectors

Using real mobile robots as individuals in GA is not practical because it is
impossible to operate several tens of real robots over more than one hundred
generations. Thus we use a simulator of Khepera (Fig.2). As shown in Fig.3, ithas two DC motors as actuators and eight Infra-Red proximity sensors whichmeasure both distance to obstacles and light strength.
We describe a state with the range of a sensed value. For reducing the search
space of behaviors, we restrict states and actions. A sensor on Khepera returns
10 bit values for distance and light strength. Thus we transform the distanceinto binary values 0 or 1. The “0” means an obstacle exists within 3cm froma robot, and “1” means it does not exist. Furthermore only three (front, leftand right) of eight sensors are used. Next states for light strength are describedusing only 4 sensors (front, left, right and back). We describe a state using thesensor with the strongest light value and its binary values which mean a lightis “near” or “far”. A state in which all of the sensors has almost same values isalso considered. As a result, the number of states for light is nine, and the total
number of states is 72 (= 23 × 9). We also describe four actions; A1 : Go 5mmstraight on, A2 : Turn 30˚left, A3 : Turn 30˚right, A4 : Turn 180˚left.
The generated action-sequence is transformed into an environment vector.
Let an action-sequence and its environment vector be [a1 , a2 ,· · ·, an ] (ai ∈ {A1 ,A2 , A3 , A4 }, a0 = 0) and V = (v 1 , v 2 , · · ·, v m ) (m ≥ n) respectively. Thevector values of V are determined by four rules: If ai = A1 then v i = v i−1 ,If ai = A2 then v i = v i−1 + 1, If ai = A3 then v i = v i−1 − 1, If ai = A4
then v i = −v i−1 . They change the vector value when the direction of movementchanges in the similar way to chain coding which is a popular method in patternrecognition.

4Applying GA to acquire behaviors

GA procedure and coding We use a simple GA procedure and parametersin the followings. We use the coding in which one of actions {A1 , · · ·, A4 } isassigned to each state.
– Population size: 50, Crossover operator: Uniform crossover.
– Selection method: Elite strategy and tournament selection (the size = 2).
– Crossover rate Pcross : 0.8, Mutation rate Pmut : 0.05
Deﬁning a ﬁtness function We introduce three conditions for suitable behaviors to AEM: termination of actions, accuracy and eﬃciency of recognition.
The ﬁtness functions for each conditions are deﬁned, and integrated.
A robot has to stop when it returns to the neighborhood of a start point.
The termination is evaluated with g =(No. of E-trial) + (No. of H-trial), where2×(Total No. of trials)

E-trial and H-trial means trials in which a robot escaped from the neighborhood of the start point and trials in which it succeeded in returning. Accuracy of identifying environments is also important. It is evaluated with h =No. of successful test env. , where h = 0 when g = 1. In AEM, the actions shouldTotal No. of test env.
nSii=1
be as small as possible for eﬃciency. Hence we introduce k = 1 − n∗S, wheremax
Si is the size of an action sequence in an environment i, Smax is the given limited

Table 1. Experimental results in Exp-1

Table 2. Experimental results in Exp-2

Env. Train. env.
GNMaxF(a) {emp, L}
1.0 (0) 2.80 (0.106)(b)(a) + L2 2.6 (1.84) 2.43 (0.131)(c)(b) + iL
2.8 (1.69) 2.44 (0.025)(d) (c) + s-emp 2.8 (1.75) 2.44 (0.093)(e)
10 env.
2.1 (0.738) 2.51 (0.024)(f)
12 env.
5.2 (3.08) 2.48 (0.07)

Env. Train. env.
GNMaxF(g) emp, 1-la 1.6 (0.966) 2.68 (0.196)(h) (g) + 2-la 4.8 (2.78) 2.59 (0.131)(i) (h) + 3-la 9.3 (5.19) 2.59 (0.111)(j) (i) + 4-la 10.0 (5.94) 2.62 (0.075)

size of an action sequence, and k = 0 when h = 1. We ﬁnally integrate threeﬁtness function into f = g + h + k having range [0, 3]. The utility of the ﬁtness
function is investigated through successful experiments.

5Experiments with simulation

We implement a system using a Khepera simulator [3], and make experiments. In
all experiments, we give each of training environments to a robot once. The robot
acts in the environments, and the environment vectors transformed from theaction sequences are stored as instances. Next each of the training environment
is given to the robot as a test environment, and the robot identiﬁes each of thetest environments with one of the training environments. In all the experiments,
we had 10 trials having diﬀerent initial population, and investigated the averages
and standard deviations of generation number in which GA stopped.
Exp-1: Environments with diﬀerent contours in shape First we madeexperiments Exp-1 using environments with diﬀerent contours in shape. The
experimental results are shown in Table 1. Four parts ((a) ∼ (d) in Table 1) of ﬁveenvironments: {emp, L, L2, iL, s-emp} were given to a robot. Additionally 10 and12 diﬀerent shape environments were used ((e) and (f) in Table 1). The “GN” isthe generation number in which GA stopped, and “MaxF” means the maximum
ﬁtness value at GN. The numbers in GN and MaxF stand for averages, and thenumbers in brackets are standard deviations. This format is common in all theexperimental results. Fig.4 indicates the action traces of the best individuals atGN in (d). In such simple environments, the suitable behaviors for AEM wereobtained within few generations. The standard deviations was large in GN andsmall in MaxF, and this tendency was observed through all the experiments.
Seeing from Fig.4, diﬀerent action sequences were obtained depending on thestructure of the environments.
Exp-2: Environments with diﬀerent lights Next, by adding diﬀerent lights
to environments in number and position, we made ﬁve environments: {emp, 1-la,2-la, 3-la, 4-la}. Exp-2 is made by using parts of the environments. Light was sostrong that a robot can detect the light direction in any place. The experimental
results are shown in Table 2. Fig.5 indicates the action trace of the best individual
at GN in (j). In the ﬁgures, a black circle stands for a light.

(a) emp(b) L(c) L2(d) iL(e) s-emp

Fig. 4. Trace of actions in Exp-1 (Five environments)(a) emp(b) 1-la(c) 2-la(d) 3-la(e) 4-laFig. 5. Trace of actions in Exp-2

Though the GN increased more than ones in Exp-1, the suitable behaviors
were obtained. Note that we cannot intuitively understand the behaviors inFig.5. This means that it is very hard for human to design such behaviors byhand-coding and this automatic design method is quite eﬀective.

6Conclusion

We proposed evolutionary design of suitable behaviors to AEM. GA was applied
to search the behaviors, and the simulated mobile robots were used as individuals. States and actions were described for coding chromosomes, and we carefully
deﬁned the ﬁtness function. We made experiments using diﬀerent environments
in shape and lights, and found out our approach is promising to learn suitablebehaviors for AEM.

References
1. R. A. Brooks. A robust layered control system for a mobile robot. IEEE Transaction
on Robotics and Automation, 2(1):14–23, 1986.
2. Maja J. Mataric. Integration of representation into goal-driven behavior-based
robot. IEEE Transaction on Robotics and Automation, 8(3):14–23, 1992.
3. O. Michel. Khepera Simulator v.2 User Manual, 1996.
4. U. Nehmzow and T. Smithers. Map-building using self-organizing networks in really
useful robots. In Proceedings of the First International Conference on Simulationof Adaptive Behavior, pages 152–159, 1991.
5. S. Yamada and M. Murota. Unsupervised learning to recognize environments frombehavior sequences in a mobile robot. In Proceedings of the 1998 IEEE International
Conference on Robotics and Automation, pages 1871–1876, 1998.
This article was processed using the LATEX macro package with LLNCS style