Applied Soft Computing 4 (2004) 35–47

Recognizing environments from action sequencesusing self-organizing maps
S. YamadaNational Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan
Received 20 June 2002; received in revised form 2 December 2002; accepted 22 July 2003

Abstract
In this paper, we describe development of a mobile robot which does unsupervised learning for recognizing an environment
from action sequences. We call this novel recognition approach action-based environment modeling (AEM). Most studies
on recognizing an environment have tried to build precise geometric maps with high sensitive and global sensors. However
such precise and global information may be hardly obtained in a real environment, and may be unnecessary to recognize
an environment. Furthermore unsupervised-learning is necessary for recognition in an unknown environment without helpof a teacher. Thus we attempt to build a mobile robot which does unsupervised-learning to recognize environments withlow sensitive and local sensors. The mobile robot is behavior-based and does wall-following in enclosures (called rooms).
Then the sequences of actions executed in each room are transformed into environment vectors for self-organizing maps.
Learning without a teacher is done, and the robot becomes able to identify rooms. Moreover, we develop a method to identify
environments independent of a start point using a partial sequence. We have fully implemented the system with a real mobile
robot, and made experiments for evaluating the ability. As a result, we found out that the environment recognition was done
well and our method was adaptive to noisy environments.
© 2003 Elsevier B.V. All rights reserved.
Keywords: Environment modeling; Behavior-based robots; Self-organizing maps

1. Introduction
In robotics research, most studies on recognizing anenvironment like occupancy grids have tried to build
a precise geometric map with high sensitive sensors[1–5]. In general, since information obtained by a mobile robot is significantly restricted, the robot needs tointegrate the fractions of information for modeling thewhole environment based on the absolute coordinate
gained by such dead reckoning.
However, a simple mobile robot only with low sensitive and local sensors, like infrared proximity sen-E-mail address: seiji@nii.ac.jp (S. Yamada).

sors, can not integrate such partial information on anenvironment. Because cumulative error increases andlocalization in the absolute coordinate is very hard.
Many natural agents like animals, insects recognize
their environments only with low sensitive sensors,
and a geometric map may not be necessary for a simple
and important task like recognition of an environment.
Furthermore, in view of engineering, it is worthful todevelop a simple mobile robot which is able to recognize environments only with inexpensive sensors. In
many real environments like a room without light, theglobal information may not be obtained by computer
vision.
Moreover, since a mobile robot should be adaptive
to unknown environments without help of a teacher,1568-4946/$ – see front matter © 2003 Elsevier B.V. All rights reserved.
doi:10.1016/j.asoc.2003.07.001

36

S. Yamada / Applied Soft Computing 4 (2004) 35–47

it needs to learn to recognize new environments byitself. Thus unsupervised learning is necessary.
Hence, we attempt to build a mobile robot which
does unsupervised-learning to recognize environments with low sensitive and local sensors [6,7]. The
robot is behavior-based and does wall-following in
enclosures. Then the sequences of actions executed ineach enclosure are obtained. The action sequences aretransformed into real-value vectors, and inputted toa Kohonen’s self-organizing maps (SOM). Learning
without a teacher is done and a mobile robot becomesable to identify the enclosures. Since we carefully
define transformation from an action sequence into
an input vector and SOM works well for generalizing
input vectors, the learned network is robust against
noise like obstacles. Furthermore, for more robust
recognition, we develop a method to identify environments independent of a start point using a partial
action sequence. In this paper, we call an enclosure,which a robot tries to recognize, a room. We call
our approach of environment modeling action-based
environment modeling (AEM).
We have fully implemented the system using a real
mobile robot with infrared proximity sensors. For evaluating our approach, we made experiments including
environments with obstacles as noise. As a result, wefound out the environment recognition was done welland our method was adaptive to noisy environments.
Though AEM needs actions by a robot in an environment, it has advantages in many situations like thefollowing.
• Environments without rich information: For example, though a computer vision system is useful forenvironment recognition with global information, it
is not available in environments without light, objects with visual features and so on. AEM is applicable to such environments without rich information
because it needs only action sequences executed using a low-level sensors like a proximity sensor.
• Robots without sensitive sensor: Since AEM does
not need sensitive sensors for global and accurate information of an environment, it is suitable to robots
having only low-sensitive and inexpensive sensors.
Nehmzow and Smithers studied on recognizing
corners in a simple environment with SOM [8,9].
Furthermore, Smart and Hallam discussed the similarity between localization of a rat and their robot

by making additional experiments [10]. They useddirection-duration pairs, which indicate the length ofwalls and shapes (convex or concave) of past corners, as an input vector to SOM. After learning, theSOM becomes able to identify corners. However,
the transformation from raw data to input vectors is
significantly sensitive to noise like small obstacles.
We propose another transformation which maintains
better topology than their one. Furthermore we experimentally evaluate robustness of our method to
obstacles.
Mataric represented an environment using automata
consisting landmarks as nodes [11]. Though the representation is more robust than a geometric one, a mobile robot must segment raw data into landmarks andidentify them. The segmentation and identification oflandmarks is difficult for a robot only with low sensitive and local sensors. Thus, though the approach issimilar to ours, it is not suitable for our purpose.
Tsuji and Li have done excellent studies on
vision-based memorizing route scenes [12]. A mobile
robot stores qualitative panoramic representation, andlocates itself in the route by matching the memorized representation to that of the incoming scenes.
If a robot has a vision system, their approach will
be valid. However, a robot may not have such an expensive and global sensing system. Hence, we needto build the robot which recognizes the environment
only with local sensors.
Kato studied segmentation of an environment using statistics on action sequences [13]. A mobile robot
does random walk which was modified to cover wide
region, and action sequences are obtained. Their approach is similar to AEM in utilizing action sequences.
However, their aim is segmentation, and it is different
from ours. Also, since their method needs very large
number of actions, the implementation on a real mobile robot is hard. In contrast with it, our approach is
fully implemented on a real mobile robot and various
experiments are made with it.
Nakamura et al. proposed environment modelingusing a sequence of sensed data obtained through action executions instead of action sequences [14]. A
mobile robot executes an obstacle-avoidance behavior
and a sequence of data sensed by a sonar-ring. Local
structures are extracted by principal component analysis, and a global map is build by integrating them. Unfortunately, it is difficult to distinguish different rooms

S. Yamada / Applied Soft Computing 4 (2004) 35–47

only in shape using their approach. AEM makes a mobile robot to distinguish such rooms.
Ordinary use of SOM in robotics is just classification of raw input data [15]. In such applications, theraw sensor data are directly inputted to SOM for compressing information. In contrast with such studies, in
our research, the output of SOM directly indicates aparticular room. Thus, we need to carefully define thetransformation from a action sequence into an input
vector so that SOM may classify input data into rooms
well. The design of the transformation is a difficultand significant problem which does not occur in suchstraightforward applications.

Training
environment

Test
environment

Actionsequence

Actionsequence

Transfomation into
environment vectors

Transfomation into
environment vectors
Environment
vectors

Environment
vectors

SOM(Learning)

Learned SOM(environment
identification)(a) Training phase(b) Test phase

2. Action-based environment modeling: AEM
In this paper, we consider it environment recognition
that a mobile robot identifies an environment in which
it acted previously. We assume segmentation of eachenvironment have been done. Our purpose is to develop a simple mobile robot which is able to recognize
environments only with imprecise and local sensors.
To achieve this purpose, we can not use methods tobuild a geometrical map by integrating locally sensed
information based on absolute coordinate [1–5].
Because a cumulative error significantly increases
and localization in the absolute coordinate is very
hard.
Hence, robust environment recognition method onlywith local and imprecise sensing is necessary. We propose a novel method that a robot acts by executing
behaviors depending on environmental structure andmodels the environment using a sequence of executed
actions [6,7]. By designing robust behaviors against
sensing noise, an action sequence is utilized as abstract
description on an environment. We call this approach
AEM.
The basic idea of AEM is that a robot models anenvironment using not sensed data, but a sequenceof executed actions. The overview of AEM is shownin Fig. 1. It is consisting of two phases: a training
phase and a test phase. In a training phase (Fig. 1(a)),
a behavior-based mobile robot [16] goes around ineach room (called a training environment), which it
should recognize, by executing wall-following behavior, and the sequence of executed actions (called an
action sequence) is obtained. For each room, a sin-

37

Fig. 1. AEM overview.

gle action sequence is obtained at least. Note that anaction sequence is different from a sequence of executed behaviors. In general, a behavior is a rule: IF
condition on sensed data THEN action, thus different behaviors may have the same action in the THEN
part.
Next the action sequences (symbol lists) are transformed into the environment vectors, and they are
given to Kohonen’s SOM as input. There is noteacher giving the correspondence from input vectors
to rooms. Unsupervised learning is done on the SOM
using the Kohonen’s learning rules. The set of environment vectors are repeatedly given to the SOM, andlearning progresses. After learning, a winner node
indicates one of the rooms in which the robot didwall-following.
After a training phase, a robot goes into a test phase(Fig. 1(b)). A test environment, which is one of training
environments, is given to a mobile robot, and it doeswall-following in the same way to a training phase.
An action sequence is obtained and the environment
vector is generated from it. The environment vector is
input into learned SOM, and the test environment is
identified with one of training environments by investigating the winner node on the input. Then environment recognition is done. The detail of the procedures
will be mentioned later.

38

S. Yamada / Applied Soft Computing 4 (2004) 35–47

3. Wall-following by a behavior-based mobilerobot
A mobile robot used in our research is shown in
Fig. 2. It is designed for micro-mouse competition
by Japan System Design Co. Ltd., and the size is
100 mm (W) × 165 mm (D) × 135 mm (H).
3.1. Sensors and actuators
The mobile robot has four infrared proximity sensors: two in front direction and other two in left andright direction on the both sides (Fig. 3). These sensors can sense obstacles within only 15 cm, and thesensed values are imprecise. Thus, this is considereda mobile robot, only with imprecise and local sensors,
for which we attempt to develop AEM. Only two sensors on the left side are actually used for detecting awall since the wall-following is fixed clockwise. The

mobile robot also has an orientation sensor for steering a robot and an encoder for measuring movement
distance roughly.
The four wheels of a mobile robot are shown in
Fig. 3. The actuators consists of two stepping motors for driving left and right wheels independently
and a dc motor for front and rear steering wheels(Fig. 3).
Also a mobile robot has CPU and DOS-like OS, andwe can do programming to control it. The programming is done in a host PC and the program is loaded
into a mobile robot through RS232C serial communication.
3.2. Behavior-based approach
Since the mobile robot needs to do wall-following
even in a room where some obstacles exist, we use
the behavior-based approach [16] which is known
robust against the change of an environment. The
behavior-based approach also can control a robot withlow sensitive sensors, and have the advantage thatthe action sequence is invariant even when the geometric movement history of the mobile robot varies
a little. In AEM, a behavior is described by a reactive rule: IF sensing condition THEN action, wherean sensing condition can be directly checked on
sensed values and an action can be executed by motor commands. The architecture of a behavior-based
mobile robot is shown in Fig. 4. Sensed data areparallel input to behaviors and the sensing conditions are checked. Then an adequate rule is selectedfrom applicable rules, and executed. A cycle of rule
execution and sensing an environment is repeatedquickly.
Behavior-based mobile robot

Fig. 2. A mobile robot.

Behaviors

Sensorvalue

Fig. 3. Sensors and actuators (top view).

IF sensing cond. 1 THEN action1
IF sensing cond. 2 THEN action2
IF sensing cond. 3 THEN action3..
.

Fig. 4. A behavior-based mobile robot.

Execution

S. Yamada / Applied Soft Computing 4 (2004) 35–47

3.3. Wall-following
In this study, we assume rooms are distinctive inwall shape. Thus an action sequence needs to be characterized by the wall shape. For example, if a mobile robot does random-walk in rooms, the action sequences are very similar each other and environment
recognition is hard. Hence we use wall-following behavior for AEM. When a robot returns into neighborhood of a start point, it stops.
Using an action sequence by wall-following, we canapproximately estimate the size of a room, strictly thelength of the wall, and information on the positions ofcorners is also acquired by designing behaviors corresponding to a corner.
We use four behaviors in the following forwall-following. The behaviors are periodically executed, and the mobile robot constantly goes forward.
The steering is done relatively with current moving
direction, and a robot follows a wall clockwise.
• Behavior-A (turning in a concave corner): If an
obstacle within 10 cm in the front and within 10 cm
on the left then turning 40 clockwise there. See
Fig. 5(a).
• Behavior-B (turning in a convex corner): If no obstacle within 5 cm on the left and the right, andFig. 5. Behavior A, B, C, D.

39

within 10 cm in the left front then turning 40 counterclockwise there. See Fig. 5(b).
• Behavior-C (leaving a wall): If an obstacle within
5 cm on the left then steering 13.5 clockwise. See
Fig. 5(c).
• Behavior-D (getting close to a wall): If no obstacle
within 5 cm on the left and an obstacle within 10 cm
in the left front then steering 13.5 counterclockwise.
See Fig. 5(d).
We experimentally verified that a mobile robot
turned well at corners by executing the behavior A
or B and followed a wall by executing the behavior
C and D in turns. Although the above behaviors arevery simple, a mobile robot is controlled well andsmoothly follows walls.

4. Generating environment vectors
An action sequence is considered to describe thestructure of the environment. Thus, we can transform
it into a vector, input the vector to SOM and the SOM
is able to classify different rooms in shape. We callthe vector an environment vector.
4.1. Transformation from an action sequence into
an environment vector
Since a robot should be adaptive to unknown
environments in which no other agents help it, itneeds unsupervised-learning. Hence we introduce
Kohonen’s SOM for identifying rooms. The action
sequence is a list of symbols, thus we need to transform it into a real-valued vector as input to SOM.
Since SOM just classifies input vectors as keeping
topology among them, the transformation of environment vectors should have carefully designed for goodresults. Furthermore, such a transformation needs tobe robust against noise.
For satisfying preconditions above, we develop thefollowing behavior to input-vector (BI)-transformation.
Given an action sequence: [r1 , r2 , . . . , rn ] (ri ∈{A, B, C, D}) and a environment vector: I =(v0 , v1 , v2 , . . . , vm ) (n ≤ m) the values of I
are obtained using the following procedure. This
BI-transformation is an improved version of chain
coding (or a turning function) [17] by using relative40

S. Yamada / Applied Soft Computing 4 (2004) 35–47

rotation and invariant vector dimension rules for behavior C and D. If C and D increase vector dimension,
more corners make more dimensions independentlyof the length of a wall and precise identification ishard. Hence, we add the invariant rules.
4.1.1. BI-transformation(1) Initialize i = j = 1, v0 = v1 = · · · = vm = 0.
(2) If i > n, finish with output I = (v0 , · · · , vm ).
(3) If ri = A, set vj−1 = vj−1 + 0.5, i = i + 1 andgo to step (2).
(4) If ri = B, set vj−1 = vj−1 − 0.5, i = i + 1 andgo to step (2).
(5) If ri = C or ri = D, set vj = vj−1 , i = i + 1,
j = j + 1 and go to step (2).
To explain the BI-transformation above, we show
Fig. 6 standing for an environment (room), trajectory of a mobile robot, an action sequence and an
environment vector generated from it. In a graph ofan environment vector, x-axis and y-axis indicate thedimension and value of an environment vector, respectively. Also the number of actions is n = 28, andthe dimension is set as m = 30. First all the values are
initialize as v0 = v1 = · · · = v30 = 0. Next the vector
value is determined depending on an action r. Notethat at step (3) or (4), the value increases or decreases
because behavior A or B turns a mobile robot significantly, however the vector dimension j is not changed.
In contrast with this, at step (5), the value is notchanged and only dimension is increased. Hence thedimension of non-zero part of an environment vector(14 in Fig. 6) is less than the length of an action sequence. When the procedure is stopped at step (2), theremained vector value is left as zero, and the environment vector is output. Thus BI-transformation makes
the dimension of a non-zero part of the environment
vector indicate the length of a single side of a room.
In Fig. 6, a region in which the same vector value
keeps correspond to a single side of a room and thechange of value indicates the existence of a corner.
Concretely, in Fig. 6, dimension 0–1, 2–3, 4–5, 6–7,
8–9, 10–13, 14–16 correspond to sides of a room andthe changes of value in dimension 1–2, 3–4, 5–6, 7–8,
9–10, 13–14 correspond to corners of a room. The increasing change and the decreasing change correspondto a concave corner and a convex corner, respectively.
See Fig. 11 for examples of environment vectors obtained through the experiments.
4.2. Influence of obstacles to an environment
vectorWe explain the robustness of BI-transformation using an example shown in Fig. 7. The trajectory of amobile robot and an environment vector from the action sequences are indicated in Fig. 7. Fig. 7(a) stands
for a room without obstacle and Fig. 7(b) stands for(a) No obstacle(b) One obstacle
Fig. 6. An environment vector.

Fig. 7. Robustness of BI-transformation.

S. Yamada / Applied Soft Computing 4 (2004) 35–47

the same room including a obstacle on a wall. Thus,
the mobile robot should identify them as the same one.
The transformation needs to be defined so that the distance between the two environment vectors may besmall. Using the BI-transformation results in the environment vectors as Fig. 7. The size of shaded areasin Fig. 7(b) indicates the distance, and it is relatively
small.
Note that environment vector representation is morerobust than symbol-based representation of an environment. If a robot uses more rigid transformation inwhich an environment vector is described with symbols of the length of walls, shapes (convex or concave) of past corners [8], noise by obstacles may makethe distance significantly large. For example, consider
symbol-based transformation for modeling an environment by using convex corner (VC), concave corner(CC), long wall (LW) and short wall (SW). By using this transformation, a symbol sequence [LW, CC,
LW, CC, LW] is obtained from Fig. 7(a), and a symbol sequence [LW, CC, SW, CC, SW, VC, SW, VC,
SW, CC, SW, CC, LW] is obtained from Fig. 7(b).
Obviously, these two symbol sequences are quite different using a simple symbol-based matching method.
Hence, we consider BI-transformation is robust, andthe effectiveness will be experimentally verified.

5. Environment recognition using SOM
5.1. SOM: self-organizing maps
In this section, we briefly explain Kohonen’s SOM[18]. It clusters large dimensional input vectors by
mapping them to small discrete vectors, and is usedwidely in pattern recognition and robotics. SOM is a
two-layered network consisting of an input layer and acompetitive layer (Fig. 8). 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 to the input vector, and competitive nodes
has values which stand for the distance between theirweights and the input vector. A winner node having
the minimum distance is determined, and weights of
the winner node’s neighbor nodes are updated.
Let an input vector and weights of links fromall input nodes to a competitive node ui be I =41

Winner nodeCompetitive
layer

...
Node-1 Node-2 Node-n( v 1 , v2 , . . . ,vn )Input layer
Input vector

Fig. 8. The structure of SOM.

[v1 , v2 , . . . , vn ] and U i = [ui1 , ui2 , . . . , uin ], respectively. First SOM computes the Euclidean distance
between the input vector and competitive nodes. The
distance is computed with the equation: ||I − U i || =
2j (vj − uij ) .
After a winner node with the minimum distance isdetermined, the weights of winner node’s neighbornodes are updated. The neighborhood is defined depending on the dimension of a competitive layer. If a
competitive layer is two dimensional, a square having
the winner node as the center is used as neighborhood.
For example, in Fig. 8, the shaded neighbor nodes are
determined in a minimal square with the black winner node as the center. The equation for updating theweights of neighbors is shown in the following, where
α is a learning rate and unew
means an updated weighij.
from uoldij
unew= uoldij + uijij
α(vj − uij ), i is neighboruij =
0,otherwise
Update of the weights is done whenever a input vector is given. The learning rate and the size of the winner node’s neighborhood is usually decreased as thelearning progresses. The learning is finished when no
update is done.
5.2. Identification in a test-phase
When learning begins to converge, the particular
nodes become winner nodes frequently. We consider

42

S. Yamada / Applied Soft Computing 4 (2004) 35–47

the winner nodes correspond to rooms, and call themr-nodes. Hence, the number of r-nodes is equal to
the number of rooms recognized by a robot. In a test
phase, at every time a test environment vector is given,a winner node of r-nodes is determined. We consider
the winner r-node corresponds to a room in which theenvironment vector was obtained. In general, though
the number of the learning iterations is very large, theidentification in a test phase is very fast because it justneeds to compute of distance between the environment
vectors and r-nodes.

6. Utilizing a partial action sequence
With the method mentioned thus far, a mobile robot
needs to completely go around in a room for environment recognition. However, if even a partial action
sequence includes unique character, the environment
recognition may be possible with it. Thus, we develop
a method for recognizing environments with a partial
action sequence like the following. The basic idea isthat we use a environment vector which is shifted sothat the longest wall may be positioned in the head
and identify a room using threshold for similarity.
• A training phase.
Learning with SOM is done using complete action sequences which are so that the longest wall
may be positioned in the head.
• A test phase.
(1) A partial action sequence is incrementally obtained. An environment vector is generated by
BI-transformation whenever the corner is detected. Find the longest wall region in an environment vector, and generate a partial environment vector by shifting the vector so that thelongest wall region may be positioned in thehead.
(2) Compute the distance between the partial environment vector and r-node’s weight.
(3) If the distance is less than a threshold ξ, output
the room corresponding to the r-node and thisprocedure stops. Otherwise go to step (1).
Using procedures above, wall-following may startat an arbitrary position near a wall. It is significant
how to determine the threshold ξ. We determine it ex-

perimentally because of no analytical way. Since theexecution of a partial action sequence is more inexpensive than that of a complete one, the above proceduremakes the environment recognition more efficient.

7. Experiments
7.1. Setting and methods
Using the mobile robot mentioned earlier, we madeexperiments for evaluating the utility of AEM. The
system consists of a mobile robot and an IBM-PC/AT
PC (Pentium 133 MHz, 128M RAM) as a host computer. All programming was done on the host computer using C++ . The program of wall-following was
down-loaded into a mobile robot through RS232C
interface, and a robot autonomously followed walls.
After wall-following, the action sequences were sent
to the host computer and the learning by SOM wasdone there.
We built different rooms in shape with 13 cm height
white plastic boards. Fig. 9 shows the scene that amobile robot was doing wall-following. The robot
stopped when it returns near a start point. It recognized the start location by dead reckoning using an
orientation sensor and an encoder.
In a training phase, a mobile robot did wall-following
one time for each of N rooms, and N action sequences and environment vectors were obtained in
total. The N environment vectors were repeatedly input to SOM as input vectors in fixed order, and theFig. 9. Experimental environments.

S. Yamada / Applied Soft Computing 4 (2004) 35–47

SOM learned. Then, in a test phase, a mobile robot
did wall-following five times for each of N rooms,
and 5 × N action sequences and environment vectors
were obtained in total. A set of the 5 × N environment
vectors was input to the learned SOM as test environments and environment recognition was examined.
In the experiments, the largest length of action sequences obtained from rooms was about 1000, and thiswas the minimum dimension of an input vector. The
parameter setting of SOM is shown in the followings.
• The number of input nodes: 1300.
• The number of competitive nodes: 128.
• Topology of a competitive layer: linear and circularwith one-dimension.
• Initial weights of competitive nodes: initial weights
are generated from uniform random number within
the range 0.5 ± 10, 1.5 ± 10, and 4.0 ± 10%.
• The number of learning iteration (the total numberof input vectors): 100,000 which is known valid
experimentally.
Also the learning rate αt and the size dt of winnernode’s neighborhood at t iteration were decreased aslearning progresses using the following formulas. The
dt is the length of a side of a square:




t
t
; dt = 16 1−
αt = 0.8 1−
100, 000
100, 000
Fig. 10 shows the convergence as learning iteration
progresses, where D of the y-axis is the square of
Euclidean distance between the input node and the43weighs of the winner node and the x-axis stands forthe number of iterations for updating the weights in
SOM.
7.2. Recognition of seven rooms
First of all, the seven rooms shown in Fig. 11 wererecognized. Fig. 11 stands for the shape of rooms,
trajectories and environment vectors. The real lengthof a side of a large square in Fig. 11 is 146 cm,

3

3

3

2

2

2

1

1

1

0

0

1

101

201 3011

101

0

201 301

3

3

3

2

2

2

1

1

1

0

1

101

0

201 301

1000

1

101

0

201 301

800
600
D
400
200

3
2

0
1

500
1000
The number of iterations
Fig. 10. Convergence of learning.

1

1
0

1

101

201 301

401

Fig. 11. Seven rooms.

1

101

201

301

101

201 301

44

S. Yamada / Applied Soft Computing 4 (2004) 35–47

and the rooms are figured with the same scale. In
this experiment, complete action sequences wereused.
As a result, for all settings of topology of a competitive layer and initial weights of competitive nodes,
the recognition rate was 100%. Note that this task is
not easy because the action sequences and environment vectors for an identical room are slightly different mutually because of sensor noise and failure of
executing actions.

E-1

E-2

E-3

E-4

E-5

E-6

7.3. Recognition of twenty rooms
Furthermore, experiments were made using twenty
rooms in Fig. 12, where the length of a side of E-3 is146 cm and the rooms are figure with the same scale.
Complete action sequences were used, and a sequenceof [E-4, E-5, E-1, E-12, E-2, E-8, E-9, E-3, E-7, E-11,
E-10, E-20, E-19, E-18, E-14, E-17, E-13, E-16, E-15,
E-6] was input to SOM repeatedly. Table 1 shows theexperimental results on recognition rate for various
settings of SOM.
As seeing from the table, the recognition rate is
not significantly dependent on topology of a competitive layer and initial weights of competitive nodes.
Also the recognition rate became less than that onseven rooms because of many similar rooms inshape.

E-8
E-7

E-9

E-10

E-11

E-12

E-13

E-14

E-15

E-16

E-17

E-18

E-19

E-20

7.4. Recognition with partial action sequences
We made experiments for evaluating recognition
with partial action sequences using twenty rooms in
the last experiment. The results of each room on recognition rate are shown in Table 2, where the topology
of a competitive layer is linear and the initial weightof a competitive node is 1.5 ± 10%.

Table 1
Recognition rates on twenty rooms for various initial weighs,
topologies of a competitive layer
Initialweights (%)

Lineartopology (%)

Circular
topology (%)

0.5 ± 10
1.5 ± 104.0 ± 10

74
74
74

69
74
69

Fig. 12. Twenty rooms.

The average values of recognition rate and partiality
are 60.8 and 47.8%, respectively, wherepartiality (%)
the length of partial action sequence=
× 100
the length of complete action sequence
The reason of deterioration in recognition rate is considered that the procedure in Section 6 sets the undetermined vector values to zero. However, since therecognition rate of a complete action sequence is less

S. Yamada / Applied Soft Computing 4 (2004) 35–47

45

Table 2
Recognition rates on partial action sequences
Room

Recognition rate (%)

E-1
E-2
E-3
E-4
E-5
E-6
E-7
E-8
E-9
E-10
E-11
E-12
E-13
E-14
E-15
E-16
E-17
E-18
E-19
E-20

50
83
100
100
33
33
83
100
100
67
100
83
17
67
17
17
67
17
67
17

than 80%, this rate is not significantly low. Also, seeing from Table 2, the recognition rate strongly depends
on the shape of a room. Recognition of the small rooms
tends to be hard.
7.5. Environments with obstacles
Though the test data used thus far included noise,
it was not so much. In this experiment, we dealt withmore noise like obstacles. We located obstacles in theseven rooms, and a mobile robot did wall-following
in the rooms. The nine complete action sequenceswere obtained and transformed into environment vectors. The environment vectors were given to the SOM
which was trained in Section 2 as test environment
vectors.
As a result, five rooms were correctly identified. Fig. 13 shows success and failure examples. In
Fig. 13(a), the robot correctly recognized the room
including either a single obstacle or two small cubical obstacles on a wall. However, in Fig. 13(b), therobot failed to recognize a room including either twolarge obstacles or an obstacle located obliquely to awall. The large or many obstacles changed the shapeof rooms from the original one, thus we consider the
failure of recognition is natural.

(a) Recognizedenvironments(b) Unrecognizedenvironments

Fig. 13. Environments with obstacles.

The robot can not evaluate the results by itself since
it does not have purpose to recognize the rooms. This
problem will be discussed in next section.

8. Discussions
In this section, we discuss open problems of ourstudy.
8.1. Toward real environments
All the experiments were made in a toy world of
enclosures with white plastic boards. We are planningto make experiments in real world like real office environment consisting of rooms, corridors, desks andchairs. However, we consider the robot used in thisstudy is not adequate for such environment because it
is too small to does wall-following efficiently and effectively in a real room. Thus, we need to implementa suitable mobile robot to such experiments.

46

S. Yamada / Applied Soft Computing 4 (2004) 35–47

8.2. Open environments

9. Conclusion

Though we assume that an environment is a closed
region, a real environment may not be closed, e.g.
a room with doors. The assumption is used only toterminate wall-following. Thus we need to develop amethod to terminate robot’s action in real environments.

We proposed AEM approach to recognize environment and built a mobile robot which learned to recognize rooms from action sequences without teaching.
SOM was used for learning since it was able to generalize an input vector without a teacher. We also developed BI-transformation and a recognition methodwith a partial action sequence. The experiments using
a real mobile robot were made for rooms both withand without obstacles, and we verified the utility of
our approach.

8.3. Restriction on the shapes of rooms
The shapes of rooms are restricted to rectangles
with right corners. If a room consists of curves like acircle, neither the behavior A nor B will be executedand a robot will not use information of corners. In
these cases, since only the length of the periphery is
obtained, the robot can not distinguish a circle from aellipse with the same periphery in length. We need to
improve the behaviors and BI-transformation.
8.4. Suitable behaviors for recognizing
environments
We used wall-following as behaviors for recognizing rooms, however we do not consider it is best one.
There may be a more robust and suitable behavior forcharacterizing environments. Currently, we are developing evolutionary acquisition for suitable behaviors
using genetic algorithm [19].
8.5. What is the identification of environment for
It is a very radical problem that the robot does
not know what it recognizes the environments for.
In supervised-learning, a teacher explicitly tells therobot the class in which the environment should
be included, and thus the robot does not need toknow the purpose. However, an autonomous robot
should have the purpose of recognizing environments, and they it classifies the environments under
the purpose. Since a robot does not have the purpose in our research, it can not evaluate the resultof classifying rooms by itself. Hence, we need togive it the purpose of recognizing environments. It
may be natural to interaction with evolution [20]though the experiments with a real mobile robot are
difficult.

References[1] J.L. Crowly, Navigation of an intelligent mobile robot, IEEE
Trans. Robot. Autom. 1 (1) (1985) 31–41.
[2] A. Elfes, Sonar-based real-world mapping and navigation,
IEEE Trans. Robot. Autom. 3 (3) (1987) 249–265.
[3] A. Elfes, Using occupancy grids for mobile robot perception
and navigation, IEEE Comput. June (1989) 46–57.
[4] M. Asada, Map building for a mobile robot from sensory data,
IEEE Trans. Syst. Man Cybernet. 20 (6) (1990) 1326–1336.
[5] R. Dillmann, F. Wallner, R. Graf, Real-time map refinement
by fusing sonar and active stereo-vision, in: Proceedings ofthe 1995 IEEE International Conference on Robotics andAutomation, 1995, pp. 2968–2973.
[6] S. Yamada, M. Murota, Applying self-organizing networks
to recognizing rooms with behavior sequences of a mobile
robot, in: Proceedings of the IEEE International Conference
on Neural Networks, 1996, pp. 1790–1794.
[7] S. Yamada, M. Murota, Unsupervised learning to recognize
environments from behavior sequences in a mobile robot, in:Proceedings of the 1998 IEEE International Conference on
Robotics and Automation, 1998, pp. 1871–1876.
[8] U. Nehmzow, T. Smithers, Map-building using self-organizing
networks in really useful robots, in: Proceedings of the FirstInternational Conference on Simulation of Adaptive Behavior,
1991, pp. 152–159.
[9] U. Nehmzow, T. Smithers, Using motor actions for location
recognition, in: Proceedings of the First European Conferenceon Artificial Life, 1991, pp. 96–104.
[10] W.D. Smart, J. Hallam, Location recognition in rats androbots, in: Proceedings of the Third International Conferenceon Simulation of Adaptive Behavior, MIT Press, 1994,
pp. 174–178.
[11] M.J. Mataric, Integration of representation into goal-driven
behavior-based robot, IEEE Trans. Robot. Autom. 8 (3)(1992) 14–23.
[12] S. Tsuji, S. Li, Memorizing and representing route scenes,
in: Proceedings of the Second International Conference on
Simulation of Adaptive Behavior, 1992, pp. 225–232.

S. Yamada / Applied Soft Computing 4 (2004) 35–47[13] K. Kato, Statistical analysis of robot behaviors in unstructured
environment, in: Proceedings of Asian Conference on
Computer Vision, 1995, pp. 219–223.
[14] T. Nakamura, S. Takamura, M. Asada, Behavior-based
map representation for a sonar-based mobile robot bystatistical methods, in: Proceedings of the 1996 IEEE/RSJ
International Conference on Intelligent Robots and Systems,
1996, pp. 276–283.
[15] R.D. Berns, U. Zachmann, Reinforcement learning for thecontrol of an autonomous mobile robot, in: Proceedings ofthe 1992 IEEE/RSJ International Conference on Intelligent
Robots and Systems, 1992, pp. 1808–1815.
[16] R.A. Brooks, A robust layered control system for a mobile
robot, IEEE Trans. Robot. Autom. 2 (1) (1986) 14–23.

47[17] E.M. Arkin, L.P. Chew, D.P. Huttenlocher, K. Kedem, J.S.B.
Mitchell, An efficiently computable metric for comparing
polygonal shapes, IEEE Trans. Pattern Anal. Mach. Intell.
13 (3) (1991) 209–216.
[18] T. Kohonen, Self-Organization and Associative Memory,
Springer-Verlag, Berlin, 1989.
[19] S. Yamada, Evolutionary design of behaviors for action-based
environment modeling by a mobile robot, in: Proceedingsof Genetic and Evolutionary Computation Conference, 2000,
pp. 957–964.
[20] D. Ackley, M. Littman, Interactions between learning andevolution, in: Artificial Life II, Addison-Wesley, Reading,MA, 1991, pp. 487–509.