IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 2012

2415

PAPER

Self-Organizing Incremental Associative Memory-Based Robot
Navigation
Sirinart TANGRUAMSUB† , Aram KAWEWONG††,†††a) , Manabu TSUBOYAMA† , Nonmembers,
and Osamu HASEGAWA† , Member

SUMMARY
This paper presents a new incremental approach for robot
navigation using associative memory. We defined the association as
node→action→node where node is the robot position and action is the action of a robot (i.e., orientation, direction). These associations are used
for path planning by retrieving a sequence of path fragments (in form of(node→action→node) → (node→action→node) →· · ·) starting from thestart point to the goal. To learn such associations, we applied the associative memory using Self-Organizing Incremental Associative Memory(SOIAM). Our proposed method comprises three layers: input layer, memory layer and associative layer. The input layer is used for collecting input
observations. The memory layer clusters the obtained observations into a
set of topological nodes incrementally. In the associative layer, the associative memory is used as the topological map where nodes are associatedwith actions. The advantages of our method are that 1) it does not needprior knowledge, 2) it can process data in continuous space which is very
important for real-world robot navigation and 3) it can learn in an incremental unsupervised manner. Experiments are done with a realistic robot
simulator: Webots. We divided the experiments into 4 parts to show theability of creating a map, incremental learning and symbol-based recognition. Results show that our method oﬀers a 90% success rate for reaching
the goal.
key words: navigation, associative memory, neural networks

1.

Introduction

Navigation is a fundamental requirement for mobile robots.
To complete a task, the robot must perform the correct action in the correct location. A navigation system is first required for navigating the robot to the correct place if thecurrent place is not the appropriate one. Fundamentally, anavigation system must achieve three main tasks: mapping,localization, and path planning. Given that the robot is in an
unknown environment, it must first explore such an environment and create a map. However, waiting for a completed
map before localizing itself to such a map is not a good solution. For that reason, the robot must create a map of the unknown environment while simultaneously localizing itself
to a such map. This situation represents the well known Simultaneous Localization and Mapping (SLAM) problem inrobotics. If the SLAM could be solved eﬃciently, then the
Manuscript received January 27, 2012.
Manuscript revised May 8, 2012.
†
The authors are with the Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology,
Yokohama-shi, 226–8503 Japan.
††
The author is with the Department of Computer Engineering,
Faculty of Engineering, Chiang Mai University, Thailand.
†††
The author is with the Materials Science Research Center,
Faculty of Science, Chiang Mai University, Thailand.
a) E-mail: aram@eng.cmu.ac.th
DOI: 10.1587/transinf.E95.D.2415

path planning could also be done easily using some standard
searching technique (i.e. depth-first search). Consequently,
most SLAM descriptions ignore path planning. In addition,
to concentrate on SLAM, most previous works have subsumed guided exploration; the robot is controlled by a human to collect data from an environment [1]–[3].
Studies of SLAM can be divided further into thosewhich do not consider the robot’s action, and those which
do. In the former case, the robot’s action is assumed tobe controlled autonomously by the control laws according to the famous Spatial Semantic Hierarchy (SSH) ofKuipers [4], [5]. Using that assumption, the robot can travelfrom place to place using another module, whereas the
SLAM module specifically examines mapping and localization. Most works of this type particularly assess and examine diﬃculties in scenes (i.e. changes of scenes acrossseasons [6] or time [2]). In the latter case, the robot must
generate some appropriate action to walk in such environments step-by-step. A popular technique for this task isto perform visual servoing [7]. By calculating the geometrical diﬀerences between scenes, the robot knows how tomove from the current scene to the next. Nevertheless, thistechnique requires that the robot store all images as a reference. This might become problematic in large-scale environments where long-term recognition is necessary. Moreover, the calculated scene-to-scene motion must comply
with the robot’s pose estimation. For a large environment,
for which the odometric information is noisy, the pose is difficult to estimate accurately. This is a common problem confronting robotic metric SLAM, which has prompted the useof a second technique: feature-depth approximation. Later,
Clemente et al. [8] estimated the camera’s position using themean of the feature’s depth approximation. This can help
the robot to relocalize its pose whenever normal estimation
fails. However, these two techniques might fail for somecases in which the scene is complex.
As described herein, we address SLAM, in which therobot’s action selection is a main concern. As an alternative to the metrical techniques described above, our method
simply makes use of the associative memory. To move fromscene q to scene f , the robot simply retrieves past actiona, which brought the robot from q to f , and performs sucha retrieved action. For every move it performs, the robot
checks to determine whether the current scene
matches theacorrect one in the association q∧ a→ f (“q−−−→f”) or not.
If it does, then the robot continues retrieving the next asso-

c 2012 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 2012

2416

Fig. 1

System architecture.

ciation. Otherwise, it retrieves another association, whichbrings it to f . That is to say, to navigate from start position
to goal position, the robot must retrieve many associations
action“place1−−−→place2” and link them to form the complete
actionactionaction“path”; place−−−→place−−−→place−−−→ · · · where the first
and the last term of this path respectively signify the startand goal. Doing this presents some advantages over othermethods, especially when the scenes are too complex to perform visual-servoing and feature-depth estimation. Evaluation of the proposed method is done through testing using
a realistic simulated robot in which the environments arepatched with real images. The use of neural-network-based
associative memory, which is a core of this paper, enables
the robot to map environments into the associated patterns
incrementally with actions in an online manner.
To implement the associative memory for the associations, we applied the associative memory using SelfOrganizing Incremental Associative Memory (SOIAM) proposed by Sudo et al. [10] to create a set of association.
Each association comprises nodes representing the clustersof data and edges connecting nodes in the same association
as shown in Fig. 1 (in the associative layer). We used the
SOIAM because it can 1) learn incrementally, 2) realize oneto-many and many-to-many relations, 3) obviate use of priorknowledge, such as the number of clusters, and 4) be tolerant of noise. Moreover, by using this approach, no training
data need to be memorized for cluster determination.
2.

System Architecture

We used the associative memory to create associations forreasoning. The association (a∧ b∧ c · · · →e) comprise of twoparts: a conditional part and a sequential part. In order toconstruct an association, a number of elements, or nodes,
are created corresponding to the number of an association’s
proposition: one element for one term. Directed links are
created to connect each element in the association. For example the rule a∧ b→c can be formed in an association bycreating elements a, b, and c and then connecting a with b
and b with c, or a→b→c.
The feature vector is used to determine the existenceof each element in the association. This is necessary forchoosing an appropriate association for solving a problem.
However, if we insert a new element each time the input datacome, especially in a case where the input data space is large
and continuous, the number of elements in the association

space will become overly large. To reduce this redundancyof elements in the associative space, some data that are very
similar should be grouped together and presented as a single
element. Consequently, we applied the clustering algorithm
in the associative memory.
To implement an associative memory, we divided thesystem into three layers, as shown in Fig. 1. The first layer
is the input layer, whose role is to get the input data. The
second layer is a memory layer. This layer’s role is to cluster input data obtained from the input layer. In this work,
we adapt the SOIAM for clustering. We chose SOIAM inthis work because it is suitable for applications in which theenvironment is expandable or adaptable and new knowledge
can occur. The third layer is an associative layer. This layer
is used for constructing associations among clusters in thememory layer. This layer comprises a number of associations whose elements of the same association are connectedby an edge.
During the training phase, when the input layer receives data, it will send these data to the memory layer forclustering. After finishing clustering, the cluster ID is thenassigned and sent to the associative layer for identifying theelement in the associative layer. After receiving the cluster
ID of all elements in a rule, the association will be established.
3.

SOIAM

SOIAM is a neural-associative memory implemented ona self-organizing incremental neural network (SOINN) [9].
In SOIAM model, each node (or neural cell) of the selforganizing network functions as a decoder, which actively
responds to a particular category of the input signal. Neighbors are defined as correlated nodes, which are connected byan edge. However, in the present study, we use SOIAM as aclustering machine. Therefore, the neighboring relationshipis equivalent to the connection of nodes in the same cluster; nodes connected to each other by at least one path aregrouped in a particular cluster.
The objectives of SOIAM and SOINN are diﬀerent
from other self-organizing maps such as SOM. SOIAM allows network structures to develop automatically rather thanon the basis of predefined information such as the number ofnodes, whereas SOM requires the initial nodes and the structure to be defined in advance. To permit the automatic development of the SOIAM-network structure, Sudo et al. [10]proposed instruction for inserting and deleting nodes andupdating weights.
In order to prevent incremental growth from developing in only one direction, SOIAM allows the removal ofnodes. The criterion for removing nodes depends on thedensity of the node’s area; nodes that are in a low-density
area or that have no neighbors are candidates for removal.
In addition, an edge can be deleted if its age, or the number of references, is not within a threshold interval. The assumption here is that a small number of clusters cannot sufficiently represent areas that contain large amounts of data.

TANGRUAMSUB et al.: SELF-ORGANIZING INCREMENTAL ASSOCIATIVE MEMORY-BASED ROBOT NAVIGATION

2417

Therefore, nodes that are highly referenced are candidates
for separation from their neighbors (by deleting a few edges)
to construct new clusters that can be more specific.
The algorithm for SOIAM will be discussed in
Sect. 4.1.

data: x1 and x2 . Add the new node c1 and c2 to A:

4.

Step 2: Input new pattern x ∈ Rn .
Step 3: Search for the nearest node (winner) s1 and thesecond-nearest node (second-winner) s2 .

Proposed Method

4.1 Memory Layer
The input patterns are memorized and clustered in this layer.
This layer comprises a number of networks (set of nodes
and edges). Each network is used for representing one cluster. The node holds pattern data whose values can be adjusted during the training process, depending on the input
data. If the new input data and the nearest existing node
is not greater than the predefined threshold, the similarity
threshold, then the pattern data which the node carries will
be changed to converge to this new data. Any two nodes
will be determined as the same cluster when there is at least
one path connecting them. In other words, the nodes in thesame network are grouped as the same cluster.
We adapt the SOIAM algorithm for use in this layer.
For the clustering task, the first two input data are inserted
into the network as new nodes in the initial state. After initialization, when input data are sent into the memory layer,
the nearest node (winner) and the second-nearest (secondwinner) node of this input are searched. Insert a new node
into the clustering space if the distance between the input
data and the winner or the second-winner is more than thewinner and second-winner similarity threshold. The weightof this new node is a pattern value of the input data. Its distance threshold is the distance between the winner node andthe new node. The winner node parameter is updated if the
distance does not exceed that of the similarity threshold.
Before explaining how this algorithm is implemented,
some variables are defined as follows as shown in Table 1.
Here is a brief description of our adjusted SOIAM.
Step 1: Initialize a node set A by choosing two input
Table 1

Definition of notation in SOINN.

Wc1 = x1 , Mc1 = 1, Nc1 = 0, T c1 = 0
Wc2 = x2 , Mc2 = 1, Nc2 = 0, T c2 = 0
A = {c1 , c2 }s1 = arg max x − Wc 

(1)

c∈A

s2 = arg max x − Wc 
c∈A\{s1 }(2)Update the accumulated times of winner s1 by
M s1 = M s1 + 1(3)

If s1 or s2 is greater than thresholds T s1 and T s2 , i.e., if
s1 > T s1 or s2 > T s2 , then go to step 4. Otherwise, go tostep 5.
Step 4: Add new node cn to A, i.e. A = A ∪ cn , where
Wcn = x, Mcn = 1, Ncn = 0, T cn = x − W s1 

(4)Then go to step 2.
Step 5: If an edge connecting s1 and s2 does not exist,
then create it and insert set E, as
E = E ∪ e s1 ,s2(5)

Set the age of new edge e s1,s2 to zero.
age(s1 ,s2 ) = 0(6)

Step 6: Increase the age of all edges emanating from s1byage(s1 ,i) = age(s1,i) + 1, (∀i ∈ N s1 )(7)

Step 7: Increase the eﬀective time of all nodes in the
network as
etci = etci + 1, (∀ci ∈ C)

(8)

Step 8: Update the weight of winner and its neighbornodes byW s1 ← W s1 + δ s1 (x − W s1 ),Wt ← Wt + δt (x − Wt ), ∀t ∈ N s1

(9)
(10)

Where
δ s1 =

1
M s1

(11)

Step 9: Remove edges whose age is greater than a predefined age threshold.
Step 10: Remove the isolated nodes whose eﬀective
time is greater than the eﬀective time threshold from A: remove {ci }, where ci is a node whose Nci  ≤ 1 and etct are
greater than the eﬀective time threshold. Go to step 2 if the
training does not finish. Go to step 11 if the last data point

IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 20122418

is already trained.
Step 11: If the number of nodes in cluster ci is greaterthan the node limitation threshold, randomly delete a node inthat cluster until the number of nodes is equal to the threshold
Note that after completion of the training process, a
representative number or cluster ID will be assigned to every
cluster in the memory layer. This number will be used as acluster reference in the associative layer.
A new cluster can be created by inserting a new node.
The similarity threshold is used for controlling the node increment. A new node is easy for inserting if the value of thisthreshold is small. On the other hand, if this value is large,
it is diﬃcult to insert. For this work, we define the similarity
threshold of each node ci as follows.
⎧⎪
if Nci  ϕmax c , c ⎪⎪⎨ ct ∈Nci i j(12)
T si = ⎪⎪⎪⎩ min ci , c j  if Nci = ϕc j ∈A\{ci }Therein, ci , c j  is a distance between ci and c j . In thiswork, we use the Euclidean distance to estimate this value.
The other threshold is the age threshold (in step 9).
An edge whose age exceeds this threshold will be deleted.
Therefore, the element of the same cluster can be changed
during the training process.
4.2 Associative Layer
This layer is used to construct the associations between each
network in the memory layer following the association ruleaq∧ a→ f (“q−−−→f”). As mentioned in Sect. 4.1, the memory
layer is a collection of networks. To construct the associations in the associative layer, we define a node element torepresent a network in the memory layer that ignores thedata type of network. An edge in the associative layer isused to connect two nodes to show the associations between
networks in the memory layer. For example, if there is an association rule a∧ b→c (where a, b and c represent networks
A, B and C of the memory layer, respectively), and then directly connecting them with edges, e.g. a→b → c.
In order to refer to a network in the memory layer,when the input layer receives data, it searches for the nearest
nodes in the memory layer. The cluster IDs for the nearest
nodes (for example a, b, and c) are then submitted to theassociative layer for constructing (in the training phase) or
recalling (in the testing phase) an association.
In this work, we defined a predefined threshold, agethreshold, and a parameter, age, for each association. Before
a new association is created, the system will check whether
the input association already exists in the associative layer.
A new association will be created and the age parameter is
set to 1 if this association is not created in this layer. On
the other hand, if the association already exists, then thisage parameter will be increased by 1. In the case wherea new association conflicts with the learned one, e.g., anassociation of a∧ b→c exists in the associative layer. Thenthe association of a∧ !b→c arises, and the age of the old one

will be decreased by 1. These associations will be deleted if
associations exist for which the age parameters are less than
the age threshold. This prevents incorrect rules because of
the error of the input data or the memory layer.
4.3

Applying the Associative Memory to a Robot Navigation Problem

We solve the problem of path planning from a start to goal
position by searching for a sequence of path fragments. Thiscan be viewed as solving a big problem by dividing it into
a set of sub-problems and trying to solve each. To solve a
sub-problem, finding a short path between two near positions, we use pattern-based reasoning by defining a set of
associations as:q∧a→ f
The q represents the “from-position” or current position of the robot. The term a is the term of robot action,and f is the “to-position” term. This association can be interpreted as “when the robot is at position q and then does
action a, the robot will go to position f ”. The image features are used for representing the “from-position” and “toposition” terms, and the 2-tuples of the left and right robot
wheel degrees are used for representing a robot action, i.e.
(L, R) = (1.00, 0.998). The robot will learn these association
sets using the associative memory proposed in the previous
section.
The system architecture is divided into three layers, as
discussed in Sect. 2: the input, memory, and associative layers. However, because the input data to the input layer canbe considered as two groups, the image feature and action
feature, and the characteristic of data of these two types differs greatly, the input layer is separated into two parts forhandling these two data. The same is done for the memory layer, in which the image feature and the robot action
feature are clustered separately. Therefore, the system architecture can be viewed as presented in Fig. 2. Moreover,because the association for robot navigation task comprises
only three elements—from-position, action, and to-position
elements—an association in the associative layer is thencomposed of three elements for each rule too.
During the training phase, we let a robot walk in a random direction, for which the direction space is continuous ina plane. For each move of a robot, three data are recorded:

Fig. 2

The architecture for a robot navigation task.

TANGRUAMSUB et al.: SELF-ORGANIZING INCREMENTAL ASSOCIATIVE MEMORY-BASED ROBOT NAVIGATION

2419

Fig. 3 Overview of how the system generate association rules in theassociative layer.

a current position image, a robot action, and a next position
image. The image feature is then extracted from these two
images and the robot action is transformed into a 2-tupleof left and right robot wheels. For example, if F(p) is theimage representative of position p and Q(a) is a parameterof robot action a. The input data for the input layer willbe (F(p1 ), Q(a1 ), F(p2 )) for one move (The current position
p1 , do action a1 and then go to the next position p2 ). These
three data (F(p1 ), Q(a1 ), F(p2 )) are submitted sequentially tothe input layer (starting from the image feature of the current position F(p1 ), the 2-tuples of robot action Q(a1 ), andthe image feature of the next position F(p2 )) as shown in
Fig. 3. Each time the input layer receives data, it will send
these data to the memory layer for clustering data. When all
three data for one move are already clustered, the cluster IDsof this three data obtained from the memory layer are sent
to the associative layer for creating an association of thesethree data.
In the robot navigation process, we divided the process into two steps, exploration step and path/action planning step as shown in Fig. 4. The first step is an exploration
step. The robot will randomly survey an unknown area, collect data and construct the associations. The map is thenconstructed from these associations (explained in the next
section) in the path/action planning step. After the exploration step, the robot will use the map to find a path fromstart to goal position and use the learn association rules toplan a sequence of actions.
4.3.1 Map BuildingThis can be done by constructing a topological map in which
a node represents a position and a link shows a path between
positions. For each association, an edge is created between
an origin position q in the conditional part and a destination
position f in the sequential part. Each edge is labeled using
a robot action for going from q to f . This label is derived
from the action in the conditional part of the rule. This map
will be used for path planning in the robot navigation task.
In our former work [13], we showed the use of our

Fig. 4

Robot navigation process.

proposed method to construct a topological map for robot
navigation, and compared the eﬃciency of creating a map
to other online incremental learning methods. According
to this work, Fig. 5 (a) shows the result of networks in thememory layer and Fig. 5 (b) shows the map constructed bythis network where the labeling numbers are cluster ID in
the memory layer.
4.3.2

Path and Action Planning

In the robot navigation task, we first begin with receiving
images of start and goal positions and then extract their image features. To find the position of start and goal in a map,the nearest image clusters of the start and goal positions aresearched. The cluster IDs are used to identify the positionin the topological map. We define the cluster feature as thenode which is closest to the mean of all nodes in that cluster.
wprototype = wmin D(Wmean,Wm) (m ∈ C)

(13)

After the start and goal positions are identified on the
topological map, a path sequence is then determined from a
pre-existing map by using a shortest-path algorithm similar
to Dijkstra’s algorithm. Then, the associations are selected
to plan a sequence of robot actions. For example, if therobot wants to go from position M to destination P by using the path sequence M→N→O→P, the associations areused to determine which actions the robot should perform
to go from M to N, N to O and O to P. To do this, therobot selects the association that has the start position in the

IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 2012

2420

Fig. 6E-puck robot.

collected images and robot actions are then submitted to the
input layer in the associative memory and clustered in thememory layer. The associations are constructed in the associative layer after receiving the cluster ID of all elements for
one association from the memory layer. A map is createdfrom these if–then rules, as discussed in Sect. 4.
The experiments are divided into four parts. The firstexperiment shows the association and map result. The second experiment specifically examines incremental learning
for associations and map building. In the third experiment,
we test our method for symbol-based recognition tasks. For
the last experiment, we combine all abilities of three previous experiments and present the accuracy of path planning.
Fig. 5Map topology created by our method [13].

conditional part and the neighbour position in the sequential
part. The sequence ends with the association containing theimage cluster of goal position in the sequential part.
During moving from one position to the neighbor position, the clusters of the images taken while the robot walking are searched for localizing the robot’s current position.
To check whether the robot is oﬀ of the map, the distancethreshold σr is used. The system will assume that the localization fails and stop finding a path if wi , wm  is greaterthan σr .
5.

Experiments

5.1 Experiment Setup
We conduct the following experiment to show that our proposed method, which uses the associative memory implemented on SOIAM, can solve the robot navigation task. The
experiments are done based on the use of a Webot robot simulator [5], [6]: a realistic 3D physical simulator from which
the system can be transferred easily to a real robot. To render the simulated world as realistic in terms of visual scenes,
we used images collected from the Suzukakedai Campus asobject textures in this simulated environment.
We assume that the robot had no knowledge about theplaces in the initial stage. The robot must create a map andassociation rules for this place by walking around it, collecting images and recording robot actions while walking. The

5.1.1

Simulation and Real-World Environments

In our experiment, not only all images are captured fromthe real-world with a poor quality camera with low resolution but we also add noise to these images in the Webots
simulator. In [11], the authors claim that the performancegap between simulation and real-world will decrease significantly by introducing a ‘conservative’ form of noise in
the simulation. This concept is agreed by [12], which emphasizes the failure of the simulation when it encountereda real-world environment. In their experiment, the authors
also added noise to the simulated environment and tested iton the Webot simulators identical to that used in our experiment. By adding noise to the simulated data, our simulation
environment will more closely resemble the real-world environment.
5.2

Images and Robot Action Feature

The images used in the experiments are collected by an epuck robot, as shown in Fig. 6. The e-puck robot is simulated by the Webot program. The images are captured asgrayscale images with a 40 × 40 resolution. Moreover, we
capture sub-images of each image for clustering in the memory layer. These sub-images are captured with a 24 × 24
resolution sliding window, which was moved in arbitrary directions throughout the original image. In our experiments,
40 images of an environment are first captured by the Webot
program, and then 20 sub-images per original image are captured, for a total of 800 sub-images. These sub-images are

TANGRUAMSUB et al.: SELF-ORGANIZING INCREMENTAL ASSOCIATIVE MEMORY-BASED ROBOT NAVIGATION

2421

used as training data. For testing data, we perform the sameprocess as that used for the training images: a robot takes
an image with 40 × 40 resolution, creating a sliding window
with 24 × 24 resolution and then captures only one image
from this window at the center of the original image.
To represent the images, we simply use the image pixel
as a feature vector. The feature vectors of the sub-images
are represented using 576 dimension vectors. These vectors
are then used as input features in the input layer.
The action feature is represented by the coordinate(Left, Right) or (L, R) which respectively identifies the degree of left and right wheel of robot. These values are continuous values varying from −1 and 1.
5.3 Experiment1: Associations Creating Experiment
In this experiment, we specifically examine the associations
used for robot action planning and a navigation map. Figure 7 shows that we simulated the location for robot exploration task. Figure 8 shows four blocks created and textured
using images taken from Suzukakedai campus.
Considering the clustering result in the memory layer,
the network size is reduced because SOINN combines similar input features into the same cluster. Experiment results
demonstrate that the memory layer clusters the image data
into 11 clusters. A picture of each representative cluster
is shown in Fig. 9. Figures 10 and 11 depict the associations obtained respectively from the associative layer anda map of the simulated place. In Fig. 11, the numbers in
the figures are the IDs of clusters in the memory layer, thered line shows the directions of the robot’s left turns, e.g.,(L, R) = (−1.00, 1.00), and the green line shows the direc-

tions of the right turns, e.g., (L, R) = (1.00, 0.998). For example, the robot must perform a right-turn action, or set thecoordinates (L, R) to (1.00, 0.998), to move from the position at cluster 43 to the position at cluster 33.
To find a path using associations and a map, we select the first image that the robot took at the training step
as a start point and chose the 40th and 100th images as
goals. The associations are used for determining the action sequence of the robot; a map is used for finding theshortest path, a set of path fragments, to progress to thedestination. Figure 12 portrays the experiment result ofaction sequence for reaching the goal derived from the40th image (Fig. 12 (a)) and 100th image (Fig. 12 (b)). In
Fig. 12 (a), a robot begins with action (L, R) = (−1.00, 1.00)
and takes other actions until it reaches the goal. As shown in
Fig. 12 (b), a robot starts with action (L, R) = (−1.00, 1.00)
and then does the action (L, R) = (0.998, 1.00) and subse-

Fig. 9Fig. 10
Fig. 7

Fig. 8Cluster representatives.

Associations result.

Simulated location created by Webot.

Images used for map simulation in Webot.

Fig. 11

Map topology created using our proposed method.

IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 2012

2422

Fig. 12 Robot action sequences: (a) 40th trained image defined as thegoal; (b) 100th trained image defined as the goal.

quent actions until it meets the goal. This action sequence isconsidered from the shortest path searching algorithm.

Fig. 13 Environment used for each training phase (a) for the first training
phase and (b) for the second training phase.

5.4 Experiment 2: Incremental Learning Experiment
In this experiment, we will verify that our proposed method
can learn incrementally. In this experiment, we set the environment in the same way as in the previous experiment(Fig. 7). Blocks labeled as “1” and “2” (from simulated textures) are created for a start and goal position.
We divided the learning phase into two phases. In thefirst phase, we inserted a red wall as shown in Fig. 13 (a)and let the robot start exploring the place at the center. The
robot cannot go across to the right side. After finishing thefirst phase, the second phase is begun. In this phase, weremove the red wall; then we add a blue wall instead, as
shown in Fig. 13 (b). Again, the robot cannot go to the left
side during training in this phase. To create a map of thewhole place, the knowledge from the first and second training phases must be combined. It might be readily apparent
that the robot cannot find a path from block “1” to “2” if therobot learns knowledge from only one phase. This can beviewed as incremental learning. The knowledge is increased
after finishing the second phase.
We let the robot find a path from block “1” to block “2”.
Images of blocks “1” and “2” are used to identify the startand goal. The robot will then find the start and goal positions
in a map, localize, and then find the shortest path linking
them. The result of the experiment is depicted in Fig. 14.
First, the robot is in the start position. It then does action(L, R) = (0.999, 0.997) to proceed to the next position. Sub-

Fig. 14

Experiment results for incremental learning experiments.

sequently, the robot does actions (L, R) = (−0.997, 0.998),(L, R) = (−0.997, 0.998) . . . until it reaches the goal.
5.5

Experiment 3: Symbol-Based Recognition Experiment

In previous experiments, we used images to identify a startand goal. This can be viewed as a pattern recognition task.
To demonstrate that our proposed method also works withsymbol-based recognition, we named the positions in thesimulated place using words and then used these words torefer to the positions.
For this experiment, we changed the simulated environment as shown in Fig. 15 (a). Eight blocks exist in thissimulated place. Figure 15 (b) portrays that the four blocks
are textured using real-world images. The other four blocks
are textured using simulated images of the numbers “1”,“2”, “3”, and “4”, labeled respectively with the JapaneseTANGRUAMSUB et al.: SELF-ORGANIZING INCREMENTAL ASSOCIATIVE MEMORY-BASED ROBOT NAVIGATION

2423

Fig. 15 Experiment environment (a) simulated location created by
Webot, (b) image used for map simulation in Webot.

Fig. 17 Experiment results for the command (a) “ichi kara ni e ite” (gofrom number one to number two), and (b) “san kara yon e ite” (go fromnumber three to number four).

sentences such as “ichi kara ni e ite” which means “go fromnumber one to number two”. The experiment result is depicted in Fig. 17, where Fig. 17 (a) shows the result from thecommand “ichi kara ni e ite” (go from number one to number two) and Fig. 17 (b) from the command “san kara yon eite” (go from number three to number four).
5.6

Fig. 16 Training images of simulated blocks, which are labeled as(a) ichi (one), (b) ni (two), (c) san (three), and (d) yon (four).

words “ichi”, “ni”, “san”, and “yon” which respectively
mean “one”, “two”, “three”, and “four” in English. The images used to train these positions are shown in Fig. 16.
To define the start and goal position, we use JapaneseExperiment 4: Combined Experiments

In this experiment, we combine the abilities of our proposed method from all previous experiments, i.e. if–thenrules and map building, incremental learning, and symbolbased recognition. The environment used for this experiment is also the same as the environment used in the third
experiment, which is depicted in Fig. 15. However, the difference of this experiment from all previous experiments isthat the robot does not move in a random direction. Instead,a human guides it. In this experiment, we view the blocks
labeled as numbers (i.e. 1, 2, 3, and 4) as boxes and also
named these boxes with the words “one”, “two”, “three”,
and “four”. The training phases are divided into four phases
for each box. Each phase is begun by letting the robot in thecenter of the place, turning the robot around; then guiding
the robot to a box. The turning direction is determined fromthe box number. The turning direction is counterclockwise
if the box number is an even number; the turning direction isclockwise if the box number is an odd number. When finishing a training phase, the robot will be restarted at the centerof the place again and then begin the next phase in the samemanner for the next box.

IEICE TRANS. INF. & SYST., VOL.E95–D, NO.10 OCTOBER 2012

2424
Table 2Path planning accuracy.

To test whether the robot can find the correct path basedon this learning, we let the robot start at the center of room ina random direction. We used the room name (i.e. one, two,
three, or four) to specify a goal. The accuracy is measured
by counting the times that a robot goes in the correct pathand comparing them with the total number of times. The
experiment results are presented in Table 2.
5.7 Discussion
We divided the experiment into four parts to show the abilities of our proposed method. The associations, the relationsof each element in the associative layer (the associations),
are used for determining a robot action sequence and map
building. Both associations and the map are used together
for path planning. A map is used for finding a set of pathfragments and associations are used for finding an action foreach path fragment, as shown in the first experiment. Because the SOIAM is designed for handling pattern data, theinput data value can be continuous. Therefore, our proposed
method can accommodate the continuous action space of arobot. In other words, the robot can move in an arbitrary
direction in a planar fashion. Moreover, SOIAM combines
similar data into one group. Therefore, the robot need notmemorize all input data. This alleviates the use of muchmemory, especially when the place is extremely large.
Considering computation time, our method requires
approximately 16 seconds to construct a map. Thus, ourmethod is superior to other incremental learning methods,
such as Incremental Spectral Clustering (ISC), which require more than 400 seconds to solve the same task (discussed in [13]). Since the topological map is constructed after the exploration step, the time required for path planning
is very fast. For searching the shortest path, our method required less than 2 minutes to find a complete path from thestart to goal position.
Because SOIAM is an unsupervised learning processthat requires no prior knowledge, our method can learn incrementally. The robot can integrate the new knowledge it
obtains into previous knowledge, as shown in the second experiment. Results of the third experiment show that our proposed method can also work for symbol-based recognition,
which can be done by binding the symbol to the training data
during the learning phase. In this work, we used the word
as the symbol of the position and used it to refer to places:
start and goal positions.
All three of the first experiments were done with noguidance from a human. The last experiment diﬀers fromthe other experiments. The human guides the robot to walkto each position in the simulated place and uses words as
symbolic representations of respective places. In this experiment, the robot must combine all abilities by collecting
information every time the robot visits a new place, developing a map and if–then rules, and also binding the symbol
to the memorized pattern in the memory layer. The experiment results show that the accuracy of path finding is approximately 90%.
5.8

Future Work

Because our experiments use a simple image representation,
they are based on the assumption that the execution lengthsof all the actions performed by the robot are identical. Our
experiments can be modified easily to reflect more complicated image features, as long as they can be represented byreal number vectors. Moreover, the length of execution canbe varied according to the level of diﬃculty in navigation
depending on factors such as energy or obstacles, e.g., byadding weights to Dijkstra’s algorithm.
The main focus of the present study is to propose usage of associative memory to search for a route, to retrieve
the corresponding action sequence for navigating along thisroute, and to build a map. However, for use in real robots,
some functions should be added. One example would bepermitting to change the views because of the robot’s movement or a dynamic environment in crowded areas. The
present study only intends to introduce a novel learning
method for robot navigation and has scope for further development.
This work is part of a project that is aimed at using
animals for automatic map generation. The proposed navigation system is intended for use with a camera mounted
on pets, such as dogs or cats, in order to acquire mapping
information. We anticipate two benefits from this project.
First, the project advances the study of navigation behavior
and capability of animals. Second, new environments canbe mapped rapidly with real animals instead of robots.
6.

Conclusion

We have proposed a novel-online-incremental learning
method for robot navigation based on associative memory.
The focus of this study is to discover a path and plan appropriate actions through incremental learning. A long path isdivided into a sequence of sub-paths, which are then correlated with a sequence of actions for performing navigation.
The correlation between a sub-path and its action is introduced in the form of an association place1→action→place2,
which is learnt using SOIAM. The advantages of SOIAM
are that it can learn incrementally, can tolerate noise, anddoes not require predefined knowledge.
We conducted four experiments to show the capabilities of our proposed method for vision-based robot navigation. These experiments produced examples of the associ-TANGRUAMSUB et al.: SELF-ORGANIZING INCREMENTAL ASSOCIATIVE MEMORY-BASED ROBOT NAVIGATION

2425

ations that our proposed method learnt through an implementation using a Webot simulated robot. The robot could
use these associations to navigate from one place to anotherwithout human intervention. In addition, the experiments
also demonstrated that these associations can be learnt incrementally and can be applied to symbol-based recognition.

Sirinart Tangruamsub
received the B.S.
degree in Computer Engineering from Chulalongkorn University in 2005, and M.S. degreefrom Chulalongkorn University in 2008. In
2011, she obtained her Ph.D. in Departmentof Computational Intelligence and Systems Science from Tokyo Institute of Technology.

Acknowledgement
This research was supported by Japan Science and Technology Agency (JST) CREST Project, and by the research
grants from National Research University Project under
Thailand’s Oﬃce of the Higher Education Commission.
References[1] A. Pronobis, B. Caputo, P. Jensfelt, and H. Christensen, “A discriminative approach to robust visual place recognition,” Proc. IEEE/RSJ
Int’l Conf. Intelligent Robots and Systems, 2006.
[2] M. Ullah, A. Pronobis, B. Caputo, J. Luo, P. Jensfelt, and H.
Christensen, “Towards robust place recognition for robot localization,” Proc. IEEE Int’l Conf. Robotics and Automation, pp.530–537,
2008.
[3] M. Cummins and P. Newman, “FAB-MAP: Probabilistic localization and mapping in the space of appearance,” Int. J. Robotics Research, vol.27, pp.647–665, 2008.
[4] B. Kuipers, “The spatial semantic hierarchy,” Artif. Intell., vol.119,
pp.191–233, 2000.
[5] B. Kuipers, J. Modayil, P. Beeson, M. MacMahon, and F. Savelli,“Local metrical and global topological maps in the hybrid spatial
semantic hierarchy,” Proc. IEEE Int’l Conf. Robotics and Automation, pp.4845–4851, 2004.
[6] C. Valgren and A. Lilienthal, “Incremental spectral clustering andseasons: Appearance-based localization in outdoor environments,”
Proc. IEEE Int’l Conf. Robotics and Automation, pp.1856–1861,
2008.
[7] T. Goedeme, M. Nuttin, T. Tuytelaars, and L.V. Gool, “Omnidirectional vision based topological navigation,” Int. J. Comput. Vis.,vol.74, pp.219–236, 2007.
[8] L. Clemente, A. Davison, I. Reid, J. Neira, and J. Tardos, “Mapping large loops with a single hand-held camera,” Proc. Robotics:
Sciences and Systems, 2007.
[9] F. Shen and O. Hasegawa, “An incremental network for online unsupervised classification and topology learning,” Neural Netw., vol.19,
pp.90–106, 2005.
[10] A. Sudo, A. Sato, and O. Hasegawa, “Associative memory for online
learning in noisy environments using self-organizing incremental
neural network,” IEEE Trans. Neural Netw., vol.20, no.6, pp.964–
972, 2009.
[11] M. Olivier, “Webots: Symbiosis between virtual and real mobile,”
Robots, Lect. Notes Comput. Sci., vol.1434, pp.254–263, 1998.
[12] P. Jim and M. Alcherio, “The cost of reality: Eﬀects of real-worldfactors on multi-robot search,” IEEE International Conference on
Robotics and Automation, pp.397–404, 2007.
[13] S. Tangruamsub, M. Tsuboyama, A. Kawewong, and O. Hasegawa,“Mobile robot vision-based navigation using self-organizing and incremental neural networks,” Proc. International Joint Conference on
Neural Networks, pp.3094–3101, 2009.

Aram Kawewong
received the B.Eng.
degree in Computer Engineering from Chulalongkorn University in 2005, and M.Eng. degreefrom Tokyo Institute of Technology in 2008. In
2010, he obtained his Ph.D. in computational intelligence and systems science from the same
university. He is currently a lecturer at the department of computer engineering, Chiang Mai
University. His research focuses on robotics
navigation and computer vision.

Manabu Tsuboyama
received the B.S. degree in Electrical Engineering from Tokyo University of Agriculture and Technology in 2007,
and M.S. degree in Computer Engineering from
Tokyo Institute of Technology in 2009. He
is currently working for Keyence Co. Ltd. inJapan. He is interested in autonomous mobile
robot path and movement planning.

Osamu Hasegawa
received his Dr. Eng.
degree in electronic engineering from the University of Tokyo in 1993. He was a research scientist at Electrotechnical Lab (ETL) from 1993
to 1999 and at Advanced Industrial Science andTechnology (AIST) from 2000 to 2002. From1999 to 2000 he was a visiting scientist at the
Robotics Institute, Carnegie Mellon University.
In 2002 he became a faculty member of the
Imaging Science and Engineering Lab, Tokyo
Institute of Technology. In 2002, he was jointly
appointed researcher at PRESTO, Japan Science and Technology Agency(JST). He is a member of the IEEE Computer Society and IPSJ.