Real time learning control of high d.o.f. robots: Automatic generationof discrete states and learning transition models
Ha jime Kimura,

Shigenobu Kobayashi

Interdisciplinary Graduate School of Science and Eng., Tokyo Institute of Technology

Abstract:

We present a model-based RL approach to cope with continuous space of high D.O.F.
robots, combining model learning and an actor-critic method. The model learner generates a discrete
state-transition model, that helps improvement of both the policy and state-representation. In general,model-based methods tends to fail in Non-Markovian problems, but the proposed method, using actorcritic, can nd good policies in such environments.
with high d.o.f. robots for state representation isStateNet3). It takes some representative poses as
We propose a new approach to construct control the states, and the actions correspond to moving
rules automatically for high-degree of freedom robots the other poses. But the state representation mustsuch as four-legged or humanoid robots. Learning be given by designers in advance, and transition unproblems in such robots have the following features: certainty is not considered in the model. There exists DP-based or model-based methods to nd op1. States and actions are continuous and high- timal control rules in uncertain environments, thatis modeled by Markov decision processes. These
dimensional large spaces.
methods need to construct environment models through2. There exists uncertainty in the state transi- trial and error interactions. This approach has sevtion.
eral advantages that when the environment model
3. The number of trial and error interactions is is obtained, the controller can learn the other tasks
limited because of its cost, especially in real easily. A problem is that the controller must construct a very accurate transition model in the modelrobots.
based approach. However, the estimated model tends
In the 3rd item (limitation of the trial), the learner to inaccurate because of 1) The number of trial
and error interactions are limited, 2) There exists
would face to the following matters:
uncertainty in state observations, especially in our It is desired to nd allowable good control robotics problem. Actually, control rules obtained
from only DP-based planning in the learned model
rules within the limited interactions.
are useless in our experiments. Non-Markovian prob It should be able to improve control rules by lems give too bad in uence to DP-based approaches.
It is caused from not only sensor noize but coarse
gaining more experiences.
discretization of state-space. To cope with this prob Gaining new experiences is more expensive lem, a standard approach is to quantize the statethan storing all sequences in its memory.
spaces into smaller ne cells. But in high-dimensional
 It should be able to give the expert's knowl- space, it cause the curse of dimensionality. Theedge to the controller easily, and to revise the other approach is to use adaptive grids, however, it
is infeasible to construct any state representations
rules if the given rules include some errors.
that have no non-Markovian problems. That is beState representation gives large in uence to the learn- cause using only DP-based methods has limitations.
Recently, several direct approaches based on reing speed and the quality of the control rules. It
is remarkable in large and continuous state spaces, inforcement learning are proposed, that do not havewhere simple partitioning continuous state-space into models. Q-learning and TD-methods are the reprea multidimensional grid tends to fail because of curse sentative methods. Although these are unstable inof dimensionality. One promising approach to deal non-Markovian environments, sometimes it is used1

Introduction

because of simplicity of the scheme in such domains.
Policy gradient methods such as actor-critic algorithms can construct desirable policies in a certainclass of non-Markovian environments5) . To copewith continuous state or action space, several methods are proposed, e.g., CMAC6), an adaptive gridding method1);7);9). Unfortunately, these methods
would not learn suÆciently in the case of limited
times of trials, because they requires enormous number of trials, Also, naive reinforcement learning approaches cannot make use of experiences obtained
from executing another tasks.
In this paper we propose a model-based RL approach to cope with continuous space of high d.o.f.
robots, combining model learning and an actor-critic
method. The model learner constructs a discrete
state-transition model based on StateNet, that helps
improvement of both the policy and the state representation. Note that the feature of our method is toconstruct a rough transition model in coarse state
representation that tends to cause non-Markovian,and the learner makes use of such an incomplete
model for the following three items:

Figure 1: Real four-legged robot.

 The policy learning is accelerated by usingstate value estimated from the model.

 The learner can eliminate wasteful search by

generating a good initial policy from the modeland planning method.

Figure 2: Imaginary four-legged crawling robot.

 The learner can improve the state represen-

The objective of learning is to nd control rules tomove forward, but the controller does not know the
dynamics ahead of time. The controller improves
its behavior through a process of trial and error.
At each time step, the agent observes current state,and select action, and immediate reward is given asa result of the action and state transition, and thetime step proceeds to the next step. The reward
signal re ects achievement of the given task. The
designer must specify the task to learn as the reward representation. Since we want the robot togo forward, the immediate reward is de ned as the
speed of the body at each step.
These robots have bounded continuous and discrete state variables. Continuous state variables
are angular-position of the eight joints, and discrete state variables represent four touch sensors foreach legs. The learning agent observes these statevariables. The action the agent selects is an objective angular-position of 8 joint-motors. That is,tation by detecting special states that have alarge error in the model.

We apply the algorithm to an imaginary four-legged
crawling robot, and demonstrate its dynamics. Also
we show preliminary experiments applying to a realfour-legged robot.
2

Problem Formulation

In this paper, we aim at obtaining control rules sothat the robot shown in Fig.1 is to walk throughtrial and error within 15 minutes . But it is difcult to execute suÆcient experiments using realrobots for comparing several algorithms. We consider an imaginary four-legged crawling robot shownin Fig.2, and we evaluate the proposed methods
from the experiments in that domain.

the same dimension of the continuous state. Whenthe agent select action, the robot moves the motors towards the commanded positions. When the
joint-angles move to the commanded position, orchanging the sensor variables, then the reward isgiven as the result of the transition, and the time
step proceeds to the next step. When the case of
sensor variable changing in the way of moving jointmotors, the angular-position would not correspondto the selected objective position. For this reason,
there exists uncertainty of the state transition. The
imaginary crawling robot has four legs, and each leg
has two joints. The body moves forward or backward when some legs are touching the ground andmoving it. Note that the controller should nd good
assignment of crawling control rules for each leg.
The state space and action space are the same as
the four-legged real robot. For simplicity, we assume that there is no noise in the state observation.
In real four-legged robot, two wheels detect amovement of its body, and generate the reward signal; the average of the moved distance of the wheels
is the moved distance of the robot, and the di erential of the wheels indicates the amount of turning
the head. Since we want the robot to go straight,
the immediate reward is de ned as the average of
the wheels minus absolute value of the di erential of
the wheels. Each foot has a touch sensor, and whenthe variable changes, an event of decision making
would occur.
In this crawling robot domain, there are many
control rules that can move the body ahead. However, in the domain of the four-legged robot, nding
walking rules are diÆcult because there are many local optimal behavior such as \not moving" that can
avoid negative rewards.

of L2 norm.

2) Generative discrete state representation:
When the smallest distance between the observed
state and representative points exceeds some threshold, the learner generates a new representative pointat that location.

3) The actions are de ned as objective states:

The actions correspond to moving the other discrete
states, but the resulting states are not always thesame objective states. In this paper, the number ofobjective action states are xed to avoid wastefulincreasing of similar actions in the process of learning.
This state-action representation is similar to StateNet3)
that can cope with high-dimensional space by using
small number of representative points. The new feature of our method is to generate new representative
points. This type of state-action representation iseasy to understand, since the behavior for the task isshown by some representative poses and transitions
between those poses. Therefore, it is easy for giving
prior knowledge, and also we can easily transformthe knowledge by natural languages. The other advantage is that the edge of the state region can beeasily improved by moving the position of its representative points. A drawback of this approachis that a local controller is needed to move robots
towards the objective positions, since the action iscorresponding to the objective states. The robots
in this paper already have such a local controller
only in the continuous state variables. But the local controller cannot treat properly in the context
of discrete state variables (sensors), the learner is tocontrol at the level of the StateNet-like representation.
3.2

3

Learning of Transition Models

Combining Model Learning with The agent constructs environment models as a Markov

decision process, translating the continuous state(and action) observation into the above discrete repWe propose a new approach that is combined model resentation, and executing most-likelihood estimation by counting the visiting times and accumulatlearning and reinforcement learning as below.
ing reward signals. However, the estimated transition model tends to inaccurate, because 1) State
3.1 State and Action Representation
discretization is too coarse, 2) The amount of thetrial data is not suÆcient.
The key points are:Reinforcement Learning1) State quantization by representative points:
The representative points specify the divided regions, and the region is based on distance measure 1. Observe state , choose action with prob- pose of accelerating the actor's learning. Since thisapproach remains the feature of the actor-critic, it
can execute the model learning and the policy improvement concurrently. It can also obtain somedegree of improved stochastic policy if the learningin arbitrary steps. When the agent is(TD-error) = rt + V^ (st+1) V^ (st ) , (1) isto terminatedlearn a new policy, if the agent has the approwhere 0   1 is the discount factor, V^ (s) priate transition models, it can eliminate wastefulis an estimated value function by the critic.
trial-and error interaction with the environment by
3. Update the estimating value function V^ (s) in generating a good initial policy from the model andthe critic according to DP in the estimated the planning method. In the planning, estimatedoptimal action would be approximately correct exmodel.
cepts for the states that have observation uncer4. Update the actor's stochastic policy by
tainty. Since the agent is to revise only such wrong@ ln (atj; st) , (2) actions by using reinforcement learning, it will bee (t) =@
more eÆcient than learning from non-prior knowle (t)e (t) + e (t) ,edge.
(t) = (TD-error) e (t) ,Fig.3 speci es the proposed method. The actor +  (t) ,holds parameterized stochastic policy function, andwhere e is the eligibility of the policy pa- updates the policy parameters towards the value
rameter , e is its trace, and  is a learning gradient. Let (aj; s) denote probability of selectrate.
ing action a under the policy  in the state s, and is the policy parameters. The agent improves the
5. Discount the eligibility traces as follows:
policy  by modifying the parameter . The parame (t + 1)
 e (t) ,(3) eter  speci es the actor's eligibility traces. Whento 0, the policy would be updated accordwhere  (0    1) is a discount factor in ing istoclose
the gradient of the estimated value function
the actor.
V^ , and when  is close to 1, the policy would be
6. Let t t + 1, and go to step 1.
updated by the gradient of the actual return. When
we want to cope with non-Markovian or incompleteFigure 3: An actor-critic algorithm using eligibility ness of the critic,  = 1 is preferable.
In the critic, the state value V^ (s) under the policy
traces in the actor, and the critic is making use of is estimated from the transition model and a DP
the model and DP.
scheme, given by:statability (atj; st), and perform it.
2. Observe immediate reward rt, resulting statest+1 , and calculate the TD-error according to


3.3



Finding Control Rules to Achive Tasks

1. For all s, substitute the following
into V^ (s)：i
h
P P
a
^
s
a Pr(s js; a) (aj; s) R (s; s ) + V (s )The actor-critic algorithm using eligibility traces in
the actor4) is a promising approach to deal with
2. Repeat the above scheme to converge.
some class of non-Markovian environments. The
critic estimates state values under the current pol- Where the transition probability P r(s js; a) fromicy, and the actor selects action improving its policy the state s taking action a to the state s , and reby using the estimated state values and reward sig- ward function Ra(s; s ) are given by the estimatednal. Note that if the critic fails to learn state values, model, and action selection probability  (aj; s) isthe actor can improve the policy. In many cases, the given by the actor's policy.
critic plays a role of accelerating the actor's policy
learning.
3.4 Improvement of The State RepresenIn this paper, we propose a new scheme in thetationcritic replacing TD-method with model-learning combined with DP planning. It will be able to provide Moving the representative points to the cenmore accurate TD-errors to the critic for the pur- ter of gravity: In our method, the performance of
0

0

0

0

0

0

0

10

8
ModelAC

State splitting using the likelihood of the model:

In order to decrease the non-Markovian in uence ofcoarse state discretizing, we propose a state splitting scheme using the likelihood of the model tothe sequence data. When state discretizing is toocoarse in a state region, the state transition probability would be considerably di erent in the same
region. This fact lead us that if the likelihood of
the model that is based on the splited region is considerably larger than the likelihood of the originalmodel, we should split the state region. The similar state splitting method based on the likelihood is
proposed using decision trees9) . In their method,
the state space is quantized by hyper rectangles,
but our method is discretized in the way of Voronoi
graph. The details of the state splitting algorithm
is omitted because of the limited space.
4

Experiments

In order to con rm the e ects of our model-based
actor-critic and state splitting, we compare the othertwo algorithms: one is estimated optimal policy derived by DP in the estimated model, the other isa standard actor-critic4) . We set the discount rate
= 0:9, and the actor's learning coeÆcient of our
method and the standard actor-critic are set to 0:02,
and the critic's learning rate is 0:4. The discrete
action representation is corresponds to the initial
representative points for discrete state representation, given by: (1 1 1 1 1 1 1 1), (0 0 0 0 0 0 00), (1 1 1 1 0 0 0 0), (0 0 0 0 1 1 1 1), (1 1 0
0 1 1 0 0), (0 0 1 1 0 0 1 1), (1 0 1 0 1 0 1 0),(0 1 0 1 0 1 0 1)．Fig.4 shows the performance oflearned policy averaged over 5 trials. The distancethreshold of the generating new state is 2:0, and all
the learning methods use the same state representations containing 13 states. Fig.5 and 6 are the samecon guration except for the number of states, 24
and 46 respectively. The policies obtained by only
the model learning and DP planning hardly moveto the front. The proposed method tends to nd
better policies than other methods as smaller thenumber of states.

Averaged Reward (1000 steps)

the model would vary in the di erent trials, because
the position of the generating new representative
point that depends on the corresponding current
state input is quite accidental. Moving the representative points to the center of gravity may improve
the performance.

6
NormalAC
4

2
RND_DP

0
0

2000

4000

6000
Learning Steps

8000

10000

Figure 4: The performance of learned policy averaged over 5 trials in 13 states. The bars are upper or lower bound of the data. ModelAC is the
proposed method, RND-DP is model-learning plus
DP-planning with random search behavior.
Fig.7 shows the e ect of improving state representation by the proposed splitting scheme. Thee ect is evaluated by the quality of learned policies
in the model learning combined with DP-planning
only method. The scheme of moving state representative points improves performance, then it nds
good policies frequently. The more increase splitting, the agent nds good policies more stably. But
in our method, the likelihood of the model is decreased when the splitting is increased.
We applied the proposed method to the real robot
shown in Fig.1, and the learner nds good policies
to walk within about 15 minutes.
5

DiscussionInsuÆciency of visiting important states: On

the learning of the transition models, arbitrary action selection policy can be taken. This feature often cause insuÆcient visiting to important states.
For this reason, the e ect of the proposed method
becomes weak as increasing states. Although weomitted detailed experimental results, when the crawling robot learns moving backward from the modelthat is constructed by a random action selection, it
is failed to nd such control rules, because such arandom policy would not provide useful experiences
for learning to move backward.
Accidental state representation: The proposed
method generates discrete state representations on

8

8

6

Averaged Reward (1000 steps)

10

Averaged Reward (1000 steps)

10

ModelAC

4
NormalAC
2

6

4
Adj

AdjSp3

2
AdjSp5
AdjSp4

RND_DP
0

AdjSp1
AdjSp2

0
0

2000

4000

6000
Learning Steps

8000

10000

2000

4000

6000
Learning Steps

8000

10000

10

Figure 7: The e ect of splitting states. Adj is moving representative state points to the center of gravity of the data, AdjSp1 is splitting one state from
Adj, AdjSp2 is splitting one state from AdjSp1, andso on.

8

References

Averaged Reward (1000 steps)

Figure 5: The performance of learned policy averaged over 5 trials in 24 states. ModelAC is the
proposed method, RND-DP is model-learning plus
DP-planning with random search behavior.

0ModelAC
61) Asada, M., Noda, S. & Hosoda, K.: Action-Based StateSpace Construction for Robot Learning, Journal of the
Robotics Society of Japan, Vol.15, No.6, pp.886{892, 1997
(in Japanese).

NormalAC
4

2
RND_DP

0
0

2000

4000

6000
Learning Steps

8000

10000

Figure 6: The performance of learned policy averaged over 5 trials in 46 states. ModelAC is the
proposed method, RND-DP is model-learning plus
DP-planning with random search behavior.
demand. As a result, the position of the generated
new representative points are quite accidental, andthe quality of the control rules depend on the position of the states. Finding stable generative state
representation is a challenging future work.

Limitations of local search in the policy space:
Since the proposed method is an extension of theactor-critic algorithm, It remains the same problem
due to the local policy search algorithm. In order toavoid this problem, it may be necessary to employ amethod holding several policies and improving themconcurrently using techniques such as importancesampling.

2) Barto, A. G., Bradtke, S. J. & Singh, S. P.: Learning to
act using real-time dynamic programming, Arti cial Intelligence 72, pp.81{138. (1995).
3) Kanehiro, F. Inaba, M. and Inoue, H.: StateNet: State
Transition Graph Description of Action Space that Includes Error Recovery Function, Journal of the Robotics
Society of Japan, Vol.20, No.8, pp.835{843, 2002 (in Japanese).
4) Kimura, H. & Kobayashi, S.: An Analysis of Actor/Critic
Algorithms using Eligibility Traces: Reinforcement Learning with Imperfect Value Function, 15th International Conference on Machine Learning, pp.278{286 (1998).
5) Kimura, H. and Kobayasi, S.: Reinforcement learningof walking behavior for a four-legged robot, Trans.IEE ofJapan, Vol.122-C, No.3, pp.330{337 (2002)
6) Sutton, R. S. & Barto, A.: Reinforcement Learning: An
Introduction, A Bradford Book, The MIT Press (1998).
7) Takahashi, Y. and Asada, M.: Incremental State Space
Segmentation for Behavior Learning by Real Robot, Journal of the Robotics Society of Japan, Vol.17, No.1, pp.118{
124, 1999 (in Japanese).

8) Watkins, C.J.C.H. & Dayan, P.: Technical Note: Q-Learning,
Machine Learning 8, pp.279{292 (1992).
9) Yairi, T. & Hori, K. & Nakasuka, S.: State Generalization Based on Maximum Likelihood Estimation Considering Multiple Behavior Outcomes, Journal of Japanese Society for Arti cial Intelligence, Vol.16, No.1, pp.128{138(2001 in Japanese).