Proceedings of the 40th IEEE
Conference on Decision and Control
Orlando, Florida USA, December 2001

TuM01-3

R e i n f o r c e m e n t Learning of Walking Behavior
for a Four-Legged R o b o t

Hajime Kimura
GEN~FE.DIS.TITECH.AC.JP
Toru Yamashita
Y A M A ~ F E . D I S .TITECH.AC .JP
Shigenobu Kobayashi
KOBAYASI~DIS .TITECH.AC .JP
Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, Yokohama 226-8502 JAPAN

Abstract
In this paper, we investigate a reinforcement
learning of walking behavior for a four-legged
robot. The robot has two servo motors perleg, so this problem has eight-dimensional
continuous state/action space. We present
an action selection scheme for actor-critic algorithms, in which the actor selects a continuous action from its bounded action spaceby using the normal distribution. The experimental results show the robot successfully
learns to walk in practical learning steps.

D

1. I n t r o d u c t i o n
Reinforcement learning (RL) is a promising method
for robots to obtain and improve control rules from interaction with their environment. The most standard
approach of RL is the value-function approach, thatis, estimating state-action value function and thereafter determining an optimal policy from it. Learning control in real world applications requires dealing
with both continuous state and/or continuous action
spaces. There are many works about the generalization techniques to approximate value functions overcontinuous state space; CMAC (Sutton ~ Barto 1998)
is one of linear architectures (Bertsekas & Tsitsiklis
1996) and the others are neural-networks, instancebased methods (Santamaria et al. 1998), etc. However, the value function approach is infeasible in highdimensional state-action space, because it needs enormous trials and memory-resources to find optimal deterministic policies.

vestigate an actor-critic algorithm and apply it to afour-legged robot. The robot has two servo motors perleg, so this problem has eight-dimensional continuous
state/action space. We present a new action selection
scheme for actor-critic algorithms, in which the actor
selects a continuous action from its bounded action
space by using the normal distribution. The experimental results show the robot successfully learns towalk in practical learning steps.

Actor-critic algorithms are an alternative approachbased on policy gradient methods, in which a parameterized stochastic policy is updated according to thegradient of the value function with respect to thepolicy parameters. Although this approach can find
only a locally optimal policy, it has several practical features for solving RL problems which have highdimensional state-action space. In this paper, we in-

We consider a real four legged locomotion task shownin Figure 1. The objective of learning is to find control rules to move forward, but the controller does notknow the dynamics ahead of time. The control rules
are specified by a policy function, that is, a mappingfrom state to a probability distribution over actions.
The controller improves its behavior through a processof trial and error. As shown in Figure 1, each leg is0-7803-7061-9/01/$10.00 © 2001 IEEE

411

Figure 1. The robot. Each leg is controlled by two servo
motors that react to angular-position commands.

2. P r o b l e m

Formulation

2.1 F o u r Legged Robotcontrolled by two servo motors that react to angularposition commands. Therefore, the robot has 8 degreeof freedom.

3. R e i n f o r c e m e n t

Learning

Algorithms

3.1 A c t o r - C r i t i c M e t h o d s

At each time step, the learning controller observes current angular-position of 8 motors as the current state,and selects action according to its policy. The actionis also the angular-position of 8 motors. Accordingly,
the current state is equal to the previous action. At
an interval of 0.5 sec, an immediate reward is given
to the learner as a result of the action, and the time
step proceeds to the next step. Two wheels shown in
the right-hand side of Figure 1 detect a movement of
the body, and generate the reward signal; the averageof the moved distance of the wheels is the moved distance of the robot, and the differential of the wheels
indicates the amount of turning the head. Since wewant the robot to go straight, the immediate reward
is defined as the average of the wheels minus absolutevalue of the differential of the wheels. The wheels havea diameter of 5cm, and turning full circle generates 200
pulses.
2.2 M a r k o v D e c i s i o n P r o b l e m
We modeled the robot's learning task as a reinforcement learning task in a Markov decision process shownin the following. Let S denote state space, ~4 be action space, 7~ be a set of real number. At each discrete
time t, the agent observes state st E $, selects action
at E .A, and then receives an instantaneous reward
rt E Tt resulting from state transition in the environment. In general, the reward and the next state may
be random, but their probability distributions are assumed to depend only on st and at in Markov decision
processes (MDPs), in which many reinforcement learning algorithms are studied. In MDPs, the next state
st+l is chosen according to the transition probabilityT(st, a, st+l), and the reward rt is given randomly according to the expectation r(st, a).
The learning agent does not know T(st,a, st+l) andr(st,a) ahead of time. The objective of RL is toconstruct a policy that maximizes the agent's performance. A natural performance measure for infinite
horizon tasks is the cumulative discounted reward:

Agent

at

Actor
stochastic policy 7r.......

_~reinforcement for at', rt + 7 V ( s t + l ) - ~Z(st) ;, WD-error

I"[,

CriticObservation

l)(s)

i~-

rt

RewardActionv

Environment

Figure 2. A standard actor-critic architecture. The critic
estimates state values and provides the TD-error to the actor. The actor updates the policy using it. If the TD-error> 0, the actor raises probability of action at because theaction at would lead the agent to a better state. Otherwise,
it decreases the probability of at.
Actor-critic architecture (see Figure 2) is one ofpromising methods to solve reinforcement learning
problems not only in MDPs, but also some POMDPs.
The actor implements a stochastic policy that maps
from state to a probability distribution over actions.
The critic attempts to estimate the evaluation function for the current policy. The actor improves its
control policy using critic's temporal difference (TD)as an effective reinforcement. In many cases, the policy
improvement is executed concurrently with the policy
evaluation, because it is not feasible to wait for thepolicy evaluation to converge.
Figure 3 specifies an actor-critic algorithm we used.
It is noteworthy that both the actor and the critic
adopt eligibility traces; obviously TD(A) in the critic
refers to use it, and the actor uses eligibility traces onpolicy parameters (Baird ~ Moore, 1999; Kimura
Kobayashi, 1998).

oo

- E

(1)

k=O

where the discount factor, 0 _ 7 ~_ 1 specifies theimportance of future rewards, and Vt is the value attime t. In MDPs, the value can be defined as:

3.1.1 LEARNING RULES IN THE CRITICThe calculation scheme of the TD(A) in the critic is
described in Step 3 and 5 in Figure 3. The parameter
Av specifies the eligibility trace of the T D ( A - Av).
3.1.2 LEARNING RULES IN THE ACTOR

where E{.} denotes the expectation. The objective
in MDPs is to find an optimal policy that maximizes
the value of each state s defined by Equation 2. In thisrobot task, the state space is continuous, bounded andeight dimensional, and the action space is the same.

412

In the actor, the policy is parameterized by parameters
and updated according to the gradient of value function with respect to the policy parameters (Kimura
and Kobayashi, 1998; Sutton, McAllester, Singh
Mansour,2000). Let 7r(alO, s) denote probability of selecting action a under the policy 7r in the state s. The

1r(a]O, s) is taken to be a probability density function
when the set of possible action is continuous. The
agent improves the policy 7r by modifying the parameter 0.

1. Observe state st, choose action at with probability 7r(at 10, st), and perform it.
2. Observe immediate reward rt, resulting state
st+l, and calculate the TD-error according to(TD-error) - rt + 7 V (st+l) - V ( s t ) , (3)where 0 _< 7 _< 1 is the discount factor, V(s)is an estimated value function by the critic.
3. Update the estimating value function V(s) inthe critic according to the TD(A) method as:

The actor's learning rule is shown in the step 4 and5 in Figure 3. The parameter A~ specifies the actor's
eligibility trace, but its features are somewhat different
from TD()~)'s. When A~ is close to 0, the policy would
be updated according to the gradient of the estimatedvalue function V, and when )~ is close to 1, the policy
would be updated by the gradient of the actual return,defined by Equation 1.
3.2 I m p l e m e n t a t i o n

for t h e R o b o t

The vector (sl, s 2 , . . . , s8) represents the angular positions of 8 motors as the state input, which are normalized as - 1 < si < 1, where i - 1 , 2 , . . . , 8 . In thecritic, the continuous state-space is discretized into 2 s
hyper square cells, and the state is encoded by a unit
basis vector (xl, x 2 , . - . , x256) of length - 2 s, in which
one component corresponding the current state is 1,
and the others are 0. The estimated value r~(st) using
in Figure 3 is given by
m

^

¢.(t)
w(t)
Aw(t)
w

(4)

=

e--

+ w(t),(TD-error)~-7(t) ,w+avAw(t),where ev denotes the eligibility of the parameter w in the function approximator V(s),is its trace, and c~ is a learning rate.
4. Update the actor's stochastic policy by°-e-g(t)
A0(t)
0

=

O ln(rr(atlO, s t ) ) ,+-+--e,~(t) +-gT(t) ,(TD-error)~7(t) ,O+a~AO(t) ,(5)-where wi is a parameter for the value function
approximation.
Let ev(t)i be the eligibility forthe i th parapeter w/ in Equation 4, i.e., e~(t) =(ev(t)l, ev(t)2, . . .ev(t)i . . . , ev(t)256), then from Equation 6, it is given by~7(t+l)+-10ev(t)i-,wherexi-1,, where x i - 0 .

(7)

Let a vector (a(1),a(2),"-,a(8)) be the angular positions of 8 motors as an action output, which are also
normalized as - 1 _< a(i) _< 1, where i - 1 , 2 , . . . , 8 .
The actor uses the following action-selection scheme;for each motor (i), the actor draws random samples
from the normal distribution N(#(i), cr~i)) until a sample which satisfies [-1, 1] is generated, and takes thelast one as the a(i). The parameters #(i) and ~r(i) are
given by the sigmoid function"

5. Discount the eligibility traces as follows:+-- 7 Av ~-j(t) ,

(6)

i=1

where e~ is the eligibility of the policy parameter 0, ~ is its trace, and a~ is a learningrate.

~-j(t + 1)

256

7A~V(t),where A~ and A~ (0 <_ A~,A~ _< 1) are discount factors in the critic and the actor respectively.

#(i)

6. Let t +-- t + 1, and go to step 1.

2

=

- 1 ,

1 + exp ( - }--]~=: sk 0k,(i))
1Figure 3. An actor-critic algorithm using eligibility traces
in both the actor and the critic. The critic is assumed to
be a linear architecture.

er(i)

=

1 + exp (-09,(i))'

where Ok,(i) (k -- 1, 2 , . . . 9 ) denotes policy parameters.
Let Pi~ be probability of generating a sample within[-1,1] from the distribution N(#(i), er~i)) as

1
Pin -

413

1 a(i) x / ~ exp((x_,(,))2)-2(r~i)dx(8)11. The divergence of the eligibility leads the algorithm to learning failure. For this reason, we adopt aheuristics that controls the step size of the update parameters so that it is proportional to ~r~i). Then, theeligibilities are given byThen, the policy function is given by;r(a(i) [0, st )= (1 + (i - Pin)+ ( 1 - Pin) 2 +...)
1((a(i)-#(i)) 2)×~exp

e~(t)k,(~)

-

=

=

1

1

Pin (7(i)~((a(i)-p(i))
exp 2cr~i)

2),

02,(1)
02,(2)

01,(8)

02,(8)"'""'"

09,(1 )
09,(2 )

"'"

09,(8

=

.

.

e~r (t) 1,(8)•e~r (t)2,(8)-..

(0
Pin Oa(i)Pi.1 ) '(13)

where k - 9.

4. R e s u l t s

)

..

~)

( 1 - or(i)) ( ( a ( i ) - #(i)) 2 - ~r~i))+(1 - cr(i))a~i)•-(1 - #(i))(1 + #(i))/2 (a(i) - ,(i))

si (1 - p(i))(1 + p(i)) ~i) Pi. O#(i) Pin+
2
where k - 1,2,-..8,

where a(i) is bounded by [-1, 1]. Let e~(t)k,(i) be theeligibility for the k th policy parapeter 0k,(i) associatedwith the i th motor, i.e., 0 and e=(t) shown in in Equation 5 represent a 9 x 8 matrix:

01,(1)
01,(2)si(9)

We applied the algorithm to the robot on two conditions; one is on a carpet, the other is on a highfrictional rubber mat. Throughout the experiments,
we use the following parameters: 7 = 0.9, av = 0.1,
a v = 0.002, Av = 1.0, Av = 1.0.

:•e~r (t)9,(8)From Equation 5 and 9, each e~(t)k,(i) is given by'e,~(t)k,(i)0-OOk,(i) In 7r(a(i)lO, st)(= si(1--#(i))(1+#(i))21(a(i)--#(i)~2(4)(a(i)-p(i)) 2 )o~ .5 \_2cr~i )4- Pin 0 ~~nl~
Op(i)

~ 40
~ .,5

\

I
,

'

1, 2 , . . . 8 . The eligibility for k - 9 is00

In rr(a(i) 10, st)ln(1cr3(~)(i) + Pi,~

'

;

+~

-~

(a(i)-p(i)) 2)= C30k,(i)Oct(i) pincr(i)x/_~__~ exp _2cr~i )= cr(i)(1 - ~r(i))( (a(i) - It(i)) 2 - cr2
0
1)
x

I'

i

-20

0

0(r(i)t I~ |.~--x--[_it~_ OOk,(i)O#(i) O#(i)0_~ In pi,~(r(i)vr~--~ exp

where k -on carpet~
on rubber mat

Oct(i)

Pi,~

'

2500

5000
leaming step

~s'oo

10000

Figure 4. Learning curves averaged over 2 trials on the carpet and the high-frictional rubber mat. Each run consistedof 10000 steps (about 80 minutes).

(11)

where k - 9. The second term of Equation 10 and 11
involve differentiating a definite integral with respect
to #(4) or cr(i). We give it by an approximated numerical calculation, but the computational cost can be easily reduced by using a table, because the function is
only depend on it(i) and cr(i) which are bounded.
Here we must draw attention to the fact that the eligibility is to divergent when or(i) goes close to 0, because~(i) is occupying the denominators of Equation 10 and

414

Figure 4 shows learning curves for the robot on the carpet and the rubber mat. The vertical axis shows theaccumulated reward translated into moved distanceto the front, but the reward signal is given according to (average of the two wheel's moved distance tothe front) - (absolute value of the differential of thewheels). Therefore, the falling curves do not (always)
mean that the robot is moving backward in the earlystage of the learning in Figure 4. On both conditions,the robot typically found good behavior in fewer than6000 steps (about 50 minutes), and the actual velocity of the learned robot is about 5cm/sec after 10000

.......................
{
.1~

",

-

"

A
:'-.

".. .....

-

A

/\

/ \

"~

i ".

./.

'
.4
..,," ~

leg 1
leg 2 ---,..

'
~,
/.\

-

leg 3 ,,,,o~';,

,,

@

-64

-

-128

0

: ...... " \ ~

Y

i

i

2

4

6

-

i

-

8

10

learning step

o

-64

/
0

i

i

2

4

i

I

6

8

10

learning step

Figure 5. Gait pattern of the learned behavior on the carpet after 10000 steps (about 80 minutes). The top graphshows the movement for lifting legs, and the bottom graphis the movement for swinging legs. This gait seems a trot.
steps. The difference of the performance between the
carpet and the rubber m a t arise from the difference of
the area. Since the rubber m a t has small area, more
loss of reward was enforced to keep moving on the mat.
In both case, the robot learned to behave like a turtle
as shown in Figure 6, and Figure 5 is its gait pattern.
The right-hand foreleg and the left hind-leg move inthe same phase, and the left foreleg and the right hindleg also move in the same phase. This gait seems atrot.
However, the behavior is slightly different between the
carpet and the rubber mat. On the carpet, the robot
tends to drag the body, because the body easily slips
on it. It rather learns to weight down the supporting leg which contributes most to moving forward. On
the other hand, on the high-frictional rubber mat, therobot keeps the body away from the ground. These observations support that the robot found good behavior

Figure 6. Learned behavior on the carpet after 10000 steps(about 80 minutes).

adaptively for each condition.

415

5. D i s c u s s i o n

References

Although there are several works making use of thenormal distribution in the actor (e.g., Williams 1992,
Doya 1997, Kimura ~ Kobayashi 1998, etc.), the naive
implementation easily causes learning failure in ourdomain. The main reason is that the naive implementation in the actor does not use the information o fboundaries of the action space. In the naive method,when the actor selects an action which is out of theboundaries, then the robot pretends to perform it, but
the actually executed action is on the boundary. If themean value of the distribution is moved to out of theboundaries, the robot can hardly move randomly, andlearning would be failed. The proposed method avoids
it by simply rejecting such actions. In compensation
for avoiding failure, the additional computational costis needed to calculate the eligibilities.

Bertsekas, D.P. ~ Tsitsiklis, J.N. (1996).
Dynamic Programming, Athena Scientific.

Neuro-

Doya, K. (1997). Efficient Nonlinear Control with
Actor-Tutor Architecture, Advances in Neural Information Processing Systems 9, pp. 1012-1018.
Kimura, H. ~ Kobayashi, S. (1998). An Analysis
of Actor/Critic Algorithms using Eligibility Traces:
Reinforcement Learning with Imperfect Value Function, 15th International Conference on Machine
Learning, pp.278-286.
Konda, V.R. ~ Tsitsiklis, J.N. (2000). Actor-Critic
Algorithms, Advances in Neural Information Processing Systems 12, pp. 1008-1014.
Santamaria, J.C., Sutton, R.S. & Ram, A. (1998). Experiments with Reinforcement Learning in Problems
with Continuous State and Action Spaces, Adaptive
Behavior 6 (2), pp. 163-218.

The coarse state-space quantization used in the critic
is one of simple and promising methods to cope withhigh-dimensional state space, but it has two undesirable effects; one is that it makes the environment nonMarkovian, the other is difficulties of finding good policies from such coarse value functions. The experimental results support that the actor's eligibility makes therobot less sensitive to these effects. Konda and Tsitsiklis (2000) proposed the other approach that the critic
should use the actor's eligibility as the feature vector
in order to approximate value (or q) functions. Theirapproach is mathematically sound and also promisingin high-dimensional problems.

Singh, S.P. ~ Sutton, R.S. (1996). Reinforcement
Learning with Replacing Eligibility Traces, Machine
Learning 22, pp.123-158.
Sutton, R.S. ~ Barto, A. (1998). Reinforcement
Learning: An Introduction, A Bradford Book, The
MIT Press.
Sutton, R.S., McAllester, D., Singh, S. ~z Mansour,Y. (2000). Policy Gradient Methods for Reinforcement Learning with Function Approximation, Advances in Neural Information Processing Systems 12(NIPS12), pp. 1057-1063.

The following three subjects restricted flexibility ofpolicy representation; one is the relatively small number of policy parameters, the use of the sigmoid function, and the other is the use of the normal distribution
for the policy. These were given by experts as knowledge of the domain, and contributed reducing search
space for learning within the practical steps. Thanks
to the policy gradient theorem (Sutton et al. 2000),
the actor can adopt any non-linear distribution functions as its policy under the assumption that the policy
is differentiable with respect to its parameters. This
flexibility of the policy function is useful for incorporating the expert's knowledge into the policy. Alsosupervised learning techniques would be available because the knowledge is provided by input-output mapping in many cases.

Williams, R. J. (1992). Simple Statistical Gradient
Following Algorithms for Connectionist Reinforcement Learning, Machine Learning 8, pp. 229-256.

In our sense, the robot learned somewhat undesirable
behavior such as dragging the body in the experiment. If the reward setting reflects conditions such aswhether the body touches the floor or not, or costs ofmoving legs, then the learner will find better behavior
in the context of the robotics.

416