Learning Behaviors for Environment Modelingby Genetic Algorithm
Seiji Yamada
Department of Computational Intelligence and Systems Science
Interdisciplinary Graduate School of Science and Engineering
Tokyo Institute of Technology
4259 Nagatsuta-cho, Midori-ku, Yokohama 226-0026, JAPAN
Abstract. This paper describes an evolutionary way to lean behaviors
of a mobile robot for recognizing environments. We have proposed AEM(Action-based Environment Modeling) which is an appropriate approach
for a simple mobile robot to recognize environments, and made experiments using a real robot. The suitable behaviors for AEM have been
described by a human designer. However the design is very diﬃcult forthem because of the huge search space. Thus we propose the evolutionary design method of such behaviors using genetic algorithm and makeexperiments in which a robot recognizes the environments with diﬀerent
structures. As results, we found out that the evolutionary approach ispromising to automatically acquire behaviors for AEM.

1

Introduction

Primary research on an autonomous agent which recognizes a real environment
have been done in robotics. The most studies have tried to build a precise geometric map using a robot with high-sensitive and global sensors like vision
sensors [3]. Since their main aim is to navigate a robot with accuracy, the precise map is necessary. However, to recognize environments, such a strict map
may be unnecessary. Actually many natural agents like animals seem to recognize environments only with low-sensitive and local sensors like touch sensors,
and a precise geometric map is not necessary. In terms of engineering, it is important to build a mobile robot which can recognize environments only with theleast sensors.
Thus we have tried to build a mobile robot which recognizes an environment
only with low-sensitive and local sensors. Since such a robot does not know its
position in an environment, it cannot build the global map of the environment
using sensor data. Hence we proposed approach that a mobile robot can recognize an environment using action sequences generated by acting there. We callthe approach AEM (Action-based Environment Modeling), and implemented it
on a real mobile robot [15]. Using AEM, a robot can build a robust model ofan environment only with low-sensitive and local sensors, and recognize an environment. In our research, the mobile robot is behavior-based and acts using
given suitable behaviors (wall-following) for AEM in enclosures made of whiteplastic boards. Then the sequences of the actions executed in each enclosure are
obtained. They are transformed into real-value vectors, and inputted to a Kohonen’s self-organizing network. Learning without a teacher is done and a mobile
robot becomes able to identify enclosures. We fully implemented the system ona real mobile robot with two infrared proximity sensors, and made experiments
for evaluating the ability. As a result, we found out the recognition of enclosures
was done well.
However, in AEM, there is a signiﬁcant problem: where the suitable behaviors come from. Although the design for such behaviors is very hard because of
the huge search space, it has been done by a human designer thus far. Hence we
propose an evolutionary design method of suitable behaviors for AEM using GA(Genetic Algorithm), and make preliminary experiments. For future implementation on a real mobile robot, we use a Khepera simulator in the experiments.
From the experimental results, we found out that the evolutionary approach ispromising to automatically acquire behaviors for AEM.
In the similar approach to AEM, several studies have been done in robotics[9][11] and A-Life [12]. Nehmzow and Smithers studied on recognizing corners
in simple enclosures with a self-organizing network [12]. They used directionduration pairs, which indicate the length of walls and shapes of past corners, as
an input vector to a self-organizing network. After learning, the network becomesable to identify corners. Mataric represented an environment using automaton
consisting landmarks as nodes [9]. Though the representation is more robust
than a geometric one, a mobile robot must segment raw data into landmarks
and identify them. Nakamura et al. utilized a sequence of sonar data in order toreduce uncertainties in discriminating local structure [11]. Though the sequence
consists of sensor data (not actions), their approach is similar to AEM.
Wall-following and random-walking were used as suitable behaviors in [9][12][15]and [11] respectively. The behaviors were described by a human designer, andﬁxed. Hence they have the same signiﬁcant problem that the design of the behaviors is very diﬃcult as AEM.
There are several studies for applying GP (Genetic Programming) [8] tobehavior learning of a mobile robot [14][7][6][13]. Unfortunately, in the studies,very simple behaviors like obstacle avoidance were learned. In contrast withthem, our aim is to learn the suitable behaviors to AEM, and the behaviors iscomplex one consisting of several kinds of primitive behaviors.

2

Action-base Environment Modeling and its Problem

In AEM, a mobile robot is designed with behavior-based approach [2]. The behavior means mapping from states to actions, and a human designer describes
states, actions and behaviors so that sequences of executed actions can represent
environment structure. Since AEM uses an action sequence, not sensed data, fordescribing an environment, the model is more abstract and robust than a geometric one [15].

An AEM procedure consists of two stages: a training phase and a test phase(Fig.1). It uses 1-Nearest Neighbor method [4], one of eﬀective supervisedlearning methods. In the training phase (Fig.1(a)), a robot is placed in a training
environments having a class in which the environment should be included. Plural environments may be included in the same class. The behavior-based mobile
robot acts in the environments using given behaviors, and obtains sequencesof executed actions (called action sequences) for each of them. The action sequences (lists of symbols) are transformed into the real-valued vectors (called
environment vectors) using chain coding [1]. The environment vectors are stored
as cases, and the training phase ﬁnishes.
Next, in the test phase (Fig.1(b)), a robot is placed in a test environment:
one of the training environments. The robot tries to identify the test environment with one of training environments, and we call this task recognition of anenvironment. The identiﬁcation is done by determined the most similar training environment (1-Nearest Neighbor) to the test environment. The similarity
is evaluated with Euclidean distance between environment vectors. The robot
considers that the most similar training environment has the same class to thetest environment, and recognition of environments is done.

A robot acts inan environment

A robot acts inan environment
Test
env.

Training
env.

Actionsequence

Actionsequence
Chain coding
transformation

Chain coding
transformation
Environment
vectorEnvironment
vectorComparing withstored instances

Storing
instances(a) Training phase(b) Test phaseFig. 1. Overview of AEM

However, in AEM, there is a signiﬁcant problem: where the suitable behav-

iors come from. Since the suitable behaviors depend on an environment structure
which a robot should recognize, they have been described by a human designer
thus far. However the task is very diﬃcult for him or her. Because the search
space for a suitable behavior is very huge: the computational complexity is O(as ),where a and s are the number of actions and states. Thus, we propose an evolutionary method to automatically acquire such behaviors using GA.

3

Describing a Mobile Robot, States and Actions

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 for acquiring behaviors, and intend to
implement the learned behavior on a real mobile robot.
3.1

A Simple Mobile Robot: Khepera

We use a miniature mobile robot KheperaTM (Fig.2, the radius and the heightare 25mm and 32mm) which widely used in A-Life and AI. It has Motorola
68331 Micro processor, 256KByte RAM, and is programmable. As shown in
Fig.3, it also has two DC motors (two black bars in Fig.3) as actuators and eight
Infra-Red proximity sensors which measure both distance to obstacles and lightstrength. However, since the sensor data is imprecise and local, Khepera cannot
localize itself in global map. In the later experiments, the simulator build for
Khepera will be used.

Fig. 2. Khepera

3.2

Fig. 3. Sensor positions

State Description

We describe a state with the range of a sensed value. For reducing the search
space of behaviors, we restrict the number of states and actions as small as
possible.
Though a sensor on Khepera returns 10 bit (0 ∼ 1023) value for distance andlight strength, the value is very noisy and crisp. Thus we transform the distancevalue into binary vlues 0 and 1. The value “0” means an obstacle exists within
3cm from a robot. The value “1” means it does not exist. Furthermore only three(front, left and right) of eight sensors are used for reducing states.
Next states for light strength are described. Since only simple behaviors likeapproaching, leaving a light are considered suitable to AEM, we describe thestate using the label of the sensor with the strongest light value and binary
values which mean a light is “near” or “far”. As well as states for distance,
the only 4 sensors (front, left, right and back) are used. Additionally a state inwhich all of the sensors has almost same values is also considered. As a result,the number of states fot light is nine (= 2 × 4 + 1). The total number of statesis 72 (= 23 + 9)
3.3

Action Description

The following four actions are described. In experiments in the past research [15],
we found the actions is suﬃcient for a mobile robot to do simple behaviors likewall-following. A mobile robot acts in an environment by executing the actions,and consequently an action-sequence like [ A2, A4, A1, A1,· · · ] is obtained.
– A1: Go 5mm straight on.
– A2: Turn 30˚left.
– A3: Turn 30˚right.
– A4: Turn 180˚.
3.4

Transformation into an Environment Vector

The generated action-sequence is transformed into an environment vector. Let
an action-sequence and its environment vector be [a1 , a2 ,· · ·, an ] (a0 = 0, ai ∈{A1, A2, A3, A4}) and V = (v1 , v2 , · · ·, vm ) respectively. The vector values of
V are determined by the following rules. They change the vector value when the
direction of movement changes. These rules are considered a kind of chain coding[1]. For example, an action sequence [ A2, A2, A3, A3, A3, A4, A1 ] is transformed
into an environment vector ( 1, 2, 1, 0, −1, 1, 1 ).
1. If ai = A1 then vi = vi−1 .
2. If ai = A2 then vi = vi−1 + 1.
3. If ai = A3 then vi = vi−1 − 1.
4. If ai = A4 then vi = −vi−1 .
As mentioned in § 2, in training phase, training environments are given toa robot for learning. The robots acts in the given environments, and stores theenvironment vectors transformed from the action sequences. Next, in test phase,test environments are given to the robot. It identiﬁes the test environment with
one of training environments by 1-Nearest Neighbor method using Euclidean
distance as similarity.

4

Applying Genetic Algorithm to Acquire Behaviors

Since the number of states is 72 and that of actions is four, the number ofpossible behaviors is 472 = 2.23 × 1043. We have to search the suitable behaviors
to AEM in such a huge search space. Genetic algorithm [5] is applied to thesearch because it does not need any domain-dependent heuristics.
4.1

GA Procedure and Coding Behaviors

In the followings, we describe GA procedure used in our research.
Step1 Initializing population: An initial population I1 , · · · , IN are randomly
generated.
Step2 Computing ﬁtness: Compute the ﬁtness f1 , · · · , fN for each individual
I1 , · · · , IN .
Step3 If a terminal condition is satisﬁed, this procedure ﬁnishes.
Step4 Selection: Using f1 , · · · , fN , select a child population C from the population.
Step5 Crossover: Select pairs randomly from C on probability Pcross (calledcrossover rate). Generate two children by applying crossover to each pair,and exchange the children with the pairs in C.
Step6 Mutation: Mutate the individuals in C based on mutation rate Pmut .
Step7 Go to Step2.
We set the following parameters which are considered eﬀective experimentally.
– Population size: 50– Selection method: Elite strategy and tournament selection (the size = 2).
– Crossover operator: Uniform crossover.
– Crossover rate Pcross : 0.8– Mutation rate Pmut per gene: 0.05
Since we deal with deterministic action selection, not probabilistic, the behavior is mapping from a single state to a single action. Thus we use the codingin which one of actions {A1, · · · ,A4} is assigned to each state of s1 , · · ·, s72(Fig.4).

S1

S2

S3

S4

S 71 S 72

A4 A1 A3 A2 ....
A4 A2
Fig. 4. A coded behavior

4.2

Deﬁning a Fitness Function

Fitness is a very important for GA. Thus we have to carefully deﬁne the ﬁtness
function for AEM. We consider three conditions for suitable behaviors to AEM:
termination of actions, accuracy of recognition and eﬃciency of recognition. The
ﬁtness functions for each conditions are deﬁned, and then are integrated.
Termination of Actions A mobile robot needs to stop its actions by itself.
Otherwise it may act forever in an environment, and no action sequence is obtained. Thus the termination of actions is the most important condition. We use
homing which a robot returns his home. Because homing is considered a general method to terminate actions, and makes the length of an action sequence
depend on the size of an environment. A method to terminate actions within aﬁxed length of an action sequence does not have such advantage. The homing
concretely means turning to the neighborhood of a start point, and the termination is evaluated with the following function g. Its range is [0, 1], and returns
1 when a robot succeeded in homing in all the training environments.
g=(No. of E-trial) + (No. of H-trial)

2 × (Total No. of trials)

where E-trial and H-trial means trials in which a robot escaped from theneighborhood of the start point and trials in which it succeeded in homing.
Accuracy of Recognition Another important criterion is accuracy of identifying test environments. The accuracy is evaluated with the following function
h. Its range is [0, 1], and when h = 1, all the test environments were recognizedcorrectly.
 No. of correctly identiﬁed test env.
g=1
h=Total No. of test env.
00≤g<1
Eﬃciency of Recognition In AEM, a robot needs to act by operating actuators for recognizing an environment, and the actions signiﬁcantly cost. Hencethe actions should be as small as possible for eﬃciency of recognition. We hence
introduce the following ﬁtness function for evaluating the eﬃciency1 .
n
i=1 Si
1−
h=1
k=
n
∗
Smax

0
0≤h<1
where Si is the size of an action sequence obtained in ith test environment,
Smax is the limited size of an action sequence, and n is the number of test environments. The function have range (0, 1] and has larger value as more eﬃcient.
1

The obstacle avoidance is implicitly evaluated by the function k because the collision
increases the length of an action sequence.

We ﬁnally integrate three ﬁtness function into the following ﬁtness function
f having range [0, 3], and it is used in this research. Since the function h (or k)
takes 0 when g (or h) does not take 1, the function f is phased: the terminationof actions is satisﬁed when 1 ≤ f , the recognition is completely correct when
2 ≤ f , and the recognition eﬃciency is improved when 2 ≤ f < 3.
f =g+h+k

5

Experiments with Simulation

It is impractical that we use real robots as individuals in GA. Thus we implement the system using a Khepera simulator [10], and make experiments in
it. The parameters used in all experiments are described in the followings: theneighborhood of a start point is a circle with 100mm radius, and the limited sizeof an action sequence is 2000 actions.
In the simulator, the motor has ±10% random noise in velocity, ±5% one inrotation of robot’s body. Furthermore an Infra-Red proximity sensor has ±10%random noise in distance, and ±5% one in light strength. These noise makes thesimulator close to a real environment.
If a robot cannot return home within the limited size, the trial ends in failure.
If the ﬁtness value becomes more than two, the trial ends in success, and thenboth termination and accuracy are satisﬁed. In all the following experimental
results, we show one of success trials, not averaged results.
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 the action 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 the test environments with one of the training environments. The startpoints and directions is ﬁxed in bottom center and left.
Note that though the test environments are same to training environments,
the action sequences are diﬀerent because of the random noise in a simulator.
Thus the obtained behavior by our method has robustness[14][6].
In all the experiments, we had 20 trials which have diﬀerent initial conditions
for GA and the generation was limited to 100. Some trials failed depending on
the initial condition. In the followings, we present the succeeded trials for eachexperiment.
5.1

Exp-1: Environments with Diﬀerent Contours in ShapeFirst we made experiments Exp-1 using environments with diﬀerent contours inshape. Parts of ﬁve environments: { empty, L, L2, invL, small-empty } are given
to a robot, and we investigated the ability to recognize them. Additionally twelve
diﬀerent shape environments including the four ones are used.
The experimental results are shown in Table.1, and Fig.5 indicates the traceof the robot with the maximum ﬁtness in the expriment for the ﬁve environments.

The “GN” is the generation number in which the ﬁtness value becomes morethan two, and “Max ﬁtness” means the maximum ﬁtness value.
In such simple environments, the suitable behaviors for AEM were obtained
within few generations. Seeing from Fig.5, diﬀerent action sequences were obtained depending on the environment structure.

Table 1. Experimental results in Exp-1
Training environments GN Max ﬁtness(1){ empty, L }
1
2.84
(2)
(1) + L22
2.40
(3)(2) + invL3
2.44
(3) + small-empty 2
2.46
twelve environments 92.45(a) empty(b) L(d) invL(c) L2(e) small-empty

Fig. 5. Trace of actions in Exp-1

5.2 Exp-2: Environments with Diﬀerent Lights in Number andPosition
Next, by adding diﬀerent lights to environments in number and position, we
made ﬁve environments: { empty, 1-lamp, 2-lamp, 3-lamp, 4-lamp }. Exp-2 ismade by using parts of the environments. A light was so strong that a robot can
detect the light direction in any place. The experimental results are shown in
Table.2. Fig.6 indicates the trace of the robot with the maximum ﬁtness in theexperiment for the ﬁve envirnments. In the ﬁgures, a black circle stands for alight.
Though the GN increased more than ones in Exp-1, the suitable behaviors
were obtained. In Fig.6(a) ∼ Fig.6(c), the actions are slightly diﬀerent. In contrast with them, the actions of Fig.6(d) and Fig.6(e) are signiﬁcantly diﬀerent
from that of Fig.6(a) ∼ Fig.6(c). The lights in the left area seem to inﬂuencethem strongly.

Table 2. Experimental results in Exp-2
Training environments GN Max ﬁtness(1) { empty, 1-lamp } 1
2.85(2)(1) + 2-lamp
7
2.53
(3)
(2) + 3-lamp
82.77(3) + 4-lamp
12
2.77

5.3

Exp-3: Environments with Diﬀerent Contours and Lights

We set six environments: { empty, 1-lamp, L, L-1-lamp, invT, invT-1-lamp } byadding a light to three environments with diﬀerent contours, and made experiments Exp-3 using them. Each environment is included diﬀerent class and all ofthem should be distinguished.
As a result, GN was 13 and the maximum ﬁtness was 2.38. Fig.7 shows thetrace of the robot with the maximum ﬁtness. Over all the environments, actions
are very diﬀerent mutually.
5.4 Exp-4: A Single Class Includes the Plural Training
Environments
In Exp-1 ∼ Exp-3, all the environments are included in diﬀerent classes. However,in Exp-4, plural environments are included in a single class. For recognizing
such environments, generalization is necessary. We assigned three classes to six
environments used in Exp-3: { empty, 1-lamp }, { L, L-1-lamp }, { invT, invT1-lamp }, and made experiments. As a result, GN was 15 and the maximum

(a) empty(b) 1-lamp(d) 3-lamp(c) 2-lamp(e) 4-lamp

Fig. 6. Trace of actions in Exp-2(a) empty(b) 1-lamp(c) L(d) L-1-lamp(e) invT(f) invT-1-lamp

Fig. 7. Trace of actions in Exp-3

ﬁtness was 2.63. Thus our approach is valid for induction from sevral instancesof a class.

6

Conclusions

We proposed the evolutionary acquisition of suitable behaviors to Action-based
Environment Modeling. GA was applied to search the behaviors, and the simulated mobile robots were used as the population. States and actions were described for coding chromosomes. We made experiments in diﬀerent environments
in shape and lights, and found out our approach is eﬀective to learn behaviors.
However there are open problems like the followings.
– Analysis and more complex domain: We must analyze the experimental results for clarify how to acquire the suitable behaviors. Furthermore we will
make experiments in more complex domains, and clarify problems there.
– Robustness against initial conditions: In all the experiments, start points
and start direction were ﬁxed. However, when a real robot is used, such a
precise initial situation are impractical. Thus we must attempt experiments
in which the initial situation is noisy. The learning may be diﬃcult becausea mobile robot acts sensitively to the initial situation [14].
– Implementing learned behaviors on a real robot: Implementation on a realrobot is our ﬁnal target. The gap between simulation and an real environment
may make it diﬃcult.

References
1. E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. An
eﬃciently computable metric for comparing polygonal shapes. IEEE Transaction
on Pattern Analysis and Machine Intelligence, 13(3):209–216, 1991.
2. R. A. Brooks. A robust layered control system for a mobile robot. IEEE Transaction on Robotics and Automation, 2(1):14–23, 1986.
3. J. L. Crowly. Navigation of an intelligent mobile robot. IEEE Transaction on
Robotics and Automation, 1(1):31–41, 1985.
4. B. V. Dasarathy. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, 1991.
5. J. Holland. Adaptation in Natural and Artificial Systems. University of Michigan
Press, 1975.
6. T. Ito, H. Iba, and M. Kimura. Robustness of robot programs generated by genetic
programming. In Genetic Programming 1996, Proceedings of the First Annual
Conference, pages 321–326, 1996.
7. J. R. Koza. Evolution of subsumpton using genetic programming. In Proceedingsof the First European Conference on Artificial Life, pages 110–119, 1991.
8. J. R. Koza. Genetic Programming. MIT Press, 1992.
9. Maja J. Mataric. Integration of representation into goal-driven behavior-based
robot. IEEE Transaction on Robotics and Automation, 8(3):14–23, 1992.
10. O. Michel. Khepera Simulator v.2 User Manual. University of Nice-Sophia Antipolis, 1996. (http://wwwi3s.unice.fr/˜om/khep-sim.html).

11. T. Nakamura, S. Takamura, and M. asada. Behavior-based map representation fora sonor-based mobile robot by statistical methods. In 1996 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 276–283, 1996.
12. U. Nehmzow and T. Smithers. Map-building using self-organizing networks in really useful robots. In Proceedings of the First International Conference on Simulation of Adaptive Behavior, pages 152–159, 1991.
13. P. Nordin and W. Banzhaf. A genetic programming system learning obstacle
avoiding behavior and controlling a miniature robot in real time. Technical report, Department of Computer Science, University of Dortmund, 1995.
14. C. W. Reynolds. Evolution of obstacle avoidance behavior: Using noise to promoterobust solutions. In Jr. K. E. Kinnear, editor, Advances in Genetic Programming,volume 1, chapter 10, pages 221–241. MIT Press, 1994.
15. S. Yamada and M. Murota. Applying self-organizing networks to recognizing
rooms with behavior sequences of a mobile robot. In IEEE International Conference on Neural Networks, pages 1790–1794, 1996.

This article was processed using the LaTEX macro package with LLNCS style