Cooperation of Cognitive Learning and Behavior Learning
Atsushi Ueno
Hideaki Takeda
Toyoaki Nishida
Department of Information Processing
Nara Institute of Science and Technology, Nara 630-0101, JAPANueno@is.aist-nara.ac.jp

Abstract
Reinforcement learning is very useful for robots withlittle a priori knowledge in acquiring appropriate behavior. Autonomous segmentation of the continuous state
space is a promising method for reinforcement learning in real robots. This is a kind of cognitive learning.
We think cognitive learning should be based on similarity of rewards since the task of the robot is expressedin the rewards in the general reinforcement learning
problem. Furthermore, cognitive learning should be performed in an on-line way for exibility to changes ofthe environment and immediate convergence of leaning.
This paper describes a learning system which can learna state representation and a behavior policy simultaneously while executing the task. We call the system
Situation Transition Network System (STNS). As cognitive learning, it extracts \situations" and maintains
them dynamically in the continuous state space on thebasis of rewards from the environment. As behavior
learning, it makes an MDP model of environment andperforms partial planning on the model. This is a kindof reinforcement learning. The results of computer simulations are given.
1 Introduction

Reinforcement learning is very useful for robots withlittle a priori knowledge in acquiring appropriate behavior. The general reinforcement learning can be regarded as learning of a behavior policy that maximizes
discounted sum of the rewards received over time. For
this purpose, many reinforcement learning methods
perform the approximation of the utility function (orthe action-value function).
In real world, almost all robots have real-valued sensors and the continuous state space (perceptual input
space). There are two approaches for approximating
the utility function in the continuous state space: using an implicit representation of the function such asneural network or segmenting the continuous space into
discrete states in which the value of the utility function
is regarded as invariable.

As the former, several kinds of implicit representations can be used such as Perceptron-like neural network [2, 7, 10, 5, 6], CMAC (Cerebellar Model Arithmetic Computer) [8], and RBF (Radial Basis Function)[3]. But this approach has three problems: 1. it is difcult to understanding the inner representation, therefore, 2. it is very dicult to analyze the convergenceand the optimality of learning, therefore, 3. the humandesigner must x many parameters arbitrarily on thebasis of his own experience. It is dicult for him when
the task of the robot is complex.
As the latter, the most usual representation is thegrid representation which the human designer must
make by dividing the continuous space at equal or arbitrary intervals. It is also dicult for him in case of acomplex task.
In order to cope with this diculty, many methods
have been proposed which can segment the state spaceautonomously. This segmentation can be regarded as akind of cognitive learning. In this kind of learning, we
think segmentation should be based on rewards. The
main reason is that the task of the robot is expressedin the rewards in the general reinforcement learning
problem. Furthermore, we think input vectors which
are similar from the view point of rewards should be
got together into the same state for a highly abstracted
state representation.
Asada et al. [1] proposed a method that divides
a continuous state space by hyper-ellipsoids. In thismethod, a state is de ned as a set of input vectors fromwhich the robot achieves the goal or already acquired
state by a variable sequence of one kind action primitive. By this de nition, it can make a highly abstracted
state representation. However, it performs cognitive
learning in an o -line way: the system learns a state on
the basis of experiences of random behaviors in learning
phase, and executes the given task on the xed state
representation. For this reason, it needs a sucient of
randam behaviors to extract a new state exactly andcannot adapt to changes of the environment.
Ishiguro et al. [4] proposed a method that rst divides a continuous state space by hyper-planes on thebasis of experiences of random (or given) behaviors,
and then learns a behavior policy by Q-learning. It
can perform these two types of learning alternately.
However, it constructs xed boundaries between states.
Therefore, the states are short of exibility.
Takahashi et al. [9] proposed a method that segments a continuous state space by the Nearest Neighbor methods while executing the task. This segmentation is based on rewards in the areas near to rewards
and based on the relationship between the sensory input and its gradient in the areas far from rewards. By
the latter policy, it can segment the state space stably
even in the areas far from rewards. But the validity ofthis policy needs to be con rmed.
This paper propose a learning system which canlearn a state representation (cognitive learning) anda behavior policy (behavior learning) simultaneously
while executing the task. We call the system Situation Transition Network System (STNS). The cognitive learning is based only on similarity of rewards
in the similar way as Asadas' method: a state is dened as a set of input vectors from which the robot
acquires the same reward by the same behavior. And
we developed a new exible situation representation.
Therefore, our system can extract highly abstracted
states. We call this highly abstracted state situation.
The behavior learning is performed by a reinforcement
learning method. In simultaneous learning of this two
types of learning, good situation recognition can makea good behavior policy, and a good behavior policy canmaintain well-shaped situations. This on-line learning
contributes to the followings:
1. The system can adapt to changes of the environment.
2. The system can extract a situation from a few data
since it can adjust its shape afterward.
3. The robot can learn the area frequently where itgo frequently in task execution.
4. The robot need not wonder how long it must continue learning in learning phase.
By 2 and 3, learning converges immediately. And incompensation for the cost of maintaining situations,
it can be expected that specialization to the task andexibility to changes are realized together by interdependence between situations and behaviors.

2 Situation Transition Network System
As shown in Fig. 1, STNS consists of a situation classi er, a situation transition network (STN), and several
behavior modules. In each behavior step, the system

identi es the current situation where the current input
is included, makes a partial plan on the STN, and activates a behavior module according to the plan. Anda list of the input, the corresponding situation, the selected behavior, and the acquired reward are put intoa 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 thedata in it.

Figure 1: The structure of STNS
In cognitive learning, the system extracts situations
and maintains them on the basis of rewards from theenvironment. This is regarded as learning of situation
representation. In behavior learning, the system learns
the Markov Decision Problem (MDP) model of the environment on the learned situation representation. The
next behavior is decided by the partial planning on themodel. This process is regarded as a kind of reinforcement learning of behavior policy. These two learning
processes are performed simultaneously while executing the task.
In the next two sections, we explain the cognitive
learning and the behavior learning in more detail.

3 Cognitive Learning in STNS

3.1 Segmentation Based on Similarity ofRewards

STNS segments the state space into some situations
each of which has a speci c meaning on the basis of similarity of rewards. The meaning of a situation is \thesystem 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 T-situation.
In a situation based on immediate rewards called RSituation, the result is to acquire a speci c big reward.
In a situation based on situation transitions called TSituation, 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 reward by the same sequence of 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 is a
contour of Mahalanobis' distance from the populationof the positive instances. This boundary forms a hyperellipsoid1 . This cognition is quick and rough that canmake up for the lack of data. Microscopic cognition isrealized by the Nearest Neighbor methods2 and grows
ner as data increase. By mixing these two types ofcognition, a ne and exible cognition is realized.

Figure 3: The state space and the discrimination treesituation 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 cbehavior and the speci c result in condition 1 asits 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.
 Renewal of the population of the positive instances

Figure 2: The bitten hyper-ellipsoid representation

3.3 Cognitive Learning in STNSIn STNS, the state space is divided into overlapped
bitten hyper-ellipsoids (situation 1-7) and a margin
space (situation 0) as shown in Fig. 3. A new perceptual input is ascertained whether it belongs to each situation from the top of the discrimination tree in Fig. 3.
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
1 [1] uses the same type of representation.
2 [9] uses the same type of representation.

and the population of the negative instances ofeach situation

 Renewal of the boundary of each hyper-ellipsoid(The boundary is settled just on the farthest positive instance.) Renewal of the order of situations in the discrimi-

nation tree (The nearer situation to rewards is put
upper.)

 Changing the meaning of deformed situations
 Removal of deformed situations

4 Behavior Learning in STNSIn 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.

In this section, we propose a new reinforcement
learning method, Interleave Planning-based Reinforcement Learning (IPRL), which is suitable for STNS
which has a exible situation representation.

4.1 STNAn STN is an MDP model which consists of thetransition probabilities between situations and the expectations of immediate rewards accompanying transitions. The transition probability from situation i tosituation j by behavior b is called p(i; j ; b), and the expectation of the immediate reward which are acquiredby 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 found bysolving the optimal equation of dynamic programming:

U (i) = max
b2B

X p i; j b r i; j b

j 2X

(

; )f (; )+U (j )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 must be estimated at
the same time as the learning of a behavior policy. This
problem is in the domain of reinforcement learning.

4.2 IPRLSTNS uses a new reinforcement learning method,
IPRL, for behavior learning. 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,
IPRL does not keep them but calculate them whennecessary in order to adapt to the changes of situation
representation immediately. For the calculation, IPRL
uses a interleave planning method on STN3 .
Interleave planning performs partial planning andplan execution alternately. As a result, it can balance between reactiveness and deliberativeness. Yamada [11] proposed interleave planning which determines the timing to switch planning into execution by
the success probability of a plan. STNS uses a method
similar to this, which limits the search space by the success probability. By this method, a short plan is madeand executed reactively in uncertain environments, and
3 The policy iteration algorithm of dynamic programming isanother promising method for behavior learning in STNS

a long plan is made and executed deliberatively in certain environments. Therefore it can balance between
reactiveness and deliberativeness automatically.
A plan P in STNS is a list of pairs of a behavior anda 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 behav-

ior. The success probability of a plan is de ned as the
product of all transition probabilities in the plan.
IPRL calculates approximate utilities of situations
using the optimal equation (Equation 1). The transition probability p(i; j ; b) and the expectation of theimmediate reward r(i; j ; b) are estimated by the maximum likelihood estimation from the data in the history
database.
The procedures for planning are as follows:

1. Plans are developed forward from the current situation within the limits that the success probability
is larger than pmin and the length is shorter than
nmax .
2. The utilities of all situations which correspond toleaves of the search tree are assumed 0.
3. The planning backtracks from leaves to the root(the current situation). In every node, the utilityof the situation is calculated by Equation 1. And apair of the behavior which maximizes the right sideof the equation and situation j which maximizes
the inside ofis back-propagated to the parent
node as a element of a plan.

P

4. When backtracking returns to the root, only one
plan remains. This is the picked plan, and called
the master plan.
Then, the system starts to execute the master planin the environment. Plan execution is stopped andplanning is started again after the last behavior in themaster plan is executed, or another situation than thetarget situation is reached.

5 Experiments

5.1 Navigation on 2-D Input

To show the validity of STNS, 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 area and situation 0 (the margin space) inR =the state space. We set parameters as follows: Ninit
T
R
3;Ninit = 15; rmin = 5:0; = 0:7; pmin = 0:1; nmax =7.
Figure 6: Results of the exibility test

Figure 4: The navigation problem on 2-D input
Learning has converged after about 1200 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.

In both experiments, STNS can exibly adapt tosmall changes while keeping the high performance bytransforming the shapes of situations, and STNS 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 after a delay of at
most 1000 behavior steps compared with learning fromthe blank state space. So it can be said that learningof STNS is stable.

5.3 Navigation on 8-D Input

The last experiment is a navigation problem on 8dimensional input. The setting is almost the same withthe previous navigation problem on 2-dimensional input. But one obstacle was settled in the room and thegoal was xed to the position shown in Fig. 7a. And
the rover got a 6-dimensional obstacle sensor shownin Fig. 7b in addition to the 2-dimensional goal senR = 9; N T =sor. We set parameters as follows: Ninit
init
R
20; rmin = 5:0; = 0:7; pmin = 0:2; nmax = 7. This
problem is dicult because the dimension of the state
space is high and the paths through the state space is
not continuous.

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

5.2 Flexibility Test

To test the exibility of STNS, 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, weprepared an STNS after 10000 behavior steps in theabove experiment (shown in Fig. 5a), changed the environment, and then let the STNS continue learning in
the new environment. As changes of environment, werotated the direction of the goal sensor in the former
test, and made the revolution rate of the left wheel
lower in the latter test. Fig. 6 shows a typical resultin the case of 15 degrees rotation of the goal sensor
and a typical result in the case of 15% lower speed ofthe left wheel. As shown in this gure, passably good
situation representation and good behavior policy wereacquired.

b. 6-dimensional obstacle
sensors
Figure 7: The navigation problem on 8-D input
a. Work space

Fig. 8 shows an typical segmentation after enoughleaning (28000 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

Figure 8: A segmentation after enough learning and the optimum segmentationnear to big rewards. However, in the areas far from big
rewards, no situation was extracted. The main reason
is that the ability for cognitive learning is not sucient. For compensating for this weak point, I thinkhierarchical learning or empirical creation of new axesof the state space is e ective.

6 Conclusion

We have proposed STNS, 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.
This sort of dual learning system can be regarded
as a symbol processing system grounded on real environments. Reinforcement learning of behavior policy isa kind of symbol processing, and learning of the state
representation is regarded as learning of symbols. But
reinforcement learning system can deal with symbols
only for representing states or behaviors. So such systems can execute only very simple symbol processing.
In order to expand this sort of symbol system, the following four functions are worth considering: structuring symbols, symbolizing objects, reusing symbols, andsharing symbols. Furthermore, in order to embed thissort of cognitive agent into the environment, parallel
processing of information should be necessary.

[2] A.G. Barto, R.S. Sutton, and C.W. Anderson.

IEEE Transactions on Systems,
Man, and Cybernetics, SMC-13(5):834{846, 1983.
ing control problems.

[3] K. Doya.

Temporal di

M.E. Hasselmo, editors, Advances in Neural Information Processing System, Vol. 8. MIT Press, 1996.
[4] H. Ishiguro, R. Sato, and T. Ishida.
state space construction. In

Robot oriented

Proc. of IROS 96, Vol. 3,

pp. 1496{1501, 1996.
[5] Long-Ji Lin.

Self-improving reactive agents based on

reinforcement learning, planning and teaching.

chine Learning, 8(3/4):293{321, 1992.

Ma-[6] P. Martn and J. del R. Millan. Reinforcement learningof sensor-based reaching strategies for a two-link manipulator. In

Proc. of IROS 96, Vol. 3, pp. 1345{1352,

1996.
[7] R.S. Sutton. Learning to predict by the method of temporal dierences.

[8] R.S. Sutton.
ing:
In

Machine Learning, 3(1):9{44, 1988.

Generalization in reinforcement learn-

Successful examples using sparse coarse coding.

Proc. of NIPS 95, 1995.

[9] 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.

[10] G. Tesauro.
learning.

Proc. of

Practical issues in temporal dierenceMachine Learning, 8(3/4):257{277, 1992.
Reactive planning withuncertainty ofProc. of The 3rd Annual Conf. on AI,
Simulation and Planning in High Autonomy Systems,
a plan.

ReferencesIn

pp. 201{208, 1992.

[1] M. Asada, S. Noda, and K. Hosoda. Action-based sensor space categorization for robot learning. In

erence learning in continuous

time and space. In D.S. Touretzky, M.C. Mozer, and[11] S Yamada.

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

Neu-ronlike adaptive elements that can solve dicult learn-

Proc. of

Deadline for submission of full paper : Feb. 1, 1999