Unsupervised Learning to Recognize Environmentsfrom Behavior Sequences in a Mobile Robot
Seiji Yamada

Morimichi Murota

CISS, IGSSE
Tokyo Institute of Technology
4259 Nagatsuta-cho, Midori-ku, Yokohama 226-0026, JAPAN
yamada@ymd.dis.titech.ac.jp
http://www.ymd.dis.titech.ac.jp/~yamada/

Abstract

recognize environments only with inexpensive sensors
because the cost is low.

In this paper, we describe development of a mobile
robot which does unsupervised learning for recogniz-

In many real environments

like a dark room, the global information like vision
may not be obtained.

ing environments from behavior sequences. Most stud-Moreover, since a robot should be adaptive to un-

ies on recognizing an environment have tried to build

known environments without help of a teacher, it

precise geometric maps with high sensitive and global

needs to learn to recognize new environment by itself.

sensors.

Thus unsupervised learning is necessary.

However such precise and global informa-tion may not be obtained in real environments. Fur-

Hence we attempt to build a mobile robot which

thermore unsupervised-learning is necessary for recog-

does unsupervised-learning to recognize environments

nition in unknown environments without help of awith low sensitive and local sensors.

teacher.

Thus we attempt to build a mobile robot

behavior-based and does wall-following in enclosures.

The robot iswhich does unsupervised-learning to recognize environ-

Then the sequences of behaviors executed in each en-ments with low sensitive and local sensors. The mobile

closure are obtained. The sequences are transformed

robot is behavior-based and does wall-following in en-

into real-value vectors, and inputted to a Kohonen's

closures. Then the sequences of behaviors executed inself-organizing network.

each enclosure are transformed into input vectors foris done and a mobile robot becomes able to identify

Learning without a teacher

a self-organizing network. Learning without a teacher

enclosures.

is done, and the robot becomes able to identify enclo-from a behavior sequence into an input vector andsures. Moreover we developed a method to identify en-

the self-organizing network works well for generaliz-vironments independent of a start point using a partial

ing data, the learned network is robust against noise

sequence. We have fully implemented the system withlike obstacles. Furthermore, for more robust recogni-a real mobile robot, and made experiments for eval-tion, we develop a method to identify environments

uating the ability. As a result, we found out that theindependent of a start point using a partial sequence.

environment recognition was done well and our method
was adaptive to noisy environments.

Since we carefully de ne transformation

We have fully implemented the system using a real
mobile robot with two infrared proximity sensors. For
evaluating our approach, we made experiments including environments with obstacles as noise. As a result,

1 Introduction

we found out the environment recognition was done
well and our method was adaptive to noisy environ-In robotics research, most studies on recognizing anenvironment have tried to build a precise geometricmap with high sensitive sensors [3].

However manyments.
Nehmzow and Smithers studied on recognizing corners in simple enclosures with a self-organizing net-natural agents like animals recognize their environ-work [6].

ments only with low sensitive sensors, and a geometricindicate the length of walls and shapes (convex or

They used direction-duration pairs, which

map may not be necessary. In view of engineering, itconcave) of past corners, as an input vector to a self-

is important to develop a simple robot which is able toorganizing network. After learning, the network be-

comes able to identify corners. However the transformation from raw data to an input vectors is signi cantly sensitive to noise like small obstacles. We pro-

Host computer
IBM-PC/AT(Pentium-133)

poses another transformation which maintains better

Wallfollowing

RS232C

topology than their one. Furthermore we experimentally evaluate robustness of our method against obsta-

A mobile
robot

cles.
Mataric

represented

anenvironment usingau-

tomata consisting landmarks as nodes [5]. Though the

Behavior sequence

representation is more robust than a geometric one, amobile robot must segment raw data into landmarks
tion of landmarks is dicult for a robot only with low
sensitive and local sensors. Thus, though her approach

Transformation
to input vector

Weights

and identify them. The segmentation and identi ca-

is similar to ours, it is not suitable for our purpose.
Tsuji and Li have done the excellent study on

Input vector

Input nodes

vision-based memorizing route scenes [7]. The mobile
robot stores qualitative panoramic representation, andlocates itself in the route by matching the memorized
representation against that of the incoming scenes. If

Training data
Test data

Kohonen self-organizing networka robot has a vision system, their approach will be

Learned network

valid.

OUTPUT: Room identified

2 Overview

Figure 1

System overview

The overview of a whole system is shown in Fig.1.
First a behavior-based mobile robot [2] goes roundsensors on the left side are actually used since the wall-

once in each offollowing is done clockwise. The mobile robot also has

n enclosure by wall-following, and ob-

n sequences of executed behaviors.

Next thean orientation sensor for steering and an encoder forsequences (symbol lists) is transformed into the real-

movement distance. Note that the infrared proximity

tains

valued vectors, and they are given to a self-organizing

sensors are low sensitive and obtain just local infor-

network as input. Note that there is no teacher giving

mation within 20 cm. The actuators consists of two

the correspondence from input vectors to enclosures.

stepping motors for driving left and right wheels inde-

Learning is done on the network using the Kohonen's

pendently and a DC motor for a front steering wheel

update rules. The(Fig.2(b)).

n input vectors are repeatedly given

to the network, and learning progresses. After learn-

Since the mobile robot needs to do wall-following

ing, a winner node indicates one of the enclosures ineven in an enclosure where some obstacles exist, we use

which the robot did wall-following. The test data are

the behavior-based approach [2] which is known robust

given to the learned network, and the mobile robot

against the change of an environment. The behavior-

identi es the test data with enclosures already trained.

based approach also can controls a robot with low

We mean this identi cation by environment recogni-

sensitive sensors, and have the advantage that the be-tion.

havior sequence is invariant even when the geometricmovement history of the mobile robot varies a little.
We use four behaviors (reactive rules) in the follow-

3 Wall-following by a behavior-based
mobile robot
A mobile robot used in our research is shown ining for wall-following. The behaviors are periodically
executed, and the mobile robot constantly goes forward.

Behavior-A (turning in a concave corner ): If an ob-

Fig.2(a). It has four infrared proximity sensors: twostacle within 10cm in the front and within 10cm

in front direction and other two in left and right direc-

Behavior-B (turning in a convex corner ): If notion on the both sides (top view in Fig.2(b)). Only twoon the left then turning 40clockwise there.

ri = A then vi = vi01 + 1.
ri = B then vi = vi01 0 1.
3. If ri = C or D then vi = vi01 .
4. Otherwise vi = 0 (i > n).
1. If

2. If

For example, Fig.5(a) shows an input vector transformed from a behavior sequence in a square enclo-(a)sure. The

: Actuatorof an input vector. For an input vector, the numberof dimensions indicates the periphery length of an enclosure, a series of the same value indicates a wall,(b)

Figure 2x and y axis indicate dimensions and values: Sensorand the change of values stands for a corner. The in-

A mobile robot

crease and the decrease indicate a concave corner anda convex corner.

obstacle within 5cm on the left and the right,
andwithin

10cm

in

the

front

then

We explain the robustness of BI-transformation us-

turning

ing an example shown in Fig.3. The movement history

Behavior-C (following-1 ): If an obstacle within 5cm
on the left then steering 13.5clockwise.
Behavior-D (following-2 ): If no obstacle within 5cm

of a mobile robot and an input vector from the behav-

40counterclockwise there.

on the left then steering 13.5counterclockwise.

We experimentally veri ed that a mobile robot
turns well by executing the behavior

A or B at cor-ners. Although the above behaviors are very simple,a mobile robot is controlled well and smoothly follows
walls.

ior sequences are indicated in Fig.3. Fig.3(a) stands
for an enclosure without obstacle and Fig.3(b) stands
for the same enclosure including a obstacle on a wall.
Thus the mobile robot should identify them as thesame one. The transformation needs to be de ned sothat the distance between the two input vectors may
be small. Using the BI-transformation results in the
input vectors as Fig.3.

The size of shaded areas in

Fig.3(b) indicates the di erence, and it is relatively
small. Note that the whole pattern of the input vector is not shifted.

4 Transformation from a behavior sequence into an input vector

If a robot uses more rigid trans-

formation in which an input vector is described withthe length of walls, shapes (convex or concave) of pastcorners [6], the whole pattern will be shifted and the
distance will be signi cantly large. Hence we consider

By wall-following, a sequence of executed behaviors is obtained. It has information on the shape ofthe enclosure: the length of a continuous sequence ofBI-transformation is robust, and the e ectiveness will
be experimentally veri ed.
The idea of BI-transformation is similar to the turn-C and D indicates the length of a wall, andbehavior A and B indicate the existence of a concave

ing function (or the chain coding)[1] in pattern recog-

corner and a convex corner respectively. Thus we con-from the raw data like a bit image, while the input

sider a mobile robot can identify enclosures with thevector is directly obtained from a behavior sequence

sequences.

using BI-transformation.

behavior

nition. In general, the turning function is extracted

Since a robot should be adaptive to unknown enviV

ronments in which no other agents help it, it needs
unsupervised-learning.

Hence we introduce a Ko-

honen's self-organizing network for identifying enclosures. The behavior sequence is a list of symbols, thus(a) No obstacle

we need to transform it into a real-valued vector asV

D

Competitive
layer

input to a self-organizing network. The transformation also needs to be robust against noise and easily
computed.
We propose BI-transformation . Given a behaviorr rA, B, C, Dg) and an inv ; v ; ; v n  m), the values of
I are obtained using the following rules, where v1 = 0.
r r

sequence: [ 1 , 2 , 1 1 1, n ] ( i 2 f
put vector: I = ( 1
2 111
m )(

...
(b) One obstacle
Figure 3

D

Robustness

Node-1 Node-2 Node-n(e 1, e 2, ..., en )Figure 4:
network

Input layer
Input vector

Self-organizing

5 Learning by a self-organizing network
In this section, we brie y explain a Kohonen's selforganizing network [4]. It clusters large dimensional

3

input vectors by mapping them to small discrete vec-

2

tors, and is used widely in pattern recognition androbotics.

A self-organizing network is a two-layered

1

3

4

2

3

1

2

0

01

1

101

201

301

101 201 301(b) Convex

210(a) Small square

3

1
1

101

201

301

(c) H

network consists of an input layer and a competitive01

101 201 301 401(d) Large square

layer (Fig.4). Any input node is linked to all competitive nodes, and all links have weights. As an input
vector is given, input nodes have values corresponding

3

3

3

to the input vector, and competitive nodes has values

2

2

2

which stand for the distance between their weights and11

the input vector. A winner node having the minimum

0

distance is determined, and weights of the winner's

1

101

201

301

0

1
1

(e) Concave

101

201 301

(f) L

0

1

101

201 301(g) Rectangle

neighbor nodes are updated.
Let an input vector and weights of links from all
input nodes to a competitive node
111 ,ui be E = [e1 ,e2 ,Figure 5

Seven enclosuresen ] and U i = [ui1 ,ui2 , 1 1 1 , uin ] respectively. Firsta self-organizing network computes the Euclidean distance between the input vector and competitive nodes.
After a winner node with the minimum distanceis determined, the weights of winner's neighbor nodes
are updated using the following formula.

u

new
ij =

uij +1uij 1uij =
old



e

( j 0
0

uij ) : i is neighbor: otherwise

Figure 6

Experimental environments

Update of the weights is done whenever a input vec-As seeing from Fig.1, the system consists of a mobile

tor is given. The learning rate and the size of the win-

robot and an IBM-PC/AT (Pentium 133MHz, 128M

ner's neighborhood is usually decreased as the learning

RAM) compatible personal computer as a host com-

progresses. The learning isnished when no update

is done.
Next the input vector is given as test data andputer. All programming was done on the host com-++ . The program of wall-following wasputer using C

down-loaded into a mobile robot through RS232C in-

the winner indicates the class including the input vec-

terface, and a robot autonomously followed walls. Af-

tor. The clustering is automatically done without ater wall-following, the behavior sequences were sent

teacher.

to the host computer and the learning by a self-

In our research, the dimension of an input vector is set larger than the length of any behavior sequence. The competitive layer is one-dimensional because the computational complexity of learning with
one-dimensional competitive layer is far less than thatorganizing network was done there.

6.1 Environment and a learning phase
Using white plastic boards, we built seven di er-with a two-dimensional one. If we set suciently manyent enclosures in shape.

nodes in an one-dimensional competitive layer, the res-the enclosures and the input vectors obtained by wall-olution of classi cation will not worse than that of afollowing in each enclosure. A mobile robot did wall-

two-dimensional one.

following ten times for each enclosure, and 70 behavior

Fig.5 shows the shapes ofsequences were obtained in total. For each enclosure,

6 Experimentsa single behavior sequence was used as an input vector for learning, and other 6 sequences were used fortesting. Fig.6 shows the scene that a mobile robot isUsing the mobile robot mentioned earlier, we madeexperiments for evaluating the utility of our approach.

doing wall-following.
The robot stops when it returns near a start point.

It can recognize the start location by dead reckoning
using an orientation sensor and an encoder. A mobile
robot, however, starts wall-following at the same position for the same enclosure. This restriction will be
removed in x6.4.
The largest length of behavior sequences obtained
from the enclosures was about 1400, and this was theminimum dimension of an input vector.

Since thelength was too large for a self-organizing network tolearn tractably, all sequences were compressed into 1/4
and the length was 500 at most.
We constructed a self-organizing network consistingof 520 input nodes and 32 competitive nodes locatedin one dimension. The neighborhood in the competi-d nodes on both sides of thewinner. The initial value d0 and 0 were set 5 and0.2. We changed
and d as learning progresses. The

Figure 7

tive layer is de ned withinitial weights of competitive nodes were set randomly
within 1.560.15.
All of 70 behavior sequences were transformed into
input vectors using BI-transformation.

The seventraining data (Fig.5) consisting of a single input vector for each of seven enclosures were randomly given

work's parameters on the accuracy. Setting the initial
weight values: 0.5610%, 1.5610%, 4.5610% and thestructure of competitive layer: a line and a circle. As aresult, the accuracy was 69%  74%, and the in uence
was considered slight.

6.3 Exp-2: Noisy environments

to the self-organizing network until the total number
becomes 4200, and learning was done.
When the learning began to converge, the particular nodes got to be winners frequently. We considered
the winner nodes correspond to enclosures, and called
them r-nodes.

Hence the number of r-nodes is thenumber of enclosures recognized by a robot.
In the test phase, at every time a test input vector
was given, a winner of r-nodes was determined. We
considered the winner r-node corresponds to an enclosure in which the input vector was obtained.

6.2 Exp-1: Identifying the enclosures
After learning with training data, the test data (63input vectors) were given to the learned self-organizing
network. As a result, we found all the test data werecorrectly identi ed (the accuracy = 100%), and veried the utility of our approach. Note that the 10 input

Twelve Enclosures

Though the test data used in Exp-1 included noise,
it was not so much.

In this experiment, we dealt

with more noise like obstacles.

We located obsta-

cles in the seven enclosures, and the mobile robot didwall-following in the enclosures.

The nine behavior

sequences were obtained and transformed into input
vectors. The input vectors (test data) were given to
the self-organizing network which was trained in Exp1.
As a result,ve enclosures were correctly identi ed.

Fig.8 shows success and failure examples. In Fig.8(a),the robot correctly recognized the enclosure including
either a single obstacle or two small cubical obstacles
on a wall.

However, in Fig.8(b) the robot failed torecognize an enclosure including either two large obstacles or an obstacle located obliquely to the wall.
The large or many obstacles changed the shape of enclosures from the original one, thus we consider thevectors for the identical enclosure are slightly di erent

failure of recognition is natural.

mutually because of noise like failure of executing be-

6.4 Exp-3: Utilizing partial sequences

haviors.
Furthermore additional experiments were made using twelve enclosures in Fig.7. 120 action sequences

Although the experimental results were satisfac-(20 for each enclosure) were used for training and test

tory, there are two important problems: a start point

examples. The network consisted of 1300 input nodes

must beand 128 competitive nodes. As a result, the accuracy

ior sequence is necessary for recognition. The former

decreased to 76%.

xed in every trial, and a complete behav-

makes recognition less robust, and the latter causes

Using the twelve enclosures, we made experiments

expensive recognition. Thus we developed a method

for investigating the in uence of self-organizing net-

to recognize environments with partial behavior se-




  






 






 





 





(a) The correct recognition
Figure 8

 




  





 
 

 




 
  


 
 (b) The wrong recognition

our approach.

Though this report may be prelimi-

nary, our approach is considered to contribute for designing a mobile robot which autonomously recognizes
environments. While we obtained good experimental
results, there are open problems like the followings.
Open environments : Though we assume that anenvironment is a closed region, real environments
may not be closed, e.g.

a room with doors.

The assumption is used only to terminate wallfollowing. Thus we need to develop a method toterminate robot's action in real environments.


Restriction on the shapes of enclosures :The

shapes of enclosures are restricted to rectangles

Enclosures with obstacleswith right corners.

If an enclosure consists ofshows the procedure.

A nor
B will be executed and a robot will not use in-Training phase : Sift a behavior sequence so that the

behaviors and BI-transformation.

curves like a circle, neither the behavior

quences independently of a start point. The following

formation of corners.

longest wall may be the head, and learn with it.
After learning, r-nodes are obtained.

Testing phase : At every corner, the following is done.

We need to improve theSuitable behaviors for recognizing environments :We used wall-following as behaviors for recognizing enclosures, however we do not consider

Make an input vector by BI-transformation, and

it is best one.

obtain the partial input vector by shifting it soand suitable behavior for characterizing environ-

There may be a more robustthat the longest wall may be the head and setting

ments. Currently we are developing evolutionary

value zero when a behavior was not executed yet.

acquisition for suitable behaviors using genetic al-Compute the distance between the partial input

gorithm [8].

vector and r-nodes. If the distance is suciently
short, the environment is determined the r-node's
environment.

References

Sifting an action sequence makes the recognition[1] E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Ke-

independent of a start point. Since the execution ofdem, and J. S. B. Mitchell. An eciently computablea partial action sequence is more inexpensive than

metric for comparing polygonal shapes.

that of a complete one, the above procedure makes

action on PAMI, 13(3):209{216, 1991.

the recognition far more ecient.
We made experiments with the twelve enclosuresin Exp-1.

As a result, the accuracy and the partial

ratio was 56.7% and 47.8%, where the partial ratio =The length of partial behavior sequences(%).
The length of complete behavior sequences

IEEE Trans-[2] R. A. Brooks.

A robust layered control system for amobile robot.

IEEE Transaction on R&A, 2(1):14{23,1986.
[3] J. L. Crowly. Navigation of an intelligent mobile robot.

IEEE Transaction on R&A, 1(1):31{41, 1985.
Self-Organization and Associative Mem-[4] T. Kohonen.

ory. Springer-Verlag, 1989.
[5] M. J. Mataric. Integration of representation into goaldriven behavior-based robot.

7 Conclusion

IEEE Transaction on

R&A, 8(3):14{23, 1992.
[6] U. Nehmzow and T. Smithers. Map-building using self-

We built a mobile robot which learns to recognize
enclosures from behavior sequences without teaching.
A self-organizing network was used for learning sinceorganizing networks in really useful robots. In Proceed-

ings of the First International Conference on Simulation of Adaptive Behavior, pages 152{159, 1991.
[7] S. Tsuji and S. Li. Memorizing and representing route

it was able to generalize an input vector without ascenes.

teacher and robust against noise. We also developed

Conference on Simulation of Adaptive Behavior, pages

BI-transformation and a recognition method with apartial behavior sequence.

The experiments using areal mobile robot were made for enclosures both withand without obstacles, and we veri ed the utility ofIn

Proceedings of the Second International

225{232, 1992.
[8] S. Yamada. Learning behaviors for environment modeling by genetic algorithm.

In

The First European

Workshop on Evolutionary Robotics, 1998. to appear.