Auton Robot
DOI 10.1007/s10514-009-9133-z

Nonparametric representation of an approximated Poincaré map
for learning biped locomotion
Jun Morimoto · Christopher G. Atkeson

Received: 17 November 2008 / Accepted: 2 August 2009
© Springer Science+Business Media, LLC 2009

Abstract We propose approximating a Poincaré map of
biped walking dynamics using Gaussian processes. We locally optimize parameters of a given biped walking controller based on the approximated Poincaré map. By using
Gaussian processes, we can estimate a probability distribution of a target nonlinear function with a given covariance. Thus, an optimization method can take the uncertainty
of approximated maps into account throughout the learning
process. We use a reinforcement learning (RL) method as
the optimization method. Although RL is a useful non-linear
optimizer, it is usually difficult to apply RL to real robotic
systems due to the large number of iterations required to acquire suitable policies. In this study, we first approximatedthe Poincaré map by using data from a real robot, and thenapplied RL using the estimated map in order to optimize
stepping and walking policies. We show that we can improve stepping and walking policies both in simulated andreal environments. Experimental validation on a humanoid
robot of the approach is presented.
Keywords Bipedal walking · Reinforcement learning ·Poincaré map · Gaussian processes · Humanoid robot
J. Morimoto ()Computational Brain Project, Japan Science and Technology
Agency, ICORP, Saitama, Japane-mail: xmorimo@atr.jp
J. Morimoto
Department of Brain Robot Interface, ATR Computational
Neuroscience Laboratories, Kyoto, Japan
C.G. Atkeson
The Robotics Institute, Carnegie Mellon University, Pittsburgh,USAe-mail: cga@cs.cmu.edu

1 Introduction
Local stability of biped walking patterns has been evaluatedusing Poincaré maps (McGeer 1990; der Linde 1999). If
a dynamical model of a biped robot and a ground contact
model are available, a Poincaré map can be derived analytically for a specified periodic orbit (Westervelt et al. 2004;
Shiriaev et al. 2005). However, in real environments, the correct robot model and the ground contact model are difficult
to identify. Therefore, we consider representing a Poincaré
map by using a nonparametric representation based on sampled data from the real environment.
As the amount of data increases, the complexity of the
Poincaré map model can be flexibly increased if we use a
nonparametric approximation method such as a GaussianProcess (Rasmussen and Williams 2006). We try to locally optimize parameters of a given biped walking controller based on the approximated Poincaré map. We use
a reinforcement learning (RL) method as the optimization
method.
A Gaussian process model allows us to estimate the probability distribution of a target nonlinear function with agiven covariance. Gaussian processes can estimate the accuracy of the approximated function based on the densityof the sampled data. This is beneficial, as it is difficult touniformly collect data from a real robot due to unknown dynamics. By using this stochastic model, RL can take the accuracy of the approximated model into account throughout
the learning process.
RL does not require a precise environmental model, andcan be a useful technique to improve task performance ofreal robots. However, one drawback of using RL is thatit usually requires a large number of iterations to improvepolicies. For this reason applications of RL to real environments have been limited (Benbrahim and Franklin 1997;

Auton Robot

(A)

(B)

Fig. 1 (A) 3D biped simulation model. Height: 1.6 m, total weight:
95 kg. (B) Small humanoid robot used in the experiment

Morimoto and Doya 2001; Tedrake et al. 2004; Morimotoand Atkeson 2007; Matsubara et al. 2006; Endo et al. 2008;
Peters and Schaal 2008).
Methods to improve policy parameters by using inaccurate models have been studied in Atkeson and Schaal (1997),
Atkeson (1998), Abbeel et al. (2006). In our approach, we
propose the use of a task specific stochastic model insteadof using a robot in a real environment to improve a policy.
In this study, we focus on improving the locomotive performance of biped robots as an application of our learning
framework. The dynamics of biped robots characteristically
include contact and collision with the ground. Modeling theinteraction with the ground is difficult in general. Using RL
methods can be a suitable approach to improve a walking
policy. We directly approximate Poincaré maps of stepping
and walking dynamics without explicitly identifying rigid
body inertial parameters and without the use of a groundcontact model.
To show the learning performance on robots which havedifferent kinematics and dynamics, we apply our learning
framework to a 3D biped simulation model (see Fig. 1(A))
and a small humanoid robot (see Fig. 1(B)).
In our approach, 1) we first construct a stepping and awalking controller (Morimoto et al. 2006, 2008) introducedin Sect. 2. We use simple periodic functions (sinusoids) as
desired joint trajectories, where the phases of the sinusoids
are modulated by the phase of the robot dynamics. Then,
2) we control the amplitude of the sinusoids according to
the current state of the robot to improve locomotive performance.
In Sect. 3, our learning method, which uses approximatedPoincaré maps of stepping and walking dynamics is introduced. In Sect. 4, we explain how we apply a Gaussian
process model to approximate stepping and walking dynamics. In Sect. 5, we describe implementation of a RL method
for our learning framework, that uses the dynamics approximated by a Gaussian process.

Fig. 2 Joint index of biped model: (A) Roll joints for lateral movements. (B) Pitch joints for lateral and forward movements

2 Periodic pattern generator
Our biped controller uses a coupled oscillator model to modulate the phase of sinusoidal patterns. The aim of using acoupled oscillator model is to synchronize periodic patterns
generated by the controller with the dynamics of the robot.
To use the coupled oscillator model, detection of the phaseof the robot is needed. We introduce a method to detect robot phase in Sect. 2.1. We briefly explain phase coordination
for biped walking in Sect. 2.2. We use simple sinusoidal patterns as nominal trajectories for each joint. We describe thedesign of the nominal trajectories for stepping movements in
Sect. 2.3, and walking movements in Sect. 2.4. Conventions
for representing joint movement are presented in Fig. 2.
2.1 Phase detection
By using the oscillator model, we can independently design
the phase dynamics and amplitude of periodic walking patterns (Tsuchiya et al. 2003). However, to take the sensory
information into account in the oscillator system, we needto explicitly detect the phase of the robot dynamics.
As shown by our previous study (Morimoto et al. 2006,2008), we can use the center of pressure ycop and the velocity of the center of pressure ẏcop to detect the phase of therobot dynamics:


ẏcop
,
(1)
φ(ycop ) = − arctan
ycop
where ycop = (ycop , ẏcop ) (see Fig. 3). We use a simplified
COP detection method introduced in Morimoto et al. (2006,2008).
2.2 Phase coordination
In this study, we use four oscillators with phases φci , wherei = 1, 2, 3, 4. We introduce coupling between the oscillators

Auton Robot

joint angles for each joint are:
θhdroll (φc ) = Ahroll sin(φc ),(3)θadroll (φc ) = −Aa roll sin(φc ),(4)

where Ahroll and Aa roll are the amplitudes of a sinusoidal
function for lateral movements at the hip and the ankle
joints, and we use an oscillator with the phase φc = φc1 .
2) Pitch joint movements: To achieve foot clearance, we
generate vertical movement of the feet (Fig. 2(B)) by using
simple sinusoidal trajectories:
Fig. 3 (A) Inverted pendulum model represented by the center of pressure (COP) and the center of mass (COM). (B) ψ roll denotes the rollangle of the pendulum. (C) ψ pitch denotes the pitch angle of the pendulumθhdpitch (φc ) = Apitch sin(φc ) + θhres
pitch ,
θkdpitch (φc ) = −2Apitch sin(φc ) + θkres
pitch ,

(5)

θadpitch (φc ) = −Apitch sin(φc ) + θares
pitch ,
where Apitch is the amplitude of a sinusoidal function. θhres
pitch ,
res represent the rest posture of the hip, knee, and
,
θ
θkres
pitch
a pitchankle joints respectively. We use the oscillator with phase
φc = φc1 for right limb movement and use the oscillator withphase φc = φc3 , which has phase difference of φc3 = φc1 + π ,for left limb movement as in Fig. 4.
2.4 Additional pitch joint movements for walking
behaviors
Fig. 4 Phase coordination. We use four oscillators with phases{φc1 , φc2 , φc3 , φc4 } to make symmetric patterns for a lateral movementwith the left and right limbs, and also to make symmetric patterns for a
forward movement with the left and right limbs. Arrows “→” indicate
phase advance, e.g., φc2 = φc1 + π2 and φc3 = φc1 + π

and the phase of the robot dynamics φ(ycop ) in (1) to regulate the desired phase relationship between the oscillators:
φ̇ci = ωc + Kc sin(φ(ycop ) − φci + φdi ),(2)

where φdi is the desired phase difference, Kc is a coupling
constant, and ωc is the natural angular frequency of oscillators.
We use four desired phase differences, {φd1 , φd2 , φd3 , φd4 } ={− 12 π, 0.0, 12 π, π}, to make symmetric patterns for stepping
movement with the left and right limbs, and also to makesymmetric patterns for forward movement with the left andright limbs. Figure 4 shows the phase coordination.
2.3 Desired joint angles
1) Roll joint movements: We introduce a controller to generate lateral movement. We control the hip joints θhroll andthe ankle joints θa roll (Fig. 2(A)) for this movement. Desired

To walk forward, we use an additional sinusoidal trajectory.
Thus, the desired nominal trajectories for the right hip andankle pitch joints become:_walk = A2d1
θhdpitch
walk sin(φc ) + θhpitch (φc ),_walk = −A2d1
θadpitch
walk sin(φc ) + θa pitch (φc ).

(6)

We use the phase φc2 , which has a 12 π phase difference of φc1
for the right limb. We use φc3 and φc4 for the left limb insteadof φc1 and φc2 .

3 Learning framework
We consider approximating Poincaré maps for stepping andwalking dynamics to improve task performance throughmodel-based reinforcement learning (Kuvayev and Sutton
1996). A number of biped walking studies have emphasized that humanoid robots have inverted pendulum dynamics (see Fig. 3), with the top of the pendulum at the center of mass and the base at the center of pressure. Control
strategies to stabilize such dynamics have been proposed(Miyazaki and Arimoto 1981; Miura and Shimoyama 1984;
Sugihara and Nakamura 2002; Hyon et al. 2007). In thisstudy, we propose using the state of the inverted pendulum

Auton Robot

Fig. 5 Step 2 and 3 in Algorithm 1. Apply the current policy with
fixed policy parameters w to the actual robot dynamics and sample
data. Generate a Gaussian process model which represents the stepping
and walking dynamics

Fig. 6 Step 4 in Algorithm 1. Update policy parameters w by applying
a reinforcement learning method to the acquired inverted pendulum
model represented by a Gaussian process

Algorithm 1
1. Initialize policy parameters.
2. Apply the current policy to the actual robot dynamics andsample data at the defined Poincaré section (see Fig. 5).
3. Generate a Gaussian process model which represents
the stepping and walking dynamics in (7).
4. Update policy parameters by applying a reinforcement
learning method to the acquired Gaussian process (seeFig. 6).
5. If the policy is not improved, terminate the iteration.
Otherwise, go back to step 2.

The policy of the learning system outputs the next action
only at this section. We also assume that we can represent
the Poincaré map by a stochastic model. If x(k) is the k-thintersection and u(k) is the control output at the intersection,
the model is defined by:as the input state for the learning system to make learning
tractable.
We assume that nominal stepping and walking controllers
are provided (see Sect. 2), and our learning system improves
the performance of these controllers. Since the nominal controller can generate periodic movements, we only consider
the pendulum state at the Poincaré section.
For example, we consider the dynamics ξ̇ = g(ξ ) of astate vector ξ ∈ Rn . The Poincaré map is a mapping froman n − 1 dimensional surface S defined in the state space
to itself (Strogatz 1994). If ξ (k) ∈ S is the k-th intersection,then the Poincaré map h is defined by ξ (k + 1) = h(ξ (k)). In
our study, we defined the section for which the roll derivativeof the pendulum equals zero (ψ̇ roll = 0) (see Fig. 3).

x(k + 1) = f(x(k), u(k)) + n(k),(7)

where x = (ψ roll ) for stepping and x = (ψ roll , ψ pitch , ψ̇ pitch )for walking (see Fig. 3). n(k) is the noise input. f(x(k), u(k))
represents the deterministic part of the Poincaré map.
To improve task performance, we stochastically modulate the amplitude of the sinusoidal patterns according to thecurrent policy πw :πw (x(k), u(k)) = p(u(k) | x(k); w),(8)where w is the parameter vector of the policy πw . In thefollowing sections, we explain how we approximate the stochastic maps (7), and how we acquire the control policy πw .
In our learning framework, we improve the approximatedPoincaré map and the policy iteratively (see Algorithm 1).
We first sample data from a simulated model or a real robot
by using the current policy for a Gaussian process regression as in Fig. 5, and then improve the policy by using the
Poincaré map approximated by the Gaussian process as inFig. 6.

Auton Robot

4 Non-parametric system identification of Poincaré
map
We use a Gaussian process (GP) (Williams and Rasmussen
1996) to approximate the Poincaré map in (7). Gaussian
processes provide us a stochastic representation of an approximated function. With Gaussian processes for regression, we assume that the output values yi (i = 1, . . . , N ) aresampled from a zero-mean Gaussian whose covariance matrix is a function of the input vectors zi (i = 1, . . . , N ):p(y1 , . . . , yN |z1 , . . . , zN ) = N (y1 , . . . , yN | 0, K),(9)where K is an covariance matrix of input vectors with elements Kij = κ(zi , zj ). Here, we used a squared exponential
covariance function (Rasmussen and Williams 2006):



Nd
1
d
2
vk (zik − zj k ) + v1 δij ,κ(zi , zj ) = v0 exp −2(10)

Fig. 7 Simple example of Gaussian process regression. The
dash-dotted line shows the target sinusoidal function. Circles show
sampled data points from the target function with additive noise. The
solid line shows mean output of the predictive distribution represented
by the Gaussian process model. Dashed lines show the standard deviation of the predictive distribution

k=1

where δij is Kronecker delta. zik and zj k are k-th elementof i-th and j -th input vectors respectively. v0 , v1 , and vkd areparameters for the covariance matrix. Nd denotes the number of input dimensions. These parameters can be optimized
by using a type-II maximum likelihood method (Williams
and Rasmussen 1996). A covariance function introduces
similarity between data points. By using the squared exponential covariance function, closely placed data points are
similar. This similarity measure works well in many applications and is widely used (Rasmussen and Williams 2006;
Bishop 2006; Ko and Fox 2009).
Bayesian prediction of an output yN +1 corresponding to
a new input zN +1 is given as:p(yN +1 | z1 , . . . , zN , zN +1 , y1 , . . . , yN ) = N (yN +1 | μ, σ 2 ),
(11)
where

4.2 Application to Poincaré map approximation

μ = k(zN +1 )T K−1 y,(12)

σ 2 = κ(zN +1 , zN +1 ) − k(zN +1 )T K−1 k(zN +1 ).

(13)

Here the vectors y and k(zN +1 ) are defined as y = (y1 , . . . ,yN ) and k(zN +1 ) = [κ(z1 , zN +1 ), . . . , κ(zN , zN +1 )]T respectively.
4.1 Simple example
To show how the Gaussian process regression method
works, we applied the GP regression to approximate a sinusoidal function:y = sin(z) + n,

where n ∼ N (0, 0.01) denotes output noise. We used thesquared exponential covariance function in (10) with the parameters v0 = 1.0, v1 = 0.01, and vkd = 1.0.
We sampled ten data points zi (i = 1, . . . , 10) from a uniform distribution ranged over 0 ≤ z ≤ 2π . Figure 7 shows apredictive distribution of an approximated sinusoidal function. Since we only sampled ten data points, interpolated regions have large approximation errors. The uncertainty of
the interpolated regions are represented by large standard
deviations.
An important aspect of the GP regression is that the uncertainty of an approximated function caused by the small
number of training samples can be evaluated. As in Fig. 7,
the standard deviation of the region where sampled data is
not available becomes large.

(14)

We use the GP model to represent how the pendulum modelin Fig. 3 behaves with a controller, a robot, actuators, andground contact models.
The input vector z for the Gaussian process is composed of the current state x(k) and control input u(k) : z =(x(k)T , u(k)T )T . The output value y is a component of thestate vector at the next intersection x(k + 1), and the control
output u(k) is used to modulate parameters of the stepping
and walking controllers. We modulate amplitudes of the sinusoidal patterns that are used as desired joint angles.
The predictive distribution represented by this Gaussian
process method is used to improve biped stepping and walking controllers.

Auton Robot

5 Policy improvement by using a reinforcement
learning method
Here, we explain how we applied RL to our biped stepping and walking tasks. RL has been used to improve policies for challenging tasks (Riedmiller et al. 2009; Howard
et al. 2009). We used a policy gradient method proposed by(Kimura and Kobayashi 1998), to implement the RL framework. This learning method was used in biped learning studies (Tedrake et al. 2004; Matsubara et al. 2006).
Policy gradient methods are considered as robust learning methods when states for the learning system are partiallyobservable (Jaakkola et al. 1995; Baird and Moore 1999;
Meuleau et al. 2001). Convergence properties of policy gradient methods with function approximators have been studied in Sutton et al. (2000), Konda and Tsitsiklis (2003).
Since we applied RL to an approximated Poincaré map
instead of a real environment, we did not care much about
convergence speed. However, using natural policy gradientmethods (Peters and Schaal 2008; Bagnell and Schneider
2003; Kakade 2002) would reduce the time required for theentire learning process.
The basic goal is to find a policy πw (x, u) = p(u | x; w)that maximizes the expectation of the discounted accumulated reward:

∞



E{V (k)|πw } = E
γ i−k r(i)πw ,
(15)

i=k

where r denotes reward, V (k) is the actual return, w is theparameter vector of the policy πw , and γ , 0 ≤ γ < 1, is thediscount factor.
In policy gradient methods, we calculate the gradient direction of the expectation of the actual return with respect tothe parameters of a policy w. Kimura and Kobayashi (1998)
suggested that we can estimate the expectation of the gradient direction as:∞∂∂ ln πw 
E{V (0) | πw } ≈ E(V (k) − V̂ (x))
πw ,
∂w
∂w 

where wiv is a i-th parameter of the approximated valuefunction, and N is the number of basis functions bi (x). An
approximation error of the value function is represented by
the temporal difference (TD) error (Sutton and Barto 1998):
δ(k) = r(k + 1) + γ V̂ (x(k + 1)) − V̂ (x(k)),(18)

We update the parameters of the value function approximator using the TD(0) method (Sutton and Barto 1998):
wiv (k + 1) = wiv (k) + αδ(k)bi (x(k)),(19)

where α is the learning rate.
5.2 Policy parameter update
We update the parameters of a policy w by using the estimated gradient direction in (16). Kimura and Kobayashi(1998) showed that we can estimate the gradient direction
by using the TD error:∞∂ ln πw (V (k) − V̂ (x(k)))
E
πw
w 
k=0

∞



=E
δ(k)e(k)πw ,
(20)

k=0

where e is the eligibility trace of the parameter w. Eligibility traces indicate which parameters are eligible for the
TD-error and are updated as∂ ln πw (x(k), u(k)) ,(21)e(k + 1) = ηe(k) +∂w
w=w(k)
where η is the decay factor for the eligibility trace. Equation(20) can be derived if the condition η = γ is satisfied. The
parameter w is updated as:w(k + 1) = w(k) + βδ(k)e(k).

(22)

5.3 Biped stepping and walking policy

k=0

(16)
where V̂ (x) is an approximation of the value function for apolicy πw : V πw (x) = E{V (k) | x(k) = x, πw }.
5.1 Value function approximation
The value function is approximated using a normalized
Gaussian network (Doya 2000):V̂ (x) =N
i=1

wiv bi (x),(17)

We construct the biped stepping and walking policies basedon a normal distribution:πw (x, u) = N (μ(x; wμ ), (x; wσ ))(23)

where u is the output vector and  is the covariance matrixof the policy πw . In this study, we defined the covariancematrix as a diagonal matrix, where the j -th diagonal element
is represented as σj . The j -th element of the mean output μ
is modeled by a normalized Gaussian network:μj (x) =

N

i=1

μ

wi j bi (x).

(24)

Auton Robot
Table 1 Parameters of the periodic pattern generator for each experiment
Simulated model

Real robot

Stepping

Walking

Stepping

ωc

3.5

3.5

6.3

6.3

Kc

10.0

10.0

9.4

9.4

Ahroll

4.0

3.5

2.5

5.0

Aa roll

4.0

3.5

8.5

9.0

Apitch

6.0

7.0

4.0

4.0

Walkingr = −K(ψdroll − ψ roll )2

Table 2 Parameters of policy gradient method
γ

α

η

β

σ0

0.95

0.3

0.3

0.3

0.5

μ

Here, wi j denotes the i-th parameter for j -th output of thepolicy πw , and N is the number of basis functions. We represent the diagonal element of the covariance matrix  using
a sigmoid function (Kimura and Kobayashi 1998):
σj (x) =σ0,
1 + exp(−σjw (x))

where σjw (x) =Nσwi j bi (x),

i=1

(25)
σ

and σ0 denotes the scaling parameter. wi j denotes the i-th
parameter for the j -th diagonal element of the covariancematrix. We update the parameters by applying the update
rules in (22) and (21).
We use same basis functions bi (x) in (17), (24), and (25).

6 Simulation
We applied our proposed method to the simple 3D simulated
biped model in Fig. 1(A). Parameters used in the controllers
are summarized in Table 1. Parameters used in the policy
gradient method are summarized in Table 2.
6.1 Improvement of biped stepping performance
We applied our proposed method to improve stepping inplace.
We selected amplitudes of the pitch joint movements as
the control output: u(k) = Astep (k). Then, the desired joint
angles in (5) becomeθhdpitch (φc ) = (Apitch + Astep ) sin(φc ) + θhres
pitch ,
θkdpitch (φc ) = −2(Apitch + Astep ) sin(φc ) + θkres
pitch ,
θadpitch (φc ) = −(Apitch + Astep ) sin(φc ) + θares
pitch .

We flip the sign of the roll angle ψ roll in the state vector x when the sign of COP in the lateral (y) direction (seeFig. 3(A)) changes so that we can use the same policy forthe left stance phase and the right stance phase.
We defined the target of the stepping task to keep the desired state at ψdroll . We use a reward function:

(26)

(27)

for this stepping task, where the desired roll angle ψdroll =2.0◦ and K = 0.1. The learning system also receives a negative reward r = −1 if the biped model falls over. We consider that the biped model falls over when the condition
ψ roll < 0.0◦ is satisfied (the COM is outside of the stancefoot).
For the Gaussian process (GP) model, we sampled 20
data sets {x(k + 1), x(k), u(k)} from the simulated environments (at step 2 of Algorithm 1).
We compare learning performance of the proposed
method using the Gaussian process model with that of using
the full model. The full model means that we run the dynamics simulator of the biped model to learn stepping policies.
Figure 8 compared learning performance on the steppingtask by using the GP model and by using the full model. At
each visit to the Poincaré section, a reward is given according to the performance of a policy. The average reward (vertical axis) shows the average acquired reward at each visit to
the Poincaré section.
Although the variance of the learning performance islarger in early stage of the learning process if we used the GP
model, the performance of the acquired policies through the
GP model is comparable to the policies acquired through thefull model after 10 learning trials. Thus, at least for this particular example, this demonstrates that a full dynamic model
is not necessary in order to acquire a policy to achieve sufficient task performance. Especially in extensive simulation
studies, we can save computation time, and still may be able
to acquire comparable performance.
Furthermore, the acquired stepping policies based on the
GP model slightly outperformed the policies acquired by
the full model after 8th trial. This difference was significant in terms of the Student’s t-test with significance level
0.05. Since the gradient estimation of policy parameters
can be biased with limited sample data, using the approximated model with a Bayesian estimation method such as
the Gaussian process regression would generate better sample data for the gradient estimation. Therefore, it would beinteresting to compare Bayesian RL approaches (Dearden etal. 1999; Ghavamzadeh and Engel 2007) with the proposed
method as a future study in addition to applying the proposed method to other examples to show how this fact canbe generalized to other applications.
Figure 9 shows policies acquired by using the GP modeland the full model. Similar policies were acquired in theAuton Robot

Fig. 8 A comparison of learning performance. At each visit to the
Poincaré section, reward is given according to the performance of apolicy. The average reward (vertical axis) shows averaged acquired reward at each visit to the Poincaré section. The solid line represents theperformance of the proposed learning method which used the acquired
Gaussian process model. The dashed line represents the learning performance of the learning method which used the full dynamics simulation. The result shows the average performance of five simulation runs.
Error bars show the standard deviation

Fig. 10 Return map of φ roll . We show relationship between φ roll (k)and φ roll (k + 2). The dashed line shows linear approximation of the
return map

trol performance of the control output from an acquired policy. We show relationship between φ roll (k) and φ roll (k + 2).
To generate the return map, we disturbed the stepping controller for 0.2 s right after the COP crosses zero by pushing
the biped model in the horizontal (y) direction (see Fig. 2)
with randomly generated force F , where F is sampled froma uniform distribution over −40 ≤ F ≤ 40 N.
The dashed line shows the linear approximation of the
return map. Since the coefficient of the linear approximation
is much smaller than one, this result shows that the acquired
policy was able to locally stabilize the stepping dynamics.
The approximated fixed point φ roll = 2.3◦ is indicated by
the circle and is close to the desired φdroll = 2.0◦ .
6.2 Improvement of biped walking performanceFig. 9 Acquired stepping policies. The solid line represents acquired
policies using the GP model. The dashed line represents acquired policies using the full model. The results show an average policy of fivesimulation runs. Error bars show the standard deviation

region 0.0◦ < ψ roll < 4.0◦ , the region of the state space
where the policies mainly explored. Outside of the region
4.0◦ ≤ ψ roll , the policies are different because the data is notfrequently sampled from this region. From 3 to 5 basis functions are allocated to represent the mean output of the policies in (24). Therefore, from 3 to 5 parameters were needed
to be learned for the mean output. Because we adaptively allocated the basis functions, the number of basis functions aredifferent in different simulation runs (Morimoto and Doya2001).
We also investigated the robustness of an acquired stepping controller. Figure 10 show the return map of the pendulum state ψ roll . Since we change the output u(k) only at
the Poincaré section, it takes two steps to evaluate the con-

We also apply our proposed method to improve walking performance. We modulate the amplitude Awalk in (6) to generate forward movement for the biped walking task. The targetof the walking task is to increase the walking velocity. Since
the angular velocity of the pendulum ψ̇ pitch (see Fig. 3(C))
at the Poincaré section corresponds to the walking velocity,
we use the reward function:r = K(ψ̇ pitch )(28)

for this biped walking task, where K = 0.1. The learning
system also receives a negative reward r = −1 if the bipedmodel falls over.
For the Gaussian process model, we sampled 100 data
sets from the simulated environments. Figure 11 shows theinitial performance of the biped walking policy. Figure 12
shows the walking performance after one iteration of the
proposed method. One iteration means that 1) acquisitionof an approximated Poincaré map from sampled data as inFig. 5. 2) acquisition of a stepping policy using the acquired

Auton Robot

Fig. 11 Initial walking pattern. The thick line represents the starting position. Initially, the simulated robot explores around the starting position.
Time proceeds from left to rightFig. 12 Improved walking pattern after one iteration of the proposed learning process. Walking speed is 0.14 m/sec. The thick line represents thestarting position. Time proceeds from left to right

7.1 Improvement of biped stepping performance
We use the roll angle x = (ψ roll ) defined by the pendulum
model (see Fig. 3) as the state. We selected amplitudes of theankle roll movements as the control output: u(k) = Aa _step .
Thus, the desired joint angle in (4) becomesθadroll (φc ) = −(Aa roll + Aa _step ) sin(φc ).

Fig. 13 Approximated stepping dynamics of the small size humanoid robot by a Gaussian process. The input vector is defined asz = (ψ roll (k), Aa _step (k)), and the output is define as y = (ψ roll (k +1))
(see (12))

Poincaré map as in Fig. 6. 3) application of the acquired policy to the simulated robot.
This result suggests that approximated dynamics can beused to improve biped walking performance.

7 Experimental results
We applied our proposed method to a small size humanoid
robot (see Fig. 1(B)). Parameters used in the controllers are
summarized in Table 1.

(29)

Since the real robot has relatively wide feet, modulating
the ankle roll joints is an easy way to control the roll angle
x = (ψ roll ). Automatic selection of the proper action variables for a given task would be an interesting research topic
for future study.
We use the reward function:r = −K(ψdroll − ψ roll )2(30)

for this stepping task, where the desired roll angle ψdroll =0.0◦ and K = 0.1. The learning system also receives a negative reward r = −1 if the biped model falls over.
For the Gaussian process model, we sampled 20 data
sets from the real environment. Figure 13 shows an approximated Poincaré map for stepping dynamics of the small size
humanoid robot using a Gaussian process. Here we define
the input vector as z = (ψ roll (k), Aa _step (k)) and the output as y = (ψ roll (k + 1)). We apply the reinforcement learning algorithm to this acquired Poincaré map for stepping dynamics to improve stepping performance.
Figure 14 shows the roll angle ψ roll at the Poincaré section ψ̇ roll = 0. This result suggests that a stepping policy was
acquired by using our proposed method, and it can keep theAuton Robot

We use the reward function based on the pitch derivativeψ̇ pitch that corresponds to the walking velocity:r=Fig. 14 The roll angle ψ roll at the Poincaré section ψ̇ roll = 0 (solidline). The dash-dotted line represents the desired angle for this steppingtask. We used a policy acquired by the proposed learning method

Fig. 15 Acquired stepping movement of the real robot after one iteration of the proposed learning process. One iteration means that 1)
acquisition of an approximated Poincaré map from sampled real data as
in Fig. 5. 2) acquisition of a stepping policy using the acquired Poincaré
map as in Fig. 6. 3) application of the acquired policy to the real robot

roll state ψ roll around the desired angle (0.0◦ ). An averageangle from 10 to 40 steps was 0.12◦ .
Figure 15 shows the acquired stepping movement of
the real robot after one iteration of the proposed learning
process.
Again, one iteration means that 1) acquisition of an approximated Poincaré map from sampled real data as inFig. 5. 2) acquisition of a stepping policy using the acquired
Poincaré map as in Fig. 6. 3) application of the acquired policy to the real robot.
7.2 Improvement of biped walking performance
We also applied our method to improve biped walking performance of the humanoid robot. We use x = (ψ roll , ψ pitch ,ψ̇ pitch ) as the state and modulate Awalk in (6) as the actionof the learning system.

1TTψ̇ pitch (t)dt

(31)

0

for this walking task, where T is the time required for moving from a Poincaré section to the next section, which is approximately the time for one cycle of walking. We used thetime integral of the angular velocity ψ̇ pitch rather than the instantaneous angular velocity at the defined section because
the instantaneous value was not consistently related to thewalking velocity in the real environment. Since this reward
can not be simply represented by the state x at the section,
we also approximated a stochastic model of the reward function from the data acquired from the real environment byusing another Gaussian process. The learning system also
receives a negative reward r = −1 if the biped model falls
over.
For the Gaussian process model, we sampled 100 data
sets from the real environments. Figure 16 shows initial performance of the biped walking controller. The initial policy
only generates random steps and the humanoid robot could
not walk forward.
Figure 17 shows improved walking performance after the
first iteration of our learning framework. The humanoid robot could walk forward with the improved policy.
Figure 18 shows improved walking performance after thesecond iteration of our learning framework. The humanoid
robot could walk faster. We also tried additional learning
iterations. However, the walking performance did not significantly improve. We may need to use different state representations and/or reward functions to acquire additional
improvement of the walking policy.

8 Discussion
8.1 Stochastic Poincaré maps
In this study, we used a Gaussian process model to represent
Poincaré maps. We determined the number of sampled data
to represent the covariance matrix in the Gaussian processmodel so that the prediction error of the state at the next
Poincaré section becomes smaller than a given threshold.
Sparse Gaussian process methods (Smola and Bartlett
2001; Snelson and Ghahramani 2006; Candela and Rasmussen 2005) can provide a method to find a sufficient number of data points to model the Poincaré maps.
By using a Gaussian process model, we can stochastically represent accuracy of the Poincaré maps based on thedensity of the sampled data.

Auton Robot

Fig. 16 Initial walking pattern. The line on the floor represents the starting position. Initially, the humanoid robot explores around the starting
position. Time proceeds from left to rightFig. 17 Improved walking pattern after the first iteration of the proposed learning process. Estimated walking speed is 2.7 × 10−2 m/sec

Fig. 18 Improved walking pattern after the second iteration of the proposed learning process. Estimated walking speed is 4.5 × 10−2 m/sec. The
robot could walk faster with this policy than after the first iteration

In Byl and Tedrake (2008), a stochastic return map isused to represent uncertainty of the ground contact conditions. The stochastic stability when a compass-gait is walking on randomly generated terrain is studied. As Byl andTedrake (2008) pointed out, stochastic representation of thewalking dynamics can be useful to acquire robust walking
policies.
8.2 Application to other walking controllers
We applied the proposed learning method to control the amplitude of phase dependent sinusoidal patterns where thephase is modulated according to the center of pressure.
However, application of the learning method is not necessarily limited to the periodic pattern generator model (Morimoto et al. 2006, 2008).
Several biped control methods have been proposed andapplied to humanoid robots (Hirai et al. 1998; Kajita et al.
2007; Nagasaka et al. 1999, 2004; Sugihara and Nakamura
2005). Most of them use ZMP-based walking controllers.
These control methods rely on accuracy of the robot modeland tracking performance of high-gain PD controllers. Since

the ZMP-based controllers also use the inverted pendulum
model to approximate the full-body dynamics, modeling errors are inevitable and feedback controllers to change desired ZMP are necessary. To design these feedback controllers, parameters need to be hand-tuned through experiments. Our proposed learning method may potentially help
to tune parameters of the feedback controllers for ZMPbased approaches.
8.3 Selection of reward functions
For the stepping task, the reward function is defined by asquared error from a desired COM roll angle. For the walking task, the reward is given according to walking velocity.
In both tasks, negative reward is given when a biped robot
falls over. Since controlling the single support phase is thegoal for the stepping task, using COM and COP states is areasonable selection. For the walking task, moving forward
at a desired speed is one of the goals, and we can represent
this goal by including walking velocity in the reward function.

Auton Robot

Other reward functions can be adopted for the stepping
and the biped walking task. If we can measure energy consumption of real biped robots, we can consider the energy cost as a negative reward (penalty). Similarity between
walking patterns of biped robots and human walking patterns could be used to acquire a policy to generate natural
looking walking patterns. Ground reaction force can be used
as a negative reward to reduce impact forces when the swing
leg contacts the ground.

In this study, we use a reinforcement learning method(Kimura and Kobayashi 1998) to improve policy parameters. In future work, we will consider using a dynamic programming approach to efficiently update policy parameters
using the Gaussian process model (Rasmussen and Kuss
2004) since an analytical update using dynamic programming may reduce the number of iterations to achieve bettertask performance.
We will also explore convergence properties of the proposed learning method.

9 Conclusion

Acknowledgements We thank Sony Corp. for allowing us the opportunity to use the small humanoid robot. We thank Gen Endo for
helping us to setup experiments. We also thank Gordon Cheng for helpful discussions. This material is based upon work supported in partby the National Science Foundation under grants ECS-0325383, EEC0540865, and ECS-0824077.

We propose using a nonparametric representation of approximated Poincaré maps for biped stepping and walking dynamics and reinforcement learning (RL) to improve task
performance. In this study, we first approximate Poincaré
maps for stepping and walking dynamics by using data froma simulated model or a real robot, then use the approximated maps for RL to improve stepping and walking policies. We explored using a Gaussian process to approximate
the Poincaré maps. By using a Gaussian process, we can estimate a probability distribution of the target nonlinear functions with a given covariance. We showed that we could improve stepping and walking policies by using a RL methodwith approximated models both in simulated and real environments. Since we used different reward for the stepping and walking tasks, the results showed that our learning
framework can improve policies for different objective functions. We applied the proposed control approach to a small
humanoid robot.
We evaluated robustness of the resulting stepping policyby pushing the biped model in the horizontal direction andanalyzing the return map. We also showed robustness of theresulting walking policy by applying the policy to a real environment. However, by only using one fixed policy, it isdifficult to cope with a large environmental change. Therefore, it would be interesting to evaluate how our learningalgorithm can quickly adapt to environmental changes.
Compared to other biped learning approaches (e.g., Benbrahim and Franklin 1997; Tedrake et al. 2004; Morimotoand Atkeson 2007), we do not directly use real environments
to improve biped walking policies. Therefore, our learning
framework requires smaller number of samples from the realenvironment and can be applied to robots that have may degrees of freedom. On the other hand, our learning method
relies on environmental models. We take the reliability ofan acquired model into account in a policy improvement
process by representing the model with a probability distribution. The estimated reliability of the acquired model canbe related to learning performance. We will analyze this relationship in a future study.

References
Abbeel, P., Quigley, M., & Ng, A. Y. (2006). Using inaccurate models in reinforcement learning. In Proceedings of the 23rd international conference on machine learning (pp. 1–8). New York:ACM.
Atkeson, C. G. (1998). Nonparametric model-based reinforcement
learning. In M.I. Jordan, M. Kearns & S. Solla (Eds.), Advances inneural information processing systems 10 (pp. 1008–1014). Cambridge: MIT.
Atkeson, C. G., & Schaal, S. (1997). Robot learning from demonstration. In Proc. 14th international conference on machine learning(pp. 12–20). San Mateo: Morgan Kaufmann.
Bagnell, A., & Schneider, J. (2003). Covariant policy search. In Proceedings of the eighteenth international joint conference on artificial intelligence (pp. 1019–1024).
Baird, L. C., & Moore, A. W. (1999). Gradient descent for general reinforcement learning. In Advances in neural information processing
systems 11 (pp. 968–974). Cambridge: MIT.
Benbrahim, H., & Franklin, J. (1997). Biped dynamic walking using
reinforcement learning. Robotics and Autonomous Systems, 22,
283–302.
Bishop, C. M. (2006). Pattern recognition and machine learning. New
York: Springer.
Byl, K., & Tedrake, R. (2008). Metastable walking on stochasticallyrough terrain. In Proceedings of robotics: science and systems IV,
Zurich, Switzerland, June 2008.
Candela, J. Q., & Rasmussen, C. E. (2005). A unifying view of sparse
approximate Gaussian process regression. Journal of Machine
Learning Research, 6, 1939–1959.
Dearden, R., Friedman, N., & Andre, D. (1999). Model based Bayesian
exploration. In Proceedings of fifteenth conference on uncertainty
in artificial intelligence (pp. 457–464). San Francisco: Morgan
Kaufmann.
der Linde, R. Q. V. (1999). Passive bipedal walking with phasic muscle
contraction. Biological Cybernetics, 82, 227–237.
Doya, K. (2000). Reinforcement learning in continuous time and space.
Neural Computation, 12(1), 219–245.
Endo, G., Morimoto, J., Matsubara, T., Nakanishi, J., & Cheng, G.
(2008). Learning CPG-based biped locomotion with a policy
gradient method: application to a humanoid robot. International
Journal of Robotics Research, 27(2), 213–228.

Auton Robot
Ghavamzadeh, M., & Engel, Y. (2007). Bayesian policy gradient algorithms. In B. Scholkopf, J. Platt & T. Hofmann (Eds.), Advancesin neural information processing systems 19 (pp. 457–464). Cambridge: MIT.
Hirai, K., Hirose, M., & Takenaka, T. (1998). The development of
Honda humanoid robot. In Proceedings of the 1998 IEEE international conference on robotics and automation (pp. 160–165).
Howard, M., Klanke, S., Gienger, M., Goerick, C., & Vijayakumar, S.
(2009). A novel method for learning policies from variable constraint data. Autonomous Robots (same special issue, Part B).
Hyon, S., Hale, J. G., & Cheng, G. (2007). Full-body compliant
human-humanoid interaction: Balancing in the presence of unknown external forces. IEEE Transactions on Robotics, 23(5),884–898.
Jaakkola, T., Singh, S. P., & Jordan, M. I. (1995). Reinforcement
learning algorithm for partially observable Markov decision problems. In G. Tesauro, D. Touretzky & T. Leen (Eds.), Advancesin neural information processing systems 7 (pp. 345–352). Cambridge: MIT.
Kajita, S., Nagasaki, T., Kaneko, K., & Hirukawa, H. (2007). ZMPbased biped running control. Robotics and Automation Magazine,
IEEE, 14(2), 63–72.
Kakade, S. (2002). A natural policy gradient. In Advances in neural
information processing systems 14 (pp. 1531–1536). Cambridge:
MIT.
Kimura, H., & Kobayashi, S. (1998). An analysis of actor/critic algorithms using eligibility traces: reinforcement learning with imperfect value functions. In Proceedings of the 15th int. conf. on
machine learning (pp. 284–292).
Ko, J., & Fox, D. (2009). GP-BayesFilters: Bayesian filtering using
Gaussian process prediction and observation models. Autonomous
Robots (same special issue, Part A).
Konda, V. R., & Tsitsiklis, J. N. (2003). Actor-critic algorithms. SIAM
Journal on Control and Optimization, 42(4), 1143–1166.
Kuvayev, L., & Sutton, R. (1996). Model-based reinforcement learningwith an approximate, learned model. In Proceedings of the ninth
Yale workshop on adaptive and learning systems (pp. 101–105).
Matsubara, T., Morimoto, J., Nakanishi, J., Sato, M., & Doya, K.
(2006). Learning CPG-based biped locomotion with a policy gradient method. Robotics and Autonomous Systems, 54(11), 911–
920.
McGeer, T. (1990). Passive dynamic walking. International Journal of
Robotics Research, 9(2), 62–82.
Meuleau, N., Kim, K. E., & Kaelbling, L. P. (2001). Explorationin gradient-based reinforcement learning. Technical report, AI
Memo 2001-003, MIT.
Miura, H., & Shimoyama, I. (1984). Dynamical walk of biped locomotion. International Journal of Robotics Research, 3(2), 60–74.
Miyazaki, F., & Arimoto, S. (1981). Implementation of a hierarchicalcontrol for biped locomotion. In 8th IFAC (pp. 43–48).
Morimoto, J., & Atkeson, C. G. (2007). Learning biped locomotion:
application of Poincaré-map-based reinforcement learning. IEEE
Robotics and Automation Magazine, 14(2), 41–51.
Morimoto, J., & Doya, K. (2001). Acquisition of stand-up behavior bya real robot using hierarchical reinforcement learning. Robotics
and Autonomous Systems, 36, 37–51.
Morimoto, J., Endo, G., Nakanishi, J., Hyon, S., Cheng, G., Atkeson,
C. G., & Bentivegna, D. (2006). Modulation of simple sinusoidal
patterns by a coupled oscillator model for biped walking. In Proceedings of the 2006 IEEE international conference on robotics
and automation (pp. 1579–1584).
Morimoto, J., Endo, G., Nakanish, J., & Cheng, G. (2008). A biologically inspired biped locomotion strategy for humanoid robots:
modulation of sinusoidal patterns by a coupled oscillator model.
IEEE Transaction on Robotics, 24(1), 185–191.

Nagasaka, K., Inaba, M., & Inoue, H. (1999). Stabilization of dynamic walk on a humanoid using torso position compliance control. In Proceedings of 17th annual conference on robotics societyof Japan (pp. 1193–1194).
Nagasaka, K., Kuroki, Y., Suzuki, S., Itoh, Y., & Yamaguchi, J. (2004).
Integrated motion control for walking, jumping and running on asmall bipedal entertainment robot. In Proceedings of IEEE 2004
international conference on robotics and automation (pp. 3189–
3194). New Orleans, LA, USA.
Peters, J., & Schaal, S. (2008). Reinforcement learning of motor skills
with policy gradients. Neural Networks, 21(4), 682–697.
Peters, J., & Schaal, S. (2008). Natural actor-critic. Neurocomputing,71(7–9), 1180–1190.
Rasmussen, C. E., & Kuss, M. (2004). Gaussian processes in reinforcement learning. In Advances in neural information processing systems (vol. 16, pp. 751–759). Cambridge: MIT.
Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian processes formachine learning. Cambridge: MIT.
Riedmiller, M., Gablel, R. H. T., & Lange, S. (2009). Reinforcement
learning for robot soccer. Autonomous Robots (same special issue,
Part A).
Shiriaev, A., Robertsson, A., Perram, J., & Sandberg, A. (2005). Periodic motion planning for virtually constrained (hybrid) mechanical systems. In Proceedings of IEEE conference on decision andcontrol (pp. 4035–4040).
Smola, J., & Bartlett, P. (2001). Sparse greedy Gaussian process regression. In T. G. Diettrich & V. Tresp (Eds.), Advances in neural
information processing systems 13 (pp. 619–625). Cambridge:
MIT.
Snelson, E., & Ghahramani, Z. (2006). Sparse Gaussian processes using pseudo-inputs. In Y. Weiss, B. Scholkof & J. Platt (Eds.), Advances in neural information processing systems 18 (pp. 1257–1264). Cambridge: MIT.
Strogatz, S. H. (1994). Nonlinear dynamics and chaos. Reading:
Addison-Wesley.
Sugihara, T., & Nakamura, Y. (2002). Whole-body cooperative COG
control through ZMP manipulation for humanoid robots. In IEEE
int. conf. on robotics and automation, Washington DC, USA,2002.
Sugihara, T., & Nakamura, Y. (2005). A fast online gait planningwith boundary condition relaxation for humanoid robots. In IEEE
int. conf. on robotics and automation (pp. 306–311). Barcelona,
Spain.
Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: an introduction. Cambridge: MIT.
Sutton, R. S., McAllester, D., Singh, S., & Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems 12 (pp. 1057–1063). Cambridge: MIT.
Tedrake, R., Zhang, T. W., & Seung, H. S. (2004). Stochastic policy
gradient reinforcement learning on a simple 3D biped. In Proceedings of the 2004 IEEE/RSJ international conference on intelligent robots and systems (pp. 2849–2854).
Tsuchiya, K., Aoi, S., & Tsujita, K. (2003). Locomotion control of abiped locomotion robot using nonlinear oscillators. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1745–1750). Las Vegas, NV, USA.
Westervelt, E. R., Buche, G., & Grizzle, J. W. (2004). Experimental
validation of a framework for the design of controllers that induce
stable walking in planar bipeds. International Journal of Robotics
Research, 23(6), 559–582.
Williams, C. K. I., & Rasmussen, C. E. (1996). Gaussian processes forregression. In Advances in neural information processing systems(vol. 8, pp. 514–520). Cambridge: MIT.

Auton Robot
Jun Morimoto is head of Department of Brain Robot Interface at
ATR Computational Neuroscience
Laboratories and the group leader of
Humanoid Motor Learning Groupin Computational Brain Project,
ICORP, JST. He received his Ph.D.
in information science from Nara
Institute of Science and Technology (NAIST), Nara, Japan, in 2001.
He was a Research Assistant with
Kawato Dynamic Brain Project,
ERATO, JST, from 1999 to 2001.
From 2001 to 2002, he was a postdoctoral fellow at the Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA. He Jointed
ATR in 2002, and then joined JST, ICORP in 2004.

Christopher G. Atkeson is a professor in the Robotics Institute andHuman–Computer Interaction Institute at Carnegie Mellon University.
His research focuses on humanoid
robotics and robot learning, using
challenging dynamic tasks such as
juggling. Specific research interests include nonparametric learning,memory-based learning including
approaches based on trajectory libraries, reinforcement learning andother forms of learning based on optimal control, learning from demonstration, and modeling human behavior. He received the M.S. degree in applied mathematics (computerscience) from Harvard University and the Ph.D. degree in brain andcognitive science from MIT. He joined the MIT faculty in 1986, moved
to the Georgia Institute of technology College of Computing in 1994,
and then joined CMU in 2000. He has received an NSF Presidential
Young Investigator Award, a Sloan Research Fellowship, and a Teaching Award from the MIT Graduate Student Council.