Environmental Change Adaptation for Mobile Robot Navigation
Takashi Minato and Minoru Asada
Dept. of Adaptive Machine Systems
Graduate School of Engineering
Osaka University
Suita, Osaka 565-0871, Japane-mail:minato@er.ams.eng.osaka-u.ac.jp,asada@ams.eng.osaka-u.ac.jp

Abstract
Most of existing robot learning methods have considered the environment where their robots work unchanged, therefore, the robots have to learn fromscratch if they encounter new environments. This paper proposes a method which adapts robots to environmental changes by eciently transferring a learned
policy in the previous environments into a new one ande ectively modifying it to cope with these changes. The
resultant policy (a part of state transition map) does
not seem optimal in each individual environment, but
may absorb the di erences between multiple environments. We apply the method to a mobile robot navigation problem of which task is to reach the target avoiding obstacles based on uninterpreted sonar and visualinformation. Experimental results show the validity ofthe method and discussion is given.

policies in terms of each individual environment
to accomplish a given task in various kinds of environments.
To cope with therst problem, Thrun et al. [4, 3, 5]

proposed \lifelong learning" which accelerates thelearning by storing invariant knowledge for a classa priori knowledge in new environments categorized intoof environments in advance and reuses it as

the same class. Their methods need a clear de nition

for the class of environments to obtain the invariant
knowledge, and therefore, no learning seems necessary
in new environments but just implementation of theplanned navigation.

Tanaka and Yamamura [2] ap-plied the similar idea to a simple navigation task ona grid world using a reinforcement learning method,in which the knowledge invariant in previous (n 0 1)

environments are extracted in advance and checked inthen 0 th environment if it is e ective or not. Thesemethods might accelerate their learning, but the robot

1 Introduction
In order for not only biological systems but also arti cial systems, typical example of which is a robot
system, to adapt themselves to changes in di erent
environments, learning and development are essential
processes.

Conventional robot learning methods tocope with such changes employ multiple modules eachof which corresponds to one or a class of environments
so as to achieve the goal in each environment. However, such methods immediately su er from two serious problems:

 It takes enormous learning time because the robot

must have many policies corresponding to the individual environments, respectively, and therefore thesecond problem has not been addressed.
In this paper, we propose a method which adapt
robots to environmental changes by transferring a Qlearned policy in the previous environments into a newone and modifying it to cope with these changes. The
resultant policy (a part of state transition map) does
not seem optimal in each individual environment, but
may absorb the di erences between multiple environments. We apply the method to a mobile robot navigation problem of which task is to achieve the target avoiding obstacles based on uninterpreted sonarand visual information. The diculty of this task is

has to learn from scratch if it encounters new en-twofold: 1) roles of multi-modal sensory information

vironments due to the lack of knowledge on them.

have not been assigned in advance, therefore the robot
has to determine how to use the multi sensory informa- It needs large capacity of memory and processing

tion, that is, the sensory information is uninterpreted,modules since the robot must have a variety ofand 2) both target reaching and obstacle avoidancetasks have to be achieved simultaneously. Nakamura
et al. [1] considered the above two issues, but theirrobot has to learn from scratch if it encounters di erent environments.

3 Task, Robot, and Assumptions

3.1 Our Robot

Another important issue in applying Q-learning to

Our robot has a Power Wheeled Steering (PWS)

real robot tasks is how to construct the state space on

system driven by two motors into each of which we

which the learning seriously depends. Too large state

can send a motor command, independently.

space causes enormous learning time while too com-experiment, we quantized each motor command into

pact one causes serious aliasings. Therefore, adequate

three levels which correspond to forward, stop, andstate space is necessary to be found. In [4, 3, 5, 2, 1],backward, respectively. Totally, the robot has 9 ac-

the state space is given intions.

Here, we attempt ata priori by human designer.

nding a compact but seemingly

In ourThe robot is equipped with a ring of 12 ultrasonicadequate state space by searching for combinations ofranging sensors (ranging from 0.0 to 300

sensory features.

has a

eld view of roughly 30cm) which(see Figure 1(a)). The

The reminders of this article is structured as fol-robot is also equipped with a color CCD camera. Im-lows. First, a brief summary of reinforcement learn-age processing procedure provides the position and theing, especially Q-learning is given. Next, task and as-

size of the target area in the image as visual informa-

sumption are given and the process ofnding a statetion(see Figure 1(b)). However, it cannot detect ob-

space is shown. Then, the method for environmental

stacles, because it is not given how obstacles can bechange adaptation is explained. Finally, experimentalseen.

results are given to show the validity of the methodand discussion is given.

3.2 Task
The task of the robot is to reach the target while

2 Basics of Q-Learning

avoiding obstacles as shown in Figure 2.
et al.

Nakamura[1] has demonstrated a limited ability coping

Q-learning is a form of model-free reinforcementwith the above problems in a single isolated environ-learning based on stochastic dynamic programming.

ment, but they su ered from the curse of dimension

It provides robots with the capability of learning toproblem, a huge state space. In addition to this, theact optimally in a Markovian environment.

environment may change in a few ways here:

sume that the robot can discriminate the set
tinct world states, and can take the set

We as-S of dis-A of actions on

the world. A simple version of a Q-learning algorithm
used here is shown as follows.
1. Initialize

Q(s; a) to 0 for all state s and action a.

2. Perceives current state
3. Choose an actions.

1. con gurations of the target and obstacles maychange, and2. the number of obstacles also changes.
Therefore, a learned policy obtained in a single environment may not be applicable to di erent environ-a according to action value func-tion.

a in the environment. Let thenext state be s and immediate reward be r .

4. Carry out action

ments, and usually it takes enormous learning time if
the robot learns from scratch.

3.3 State Vector Selection

0s; a; s ; and r,05. Update action value function fromQt+1(s; a)=(1 0rQt(s; a)t)

+ t( +wheremaxt is a learning rate andcounting factor between 0 and 1.
6. Return to 2.

Aa0 2

As mentioned above, the state space construction
problem is one of the most serious issues in reinforcement learning even in an isolated single environment.

Qt (s ; a ))is a00Since our robot has a considerably large sensor space,
we have to build a reduced-size state space from theoriginal sensor space. As primitive features, we havexed dis-selected the center position

gx and the height gh of thetarget image from vision as image features, and followings (Table 1) from sonar pro le as sonar features (seeFigure 3).

Table 1: sonar features

dmindmaxdmean
ddif fProfile of Distance
30deg

0 1

1110Sonar sensor

minmaxmeandif f

11102349range feature
minimum range value
maximum range value observed
mean range value observed

dmax 0 dmin

direction feature

dmin
dmax
mean between min and max
width between min and max
direction of
direction of587(a) sonar

dd limitd max
Targetgx

Obstacle

Camerad diffd meand min

diffminmean

max

60deg

gh

Figure 3: Primitive features from sonar pro le

Image Plane
Since these features still consists a large feature(b) vision

space, we have constructed several spaces as the combinations of one or two image features and one or two

Figure 1: Sensory information

sonar features, and applied Q-learning to the robots
having each state space in a single environment (seeFigure 2). Here, we have appropriately quantized eachstate space under a constraint of the maximum number of substates to realize physical memory capacity

Targetconstraint.
which

Obstacle

Figure 4 shows the success rates by ap-plying each obtained policy to the environment, indnone and none means no features. Hereafter,

we de ne the success rate as (number of successful

reach

avoid

target reaching)/(trials). In Figure 4, feature vectors
including

Obstaclemin show high success rates regardless of

the range features, which means that the robot pays
its much more attention to the direction of the minimum range value than to the value itself. According

Mobile Robot
Figure 2: Task and environment

to the result of these analysis, we have selected thefollowing state vector

0x for the task.

x = gx gh min dmin

1T(1)stroyed.

Environment 14060

30

4020
10min

20

mean0d noned diffd max

d mean ddiffnoneminstartmin

a2

Feasible Patha1

mean0d none d diffmax(a) gx ; 3 ; d3

goalmaxdmax

dmeand min

Optimal Path a3

diffnone(b) gh ; 3 ; d3StateAction

Environment 280

a3

Feasible Path60

a1a2 fail!

40
min

20

mean

0d none d diffOptimal Pathmax

dmax

dmean

d min

diff
none

Figure 5: Not an optimal path but a feasible one can(c) gx ; gh ; 3 ; d3

be found.

Figure 4: Performance of each state space

The algorithm is as follows:
1. Quantize the state space as

4 Environmental change adaptation

2. Apply Q-learning to the initial environment, andobtain the policy

The basic idea to accelerate the learning and to savememory is to adapt a robot to a new environmentby transferring the Q-learned policy in the previous
environments and modifying it to cope with environmental changes. The robot realizes the environmental changes by a drop of the success rate. Unless thesuccess rate drops, the robot does not realize the environmental change even if the environment actuallychanges.
If the robot realizes the environmental change, it relearns the policy of the states where it fails to achieverateRS .

3. Apply

P to any environment unless RS decreases.

RS decreases, then nd states S r  S whereP fails to achieve the goal, and modify P for suchstates by applying Q-learning as follows until RS

4. If

recovers to pre-speci ed adaptability rate
5. Apply Q-learning toifs 2 S r [ S u follow the normal action

makes a collision with the obstacles)

otherwise follow

at the stateP6. Go to 3 with the obtained policy
The adaptability rate

P.

determines the extent towhich re-learning occurs, that is:

RSd = RSc +changes by modifying the policy around states where itfails. However, there is in practice a trade-oSu  Sdenotes inexperienced states.

in the environment 1 (optimal path), the robot fails

is expected that the robot adapts the environmental

S r  S . Action selection

selection in Q-learning, wherepolicy in the environment 2 which has been obtained

not optimal but feasible in the both environment. It.

during the learning is as follows:ments which have di erent state transitions. Using theA. Then the robot re-learns the policy
only around state A so that it can achieve the goal
and as a result, it nds the policy A ! a2 , which is

P : S ! A(A:action set) until

the success rate exceeds the pre-speci ed successthe goal. Figure 5 shows an example of two environ-the task (e.g.

S.

to what(RSp 0 RSc );(2)

RSp ; RSc and RSd denote the success rates inextent the current policy can be modi ed. Then, wewhereintroduce the adaptability rate

the previous environment, in the current one, and theby which the robot

controls to what extent the previous policy can be de-desired one, respectively.

Based on the selected state vector, we apply the5400 (case 1) trials and 1900 (case 2) trials werealgorithm to the given task with the following speci -needed for the two methods to converge.

cations:

ferring the policy the convergence was accelerated up:

t = 0 25,:= 0 9,:= 0 5. The number of allstates is 3060.

ward 1 is given. Otherwise 0.

Finally, we apply the learned policy to a real situa-get, makes a collision with any obstacles, or thegiven time interval expires.

 The states S r are around states where the robot
makes a collision with any obstacles.

di erentsame as in [1]. We used a mobile robot platform \Yamtarget (trash can) and two obstacles (trash cans) in theenvironment, and Yamabico uses the policy

P 5. Then,

Yamabico succeeded in reaching the target avoiding
two obstacles.

Table 2: Success rates of each policy [%]5 Experimental Resultsveof real robot experiment. The system used is almostabico" which is modeled in section 3.1. There are a One trial terminates if the robot reaches the tar-tested

to 35%.
tion as a new environment. Figure 7 shows the result

 If the robot reaches the target, the positive re-We

By trans-environments

calledE1; . . . ; E 5 shown in Figure 6 where a solid black circle, gray circles, and empty pentagons indicate thetarget, obstacles, and robot trajectories, respectively.

policyP1P2
P3P4P52 Sr# of s61754469E1
90.9
92.4
88.2
82.2
89.4

E2
61.0
90.8
88.8
87.0
89.9

E3
(48.2)
45.2
93.3
93.2
89.8

E4(47.3)(50.2)
82.7
87.5
76.4

E5(61.5)(69.5)(68.9)
67.4
84.7

6 Discussion and Future work

The sequence of the environments the robot encoun-

E 1; E 2; . . . ; E 5, where E 1 is the initial environPi
which is obtained policy in Ei by the method. The

to environmental changes by transferring a Q-learned

second column shows the number of states found toand modifying it to cope with them.

be re-learned whenpolicy could absorb the di erences between multiple

ters isment. Table 2 shows the success rates in terms ofset:

P i applied to E (i + 1). Here, we= 0 5 but iteration of modi cation is performedin terms of discreet state space.

Therefore, some ofpolicies were improved much more than.

When the robot encounters an inexperienced environment, the success rate starts to decrease and robot
realizes that the environment has been changed. After policy modi cation, the robot obtained the policy
which may cope with the previous environments, too.
The successful trajectories in Figure 6 are the resultof application of thement. Thenal policy

P 5 to each environ-nal policy does not seem optimal in eachindividual environment, but can absorb the di erences
between multiple environments. For example, in Figure 6(e), the most left trajectory includes curves turning to the right although its optimal policy was just astraight path to the target.
Next we tested how transferring a Q-learned policy accelerated the learning. Two methods inE 2 arecompared.

 case 1:the normal learning method from scratch
inE 2.

 case 2:our method with P 1.

We have proposed a method which adapts robots
policy in the previous environments into a new one
The resultantenvironments. The resultant policy includes:
1. invariant state-action pairs common to all environments,
2. state-action pairs common to some environment
but may not be applicable in other environments,
3. state-action pairs e ective in the last environments,
but excludes state-action pairs that con icts from eachother (class 4) in multiple environments. Our methodattempts at minimizing the number of class 4 byadopting not optimal but feasible solutions. However,
to make the obtained policy reasonable, we need tobe careful about the sequence of environments which
the robot encounters. Next, a method that de nes thetask class in such a way that the robot can graduallyskill up the learned policy should be developed. In addition to that, there is another problem of state spaceconstruction:state vector selection is currently o -line process, but ideally the issue should be includedin the on-line learning process. These are under theinvestigation.

Camera Image(a) Env.E 1(b) Env.E 2

Detected Image(c) Env.E 3

TargetObstacle

Detected
Target Area

12(d) Env.E 4(e) Env.E 5

Figure 6: Environments and successful tra jectories

3References[1] T. Nakamura, J. Morimoto, and M. Asada. Direct
coupling of multisensor information and actions

Proc. of1996 IEEE/SICE/RSJ International Conference
on Multisensor Fusion and Integration, pages 139{

4for mobile robot behavior acquisition. In(a) Real input images

144, 1996.

[2] F. Tanaka and M. Yamamura. An approach to lifelong reinforcement learning through multiple environments. In

6th European Workshop on Learning

TargetRobots, pages 93{99, 1997.
[3] S. Thrun.

A lifelong learning perspective fornavigation.
In Proc. of theIEEE/RSJ/GI Conference on Intelligent Robotsand Systems, pages 23{30, 1994.
mobileObstaclerobot[4] S. Thrun and T. Mitchell.

Lifelong robot learn-

Obstacle
Yamabicoing. Technical Report IAI-TR-93-7, University ofBonn, Dept. of CS III, 1993.

(b) Success trajectory[5] S. Thrun and J. O'Sullivan. Discovering structure
in multiple learning tasks: The tc algorithm. In

Proc. of the thirteenth International Conference onMachine Learning, 1996.

Figure 7: Experimental result