Minimax Differential Dynamic Programming:
An Application to Robust Biped Walking

Jun Morimoto
Human Information Science Labs,Department 3, ATR International
Keihanna Science City,Kyoto, JAPAN, 619-0288
xmorimo@atr.co.jp

Christopher G. Atkeson ∗The Robotics Institute and HCII,
Carnegie Mellon University
5000 Forbes Ave.,
Pittsburgh, USA, 15213
cga@cs.cmu.edu

Abstract
We developed a robust control policy design method in high-dimensional
state space by using differential dynamic programming with a minimax
criterion. As an example, we applied our method to a simulated five link
biped robot. The results show lower joint torques from the optimal control policy compared to a hand-tuned PD servo controller. Results also
show that the simulated biped robot can successfully walk with unknown
disturbances that cause controllers generated by standard differential dynamic programming and the hand-tuned PD servo to fail. Learning tocompensate for modeling error and previously unknown disturbances in
conjunction with robust control design is also demonstrated.

1 Introduction
Reinforcement learning[8] is widely studied because of its promise to automatically generate controllers for difficult tasks from attempts to do the task. However, reinforcement
learning requires a great deal of training data and computational resources, and sometimes
fails to learn high dimensional tasks. To improve reinforcement learning, we propose using
differential dynamic programming (DDP) which is a second order local trajectory optimization method to generate locally optimal plans and local models of the value function[2, 4].
Dynamic programming requires task models to learn tasks. However, when we apply dynamic programming to a real environment, handling inevitable modeling errors is crucial.
In this study, we develop minimax differential dynamic programming which provides robust nonlinear controller designs based on the idea of H ∞ control[9, 5] or risk sensitive
control[6, 1]. We apply the proposed method to a simulated five link biped robot (Fig. 1).
Our strategy is to use minimax DDP to find both a low torque biped walk and a policy orcontrol law to handle deviations from the optimized trajectory. We show that both standard
DDP and minimax DDP can find a local policy for lower torque biped walk than a handtuned PD servo controller. We show that minimax DDP can cope with larger modelingerror than standard DDP or the hand-tuned PD controller. Thus, the robust controller allows us to collect useful training data. In addition, we can use learning to correct modeling∗also affiliated with Human Information Science Laboratories, Department 3, ATR International

errors and model previously unknown disturbances, and design a new more optimal robust
controller using additional iterations of minimax DDP.

2 Minimax DDP
2.1 Differential dynamic programming (DDP)
A value function is defined as sum of accumulated future penalty r(x i , ui , i) from current
state and terminal penalty Φ(x N ),V (xi , i) = Φ(xN ) +N−1r(xj , uj , j),

(1)

j=i

where xi is the input state, ui is the control output at the i-th time step, and N is the numberof time steps. Differential dynamic programming maintains a second order local model ofa Q function (Q(i), Q x (i), Qu (i), Qxx (i), Qxu (i), Quu (i)), where Q(i) = r(xi , ui , i) +V (xi+1 , i + 1), and the subscripts indicate partial derivatives. Then, we can derive the= ui + δui from arg maxδui Q(xi + δxi , ui + δui , i). Finally,
new control output u newiby using the new control output u new, a second order local model of the value functioni(V (i), Vx (i), Vxx (i)) can be derived [2, 4].
2.2 Finding a local policy
DDP finds a locally optimal trajectory x opt
and the corresponding control trajectory u optii .
When we apply our control algorithm to a real environment, we usually need a feedback
controller to cope with unknown disturbances or modeling errors. Fortunately, DDP provides us a local policy along the optimized trajectory:
uopt (xi , i) = uopt
+ Ki (xi − xoptii ),(2)where Ki is a time dependent gain matrix given by taking the derivative of the optimal
policy with respect to the state [2, 4].
2.3 Minimax DDP
Minimax DDP can be derived as an extension of standard DDP [2, 4]. The difference is thatthe proposed method has an additional disturbance variable w to explicitly represent theexistence of disturbances. This representation of the disturbance provides the robustness
for optimized trajectories and policies [5].
Then, we expand the Q function Q(x i + δxi , ui + δui , wi + δwi , i) to second order interms of δu, δw and δx about the nominal solution:
Q(xi + δxi , ui + δui , wi + δwi , i) = Q(i) + Qx (i)δxi + Qu (i)δui + Qw (i)δwiQxx (i) Qxu (i) Qxw (i)δxi
1 T T Tδui ,+ [δxi δui δwi ] Qux (i) Quu (i) Quw (i)2δwiQwx (i) Qwu (i) Qww (i)(3)

The second order local model of the Q function can be propagated backward in time using:Qx (i)Qu (i)Qw (i)Qxx (i)====Vx (i + 1)Fx + rx (i)Vx (i + 1)Fu + ru (i)Vx (i + 1)Fw + rw (i)Fx Vxx (i + 1)Fx + Vx (i + 1)Fxx + rxx (i)

(4)
(5)
(6)
(7)

Qxu (i)Qxw (i)Quu (i)Qww (i)Quw (i)=====Fx Vxx (i + 1)Fu + Vx (i + 1)Fxu + rxu (i)Fx Vxx (i + 1)Fu + Vx (i + 1)Fxw + rxw (i)Fu Vxx (i + 1)Fu + Vx (i + 1)Fuu + ruu (i)Fw Vxx (i + 1)Fw + Vx (i + 1)Fww + rww (i)Fu Vxx (i + 1)Fw + Vx (i + 1)Fuw + ruw (i),

(8)
(9)
(10)
(11)
(12)

where xi+1 = F(xi , ui , wi ) is a model of the task dynamics.
Here, δui and δwi must be chosen to minimize and maximize the second order expansionof the Q function Q(x i + δxi , ui + δui , wi + δwi , i) in (3) respectively, i.e.,δui=δwi=−Q−1
uu (i)[Qux (i)δxi + Quw (i)δwi + Qu (i)]−Q−1
ww (i)[Qwx (i)δxi + Qwu (i)δui + Qw (i)].

(13)

By solving (13), we can derive both δu i and δwi . After updating the control output u i andthe disturbance w i with derived δui and δwi , the second order local model of the valuefunction is given as
V (i) =Vx (i) =Vxx (i) =−1
V (i + 1) − Qu (i)Q−1
uu (i)Qu (i) − Qw (i)Qww (i)Qw (i)−1
Qx (i) − Qu (i)Q−1
uu (i)Qux (i) − Qw (i)Qww (i)Qwx (i)−1Qxx (i) − Qxu (i)Q−1
uu (i)Qux (i) − Qxw (i)Qww (i)Qwx (i).

(14)

3 Experiment
3.1 Biped robot model
In this paper, we use a simulated five link biped robot (Fig. 1:Left) to explore our approach.
Kinematic and dynamic parameters of the simulated robot are chosen to match those of abiped robot we are currently developing (Fig. 1:Right) and which we will use to further
explore our approach. Height and total weight of the robot are about 0.4 [m] and 2.0 [kg]respectively. Table 1 shows the parameters of the robot model.
3link3
joint2,3

4

link4
link2
joint42
link1

joint1

5
1

link5

ankle

Figure 1: Left: Five link robot model, Right: Real robot

Table 1: Physical parameters of the robot modellink1 link2 link3 link4 link5mass [kg]0.05 0.43
1.0
0.43 0.05
length [m]
0.2
0.2
0.01
0.2
0.2
inertia [kg·m ×10 −4 ] 1.75 4.29 4.33 4.29 1.75

We can represent the forward dynamics of the biped robot as
xi+1 = f (xi ) + b(xi )ui ,(15)where x = {θ1 , . . . , θ5 , θ̇1 , . . . , θ̇5 } denotes the input state vector, u = {τ 1 , . . . , τ4 } denotes the control command (each torque τ j is applied to joint j (Fig.1):Left). In the minimax optimization case, we explicitly represent the existence of the disturbance as
xi+1 = f (xi ) + b(xi )ui + bw (xi )wi ,(16)where w = {w0 , w1 , w2 , w3 , w4 } denotes the disturbance (w 0 is applied to ankle, and w j(j = 1 . . . 4) is applied to joint j (Fig. 1:Left)).
3.2 Optimization criterion and method
We use the following objective function, which is designed to reward energy efficiency andenforce periodicity of the trajectory:J = Φ(x0 , xN ) +N−1

r(xi , ui , i)

(17)

i=0

which is applied for half the walking cycle, from one heel strike to the next heel strike.
This criterion sums the squared deviations from a nominal trajectory, the squared control
magnitudes, and the squared deviations from a desired velocity of the center of mass:r(xi , ui , i) = (xi − xdi )T Q(xi − xdi ) + ui T Rui + (v(xi ) − v d )T S(v(xi ) − v d ), (18)where xi is a state vector at the i-th time step, x di is the nominal state vector at the i-thtime step (taken from a trajectory generated by a hand-designed walking controller), v(x i )denotes the velocity of the center of mass at the i-th time step, and v d denotes the desired
velocity of the center of mass. The term (x i − xdi )T Q(xi − xdi ) encourages the robot tofollow the nominal trajectory, the term u i T Rui discourages using large control outputs,
and the term (v(xi ) − v d )T S(v(xi ) − v d ) encourages the robot to achieve the desiredvelocity.
In addition, penalties on the initial (x 0 ) and final (xN ) states are applied:Φ(x0 , xN ) = F (x0 ) + ΦN (x0 , xN ).

(19)

The term F (x0 ) penalizes an initial state where the foot is not on the ground:F (x0 ) = Fh T (x0 )P0 Fh (x0 ),(20)

where Fh (x0 ) denotes height of the swing foot at the initial state x 0 . The term ΦN (x0 , xN )is used to generate periodic trajectories:ΦN (x0 , xN ) = (xN − H(x0 ))T PN (xN − H(x0 )),(21)

where xN denotes the terminal state, x 0 denotes the initial state, and the term (x N −H(x0 ))T PN (xN − H(x0 )) is a measure of terminal control accuracy. A function H()
represents the coordinate change caused by the exchange of a support leg and a swing leg,and the velocity change caused by a swing foot touching the ground (Appendix A).
We implement the minimax DDP by adding a minimax term to the criterion. We use amodified objective function:
Jminimax = J −N−1
wi T Gwi ,(22)i=0where wi denotes a disturbance vector at the i-th time step, and the term w i T Gwi rewards
coping with large disturbances. This explicit representation of the disturbance w provides
the robustness for the controller [5].

4 Results
We compare the optimized controller with a hand-tuned PD servo controller, which also
is the source of the initial and nominal trajectories in the optimization process. We set
the parameters for the optimization process as Q = 0.25I 10 , R = 3.0I4 , S = 0.3I1 ,desired velocity v d = 0.4[m/s] in equation (18), P 0 = 1000000.0I1 in equation (20), andPN = diag{10000.0, 10000.0, 10000.0, 10000.0, 10000.0, 10.0, 10.0, 10.0, 5.0, 5.0} inequation (21), where I N denotes N dimensional identity matrix. For minimax DDP, weset the parameter for the disturbance reward in equation (22) as G = diag{5.0, 20.0, 20.0,20.0, 20.0} (G with smaller elements generates more conservative but robust trajectories).
Each parameter is set to acquire the best results in terms of both the robustness and theenergy efficiency. When we apply the controllers acquired by standard DDP and minimaxDDP to the biped walk, we adopt a local policy which we introduced in section 2.2.
Results in table 2 show that the controller generated by standard DDP and minimax DDP
did almost halve the cost of the trajectory, as compared to that of the original hand-tuned
PD servo controller. However, because the minimax DDP is more conservative in taking
advantage of the plant dynamics, it has a slightly higher control cost than the standard DDP.
N −1
Note that we defined the control cost as N1 i=0 ||ui ||2 , where ui is the control output(torque) vector at i-th time step, and N denotes total time step for one step trajectories.

Table 2: One step control cost (average over 100 steps)
PD servo standard DDP minimax DDPcontrol cost [(N · m)2 × 10−2 ]
7.50
3.54
3.86
To test robustness, we assume that there is unknown viscous friction at each joint:τjdist = −μj θ̇j(j = 1, . . . , 4),(23)

where μj denotes the viscous friction coefficient at joint j.
We used two levels of disturbances in the simulation, with the higher level being 3 timeslarger than the base level (Table 3).

Table 3: Parameters of the disturbance
μ2 ,μ3 (hip joints) μ1 ,μ4 (knee joints)
base
0.01
0.05
large
0.03
0.15

All methods could handle the base level disturbances. Both the standard and the minimax
DDP generated much less control cost than the hand-tuned PD servo controller (Table 4).
However, only the minimax DDP control design could cope with the higher level of disturbances. Figure 2 shows trajectories for the three different methods. Both the simulated
robot with the standard DDP and the hand-tuned PD servo controller fell down before
achieving 100 steps. The bottom of figure 2 shows part of a successful biped walking trajectory of the robot with the minimax DDP. Figure 3 shows ankle joint trajectories for thethree different methods. Only the minimax DDP successfully kept ankle joint θ 1 around90 degrees more than 20 seconds. Table 5 shows the number of steps before the robot felldown. We terminated a trial when the robot achieved 1000 steps.

Table 4: One step control cost with the base setting (averaged over 100 steps)PD servo standard DDP minimax DDP
control cost [(N · m)2 × 10−2 ]
8.97
5.23
5.87
Hand-tuned PD servo

Standard DDP

Minimax DDP

Figure 2: Biped walk trajectories with the three different methods

5 Learning the unmodeled dynamics
In section 4, we verified that minimax DDP could generate robust biped trajectories andpolicies. The minimax DDP coped with larger disturbances than the standard DDP andthe hand-tuned PD servo controller. However, if there are modeling errors, using a robust
controller which does not learn is not particularly energy efficient. Fortunately, with minimax DDP, we can collect sufficient data to improve our dynamics model. Here, we propose
using Receptive Field Weighted Regression (RFWR) [7] to learn the error dynamics of thebiped robot. In this section we present results on learning a simulated modeling error (thedisturbances discussed in section 4). We are currently applying this approach to an actualrobot.
We can represent the full dynamics as the sum of the known dynamics and the error dynamics ΔF(xi , ui , i):(24)xi+1 = F(xi , ui ) + ΔF(xi , ui , i).
We estimate the error dynamics ΔF by using RFWR:Nb i
α φk (xi , ui , i),(25)
ΔF̂(xi , ui , i) = k=1kNbi
k=1 αkφk (xi , ui , i) = βkT x̃ik ,(26)1αik = exp − (i − ck )Dk (i − ck ) ,(27)2where, Nb denotes the number of basis function, c k denotes center of k-th basis function,
Dk denotes distance metric of the k-th basis function, β k denotes parameter of the kth basis function to approximate error dynamics, and x̃ik = (xi , ui , 1, i − ck ) denotes
augmented state vector for the k-th basis function. We align 20 basis functions (N b = 20)
at even intervals along the biped trajectories.
The learning strategy uses the following sequence: 1) Design the initial controller using
minimax DDP applied to the nominal model. 2) Apply that controller. 3) Learn the actualdynamics using RFWR. 4) Redesign the biped controller using minimax DDP with thelearned model.

ankle [deg]10090807060

0246ankle [deg]10121416182014161820141618209080
7060024681012time [sec] (Standard DDP)

100ankle [deg]8time [sec] (PD servo)

100

9080
7060024681012time [sec] (Minimax DDP)

Figure 3: Ankle joint trajectories with the three different methods

Table 5: Number of steps with the large disturbances
PD servo standard DDP minimax DDP
Number of steps
4924> 1000

We compare the efficiency of the controller with the learned model to the controller without the learned model. Results in table 6 show that the controller after learning the error
dynamics used lower torque to produce stable biped walking trajectories.

Table 6: One step control cost with the large disturbances (averaged over 100 steps)
without learned model with learned model
control cost [(N · m)2 × 10−2 ]
17.1
11.3

6 Discussion
In this study, we developed an optimization method to generate biped walking trajectories
by using differential dynamic programming (DDP). We showed that 1) DDP and minimax
DDP can be applied to high dimensional problems, 2) minimax DDP can design morerobust controllers, and 3) learning can be used to reduce modeling error and unknown
disturbances in the context of minimax DDP control design.
Both standard DDP and minimax DDP generated low torque biped trajectories. We showedthat the minimax DDP control design was more robust than the controller designed bystandard DDP and the hand-tuned PD servo. Given a robust controller, we could collectsufficient data to learn the error dynamics using RFWR[7] without the robot falling down
all the time. We also showed that after learning the error dynamics, the biped robot could
find a lower torque trajectory.
DDP provides a feedback controller which is important in coping with unknown distur-bances and modeling errors. However, as shown in equation (2), the feedback controller isindexed by time, and development of a time independent feedback controller is a futuregoal.

AppendixA

Ground contact model

The function H() in equation (21) includes the mapping (velocity change) caused byground contact. To derive the first derivative of the value function V x (xN ) and the second derivative V xx (xN ), where xN denotes the terminal state, the function H() should beanalytical. Then, we used an analytical ground contact model[3]:+−θ̇ − θ̇ = M −1 (θ)D(θ)f Δt,(28)where θ denotes joint angles of the robot, θ̇ − denotes angular velocities before groundcontact, θ̇+ denotes angular velocities after ground contact, M denotes the inertia matrix,
D denotes the Jacobian matrix which converts the ground contact force f to the torque ateach joint, and Δt denotes time step of the simulation.

References[1] S. P. Coraluppi and S. I. Marcus. Risk-Sensitive and Minmax Control of Discrete-Time
Finite-State Markov Decision Processes. Automatica, 35:301–309, 1999.
[2] P. Dyer and S. R. McReynolds. The Computation and Theory of Optimal Control.
Academic Press, New York, NY, 1970.
[3] Y. Hurmuzlu and D. B. Marghitu. Rigid body collisions of planar kinematic chainswith multiple contact points. International Journal of Robotics Research, 13(1):82–92, 1994.
[4] D. H. Jacobson and D. Q. Mayne. Differential Dynamic Programming. Elsevier, New
York, NY, 1970.
[5] J. Morimoto and K. Doya. Robust Reinforcement Learning. In Todd K. Leen,Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, pages 1061–1067. MIT Press, Cambridge, MA, 2001.
[6] R. Neuneier and O. Mihatsch. Risk Sensitive Reinforcement Learning. In M. S. Kearns,S. A. Solla, and D. A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 1031–1037. MIT Press, Cambridge, MA, USA, 1998.
[7] S. Schaal and C. G. Atkeson. Constructive incremental learning from only local information. Neural Computation, 10(8):2047–2084, 1998.
[8] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT
Press, Cambridge, MA, 1998.
[9] K. Zhou, J. C. Doyle, and K. Glover. Robust Optimal Control. PRENTICE HALL,
New Jersey, 1996.