Learning of the Way of Abstraction in Real Robots

Atsushi Ueno3 , Hideaki Takeda3 & Toyoaki Nishida3 33
3 Graduate School of Information Science, Nara Institute of Science and Technology,
Ikoma, Nara 630-0101, Japanfueno, takeda, nishidag@is.aist-nara.ac.jp
33 School of Engineering, The University of Tokyo, Tokyo 113-8656, Japannishida@kc.t.u-tokyo.ac.jp
ABSTRACTReal robots should be able to adapt exibly to various
environments. The main problem is how to abstract
useful information from a huge amount of informationin the environment. This is called the frame problem.
This paper proposes a new architecture which can learn
how to perform abstraction while executing the task.
We call the architecture Situation Transition Network
System (STNS). By this architecture, a robot can acquire a necessary and sucient symbol system for thecurrent task and environment. Furthermore, this symbol system is exible enough to adapt to changes ofthe environment. STNS performs cognitive learningand behavior learning parallelly while executing thetask. In cognitive learning, it extracts situations andmaintains them dynamically in the continuous state
space on the basis of rewards from the environment. A
situation can be regarded as an empirically obtained
symbol. In behavior learning, it constructs an MDP(Markov Decision Problem) model of the environmenton the abstracted situation representation. This modelis used for planning of behavior. The validity of STNS
is shown in computer simulations.

1 INTRODUCTION

Real robots should be able to adapt exibly to various
environments. However, most existing robots cannot
adapt. The main reason is that they have xed symbol
systems. A human-made symbol system is not always
suitable for the robot. Therefore, in the environments
which the designers cannot expect, such a robot is apt
to fail to manage a huge amount of information and
get into the frame problem. In this paper, the frame
problem is de ned as \the problem of how to deal withpartiality of information" [3].
The frame problem cannot be solved intrinsicallybecause no agent can have all information in the world.
However, animals seem not to be troubled with theframe problem in the daily life. It can be considered
as a practical solution of the frame problem. We thinkthat \obtaining appropriate information frames empirically" is a key function for this solution. This function
can be regarded as cognitive learning or learning how
to perform abstraction. It is expected that an agent
with this function can obtain a necessary and sucient symbol system for the current environment. By

incorporating this with behavior learning on the symbolic system, an agent can have exibility necessary foradapting to unfamiliar environments. Although thisparallel learning has demerits in ineciency and complexity of information processing, we think that it isessential to the practical solution of the frame problem.
Such cognitive agents are realized only in the domain of reinforcement learning. In the agent, reinforcement learning of behavior policy is executed in thesymbol space, and learning of the state representation
is executed in the continuous input space. The latter isa kind of cognitive learning. Since the task of the agent
is expressed all in the rewards from the environment
in the general reinforcement learning problem, rewards
can be used reasonably as the basis of articulation. In
this point of view, reinforcement learning is suitablefor cooperating with cognitive learning.
The following two properties are important for thecognitive learning to solve the frame problem practically. First, articulation should be based on rewards.
By this property, highly abstracted state representation can be expected because the task is represented
in rewards. Second, cognitive learning and behavior
learning should be executed parallelly while executing
the task. In this case, good state recognition can makegood behavior, and good behavior can maintain wellshaped states. This on-line learning contributes to thefollowing three advantages:
1. The system can adapt to changes of the environment.
2. The system can make a state representation froma few data since it can be adjusted afterward.
3. The robot can learn the area frequently where itgoes frequently in task execution.
Advantage 1 means the exibility of the symbol system. By this advantage, the robot need not wonder
when it should start cognitive learning or how long it
must continue learning. By advantage 2 and 3, it canbe expected that learning converges immediately.

2 STNS

We have developed a new architecture which has theabove two properties. We call the architecture Situation Transition Network System (STNS). This is asolution to the problem of how to adapt to various environments. By this architecture, a robot can acquire anecessary and sucient symbol system for the current
task and environment.
As shown in Fig. 1, STNS consists of a situation
classi er, a situation transition network (STN), andseveral behavior modules. In each behavior step, thesystem identi es the current \situation" where the current input is included, makes a plan on the STN, andactivates a behavior module according to the plan.
And a list of the input, the corresponding situation,
the selected behavior, and the acquired reward are put
into a history database. It keeps the data for a xed
period, and always has xed numbers of data. Cognitive learning and behavior learning are performed on
the data in it.

Figure 1: The structure of STNS
In cognitive learning, it extracts situations andmaintains them dynamically in the continuous state
space on the basis of rewards. A situation is de ned
as a set of input vectors from which the robot receives
the same reward by the same behavior. It is a highly
abstracted state and can be regarded as a empiricallyobtained symbol. In this way, the system can learn theappropriate way of abstraction from a huge amount of
information of the real environment.
In behavior learning, it stores results of transitions
between situations and constructs an MDP (Markov
Decision Problem) model of the environment on thelearned situation representation. This model is used
for planning of behavior. The goal of the planning is
to maximize discounted sum of rewards received over a
period of time. Because the planning is performed on
the abstracted situation representation, the robot withSTNS does not have to deliberate details in planning.
This process can be regarded as a kind of reinforcement
learning of behavior policy.
The previous version of STNS [7] uses Interleave Planning-based Reinforcement Learning (IPRL)
method for planning on the STN. Hereinafter, wecall it STNS1. In this paper, we propose an improved version, STNS2, which uses the policy iteration
method for planning on the STN. The policy iterationis one of generally used dynamic programming methods, and it is often the most ecient approach for small
state spaces. The other modules in STNS2, that is asituation classi er, behavior modules, and a history
database, are just the same as STNS1 because of themodularity of this architecture.
Cognitive learning and behavior learning are performed parallelly while executing the task. Therefore,
the above-mentioned three advantages are realized.
In the next two sections, we explain the cognitive
learning and the behavior learning in more detail.

3 COGNITIVE LEARNING IN STNSIn this section, we explain a new cognitive learning
method which is used in STNS1 and STNS2 in common.

3.1 Segmentation Based on Similarity of Rewards

STNS segments the state space into some situations
each of which has a speci c meaning on the basis ofsimilarity of rewards. The meaning of a situation is\the system can acquire the speci c result by the speci c behavior". The speci c behavior is called the condition behavior of the situation. The speci c results
are divided into two types, i.e., R-situation and Tsituation. In a situation based on immediate rewards
called R-Situation, the result is to acquire a speci cbig reward. In a situation based on situation transitions called T-Situation, the result is to transit to a
speci c situation. If every chain of T-Situations is anchored to an R-Situation, every situation is guaranteed
to lead to a speci c big reward by the same sequenceof behaviors.

3.2 Bitten Hyper-Ellipsoid Representation

In on-line learning, the system should be able to decide rough shapes of situations from a limited amountof data, and to decide ner shapes as data increase.
For this purpose, we propose the bitten hyper-ellipsoid
representation. In this representation, each situationis shaped by the positive instances and the negative instances that are decided based on the meaning of thesituation.
As shown in Fig. 2, this representation is a mixtureof macroscopic cognition and microscopic cognition. In
macroscopic cognition, the boundary of a situation isa contour of Mahalanobis' distance from the population of the positive instances. This boundary formsa hyper-ellipsoid1 . This cognition is quick and roughthat can be formed even from very few data. Microscopic cognition is realized by the Nearest Neighbormethods2 and grows ner as data increase. By mixing these two types of cognition, a ne and exible
cognition is realized.

3.3 Cognitive Learning in STNSIn STNS, the state space is divided into overlapped bitten hyper-ellipsoids (situation 1-7) and a margin space
1 [1] uses the same type of representation.
2 [6] uses the same type of representation.

 Adjustment of the boundary of each hyper-ellipsoid

Figure 2: The bitten hyper-ellipsoid representation(situation 0) as shown in Fig. 3. A new perceptual input is ascertained whether it belongs to each situationfrom the top of the discrimination tree in Fig. 3.

Figure 3: The state space and the discrimination tree
Cognitive learning is realized by extraction andmaintenance of situations. There are two conditions
for situation extraction.
1. R-Situation In the whole state space, there areR ) data in which theenough (more than Ninit
system acquired a speci c reward larger thanR ) by a speci c behavior.
a threshold (rminT-Situation In situation
0, there are enoughT ) data in which the system(more than Ninit
transited to a speci c situation other than situation 0 by a speci c behavior and did notR ) reward.
acquire a large (more than rmin
2. There is no situation yet which has the speci c behavior and the speci c result in condition 1 as its
meaning.
When both of these conditions are ful lled, a newsituation is extracted. In extraction, the meaning of
the new situation is de ned referring to the condition 1,
and positive instances are collected from the history
database.
The extracted situations are maintained by theseve methods.
 Replacement of instances in the population of thepositive instances and the population of the negative instances of each situation(The boundary is settled just on the farthest positive instance.) Adjustment of the order of situations in the discrimination tree (The nearer situation to rewards
is put upper.) Changing the meaning of deformed situations
 Elimination of deformed situations

4 BEHAVIOR LEARNING IN STNS2

In STNS, each situation has a condition behavior.
However, it decides a behavior policy by reinforcement
learning. The main reason is that the cognitive learning in STNS is on-line learning: it extracts a situationfrom a few data and it is assumed that the environment can be changed, therefore the initial condition
behavior is not always the optimal behavior.
Behavior learning is realized by combination oflearning of the STN and behavior planning on it.
There is no di erence in components of STN between
STNS1 and STNS2. The only di erence is the planning
method: STNS1 uses IPRL and STNS2 uses the policy
iteration method. In this section, we explain the STN
rst, and then explain a planning method with policy
iteration.

4.1 STNAn STN is an MDP model which consists of the transition probabilities between situations and the expectations of immediate rewards accompanying transitions.
The transition probability from situation i to situation j by behavior b is called p(i; j ; b), and the expectation of the immediate reward which are acquired by
the transition is called r(i; j ; b).
If Marcov property is assumed, the problem of nding the optimal policy on an STN is a Markov decision problem. Accordingly, the optimal policy is determined by solving the optimal equation of dynamic
programming:

U (i) = maxb2B

X p(i; j; b) r(i; j; b) + U (j)

j 2X

f

g

(1)

where X is the state space, B is the behavior space,i (i 2 X ) is a situation, and (0  < 1) is a discounting factor. U (i) is the utility of situation i, whichis the expectation of the discounted sum of the rewards
received over time by the optimal policy.
In STNS, the MDP model cannot be given in advance since the situation representation is changed dynamically. Therefore, the model are estimated by the
maximum likelihood estimation from the data in thehistory database at the same time as the learning of
a behavior policy. This problem is in the domain of
reinforcement learning.

4.2 Planning with Policy Iteration

Many reinforcement learning methods keep the estimated utilities of situations, and improve them little
by little after every behavior to convergent to the optimal values. However, STNS does not keep them but
calculate them as the need arises in order to adapt tothe changes of situation representation immediately.
STNS2 uses the policy iteration method for calculating the utilities of situations. This method works
by picking a policy, then calculating the utility of eachsituation. Given a xed policy, a set of optimal equations (Equation 1) are simultaneous linear equations
and can be solved directly by linear algebra methods
such as Gaussian elimination to nd the utilities of situations. It then updates the policy at each situation to
maximize its utility using the utilities of the successor
situations, and repeats until the policy stabilizes.
By this method, optimal behaviors in all situations are determined. It is expected that a simple
hill-climbing method which picks the optimal behavior reactively in each situation leads the robot to a big
reward. However, STNS2 makes a plan before activate
a behavior module. A plan P in STNS is a list of pairsof a behavior and a target situation of the behavior:
P = ((b1 ; d1); (b2 ; d2 ); :::; (bn; dn ))where n is the length of the plan, bi is the ith behavior in the plan, and di is the target situation of the
behavior. The target situation can be used as a stopping condition of a continuous behavior. As shownin Fig. 3, the situations made by STNS has rugged
shapes. Therefore, this sort of stopping condition isuseful in order not to be caught in a projection of anundesirable situation.
The procedures for planning are as follows:
1. Find the utilities of all situations by the policy iteration method.
2. Develop a plan forward from the current situation.
Set the optimal behavior of the situation as the
behavior bi, and the most promising destination as
the target situation di :di = arg max
p(d ; j ; bi )fr(di01 ; j ; bi) + U (j )g
j 2X i01
3. Continue plan developing until the peak of the utility or a terminal situation which has no successor
situations.
Then, the system starts to execute the plan in the environment. Plan execution is stopped and planning isstarted again after the last behavior in the plan is executed, or another situation than the target situationis reached.

5 EXPERIMENTS

We conducted three types of experiments on computer
simulation in order to examine the validity of STNS2.
The results of the same sorts of experiments of STNS1
are shown in [7].

5.1 Experiment 1: Navigation on 2-D Input

To show the validity of STNS2, we show a simple experiment on computer simulation. Fig. 4 shows thenavigation problem on 2-dimensional input. Every
trial starts after the goal is settled at an arbitrary position and the rover is set at an arbitrary position outside of the goal in an arbitrary direction. The trial ends
when the rover arrives at the goal, and the next trial
starts immediately. At the beginning of learning, there
are only the goal situation and situation 0 (the margin
space) in the state space. We set parameters as folR = 3; N T = 15; r R = 5:0; = 0:7. Note
lows: Ninit
initminthat the number of positive instances for R-Situation
R = 3, is the minimum in order to conextraction, Ninit
struct an ellipsoid in the 2-dimensional state space. We
repeated this experiment 20 times.

Figure 4: The navigation problem on 2-D input
Learning has converged after about 1300 behaviors
are executed on average. Fig. 5 shows a typical state
space after leaning has converged and the optimum
state space. The small circle at the center of each spacedenotes states in which the rover arrives at the goal.
As shown in this gure, good situation representationand good behavior policy were acquired.

Figure 5: A state space after convergence and the optimum state space

5.2 Experiment 2: Flexibility Test

To test the exibility of STNS2, we conducted two experiments on computer simulation. One is a exibility
test to sensor trouble and the other is a exibility test
to actuator trouble. In both experiments, we picked
10 systems after 5000 behavior steps in Experiment 1,changed the environment, and then let them continuelearning in the new environment. As changes of environment, we rotated the direction of the goal sensor(10, 15, 20, 25, 90, and 180 degrees rotation) in theformer test, and made the revolution rate of the left
wheel lower (5%, 10%, and 15% lower speed) in thelatter test. Fig. 6 shows a typical result in the caseof 15 degrees rotation of the goal sensor and a typicalresult in the case of 15% lower speed of the left wheel.
As shown in this gure, passably good situation representation and good behavior policy were acquired.

leaning (29000 behavior steps) and the optimum segmentation. The 8-D state space was mapped onto the2-D work space by xing the attitude of the rover. As
shown in this gure, not bad situation classi cationand not bad behavior policy was obtained in the areas
near to big rewards. However, in the areas far frombig rewards, no useful situation was extracted. The
main reason is that the ability for cognitive learning is
not sucient. For compensating for this weak point, I
think hierarchical learning or empirical creation of newaxes of the state space is e ective.

5.4 Comparison between STNS1 and STNS2
Figure 6: Results of the exibility test
In both experiments, STNS2 can exibly adapt
to small changes while keeping the high performanceby transforming the shapes of situations, and it canstably adapt to big changes by eliminating deformed
and obstructive situations and starting again from theblank state space. These two types of adaptation areswitched to each other autonomously. Even in the caseof big changes, learning converged to the same performance after a delay of at most 1000 behavior steps
compared with learning from the blank state space.
So it can be said that learning of STNS2 is stable.

5.3 Experiment 3: Navigation on 8-D Input

When comparing STNS2 with STNS1, they have similar performance on learning: similar convergence rates,
similar performance after convergence, similar exibility to changes of environment, and so on. As an example, Fig. 9 shows the changes of the average numbersof behaviors to the goal in Experiment 1 comparing
STNS1 and STNS2.

The last experiment is a navigation problem on 8dimensional input. The setting is almost the samewith Experiment 1. But one obstacle was settled in
the room and the goal was xed to the position shownin Fig. 7a. And the rover got a 6-dimensional obstacle sensor shown in Fig. 7b in addition to the 2dimensional goal sensor. We set parameters as folR = 9; N T = 20; rR = 5:0; = 0:7. Note
lows: Ninit
initminthat the number of positive instances for R-Situation
R = 9, is the minimum in order toextraction, Ninit
construct a hyper-ellipsoid in the 8-dimensional state
space. This problem is dicult because the dimensionof the state space is high and the paths through thestate space is not continuous. We repeated this experiment 10 times.

Figure 9: Learning Curves of STNS1 and STNS2
On the other hand, the elapsed time for the simulation of STNS2 was much shorter than STNS1.
Fig.10 shows the changes of the average elapsed timesof 1000 behaviors in Experiment 1 on an SGI Indy
R5000SC workstation comparing STNS1 and STNS2.
The elapsed time of STNS2 was about from 2.5 times
to 5 times as short as STNS1, and furthermore, converged much earlier than STNS1. The reason for thisis that the planning time of STNS2 is much shorter
than STNS1. Although it is necessary to conduct still
more experiments for general comparative conclusion,
STNS2 seems to be more ecient than STNS1.

b. 6-dimensional obstaclea. Work spacesensors
Figure 7: The navigation problem on 8-D input
Fig. 8 shows a typical segmentation after enoughFigure 10: Elapsed Time of STNS1 and STNS2

Figure 8: A segmentation after enough learning and the optimum segmentation

6 RELATED WORKS

There are many systems that can learn the state representation for reinforcement learning. Some of them
are based on the similarly of rewards. Chapman and
Kaelbling [2] proposed the G algorithm that splits thestate space statistically on the basis of rewards. Mahadevan and Connell [5] proposed an algorithm thatextracts clusters of states in the state space statistically on the basis of rewards. Both methods deal withstates each of which consists of a bit sequence. Therefore, their systems are di erent from STNS that deals
with a problem with a continuous state space. Asadaet al. [1] proposed a method that divides a continuous
state space by hyper-ellipsoids. The method executes
cognitive learning in a o -line way: the system rst
learns the whole state representation on the basis of experiences of random behaviors and then shifts to task
execution. Ishiguro et al. [4] proposed a method thatrst divides a continuous state space by hyper-planeson the basis of experiences of random (or given) behaviors, and then learns a behavior policy by Q-learning.
It can execute these two types of learning alternately.
But it constructs xed boundaries between states. It isdi erent from STNS at this point because STNS constructs a exible situation representation. Takahashi
et al. [6] proposed a method that segments a continuous state space by the Nearest Neighbor methods while
executing the task. The segmentation of the method
is based on rewards in the areas near to rewards andbased on the relationship between the sensory input
and its gradient in the areas far from rewards. By thelatter policy, the method can segment the state spacestably even in the areas far from rewards. However,the validity of this policy needs to be con rmed.

7 CONCLUSION

We have proposed STNS2, a method for performing
both cognitive learning and behavior learning simultaneously with task execution, and shown that themethod is e ective to acquire good state representationand good behavior policy in continuous state space.

The representation also have exibility to changes ofthe environment. Furthermore, we have shown STNS2
is superior to the previous version, STNS1, in eciencyof planning.
There needs more work for the symbol processing
system grounded on real environments. Reinforcement
learning system can deal with symbols only for representing states or behaviors. Therefore, the dual learning system like STNS can execute only very simple
symbol processing. In order to expand this sort ofsymbol system, the following four functions are worth
considering: structuring symbols, symbolizing objects,
reusing symbols, and sharing symbols.
In order to con rm the validity of STNS2, it is necessary to conduct experiments on real robots. We are
now preparing to put it on a real robot.

REFERENCES[1] M. Asada, S. Noda, and K. Hosoda.

Action-based

sensor space categorization for robot learning. In

of IROS 96, Vol. 3, pp. 1502{1509, 1996.

Proc.

[2] D. Chapman and L. P. Kaelbling. Input generalizationin delayed reinforcement learning: An algorithm andperformance comparisons.

In

Proc. of IJCAI-91, pp.

726{731, 1991.
[3] K. Hasida and H. Matsubara. Partiality of informationand the structure of the frame problem.

PRICAI '90, pp. 711{716, 1990.

[4] H. Ishiguro, R. Sato, and T. Ishida.
state space construction. In

In

Proc. of

Robot oriented

Proc. of IROS 96, Vol. 3,

pp. 1496{1501, 1996.
[5] S. Mahadevan and J. Connell.
ming

of

behavior-basedlearning. In

robotsAutomatic programusing

reinforcement

Proc. of AAAI-'91, pp. 768{773, 1991.

[6] Y. Takahashi, M. Asada, and K. Hosoda. Reasonable
performance in less learning time by real robot basedon incremental state space segmentation. In

IROS 96, Vol. 3, pp. 1518{1524, 1996.

Proc. of[7] A. Ueno, H. Takeda, and T. Nishida. Cooperation of
Cognitive Learning and Behavior Learning. To Appear
inProc. of IROS 99, Oct. 1999