LEARNING AND CONTROL WITH INACCURATE MODELSA DISSERTATIONSUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCEAND THE COMMITTEE ON GRADUATE STUDIESOF STANFORD UNIVERSITYIN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY

J. Zico Kolter
August 2010

Abstract
A key challenge in applying model-based Reinforcement Learning and optimal control
methods to complex dynamical systems, such as those arising in many robotics tasks,
is the difficulty of obtaining an accurate model of the system. These algorithms
perform very well when they are given or can learn an accurate dynamics model, but
often times it is very challenging to build an accurate model by any means: effects
such as hidden or incomplete state, dynamic or unknown system elements, and othereffects, can render the modeling task very difficult.
This work presents methods for dealing with such situations, by proposing algorithms that can achieve good performance on control tasks even using only inaccurate models of the system. In particular, we present three algorithmic contributionsin this work that exploit inaccurate system models in different ways: we present anapproximate policy gradient method, based on an approximation we call the Signed
Derivative, that can perform well provided only that the sign of certain model derivative terms are known; we present a method for using a distribution over possible
inaccurate models to identify a linear subspace of control policies that perform wellin all models, then learn a member of this subspace on the real system; finally, we
propose an algorithm for integrating previously observed trajectories with inaccurate
models in a probabilistic manner, achieving better performance than is possible witheither element alone.
In addition to these algorithmic contributions, a central focus of this thesis is
the application of these methods to challenging robotic domains, extending the stateof the art. The methods have enabled a quadruped robot to cross a wide varietyof challenging terrain, using a combination of slow static walking, dynamic trottingiv

gaits, and dynamic jumping maneuvers. We also apply these methods to a full-sizedautonomous car, where they enable it to execute a “powerslide” into a narrow parking
spot, one of the most challenging maneuvers demonstrated on an autonomous car.
Both these domains represent highly challenging robotics tasks where the dynamicalsystem is difficult to model, and our methods demonstrate that we can attain excellent
performance on these tasks even without an accurate model of the system.

v

To my mom, Janine, my dad, Roberto, and my wife, KD.

vi

Acknowledgments
This thesis has been the product of a long and close collaboration with my advisor,
Andrew Ng. I am hugely indebted to Andrew for all the help, guidance, and insighthe has provided to me over the years. While I couldn’t succinctly describe all theways in which he has helped shaped my academic mindset, the way he approaches
new research problems, how he analyzes theoretical questions, and his logical mindset
on “diagnostics” for machine learning methods have all become an integral part of
how I look at any new problems. In addition, his enthusiasm and happiness to talkabout any new ideas have constantly made it a joy to work with him.
I want to thank the other members of my reading committee for their help withthis work. Daphne Koller, in addition to providing a great many detailed commentson this work, has for the past year been an amazing source of knowledge and insight.
Often times upon hearing just briefly about an algorithm or idea I had been working
on, she would immediately have an idea for building upon it in a new and interesting
way. Sebastian Thrun has been a constant source of inspiration, and in all my talks
with him always exudes a genuine excitement about how the work we do in AI canhave a real effect on the world.
I also want to thank the other members of my orals committee: Stephen Boyd andIlan Kroo. Stephen’s classes have profoundly shaped the way I approach almost every
new problem I look at, and his enthusiasm for talking about any new application or
algorithmic idea is truly inspirational. I only met Ilan later in my PhD program, andhis knowledge and intuition about aerodynamics, as well as his enthusiam, has been
wonderful to experience.
Recently I have begun several projects relating to energy issues, and Carrie Armelvii

has been extremely helpful in getting me involved in this research. Her passion andexcitement about getting new people involved in this work has made me feel welcomeand even more excited about this new area of research.
Looking back, I owe a large debt of gratitude to Mark Maloof, my undergraduate
advisor who first got me interested in machine learning research. Mark’s enthusiasm
and commitment to clear and engaging presentation of machine learning work is oneof the main reasons why I got so excited about this field in the first place.
I want to thank my officemates, Morgan Quigley and Honglak Lee, as well as themembers of our frequent lunch groups, Adam Coates and Pieter Abbeel. Numerous
times I’ve been grateful to have Honglak around for commiseration during late night
paper writing sessions. Talking with Morgan and Adam about various potential robot
platforms and algorithms, both plausible and wildly implausible versions, has been
one of the most fun parts of the past five years; it will also be a huge loss not tobe able to constantly bug Morgan with questions about any and every mechanicalor engineering issue I’d run into. Working with Pieter was another highlight of myearlier PhD experience; his excitement in talking about new algorithms and ideas has
always been an inspiration.
I’m very grateful for having had the chance to work with and talk to many of theother members of Andrew’s group, both past and present. I want to thank Ashutosh
Saxena, Tom Do, Rion Snow, Rajat Raina, Olga Russakovsky, Quoc Le, Andrew
Maas, Andrew Saxe, and Jiquan Ngiam.
Thanks to all those who I have collaborated with on various research and papers: Sam Schreiber, Mike Rodgers, Danny Jachowski, Yi Gu, Charles DuHadway,
Youngjun Kim, Christian Plagemann, and David Jackson. In the last year, I havealso begun working with Zouhair Mahboubi, Geoff Bower, and Tao Wang. Their
constant excitement in our projects, even when it means getting to Gates at 6:30 AM
to go fly RC airplanes, has made this work a true joy, even when we were all sleep
deprived.
During the two quarters that I TA’d Andrew’s machine learning class I had thepleasure of working with a number of other students: Sam Ieong, Erick Delage,
Haidong Wang, Catie Chang (both times!), Tom Do, Dan Ramage, Joseph Koo andviiiPaul Baumstarck. Sam and Tom in particular were invaluable in taking a huge partof the workload, and made even the experience of grading problem sets until two in
the morning seem less of a burden.
Finally, moving away from the academic sphere, I can’t imagine getting throughthe past several years without the support of family and friends. To my mom, Janine,
my dad, Roberto, and my sister, Amanda, I want to thank you for all your supportand encouragement.
Lastly, and most importantly, I want to thank my companion throughout mytime at Stanford and beyond, my wife KD. Your unconditional love and support hassustained me through this all, your strength has inspired me, and I will be forevergrateful for all that you do. Thank you from the bottom on my heart.

ix

Contents
Abstractiv

Acknowledgments

vii

1 Introduction1

1.1

Model-based Reinforcement Learning, Optimal Control, Robust and
Adaptive Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Overview of Contributions . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Outline of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4First Published Appearances of Contributions . . . . . . . . . . . . .

7

2 Background
2.1

2.2

2.3

9

Dynamical Systems and Optimal Control . . . . . . . . . . . . . . . .

9

2.1.1

States and Controls . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.2

First-order Markov Models . . . . . . . . . . . . . . . . . . . .

10

2.1.3

Stochastic models . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.1.4

Control policies . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.1.5

Optimal Control . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.6

Markov Decision Processes . . . . . . . . . . . . . . . . . . . .

16

Multi-variate Calculus . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2.1

The Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2.2

The Jacobian . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Policy Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.3.1

19

Known deterministic model . . . . . . . . . . . . . . . . . . .
x

2.4

2.5

2.3.2

Known stochastic model . . . . . . . . . . . . . . . . . . . . .

20

2.3.3

Unknown deterministic or stochastic model . . . . . . . . . . .

21

Linear Quadratic Regulator Methods . . . . . . . . . . . . . . . . . .

23

2.4.1

Linear Dynamics and Quadratic Cost . . . . . . . . . . . . . .

24

2.4.2

Non-linear models . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.4.3

Non-linear trajectory stabilization . . . . . . . . . . . . . . . .

28

2.4.4

Iterative LQR . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3 Approximate Policy Gradient via the Signed Derivative

32

3.1

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.2

The Signed Derivative Policy Gradient Approximation . . . . . . . .

37

3.2.1

The Signed Derivative Approximation and Algorithm . . . . .

38

3.2.2

The Signed Derivative Term . . . . . . . . . . . . . . . . . . .

40

Theoretical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.3.1

Overview of the Theoretical Results . . . . . . . . . . . . . . .

45

3.3.2

Formal Results . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.3.3

Proofs of Technical Lemmas . . . . . . . . . . . . . . . . . . .

52

Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.4.1

Simulated Two-Link Arm . . . . . . . . . . . . . . . . . . . .

54

3.4.2

Autonomous RC Driving . . . . . . . . . . . . . . . . . . . . .

59

3.4.3

LittleDog Jumping . . . . . . . . . . . . . . . . . . . . . . . .

62

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

3.3

3.4

3.5

4 Dimensionality Reduction in Policy Search

68

4.1

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.2

Dimensionality Reduction Policy Search . . . . . . . . . . . . . . . .

72

4.2.1

Dimensionality Reduction Policy Gradient . . . . . . . . . . .

75

4.2.2

Least Squares Policy Search . . . . . . . . . . . . . . . . . . .

77

Application to Omnidirectional Path Following . . . . . . . . . . . . .

78

4.3.1

A Balancing Policy for Omnidirectional Trotting . . . . . . . .

79

4.3.2

Policy Search as Least Squares . . . . . . . . . . . . . . . . . .

81

4.3

xi

4.3.3

Experimental Setup and Results . . . . . . . . . . . . . . . . .

82

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5 Multi-model Control for Mixed Closed-loop/Open-loop Behavior

88

4.4

5.1

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

5.2

A Probabilistic Framework for Multiple Model Control . . . . . . . .

91

5.2.1

LQR with multiple probabilistic models . . . . . . . . . . . . .

93

5.2.2

A dynamics model for open-loop trajectories . . . . . . . . . .

96

5.2.3

Estimating Variances . . . . . . . . . . . . . . . . . . . . . . .

97

Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

5.3.1

Cart-pole Task . . . . . . . . . . . . . . . . . . . . . . . . . .

98

5.3.2

Extreme Autonomous Driving . . . . . . . . . . . . . . . . . . 100

5.3

5.4

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6 Application to the LittleDog Robot

105

6.1

Introduction to Legged Locomotion . . . . . . . . . . . . . . . . . . . 106

6.2

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.3

6.4

6.5

6.2.1

Background on legged locomotion . . . . . . . . . . . . . . . . 107

6.2.2

The Learning Locomotion program and LittleDog robot . . . . 109

A software architecture for quadruped locomotion . . . . . . . . . . . 111
6.3.1

Route Planner . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.3.2

Gait Selector . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

6.3.3

Static Walking Gait . . . . . . . . . . . . . . . . . . . . . . . . 115

6.3.4

Trot Gait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.3.5

Specialized Maneuvers . . . . . . . . . . . . . . . . . . . . . . 119

6.3.6

Introduction to Rapid Replanning Methods . . . . . . . . . . 120

Recovery and Stabilization Control . . . . . . . . . . . . . . . . . . . 120
6.4.1

Control Elements . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.4.2

Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 122

Motion Planning via Cubic Spline Optimization . . . . . . . . . . . . 124
6.5.1

The Cubic Spline Optimization Algorithm . . . . . . . . . . . 125

6.5.2

Planning Foot Trajectories . . . . . . . . . . . . . . . . . . . . 132
xii

6.5.3
6.6

Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 136

Cost Learning via Hierarchical Apprenticeship Learning . . . . . . . . 138
6.6.1

The Hierarchical Apprenticeship Learning Algorithm . . . . . 139

6.6.2

Application to Cost Map Learning . . . . . . . . . . . . . . . 143

6.6.3

Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . 145

6.7

Learning Locomotion Program Results . . . . . . . . . . . . . . . . . 147

6.8

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

7 Conclusion

152

xiii

List of Tables
4.1

Performance of the different centering methods on each of the threebenchmark paths, averaged over 5 runs, with 95% confidence intervals.

5.1

Total average cost at the last time step for different algorithms on the
cart-pole task. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1

85

99

The four terrains used for evaluation of recovery and stabilization procedures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.2

Success probabilities out of 20 runs across different terrains for thecontroller with and without recovery, body stabilization, and closedloop foot placement. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6.3

The training and testing terrains used to evaluate the cubic spline
trajectory planning on LittleDog.. . . . . . . . . . . . . . . . . . . . . 137

6.4

Performance of cubic spline optimization on the two quadruped terrains. Terms include 95% confidence intervals where applicable. . . . 137

6.5

The training and testing terrains used to evaluate HAL. . . . . . . . . 145

6.6

Execution times for different constraints on training and testing terrains. Dashes indicate that the robot fell over and did not reach thegoal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.7

Speeds for Phase II system and terrains. Average speed is based upon
the best two out of three runs. We received no information as towhether the system based all 3/3 test or only 2/3, but all test passed
at least 2/3 of the runs. . . . . . . . . . . . . . . . . . . . . . . . . . 148

xiv

6.8

Speeds and success rates for Phase III system and terrains. Average
speed is based upon best two runs. The first six terrains represent
the “standard” Phase III tests, while the last three represent three
additional optional terrains. The video references in the text shows allnine terrains. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

xv

List of Figures
3.1

Two-link pendulum trajectory following task. . . . . . . . . . . . . .

3.2

Average cost versus time for different policy gradient methods. Costs

56

are averaged over 20 runs, and shown with 95% confidence intervals. .

56

3.3

Trajectories from initial controller. . . . . . . . . . . . . . . . . . . .

57

3.4

Trajectories from controller learned using PGSD. . . . . . . . . . . .

58

3.5

Average cost versus time for PGSD versus model-based methods. Costs
are averaged over 20 runs, and shown with 95% confidence intervals. .

58

3.6

RC car used for the driving experiments. . . . . . . . . . . . . . . . .

59

3.7

Desired trajectory for the autonomous RC driving experiments, withtrajectory for initial controller. . . . . . . . . . . . . . . . . . . . . . .

3.8

61

Desired trajectory for the autonomous RC driving experiments, withtypical trajectory learned using PGSD after approximately 20 secondsof learning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.9

61

Average cost versus time for the PGSD algorithm on the RC car task.
Costs are averaged over 10 runs, and shown with 95% confidence intervals. 62

3.10 The desired task for the LittleDog: climb over three large steps. . . .

63

3.11 Overview of the front jump maneuver. . . . . . . . . . . . . . . . . .

64

3.12 A properly executed jump. . . . . . . . . . . . . . . . . . . . . . . . .

65

4.1

Pictures of the quadruped robot following several paths. . . . . . . .

84

4.2

Trajectory and center offsets for the learned controller. . . . . . . . .

84

xvi

5.1

(left) Trajectory followed by the cart-pole under open-loop control(middle) LQR control with an inaccurate model and (right) Multimodel LQR with both the open loop trajectory and inaccurate model.

5.2

99

Average total cost on cart-pole task, versus time. Shaded regions indicate 95% confidence intervals. . . . . . . . . . . . . . . . . . . . . . 100

5.3

Snapshots of the car attempting to slide into the parking spot using(top) open-loop control, (middle) pure LQR control, and (bottom)
Multi-model LQR control. The desired trajectory in all cases is toslide in between the cones. . . . . . . . . . . . . . . . . . . . . . . . . 102

5.4

Plots of the desired and actual trajectories followed by the car under(left) open-loop control, (middle) pure LQR control, and (bottom)
Multi-model LQR control. Bottom plots show a zoomed-in view of the
final location. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.1

The LittleDog robot, designed and built by Boston Dynamics, Inc. . . 109

6.2

Typical quadruped locomotion task: navigate robot over terrain to goal.111

6.3

Hierarchical software architecture for quadruped planner and controller.112

6.4

Overview of route planning element.

6.5

Overview of the footstep planning process. . . . . . . . . . . . . . . . 116

6.6

Illustration of kinematic feasibility constraints. (a) Kinematically fea-

. . . . . . . . . . . . . . . . . . 113

sible region for q1 ∈ [−π/2, π/2], q2 ∈ [−2.6, 2.6]. (b) Convex subset ofthe feasible region. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.7

Illustration of collision constraints. (a) Initial (infeasible) plan. (b)Height constraints imposed to avoid collision with obstacle. (c) Resulting optimized cubic spline trajectory. . . . . . . . . . . . . . . . . 130

6.8Foot planning task, and initial trajectory. . . . . . . . . . . . . . . . . 132

6.9

Typical example of a foot trajectory generated by the algorithm. The
top figure shows the resulting trajectory in 3D space, while the bottom
shows each component as a function of time. . . . . . . . . . . . . . . 136

6.10 Typical example of a COG trajectory generated by the algorithm. . . 136
6.11 High-level (route) expert demonstration. . . . . . . . . . . . . . . . . 145

xvii

6.12 Low-level (footstep) expert demonstration. . . . . . . . . . . . . . . . 146
6.13 Body and footstep plans for different constraints on the training (left)
and testing (right) terrains: (First/Red) No Learning, (Second/Green)
HAL, (Third/Blue) Path Only, (Fourth/Yellow) Footstep Only. . . . 147
6.14 Prototype system with onboard stereo camera, and snapshots of thesystem crossing one of the more difficult terrains, using only onboard
vision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

xviii

Chapter 1
Introduction
This work focuses on controlling complex dynamical systems, such as a legged robot
climbing over large obstacles and a full-sized autonomous car sliding sideways overthe ground. In these and many other control tasks a similar theme emerges: thechallenge of creating an accurate model of the system. Many control methodologies
rely on the presence of an accurate model in order to obtain good performance, andthere exists a variety of methods for creating such models; the models can be built
from physical principles or learned from data collected on the real system. But often
times it is very challenging to build an accurate model even using all these methods:
there can be hidden state in the system that is difficult to sense or model, leading to
non-Markovian dynamical effects; there are often properties of the system that are
constantly changing, with no way to know these properties a priori; or the dynamics
of the system may simply be sufficiently complex such that efficient simulation of thesystem is not possible. In all these settings it is useful, then, to consider how we
may develop learning and control methods that rely only on inaccurate models of thesystem in order to achieve good performance.

1CHAPTER 1. INTRODUCTION

1.1

2

Model-based Reinforcement Learning, OptimalControl, Robust and Adaptive Control

Broadly speaking, the fields of model-based Reinforcement Learning (RL) (Suttonand Barto, 1998) and optimal control (Bertsekas, 2005a,b; Stengel, 1994) provide acanonical set of methods for controlling dynamical systems.1 While there are numerous different approaches to model-based RL and optimal control (we will describe
the framework as well as some of the more relevant algorithms in much greater detail in Chapter 2) such methods typically work in the following manner. As input,
these algorithms take a dynamical model of the system of interest and a cost functionthat specifies what constitutes good or bad behavior, and they then output a control
strategy that attempts to minimize this cost function in the dynamical system. While
the algorithms can work in many different ways, intuitively, we can think of such approaches as simulating multiple possible experiences in the dynamics model, thenoutputting the control strategy that performs best (i.e., minimizes the cost function)in the model.
There are many things that could potentially go wrong with this approach. For
instance, the cost function may incorrectly capture the desired notion of good behavior
in the system. Alternatively, the reinforcement learning or optimal control algorithm
may fail to minimize the desired criterion. However, in practice we find that fornearly all cases, for the types of control problems we consider here, the fault liesin the dynamics model: the resulting controller output by the algorithm typically
performs very well in the dynamical model we provide to the algorithm, but does not
perform well in the real world. Thus, the fundamental issue often is one of model
accuracy: we simply do not have a sufficiently accurate model of the real system toperform well on the task of interest. Indeed, one of the fundamental challenges inmodel-based RL and optimal control is the task of either coming up with suitably
accurate dynamics model, or avoiding the need for an accurate model entirely.
A number of classical control methodologies exist that attempt to remedy the1

Model-based RL and optimal control generally refer to a very similar body of algorithms andmethodologies, so we make no distinction between the two for the purposes of this work.

CHAPTER 1. INTRODUCTION

3

problem described above. Perhaps the simplest method to address the issue of an
inaccurate dynamical system is to attempt to use data from the real system to learn
a better dynamics model; this is the strategy employed by methods such as adaptive
control (Sastry and Bodson, 1994; Astrom and Wittenmark, 1994) or many methods of system identification (Ljung, 1999). In a similar vein, a great deal of workin model-based RL focuses on methods for exploring the state space to extent thatguarantee a sufficiently accurate learned dynamics model (Strehl et al., 2009; Kearns
and Singh, 2002); recent work also focuses on the ability to use expert demonstrations
when learning such dynamics models (Abbeel and Ng, 2005). However, the problem
here, which we alluded to previously, is that often times it is still very challenging todevelop an accurate model of the system, even given a large amount of data from thereal system: effects like hidden state/non-Markovian dynamics, or unknown and constantly changing parameters render certain problems unsuitable to such approaches.
This situation, then, motivates the use of inaccurate models in control. Of course,
if we concede the ability to develop an accurate dynamics model of the system ofinterest, the question naturally arises as to what, and how, we can learn from sucha model. The classical control methodology that deals most directly with inaccurate
models is the area of robust control (Zhou et al., 1996). Broadly speaking, robust
control deals with scenarios where we do not know the true model of the system,
but where we have some distribution or uncertainty set over possible models, andthe goal is to find a controller that performs well in all these models (or with highprobability given a distribution over possible models). One difficulty of this method
is that, in order to ensure that the controller does indeed perform well in all models,
the result is often a very conservative control law, that in exchange for robustness
does not perform optimally in any of the models in question. There have also been
approaches that combine elements of both adaptive and robust control (Ioannou andSun, 1995), where one identifies a system along with uncertainty bounds suitable forrobust control methods, but these methods still inherit the general limitations of boththese approaches.

CHAPTER 1. INTRODUCTION

1.2

4

Overview of Contributions

The work we present in this thesis also deals with the question of how to learn
good control strategies given an inaccurate model of the system, but it does so ina different manner from the techniques described above. Unlike adaptive control orsystem identification, the methods we present here will typically make no efforts tolearn an improved model of the dynamical system. Indeed, we will often use a learned
model as our inaccurate model, so the assumption is that we have exhausted all our
options in terms of building a good model, and now wish to use the model we have tothe best of our abilities. Likewise, our methods differ from robust control in that we
do not seek a control system that performs well in a wide variety of models; rather,
we want a control policy that performs well in just one system: the real system in
the world. Having said this, there are certainly manners in which our work overlaps
with adaptive and robust control techniques, and we will highlight these connectionsin the individual chapters. But as a general theme, the task we focus on is as follows:
we want to obtain optimal (or as close to optimal as possible) performance on thereal system, through techniques that exploit an inaccurate dynamics model of thesystem.
While most of the chapters in this thesis present algorithmic or theoretical contributions, a key contribution of this work is the application of these algorithms toreal-world problems. Indeed, the examples of a quadruped robot climbing over large
obstacles and a robotic car sliding over gravel, described previously, are real-world
tasks that have motivated many of the algorithms we present here. In particular,much of the work in this thesis centers around applications to the LittleDog robot(Murphy et al., 2010), a small quadruped robot intended for negotiating rough terrain. Although we have spent a great deal of time attempting to develop an accurate
simulation model of the robot, we have repeatedly found that it is very difficult tocome up with an accurate simulator of the real robotic system, due to hard-to-model
effects like backlash in the gears and the friction of the robot’s feet and body sliding
over the ground. Thus, many of the techniques we present in this paper, designed
to operate using inaccurate models, were developed precisely for this real-world task

CHAPTER 1. INTRODUCTION

5of learning and control with this quadruped robot. Using our methods, we achieve
state-of-the-art results in terms of both navigating over large obstacles, and executing
dynamic maneuvers/gaits in the presence of large obstacles.2
Likewise, the previously mentioned task of sliding an autonomous car sideways
over gravel is another real-world task to which we apply these methods. In particular,
Chapter 5 presents a method for using inaccurate models that we apply to the taskof “powersliding” a full-sized autonomous car (“Junior,” Stanford’s entry into the
DARPA Urban Challenge (Montemerlo et al., 2008)) into a narrow parking spot.
Again the challenge that arises in this task is one of model accuracy: effects likefriction of the car’s tires sliding over the gravel are very difficult to model, especiallywhen we do not sense all the relevant quantities, such as the speed of the individual
tires of the car. Despite this, our methods are able to accurately and repeatedly
slide the car into a narrow target area, representing the state of the art in terms ofaccurately controlling a full-sized car in such a maneuver.

1.3

Outline of Thesis

The chapters in this work are organized as follows:• Chapter 2: Background. Here we present background on reinforcement
learning and optimal control that forms the basis for the algorithms in futuresections. Since RL and optimal control are obviously very broad fields, we
focus here particularly on those elements that we later build upon in our own
algorithms. In particular, after presenting the formal framework of optimal control, we focus in particular on Policy Gradient and Linear Quadratic Regulator(LQR) methods as two techniques for solving optimal control tasks.
2
Several different institutions have been simultaneously working with the LittleDog platform,
through the Learning Locomotion program, a competitive effort to build the software that enables
this robot to cross challenging terrain. The robot and program will be described much more in
Chapter 6. Here we just claim that the sum total of all this work, including our own, represents
the state of the art in quadruped locomotion, and leave a more detailed detailed description of theindividual strengths and weaknesses of our approach in this later chapter.

CHAPTER 1. INTRODUCTION

6• Chapter 3: Approximate Policy Gradient via the Signed Derivative.
This chapter looks at one of the fundamental questions that arises when dealing
with learning control policies from inaccurate models: how can an inaccurate
model, unsuitable for directly learning a control policy, still help us obtain good
performance on the system of interest? The criterion we look at in this chapter
states that an inaccurate model can still be used to improve performance when
the signs of certain dominant model derivative terms are correct; this motivatesthe development of a highly simplified form of model, which we call the signed
derivative, that only specifies the signs of these dominant derivative terms.
We show, both theoretically and empirically, that policy gradient methods can
exploit such a model to obtain good performance on a system without everusing an accurate model. We evaluate this approach on a number of tasks,
including a simulated two-link arm, an autonomous RC car, and a quadruped
robot learning to jump up steps.
• Chapter 4: Dimensionality Reduction in Policy Search. This chapter also deals with policy search and policy gradient methods, but exploitinga different type of inaccuracy. In particular, we assume here that we have aparametrized dynamics model that is described by some number of free parameters, and we have a distribution over these parameters encoding our uncertainty
in the model. However, unlike robust control procedures, which try to find asingle policy that performs well over this entire distribution, we use dimensionality reduction techniques to identify a linear subspace that contains (near)
optimal control laws for models drawn from that distribution. This enables us
to greatly reduce the number of parameters we need to learn for control policies,and enables us to efficiently learn a policy on the real system, using either thetechniques described in Chapter 3 or via model-free techniques. We demonstrate the approach on a task of learning fast omni-directional locomotion on aquadruped.
• Chapter 5: Multi-model Control for Mixed Closed-loop/Open-loop
Behavior. This chapter deals with the question of what happens when there

CHAPTER 1. INTRODUCTION

7

is a dynamical system that we simply cannot model accurately, even in termsof its dominant derivative signs or a distribution over parameters. In sucha setting it may appear as though there is little chance that we will be able
to control the system as desired; however, a common feature of many control
tasks, even in highly challenging domains, is that they are often remarkably
deterministic over short periods of time. This motivates a control strategy where
we use models to control the system in regions where the model is accurate,and execute previously observed trajectories “open-loop” in regions where themodel is inaccurate, but where we have observed a previous demonstration that
accomplishes the desired behavior. In this chapter we develop a probabilistic
approach for such a strategy, which smoothly trades off between LQR-based
control and open loop based upon a measure of model variance. We first evaluate
the method on a standard cart-pole benchmark, and then show that it is able
to achieve very good performance on the challenging task of sliding a full-sizedautonomous car into a narrow parking spot.
• Chapter 6: Application to the LittleDog Robot In this chapter we focus
on developing a control system that allows a quadruped robot to quickly androbustly cross a wide variety of challenging terrain. As mentioned one of the key
challenges that drives our approaches to this problem is that accurately modeling the LittleDog, in particular how its feet will react with different portionsof the terrain, is a highly challenging task. This chapter differs from previous
chapters in that the focuses is largely on the application itself, and we present
a variety of different algorithms that we have developed for this task. We showthat the final system is able to repeatedly cross a wide variety of challenging
terrain, with obstacles as large as the robot’s legs.

CHAPTER 1. INTRODUCTION

1.4

8First Published Appearances of Contributions

Much of the material here has appeared in previous publications, though in somechapters substantial portions have also been expanded. The signed derivative algorithm in Chapter 3 first appeared in (Kolter and Ng, 2009a), though the algorithm
description has been greatly expanded upon. Similarly, the dimensionality reduction
for policy gradient method was first published in (Kolter and Ng, 2007), though again
the algorithm has been expanded upon here. Our work on multiple model control for
mixed open-loop and closed-loop behavior, and its application to the an autonomous
sliding parking maneuver in Chapter 5 appears in (Kolter et al., 2010). Finally, theLittleDog work we present in Chapter 6 encompasses a number of papers: (Kolter
et al., 2008a,b; Kolter and Ng, 2009b).

Chapter 2
BackgroundIn this chapter, we present a basic background on learning and control techniquesthat provide the foundation for the later algorithmic chapters. Machine learning andcontrol are clearly both large fields of research, so we focus here particularly on thosealgorithms that we will later build upon in subsequent chapters. In particular, thischapter will mainly introduce the notation for dynamical systems and the optimal
control framework, and focus on two methods for optimizing controllers based upon amodel: policy-gradient methods and Linear Quadratic Regulator (LQR) based algorithms. For broader introductions to the topics, a number of references are available(e.g., Bertsekas, 2005a; Sutton and Barto, 1998; Stengel, 1994).

2.1

Dynamical Systems and Optimal Control

2.1.1

States and Controls

Foremost in the technical description of dynamical systems is the notion of a system
state. Although “state” can potentially refer to a number of things, informally, thestate captures those elements of the system that are relevant to its evolution andcontrol, but which typically are not directly specified by the agent. For instance, for
the quadruped robot, the state of the robot itself may include the 3D position andorientation of the robot’s center in space, as well as the the joint angles for each of its

9CHAPTER 2. BACKGROUND

10

legs plus velocities for all these terms; for a car the system state may consist of therobot’s position, orientation, and steering wheel angle, again plus velocities for theseterms. Throughout this work we will use the notations ∈ Rn(2.1)

to denote the state of the system, where n denotes the dimension of the state space.
Often times there is much greater structure than this definition implies (for instance, if
the state space is discrete), but because we want to work with a general representation
for states, we will adopt this notation.
Controls, in contrast, specify those elements, relevant to the evolution of thesystem, that the agent can specify directly. For instance, in the quadruped robot, thecontrols may correspond to torques on the robot joints; the distinction here is thatwhile it is not possible for the agent to directly command the state of the system(we could not, for instance, direct the robot to immediately assume some position ororientation), it is possible to directly command control torques to the robot’s joints(for our sake ignoring the complexity of the joint motors themselves, so we assume
the ability to instantaneously apply a torque to one of the motors). Similarly, forthe car, the controls could correspond to torque applied to the steering wheel, or
throttle/brake commands. We will use the notationu ∈ Rm(2.2)

to denote controls, where m in the dimension of the control input.

2.1.2

First-order Markov Models

Given these notions of states and controls, we must then determine how the stateevolves as a function of past states and control inputs. Typically this is done either
in a continuous-time manner, by specifying the time derivative ṡ as a function of
past states and controls (thus specifying the evolution of the state as an ordinary
differential equation), or in a discrete-time manner, specifying the next state, denotedCHAPTER 2. BACKGROUND

11

st+1 , as a function of previous states and controls. We will focus on the discrete-timecase in this work, both for intuitive simplicity of computing state updates (computing
the next state from past events will involve just evaluation a function, rather than
numerically integrating a differential equation), and because in practice, we typicallycontrol any actual system at a discrete set of points. However, we note that all the
results presented here can be carried over to the continuous time case with little
difficulty.
In this discrete-time setting, we can formalize the notion of a model as somefunction that predicts the next state given past states and control
st+1 = f (st , ut , st−1 , ut−1 , . . .).

(2.3)

However, in practice such general models can be quite cumbersome, as the next state
could depend on a long history of controls. Thus, in this work, as is common in
the control literature, we will restrict our attention to first-order Markov models, a
subset of dynamical systems where the next state depends only on the current stateand control
st+1 = f (st , ut ).

(2.4)

Despite the simplification, we are actually not loosing a great deal of expressive powerwith this limitation; since the state can be augmented to include a history of paststates, any model that depends on a finite number of previous states can controls canbe represented as a first-order Markov model. This framework also helps to clarify
the definition of states and controls; in a first-order Markov model, the state andcontrol input contain everything needed to determine the next state of the system,
where the controls and states respectively represent those quantities that the agent
can and cannot directly affect.

2.1.3

Stochastic models

There are many times that we want to capture some element of randomness or stochasticity in the model. Indeed, when represented using typical state and control spaces,CHAPTER 2. BACKGROUND

12

complex systems like quadruped robots and cars exhibit some amount of stochasticity:even given perfect knowledge of the current state and control, no model could predict the next state with perfect accuracy, because the next states can actually differ
slightly even for identical initial states and controls. Note that this use of stochasticity is independent of whether there are “real” stochastic effects in the world. What’s
occurring here is that our parametrization of the state is typically incomplete: wechoose some representation of the system’s state so that “most” of the system’s evolution can be described using a first-order Markov model, but there are almost always
certain elements that affect the system evolution to some degree, but that we either
cannot observe or simply don’t want to include in the model. In a car, for instance,
it may be the case that the next state could be affected by small differences in how
much the tire in worn on the different wheels; but we may have no desire to actual
include tire wear on each wheel as a state in our model, because it is both hard tomeasure and has a relatively negligible effect the system. Thus, we can instead add
some amount of stochasticity to the system, both to capture any “real” stochasticity
that may exist in the world, but also to account for unmodeled effects due to our
choice of state representation. Indeed, this notion of “stochasticity as a proxy formodel inaccuracy” will be further discussed and exploited in later chapters.
For the present time, however, we simply note that stochasticity is often a desirable
element in models, and we can represent such stochasticity by a model of the form
st+1 = f (st , ut ) + ǫt

(2.5)

where ǫt denotes some zero-mean noise term, such as a Gaussian random variablewith covariance Σ:ǫt ∼ N (0, Σ).

(2.6)

Indeed, we will often use noise terms of this form, but it is important to note that
(2.5) is a fully general means for representing any stochastic model (assuming weallow ǫt to depend arbitrarily on the state, control and time), and that (2.6) is a very
specific special case, that is no longer fully general.

CHAPTER 2. BACKGROUND

2.1.4

13

Control policies

A control policy (also referred to simply as a controller ) provides a means for choosing
control actions based upon the current state. Formally, we define a policy
π : Rn → Rm

(2.7)

simply as a mapping from states to actions. In practice, however, because the state
space can be large and continuous, we typically want to work with some restrictedclass of policies.
In this thesis, we will typically work with parametrized policies, where the policy
function is specified by some small set of parameters θ ∈ Rk . We will use the notationut = π(st ; θ)

(2.8)

to denote that, for instance, ut is given by the policy π, evaluated for state st , andparametrized by θ. One common example of a parametrized policy is a linear policy
where the controls are prescribed as a linear function of the stateπ(st ; θ) = Kst(2.9)

where K ∈ Rm×n is a matrix of the policy parameters, with θ = {K}. Notice a
subtle distinction here: for notational simplicity in many cases, we will typically useθ to denote a vector of the policy parameters. However, in the case of linear policies,
we need a matrix to output m controls for n state variables; thus, we use a different
symbol (typically K) to denote this matrix, and use θ to represent a vector containing
all the elements of K. In control terminology, the matrix K is often called the gain
matrix in this setting.
Another common form of policies are those linear in state features. Formally,
π(st ; θ) = Kφ(st )(2.10)

where φ : Rn → Rp is a function mapping from states to some p-dimensional feature

CHAPTER 2. BACKGROUND

14

vector, K ∈ Rm×p is again a matrix of parameters, and again θ = {K}. Notice that
this is a completely general policy: because φ can be an arbitrary feature mapping,
we can actually represent any (time independent) parametrized policy in this form.
Finally, as we will see below, there are times where it is actually desirable to use
stochastic control policies. As with the dynamics model, we can for example define astochastic policy by adding a zero-mean noise term to the output of a deterministic
policyπ(st ; θ) = Kφ(st ) + νt

(2.11)

where νt ∼ N (0, Λ). Unlike the dynamics model, stochastic policies are often viewed
as an undesirable element, introducing artificial noise into the system where none
existed before. Thus, as we will show shortly, while stochastic policies can be usefulfor learning methods, one often removes this stochasticity when applying the final
policy on the real system.

2.1.5

Optimal Control

Finally, in order to determine how to choose a policy that can control some dynamicalsystem, it is necessary to specify what constitutes “good” behavior in this system. The
typical method for doing this is through a cost function, that specifies the “badness”
of a given state (and possibly control). We formally define cost functions as mappingsfrom states and controls to a real number:
C : Rn × Rm → R.

(2.12)The goal of a control policy in the optimal control framework is then to minimize
the expected sum of costs over some time horizon H. Formally, we define the valuefunction for a policy π and state s starting at time t, denoted Jtπ (s) (also called thecost-to-go function) as the sum of expected costs, starting at time t, in state s, andacting according to policy π
Jtπ (s) = E

" H
X
t′ =t

#

C(st′ , π(st′ )) st′ +1 = f (st′ , π(st′ )) + ǫt′ , st = s .

(2.13)

CHAPTER 2. BACKGROUND

15

When we use the notation J π , the subscript t = 0 is implied, and we will typically
only use a subscript when defining a value function for some other time horizon. The
value function Jtπ also satisfies a recurrence relation know as Bellman’s equation
 π
Jtπ (s) = C(s, π(s)) + E Jt+1
(f (s, π(s)) + ǫ)

(2.14)

and with JHπ (s) = C(s, π(s)). Intuitively, this relation says that the value of a stateis equal to the cost of that state, plus the expected value of the next state, following
policy π.
The optimal policy, denoted π ⋆ , is the policy that minimizes the value function(2.13) over all possible policies. The value of function of this optimal policy, denoted
J ⋆ , obeys its own version of Bellman’s equation, sometimes referred to as Bellman’s
optimality equation to distinguish it from the case above: ⋆
Jt⋆ (s) = min C(s, u) + E Jt+1
(f (s, u) + ǫ) .
u

(2.15)

In certain situations, such as discrete state spaces, or linear systems with quadratic
costs (a case that we will discuss at length below), it is possible to use the Bellman
optimality equation to analytically solve for the optimal value function, which in turngives us the optimal policy at time t ⋆πt⋆ (s) = arg min C(s, u) + E Jt+1
(f (s, u) + ǫ) .
u

(2.16)

In most cases, though, computing an exact solution to Bellman’s optimality equation
is intractable, and so we must resort to approximate methods or methods that only
find locally optimal policies. Indeed, much of the remainder of this chapter will
focus on two methods for finding approximately optimal control laws: policy gradientapproaches, and Linear Quadratic Regulator (LQR) techniques.

CHAPTER 2. BACKGROUND

2.1.6

16

Markov Decision Processes

The learning and control community, and in particular the Reinforcement Learning
community, often uses the machinery of Markov Decision Processes (MDPs) to formalize the optimal control framework. Intuitively, an MDP is simply a structurethat contains all the elements described previously in this section: state and control spaces, a dynamics model (also called transition probabilities), a cost function(or reward function, which just corresponds to negative cost), a time horizon, anda distribution over initial states, and a cost function. Formally, using the notationfrom this chapter, an MDP is a tuple M = (S, U, P, D, H, C) where S and U are thestate and control spaces; P is a set of transition probabilities given by the dynamics
model, D is a distribution over initial states, H is the time horizon, and C is the costfunction. There are many slightly different formulations for MDPs, such as the thosewith a reward function instead of a cost function, or those with an infinite (possibly
discounted) value function instead of the finite time horizon we use above. However,these are minor differences, and the basic machinery and algorithms for MDPs arevery similar across all the different formulations. Thus, we include this section justto note the connection, as much other work and many later chapters will use the
MDP formulation specifically. For a more complete introduction to MDPs, see e.g.,
Putterman (2005).

2.2

Multi-variate Calculus

This thesis makes extensive use of calculus in multiple variables. While the actual
calculus we use is actually very simple (almost entirely differential calculus), the notation may be initially confusing, as there are actually a variety of different notationsin use for these functions. Thus here we briefly review some of the notation that wewill use in the remainder of the thesis.

CHAPTER 2. BACKGROUND

2.2.1

17

The Gradient

The gradient of a function is defined for real-valued functions with vector or matrix
inputs f : Rm×n → R. The gradient is a vector (or matrix) of equal size as thefunction input, and is defined as∇A f (A) ∈ Rm×n = ∂f (A)
∂A11

..
.

···
...

∂f (A)∂A1n∂f (A)∂Am1···∂f (A)
∂Amn

..
.




,


(2.17)

i.e., the ijth entry of ∇A f (A) is equal to the derivative of f (A) with respect to theijth entry of A.

2.2.2

The Jacobian

The Jacobian of a function is defined for vector-valued functions with vector inputs
f : Rn → Rm . The Jacobian is an m × n matrix, defined as∂f (x)∈ Rm×n = ∂x∂f (x)1
∂x1

..
.

···
...

∂f (x)1∂xn∂f (x)m∂x1···∂f (x)m
∂xn

..
.




,


(2.18)

i.e., the ijth entry of ∂f∂x(x) is equal to the the derivative of f (x)i with respect to xj .
Because Jacobians behave much like scalar derivatives, we use the same notation,
but is is important to remember that ∂f∂x(x) is a matrix when used for multi-variate
functions and inputs. It is also important to note the subtle difference between the
Jacobian and the gradient: for a real-valued vector function f : Rn → R, the gradientis the transpose of the Jacobian∇x f (x) =∂f (x)∂x

T.

(2.19)

A useful property of the Jacobian, completely analogous to the scalar case, is theCHAPTER 2. BACKGROUND

18

chain rule. For functions f : Rk → Rm and g : Rn → Rk ,∂f (g(x))∂f (y) ∂g(x)
=
,
∂x
∂y
∂x

y ≡ g(x)(2.20)

A useful special case of this rule applies when we have f that is explicitly a functionof two vector arguments, f : Rk × Rℓ → Rm , g : Rn → Rk , h : Rn → Rℓ ,∂f (y, z) ∂g(x) ∂f (y, z) ∂h(x)∂f (g(x), h(x))
=
+
,
∂x
∂y
∂x
∂z
∂x

2.3

y ≡ g(x), z ≡ h(x).

(2.21)

Policy Gradient Methods

When global optimization of the control policy is intractable, one of the simplest andmost common methods for finding a good policy is via policy gradient techniques.
In this section we use the terminology of parametrized policies as defined above, andwe use J(·; θ) as shorthand for J π(·;θ) , the value function of the policy parametrizedby θ ∈ Rk . Policy gradient methods use a simple gradient descent rule to find theparameters that minimize the value function. In particular, if we let∇θ J(s; θ) ∈ Rk

(2.22)

be the gradient of the value function, evaluated as state s, with respect to the parameters (this quantity itself is known as the policy gradient), then by performing
the simple updateθ ← θ − α∇θ J(s; θ)(2.23)

for a small step-size α ∈ R+ , we will adjust θ so as to incrementally improve J(s; θ).
Under certain smoothness conditions, this process will find a locally optimal set ofcontrol parameters. Also note that if we desire a policy that performs well over some
distribution D over states, we can just as easily compute gradients with respect toJ(D; θ) = Es∼D [J(s; θ)](2.24)

CHAPTER 2. BACKGROUND

19

by using sampling methods, for instance.
The key to policy gradient approaches, of course, is how we compute these gradientterms ∇θ J(s; θ). This section discusses several methods for doing so in different
scenarios.

2.3.1

Known deterministic model

The most straightforward scenario for computing policy gradients is the case of aknown deterministic model, (2.4). First, note that we can easily compute J(s; θ) by
the procedure
1. Run the policy for H steps: st+1 = f (st , π(st )) for t = 0, . . . , H − 1, with s0 = s.
2. Sum the costs: J(s; θ) =PH

t=0 C(st , π(st )).

Given this (deterministic) method for computing J(s, θ) we can easily compute its
gradient with respect to θ by finite differencing, for example: we simply make minor
adjustments by adding some some small δ to one of the elements of θ, then recomputethe value function and divide by δ:(∇θ J(s, θ))i ≈J(s, θ + δei ) − J(s, θ)δ(2.25)

where ei ∈ Rk denotes the ith unit basis (a vector whose elements are all zero except
for the ith element, which is one).
While finite differencing is useful in its simplicity, if we are able to compute derivatives of the model analytically, then we can also compute the policy gradient analytically by applying the chain rule (a strategy known as real-time recurrent learningin the Neural Network community (Williams and Zisper, 1989)). The material here
is more advanced than that in the remainder of this chapter, and is not crucial for
its understanding, but the way in which we derive the equations here will be used inlater chapters as well. To determine an analytical form of the policy gradient, we canapply the chain rule to see that
∂C(st , ut )∂C(st , ut ) ∂st ∂C(st , ut ) ∂ut ∂st ∂C(st , ut ) ∂ut
+
+
,
=
∂st
∂st
∂θ
∂ut
∂st ∂θ
∂ut∂θ

(2.26)

CHAPTER 2. BACKGROUND

20

and
∂st+1
∂f (st , ut )∂f (st , ut ) ∂st ∂f (st , ut ) ∂ut ∂st ∂f (st , ut ) ∂ut
=
=
+
+
.
∂θ
∂θ
∂st
∂θ
∂ut
∂st ∂θ
∂ut∂θ

(2.27)

By also noting that∇θ J(s; θ) =H
X∇θ C(st , ut ) =

t=0

T
H 
X
∂C(st , ut )t=0∂θ(2.28)

we can derive a simple algorithm for computing the gradient that maintains the matrixt, uses this term to compute each element of the policy gradient, and updates
G = ∂s∂θ

this term according to (2.27). Thus, the procedure is as follows:• Initialize s0 ← s, ∇θ J(s; θ) ← 0, G ← 0.
• For t = 0, . . . , H − 1,
1. ut ← π(st ; θ), st+1 ← f (st , ut )T∂C(st , ut ) ∂C(st , ut ) ∂π(st ; θ)T+
2. ∇θ J(s; θ) ← ∇θ J(s; θ) + G
∂st
∂ut
∂st

T
∂C(st , ut ) ∂π(st ; θ)
+
∂ut
∂θ


∂f (st , ut ) ∂π(st ; θ)∂f (st , ut ) ∂f (st , ut ) ∂π(st ; θ)G++
3. G ←
∂st
∂ut
∂st
∂ut
∂θ

2.3.2

Known stochastic model

When the dynamics model of the system is known, but includes a stochastic noise
term as in (2.5), then additional techniques are needed: simply computing the policy gradient ignoring the noise term will not give an unbiased estimate of the true
gradient. The most common means for computing policy gradients in this domain is
via sampling: we compute the policy gradient (by any of the methods above) using
some fixed ǫ1 , . . . , ǫH drawn by random sampling. We repeat this process a numberof times and average all the resulting policy gradients to get our final estimate of
the gradient. This is known as the PEGASUS algorithm (Ng and Jordan, 2000), andCHAPTER 2. BACKGROUND

21

it can be shown that this procedure produces an unbiased estimate of the gradient,and furthermore that given a suitable number of samples it will be close to the true
gradient with high probability.

2.3.3

Unknown deterministic or stochastic model

Finally, we note that there are algorithms which can compute an estimate of thepolicy gradient even when an explicit model is unknown (but, of course, assuming
we can execute control policies in the system). Because these methods are not thefocus of this thesis, we just introduce the basic ideas here, and leave the numerous
extensions of these methods to the references. However, since this thesis is about
inaccurate models (which are hopefully easy to obtain), the methods presented here
are often the best comparisons to our approaches, as the relevant question is: howmuch can it help to have an inaccurate model versus no model at all?
The method presented here is known in the context of Reinforcement Learningas the REINFORCE, or Episodic REINFORCE algorithm (Williams, 1992), but it isbased on a method known as likelihood ratio gradient estimation (Glynn, 1987). Unlike the previous approaches, this method and extensions require stochastic policies,
so we will use the notationp(u|s; θ)(2.29)

to denote the probability density of action u given state s, when executing the policy
parametrized by θ. Typically this takes the form of a deterministic policy plus noise,
as in (2.11).
To simplify the presentation, we will also introduce here the notion of a trajectory,
denoted τ , which is simply a sequence of states and actions
τ = (s0 , u0 , . . . , sH , uH ).

(2.30)We also overload the cost notation, so thatC(τ ) ≡H
X
t=0

C(st , ut ).

(2.31)

CHAPTER 2. BACKGROUND

22

Using this notation, notice that the value function can also be written as
J(s; θ) = Eτ [C(τ )] =Zp(τ |s0 = s; θ)C(τ )dτ

(2.32)(for the remainder of this section, we will omit the s0 = s qualification, as this will
always be implied).
Given this form of the value function, the policy gradient can be written asZ∇θ J(s; θ) = ∇θ p(τ ; θ)C(τ )dτZp(τ ; θ)∇θ p(τ ; θ)C(τ )dτ=p(τ ; θ)Z
= p(τ ; θ)∇θ log p(τ ; θ)C(τ )dτ

(2.33)= Eτ [∇θ log p(τ ; θ)C(τ )] .

By this “trick” of introducing the gradient of a log term, we can transform the gradient
into an expectation, which we will then approximate using sampling. However, wemust first show how to compute the derivative term ∇θ log p(τ ; θ). Fortunately, thiscan be done without the need for an explicit dynamics model, since∇θ log p(τ ; θ) = ∇θ log

HYp(st+1 |st , ut )p(ut |st ; θ)

t=0

=
=

H
X

t=0
H
X

!

(∇θ log p(st+1 |st , ut ) + ∇θ log p(ut |st ; θ))(2.34)∇θ log p(ut |st ; θ)

t=0

where the ∇θ log p(st+1 |st , ut ) term drops out because it does not depend on θ. Thus,
as claimed above, we see that this term can be computed without an analytical modelof the system. The complete procedure for computing the gradient is as follows, where
we approximate the expectation in (2.33) using M sample trajectories:• For i = 1, . . . , M , sample a trajectory τ (i) by starting in state s and executing

CHAPTER 2. BACKGROUND

23

the policy (with parameters θ) for H steps.
!
M
H
1 X X
(i) (i)∇θ log p(ut |st ; θ) C(τ (i) ).
• ∇θ J(s; θ) ≈M i=1 t=0
One requirement of the algorithm, as written, is that we need the ability to “reset”
the system to the same initial state s and perform multiple simulations of the policy.
While this could be avoided by using M = 1, this typically produces a very noisy
estimate of the gradient, which is of limited use for improving the policy. Thus, thesemodel-free policy gradient methods are typically applied to scenarios where we canreset the state to the same or very similar initial state. Furthermore, as mentioned
above, the algorithm above is the simplest version of a likelihood ratio policy gradient method; obtaining good performance with such algorithms typically requires
more advanced techniques, such as the selection of an optimal baseline (Greensmith
et al., 2004) (a bias on the cost, which doesn’t change the gradient, but which reduces
the variance of the estimate), and natural gradient methods (Kakade, 2001; Bagnell
and Schneider, 2003; Peters et al., 2005) (a technique that performs steepest descent
updates according to a metric on the trajectory probabilities, rather than the parameter space, and which typically results in much faster convergence). However, these
extensions are beyond the scope of this background introduction.

2.4

Linear Quadratic Regulator Methods

Methods based upon linear quadratic regulator (LQR) control form another common
family of algorithms for find locally optimal control laws. In contrast to policy gradient methods, which can be applied to any arbitrary form of parametrized policy,
LQR methods typically output a very specific form of parametrized policy: (possibly time-varying) open-loop controls plus (also possibly time-varying) linear feedback
controllers. LQR control is based upon a special case of continuous state and action dynamics and cost, where the solution to Bellman’s optimality equation can besolved analytically. Thus, we begin our presentation with a discussion of this specialcase. For more detailed discussion of Linear Quadratic methods, there are a number

CHAPTER 2. BACKGROUND

24

of available references (e.g. Bertsekas, 2005a; Anderson and Moore, 1989; Stengel,
1994)

2.4.1

Linear Dynamics and Quadratic Cost

We begin by considering the special case of a linear dynamics model
st+1 = Ast + But(2.35)

and a (positive definite) quadratic cost function1
C(s, u) = sT Qs + uT Ru,

Q ∈ Rn×n  0, R ∈ Rm×m ≻ 0(2.36)

i.e., the goal is to maintain the system at the zero state, s = 0, while applying zero
control, u = 0. In this case, we will show that Bellman’s optimality equation admits
a closed form solution, and that the optimal value function is quadratic in the stateJ ⋆ (s) = sT P s(2.37)

for some P ∈ Rn×n  0. The derivation here is relatively brief: a more detailed
derivation is given in the references above. First note that
JH⋆ (s) = min(sT Qs + uT Ru) = sT PH s (for PH = Q).

(2.38)u

Now suppose Jt⋆ = sT Pt s for some Pt  0. Then by Bellman’s optimality equation
we have⋆Jt−1(s) = min sT Qs + uT Ru + Jt⋆ (As + Bu)u= sT Qs + min uT Ru + (As + Bu)T Pt (As + Bu)u= sT Qs + sT AT Pt As + min uT Ru + uT B T Pt Bu + 2sT AT Pt Buu

1(2.39)


Here A  0 and A ≻ 0 denote positive semidefinite and positive definite matrices respectively.

CHAPTER 2. BACKGROUND25

The u that minimizes the right hand size is given byu⋆t = (R + B T Pt B)−1 B T Pt As(2.40)and substituting this expression back into (2.39), the value function takes the form
(after some simplification)⋆
Jt−1= sT (Q + AT Pt A − AT Pt B(R + B T Pt B)−1 B T Pt A)s = sT Pt−1 s,(2.41)

which again is a quadratic form (and, though we don’t prove it here, is also positive
semidefinite). This implies that the optimal policy in this domain is a (time-varying)
linear feedback policyπt⋆ (st ) = Kt st ,Kt ≡ (R + B T Pt B)−1 B T Pt A.

(2.42)

Using the notation of parametrized policies from the preceding section, we would
say that the policy parameters here are a separate gain matrix for each time step
θ = {K1 , K2 , . . . , KH } with Ki ∈ Rm×n , and the LQR algorithm allows us to find theglobally optimal set of parameters for the case of linear dynamics and quadratic cost.
While the requirement of linear dynamics and quadratic cost may seem overly
restrictive, the algorithm can be extended to certain more general settings while
maintaining global optimality:• Time-varying dynamics and costs. The algorithm can be easily generalized
to time-varying linear dynamics models and costs:
st+1 = At st + Bt ut ,Ct (s, u) = sT Qt s + uT Rt u.

(2.43)

We omit the derivation because it is identical to that above, but the resulting
optimal value function and optimal policy have the formJt⋆ (s) = sT Pt s,πt⋆ (s) = (Rt + BtT Pt Bt )−1 BtT Pt At s ≡ Kt s

Pt−1 = Qt + ATt Pt At − ATt Pt Bt (Rt + BtT Pt Bt )−1 BtT Pt At ),PH = QH .

(2.44)

CHAPTER 2. BACKGROUND

26• Affine systems. We can apply LQR to affine systems
st+1 = Ast + But + a(2.45)

by adding a constant term to the and applying LQR to the augmented system
s̄ =

"

s
1

#

, Ā =

"

A a
0 1

#

, B̄ ="

B
0#, Q̄ =

"

Q 0
0 0

#

, R̄ = R.

(2.46)• Trajectory tracking. We can also express costs that penalize deviation froma time-varying desired state and control
Ct (s, u) = (s − s⋆t )T Q(s − s⋆t ) + (u − u⋆t )T R(u − u⋆t ).

(2.47)

While it is possible to solve this equation by augmenting the state as in theprevious example, this also requires a cost function that has cross-terms that
depend on both the state and control (to account for a term that is linear in
the control input). Instead, using the same method as above it can be shownthat the optimal value function and policy are of the formJt⋆ (s) = sT Pt s + 2qtT s + rt ,πt⋆ (s) = Kt st + gt

Kt = −(R + B T Pt B)−1 B T P A,

gt = −(R + B T Pt B)−1 (Bqt − Ru⋆t )Pt−1 = Q + AT Pt A − AT Pt B(R + B T Pt B)−1 B T Pt A,
qt−1 = (A + BKt )qt − KtT Ru⋆t − Qs⋆t ,PH = QH(2.48)

qT = −Qs⋆T

rt−1 = rt + u⋆t T Ru⋆t + s⋆t T Qs⋆t − (B T qt − Ru⋆t )T gt ,rT = s⋆t T Qs⋆t

• Stochastic models. LQR can also be easily applied to stochastic linear modelsof the form
st+1 = Ast + But + ǫt ,ǫt ∼ N (0, Σ).

(2.49)

In fact, it turns out that the optimal control law for this system with Gaussian
noise is identical to the optimal control law for the system without noise, andCHAPTER 2. BACKGROUND

27

thus we can solve this setting by the same method as above. Although we
do not prove it formally here, the basic intuition is that, because the noise isindependent of the state and control, it has no impact on the optimal policy;
the only difference in the stochastic setting is that there is an additional termin the value function, accounting for the additional expected cost due to noise.
Thus, in general we won’t distinguish between the stochastic and deterministic
case for LQR models.
Many other simple extensions to the setting can be solved exactly, and of course
we can combine any of these extensions. However, the constraint of linear (or affine)models is still a large restriction, and thus in the next section we discuss how thesetechniques can be extended (approximately) to non-linear systems.

2.4.2

Non-linear models

Consider a general nonlinear model of the form previously considered
st+1 = f (st , ut )(2.50)and initially suppose further that s = 0, u = 0, is an equilibrium point of the system
0 = f (0, 0)(2.51)

i.e., starting in state s = 0 and applying control u = 0 keeps the system in states = 0 (notice that this holds for the linear dynamical systems described above, so
we are merely making this requirement to keep the parallels to the linear case as
close as possible at first). Again we assume a positive definite quadratic cost function
C(s, u) = sT Qs + uT Ru.
To apply LQR to this setting, we linearize the dynamics around this equilibrium
point, equivalent to taking a first-order Taylor expansion of the non-linear system, toobtain the approximate system matricesA≡∂f (0, 0),∂sB≡∂f (0, 0).
∂u(2.52)

CHAPTER 2. BACKGROUND

28

We then solve the resulting LQR problem to obtain a controller πt (s) = Kt s exactly
in the manner described above. While this controller will no longer be optimal forthe non-linear system, in practice these control laws typically perform very well,especially when the system begins in a state “close” to the equilibrium point, sothat the linearization does not introduce very much error. Indeed, although themathematical analysis is beyond the scope of this material, under suitable conditions
on the dynamics model the resulting controller is guaranteed to stabilize the nonlinear system (bring the system to the desired s = 0, u = 0 state) for some suitable
ellipse around the equilibrium point. Indeed, the quadratic cost function of LQR
methods can generally be thought of as producing policies that stabilizes the system
around some the zero point. For a more detailed explanation of this linearization
procedure and the application of LQR to non-linear systems, see e.g., (Anderson and
Moore, 1989, Ch. 3) and (Stengel, 1994, Ch. 5).

2.4.3

Non-linear trajectory stabilization

The requirement in the preceding section, that we stabilize the system around thezero state and control, may seem overly restrictive, and indeed the same technique
can be applied to stabilize the system around a trajectory. Given a trajectory of theform described earlier in this sectionτ̄ = (s̄0 , ū0 , s̄1 , ū1 , . . . , s̄H , ūH )(2.53)

we consider a quadratic cost function that penalizes deviations from this trajectory
Ct (s, u) = (s − s̄t )T Q(s − s̄t ) + (u − ūt )T R(u − ūt ).

(2.54)

We construct a time-varying LQR task by linearizing the dynamics along the trajectory:At =∂f (s̄t , ūt )
,
∂st

Bt =

∂f (s̄t , ūt ),∂ut(2.55)

CHAPTER 2. BACKGROUND

29

and we solve the time-varying LQR task (but with time-invariant Q and R), according
to equation (2.44). The resulting policy will be to apply control
πt (s) = ūt + Kt (s − s̄t ).

(2.56)

There is a subtle distinction here, but the LQR algorithm we apply here is not the“trajectory tracking” LQR cost function described above in (2.47); in particular, we
can solve this LQR task using just the normal quadratic equations, without the needfor a linear term in the value function. This is because we are linearizing the non-linear
system around the trajectory τ̄ ; in effect the linearization implies a (time-varying)
linear system in the trajectory errorδst+1 = At δst + Bt δut ,

Ct (δst , δut ) = δsTt Qδst + δuTt Rδut

(2.57)

where δst ≡ st − s̄t and δut ≡ ut − ūt denote the deviation from the desired trajectory.
Thus, the final policy specifies the control deviation will be a linear function of thestate deviation, δut = Kt δst , which is equivalent to (2.56) above.

2.4.4

Iterative LQR

Finally, the trajectory stabilization methods described above is still limited in that it
requires a priori knowledge of a realizable trajectory (i.e., both states and the controlsthat result in these states in the model). In this last section, we briefly illustrate how
we can iterate LQR techniques to generate a full sequence of open-loop controls, aswell as feedback controllers, that minimize some cost function without an a priori
trajectory. This general strategy goes by many different names, such as iterative
LQR (Li and Todorov, 2005), Gauss-Newton LQR (Boyd, 2003), or sequential linear quadratic methods (Sideris and Bobrow, 2005). The method is highly related to
the Differential Dynamic Programming (Jacobson and Mayne, 1970) and the successive sweep method (Dyer and McReynolds, 1970), and largely involves a very minor
simplification of these classical control strategies.

CHAPTER 2. BACKGROUND

30

Suppose we wish to minimize some trajectory tracking cost function
Ct (s, u) = (s − s⋆t )T Q(s − s⋆t ) + uT Ru(2.58)

in the nonlinear model st+1 = f (st , ut ). To solve this problem, we begin with somearbitrary sequence of controls ū0 , . . . , ūH and execute these controls in the model toobtain the resulting states s̄0 , . . . , s̄H . We then linearize around this trajectory, as
in the previous section but instead solve a time-varying tracking LQR problem withcost
Ct (δst , δut ) = (δst + s̄t − s⋆t )T Q(δst + s̄t − s⋆t ) + (δut + ūt )T R(δut + ūt )(2.59)

under the linear approximation of the error dynamics, δst+1 = At δst +Bt δut , describedin the previous section. Intuitively, since ut ≈ ūt + δut and st ≈ s̄t + δst for smallenough δut and δst (i.e., in a region close to the linearization point of the system),(2.59) closely approximates the cost function of interest (2.58). Thus, adjusting thecontrols according toūt ← ūt + δut = ūt + Kt δst(2.60)

will result in a new sequence of states and controls s̄0 , ū0 , . . . , s̄H , ūH that typicallyhas lower cost than the previous set of controls and states; we then iterate this processuntil convergence.
There is, however, the possibility that the algorithm as describe above will notconverge, due to the fact that for large δst or δut , the linearized model may be a poor
approximation of the non-linear model. To overcome this difficulty, we can add an
additional penalty term on δst and δut , to ensure that the resulting controller does
not deviate too far from the linearization — i.e., we add an additional penalty to thecost function of the form
H
X
t=0


δsTt Q0 δst + δuTt R0 δut .

(2.61)

By including such a term, and using large enough Q0 and R0 matrices such that

CHAPTER 2. BACKGROUND

31

the resulting δst and δut do not deviate too much from the linearization point, we
can guarantee that the algorithm convergences to a locally optimal set of open loop
controls ūt and feedback matrices Kt .

2.5

SummaryThis chapter presented a briefly background on reinforcement learning and optimal
control algorithms. We focused specifically on two categories of algorithms that
we will build upon in the subsequent work: policy gradient approaches and linear
quadratic regulator methods.

Chapter 3
Approximate Policy Gradient via
the Signed Derivative
The previous chapter discussed a number of standard methods for optimizing a policy
given a (presumably accurate) model of the system. However, as discussed in the
introduction, the theme of this work is the ability to use inaccurate models to findgood policies. The natural question, then, is how an inaccurate model of the system,
which may be unable to control the system using the methods from the previous
chapter alone, could still allow us to find policies that perform well.
The algorithm we present in this chapter is based upon the fact that, as we willshow shortly, the policy gradient term discussed in the previous chapter can be written such that it depends only on certain model derivative terms. The intuition of
our algorithm is that while such derivative terms may be hard to determine precisely(since we assume that the system is difficult to model), it is often very easy to estimate
the sign of these derivative terms. Furthermore, if we compute an approximate policy
gradient by simply substituting these signs for the derivatives themselves, the resulting algorithm works well (both theoretically and empirically) in many situations, anddoes not require an accurate model of the system.
Our method requires an additional constraint on the dynamics as well; for technical reasons that we will discuss in detail shortly, both our theoretical and empirical32

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

33

analysis focuses on dynamical systems where each state variable is primarily controlled by only one control variable (although a single control can affect multiple
state variables). While most state variables will naturally be affected by all control
inputs to some degree, we consider the scenario where each state variable is merely
primarily affected by one control (i.e., affects of other controls are treated as noise
terms), where we will formalize this notion shortly. The rationale behind this focus
will be discussed later in this chapter, but for the time being, we merely mention thatthe algorithm we present here does focus on this restricted class of dynamics models.
To highlight the critical intuition that certain model derivative signs are “easy” todetermine, and to illustrate why settings with the “orthogonal” control inputs mentioned above still capture interesting problems, we consider the simple example taskof driving a car along a trajectory. In this setting, the state could be the car’s lateraldeviation from the trajectory, its orientation relative to the trajectory, and its velocity, the cost could penalize lateral deviation from the trajectory and deviation froma desired velocity, and the policy could determine steering and throttle and a simple(e.g., linear) function of the current state or state features. Consider now the relationship between the car’s lateral deviation from the trajectory and the commanded
steering angle: it may be very difficult to determine the precise relationship between
how a change in steering angle results in a change in lateral deviation (this would
correspond to the derivative of lateral deviation states with respect to the steering
control input). However, the sign of the derivative term in this case is very obvious:
turning more to the left typically results in a lateral deviation that is also more to theleft. Furthermore, it should be apparent that the car driving domain is one where theabove constraint on control inputs and states holds: while the lateral deviation fromthe trajectory is affected by both the throttle and the steering angle, it is primarily
affected by the steering angle. While such “obvious” derivative signs, and constraints
on the control inputs, clearly don’t apply to all control tasks, we demonstrate in thispaper that they do apply in many interesting domains, and that when they do apply, the approximate policy gradient techniques based on these signed derivatives canperform very well.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

3.1

34

Related Work

The algorithm we present in this chapter relates most to two threads of research in thecontrol and optimization communities. The first of these is the focus on the accuracyof model derivative terms, rather than the predictive accuracy of the model itself.
Recalling the policy gradient and LQR approaches described in the previous chapter,
note that nowhere in the equations for the policy gradient (2.26) – (2.28), or in thelinearization of the LQR model (2.53), does the actual equation of the model itself,
f (st , ut ), come into play; rather, these terms depend on the model only through its
(s,u)
(s,u)
derivative terms ∂f ∂sand ∂f∂u. The only way in which these methods actually use

the model is for simulating the sequence of states s0 , . . . , sH given the control inputs
u0 , . . . , uH . But if we have the ability to run trials on the real system, then we canperform this step on the actual system itself, and if only the model derivative terms
are accurate, then we can use the equations above to effectively compute the policy
gradient or run LQR on the real system. This insight has been observed in a numberof different works, such as Jordan and Rumelhart (1992), and recently Abbeel et al.
(2006) provide a theoretical analysis and experimental results on such algorithms.
However, although this insight is quite useful, from a practical standpoint therequirement of “only” needing accurate derivatives is not a huge gain. In particular,
(s,u)
(s,u)
for the standard model st+1 = f (st , ut ), ∂f ∂scontains n2 terms and ∂f∂u
contains

mn terms. The derivative terms will be identical for the model with any added bias
st+1 = f (st , ut ) + bt

(3.1)

where bt ∈ Rn is a (state and control independent) bias term. Requiring only accurate
derivative, instead of accurate derivative and prediction, means we don’t need tolearn this bias term, but in the general case this only reduces the number of model
parameters needed by n, and it is unclear if there is any better way to learn themodel derivatives than to simply minimize prediction error. Instead, the algorithm
we present here requires that we only know the sign of the dominant derivative terms(s,u)
and similar terms), a(and, in fact, as we will show shortly only the signs of ∂f∂u

requirement that can be much easier to satisfy, as argued in the car driving example

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

35

above. Of course, as we will also discuss, the algorithm we present is also more limitedin the situations we can apply it to, so there is certainly a trade-off between the two
approaches.
The second main area of work which we build upon is work within the optimization
community on using sign terms in optimization. The idea here is simple: if we want
to minimize some function f (x), we can take small descent direction steps in the
direction of the gradient’s sign,x ← x − α sign(∇x f (x))(3.2)

where the sign function defined in the standard waysign(x) = −1 x < 0
0


 1

x=0

(3.3)

x>0

and is applied component-wise to vectors, and where α is some small step size. For
small enough step sizes (and assuming certain continuity requirements), this stepis guaranteed to decrease the objective; this fact can be shown by simply notingthat the sign of the gradient makes a positive inner product with the gradient,(∇x f (x))T sign(∇x f (x)) ≥ 0, which is the condition for a valid descent direction(Boyd and Vandenberg, 2004, pg. 463).
This general technique of using the sign of the gradient term as the update direction has a long history in optimization, machine learning, and control. One of thefirst algorithms to use this method is the so-called sign-sign LMS algorithm (Dasgupta and Johnson, 1986), a modification of the classical LMS algorithm (Widrow
and Hoff, 1960) (a stochastic algorithm for least-squares minimization), where thenormal gradient update is replaced by the sign of the gradient; an early applicationof this technique was used for channel equalization (Lucky, 1966). In this machinelearning community, such sign-update methods have been used extensively withinneural networks (Anderson, 1986), especially in the context of the RPROP algorithm(Riedmiller and Braun, 1992), which uses the same idea of gradient sign updates, but

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

36

also adds additional machinery to automatically select step size parameters basedon whether the gradient changes sign in successive updates. Indeed, the notion ofgradient sign updates was also discussed briefly in (Jordan and Rumelhart, 1992)
specifically in the context of optimizing control performance.
The way in which our proposed method differs from these past approaches is that,
as we will show shortly, our algorithm does not propose to update the policy parameters via the actual sign of the policy gradient; rather, our method replaces only certain
model derivative terms in the policy gradient with their signs, but includes many otherelements of the gradient which are not signed. Indeed, as we will show, the final approximate policy gradient produced by our approach does not necessarily share thesame signs as the true policy gradient (although it often does in practice). Thus, wecannot guarantee that the updates produced by our algorithm are descent directionsof the value function. However, as we will show below, the updates produced by ourapproximation are descent directions for a modified version of the value function, andone which often minimizes the true value function as well. We will of course discussthese points in greater detail below, but we merely mention this now to highlight thedifference between out approach and standard signed optimization methods. Finally,
we note that while a gradient descent approach that did always have the same signs
as the true gradient term may ultimately have better convergence properties than ouralgorithm, computing the signs of the true gradient seems no simpler than computing
the actual gradient (i.e., it requires a model of the system).
Finally, we want to note the connection between the algorithm we propose here andthe field of adaptive control (Sastry and Bodson, 1994; Astrom and Wittenmark, 1994)— in particular the subtopics of Model Reference Adaptive Control (MRAC) and
Self-Tuning Regulators — and Iterative Learning Control (ILC) (Moore, 1999). The
general philosophy of these approaches is similar to our own: they use an error signal(i.e., between the actual and desired state) to directly adapt the parameters. However,typical formulations of MRAC or ILC use hand-crafted update rules to modify thecontroller, with update gains that are typically chosen by a system designer. From ahigh level, though, the signed derivative policy gradient approximation could certainly
be viewed as an instance of MRAC or ILC, with a very particular form for the update

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

37

rule.

3.2

The Signed Derivative Policy Gradient Approximation

In this section we derive a simple approximate policy gradient method, using theapproximation we call the signed derivative. We want to emphasize that the final formof the algorithm, shown in Algorithm 1, is quite simple, even though the derivation
is somewhat involved.
To reiterate our domain settings, we assume the (true) system evolves according
to some non-linear, and unknown, model
st+1 = f (st , ut ).

(3.4)

For simplicity of the presentation we will assume the model is deterministic, but themethods easily extend to the setting of generating a single sample of the (approximate)gradient in the stochastic setting. We suppose a parametrized policy π(s; θ) for someparameters θ ∈ Rk , a cost function C(s, u), and again our goal is to (approximately)
compute the policy gradient ∇θ J(s; θ), which we will use to iteratively improve thepolicy parameters.
The signed derivative approximation is based on the following intuition. As wewill show below, is it possible to explicitly write the analytical form of the policy
gradient in a different manner as that presented in the previous chapter, such thatthe only terms which depend on the dynamics model are terms of the form
∂st
∂ut′

(3.5)

for t > t′ . Writing the gradient in this manner is not particularly useful for analyticalcomputation, since the exact analytical form of these derivative terms for t ≫ t′ ititself quite complex. However, these terms provide the critical motivation for thesigned derivative approximation, so it is worth looking at them more closely. TheseCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

38∂stindicates how
Jacobian matrices are n × m matrices, where the ijth element of ∂u′t

the ith element of st changes if we made a small adjustment to ut′ , but otherwise
continued to follow the policy parametrized by θ. For instance, when t = t′ + 1, thisterm is simply the partial derivative of the model with respect to the controls∂st′ +1∂f (st′ , ut′ )
=
,
∂ut′
∂ut′

(3.6)

which corresponds for example to the “B” matrix in the LQR linearization of the
dynamics model. The terms are more complex for t ≫ t′ , but the overall intuitionof the terms of the same even for longer time horizons: these terms represent how
past control inputs affect future states. Thus, we can reasonably assume that overa relatively short time horizon, these terms will be similar to the single-step term,∂f (st′ ,ut′ ).
∂ut′The signed derivative approximation is based on the intuition that while it may
be difficult to know these derivative terms exactly, it is often fairly easy to estimate
their sign. Returning to the above example of driving a car, while it is difficult toknow exactly how turning the wheel will affect future states, we can easily intuit thatturning the steering wheel more to the left results in future states where the lateraldeviation from the trajectory is also more to the left; further, this holds not just for
the immediate next time step as implied by∂f (st′ ,ut′ ), but for some sequence of future∂ut′time steps as well. The signed derivative approximation, then, simply computes an∂stapproximate policy gradient, where we replace all the Jacobian terms ∂ufor t > t′′twith a single signed matrix S ∈ R

m×n(i.e., a matrix consisting of -1, 0, and 1 entries,

which we will also refer to as the signed derivative), that captures the signs of thedominant entries of these derivative terms. We will shortly present several examples
of such matrices for a variety of different systems, but we first want to present theformal derivation and algorithm, as well as highlight the restrictions on these signed
derivative matrices that are needed for the theory.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

3.2.1

39

The Signed Derivative Approximation and Algorithm

As mentioned in the previous section, we begin the derivation of our algorithm byexpanding the policy gradient term in a manner that removes any dependence on themodel except via terms of the form (3.5). To do this, first note that for a sequenceof states and actions executed according to a policy (s0 , u0 = π(s0 ; θ), . . . , sH , uH =π(sH ; θ)) st depends on the parameters θ only through the inputs u0 , . . . , uH . Thus,
we can apply the chain rule to obtaint−1∂st X ∂st ∂π(st′ ; θ)
=
.
∂θ
∂ut′
∂θ
t′ =0

(3.7)

Repeating the derivation from the previous chapter for clarity, we can apply the chain
rule to write the policy gradient as
H∂J(s; θ) X ∂C(st , ut )
=
∂θ
∂θ
t=0


H
X
∂C(st , ut ) ∂st ∂C(st , ut ) ∂π(st ; θ) ∂st ∂C(st , ut ) ∂π(st ; θ)
=
+
+
∂st
∂θ
∂ut
∂st
∂θ
∂ut
∂θ
t=0

H 
X
∂st
≡
(qt + rt Kt )+ rt Φt
∂θ
t=0

(3.8)

where for ease of notation we use the definitions
qt ≡∂C(st , ut )∂C(st , ut )∂π(st ; θ)∂π(st ; θ), rt ≡, Kt ≡, Φt ≡
∂st
∂ut
∂st
∂θ

(3.9)

(note that because the cost function and policy are known analytically, we can comt
pute these terms analytically as well). Substitution our expansion of ∂s, (3.7), into∂θ(3.8), we obtain
H
t−1
X
∂st
∂J(s; θ) X=
Φt(qt + rt Kt )
∂θ
∂ut′
t=0
t′ =0

!

+ rt Φt!

.

(3.10)

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

40

Algorithm 1 Policy Gradient with Signed Derivative (PGSD)
Input:S ∈ Rn×m : signed derivative matrix
H ∈ Z+ : horizon
C : Rn × Rm → R: cost function
π : Rn × Rk → Rm : parametrized policyθ0 ∈ Rk : initial policy parametersα ∈ R+ : learning rate
Repeat until convergence:
1. Initialize policy gradient and feature sum: G ← 0, Ψt ← 0.
2. For t = 0, . . . H,
• Observe state st , take action ut = π(st ; θ).
• Update policy gradient G ← G + (qt + rt Kt )SΨt + rt Φt .
• Update feature sum Ψt+1 ← Ψt + Φt .
3. Update policy parameters: θ ← θ − αGT .

We now introduce the signed derivative approximation into this expression. As
mentioned previously, the signed derivative approximation replaces all derivatives of∂stthe form ∂uwith a single matrix S ∈ Rn×m , with 1, 0, and -1 entries, that captures′tthe dominant signs of these derivative terms. Thus, our approximation of the entire
policy gradient term becomes
H
^θ) X
∂J(s;
=
((qt + rt Kt )SΨt + rt Φt )∂θ
t=0where we define
Ψt ≡

t−1
X

Φt .

(3.11)(3.12)t′ =0

The final form of the policy gradient with signed derivative (PGSD) algorithm issimply to repeatedly compute approximations to the policy gradient using (3.11),
and use these to update the parameters θ. The full method is shown in Algorithm 1.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

3.2.2

41

The Signed Derivative Term

Before presenting theoretical analysis of the policy gradient with signed derivativealgorithm, we want to focus in greater detail on the signed derivative term itself.
In particular, we will discuss the validity of the assumption that we can reasonably
replace all the derivative terms with a single matrix representing their dominant signs,
and we discuss restrictions on this signed matrix term that manifest themselves in
the later analysis.
We begin by looking more thoroughly at the actual form of the model derivative∂st. For simplicity, we will use the notation
terms ∂u′t

Bt,t′ ≡

∂st∂ut′

(3.13)

as well as the definition of Kt above and the standard definitions from LQR-based
linearization as described in the previous sectionAt ≡∂f (st , ut )∂st+1
∂f (st , ut )∂st+1=
, Bt ≡
=
.
∂st
∂st
∂ut
∂ut

(3.14)

Once again applying the chain rule, we can derive the following recurrence relation
for the Bt,t′ matrices∂st∂f (st−1 , ut−1 )
=
′
∂ut
∂ut′
∂f (st−1 , ut−1 ) ∂st−1 ∂f (st−1 , ut−1 ) ∂ut−1 ∂st−1
+
=
∂st−1
∂ut′
∂ut−1
∂st−1 ∂ut′

Bt,t′ =

(3.15)= (At−1 + Bt−1 Kt−1 )Bt−1,t′t ,ut ). The matrix At−1 +Bt−1 Kt−1 corresponds to the linearizawith Bt+1,t = Bt = ∂f (s∂uttion of the closed loop system at time t − 1, and a common property of most practical
dynamical systems is that this term is close to the identity matrix.1 Of course, the1

To see this more formally , note that if the dynamics are based for example on a discretizationt ,ut )of the differential equation ṡ = g(s, u), then st+1 ≈ st + ∆tg(st , ut ), so At ≈ I + ∆t ∂g(s,∂stt ,ut )
, and thus if Kt is bounded the At + Bt Kt term will only differ from the identity
Bt ≈ ∆t ∂g(s∂utby O(∆t).

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

42“interesting” elements of the dynamics are precisely how this term differs from theidentity, but the fact that this matrix is close to the identity just corresponds tothe intuition that the state isn’t likely to change widely from one time step to thenext, assuming a relatively small time step. The above recurrence relation simply
establishes that this also holds for the Bt,t′ matrices, and so these terms are likely tochange relatively little between time steps.
Of course, just because the Bt,t′ matrices change little over relatively short time
periods, this does not imply that their signs do not change. In particular, it is very
possible that an element of Bt,′ t with low magnitude (relative to the other entries) may
change sign, as even a small deviation from the identity in At + Bt Kt could multiply
by one of the larger-magnitude entries of Bt,t′ and change the sign of a smallermagnitude entry. Thus, as alluded to previously, we actually stipulate that the S
matrix only capture the signs of the dominant entries of the Bt,t′ terms, while lowermagnitude entries are simply ignored by setting Sij = 0 for such variables. While
we are intentionally imprecise in terms of what we mean by the “dominant” entries,
for many domains it is apparent that some controls exert significantly less effect onsome states than on others. For car driving, for example, we expect the steering
wheel angle to have a large effect on the car’s orientation and lateral deviation fromthe trajectory, but less effect on the car’s velocity; of course, in practice the steering
wheel does affect velocity, but the magnitude of this dependence is much less, and so
we don’t represent it in the signed derivative matrix.
Finally, to highlight an additional point about the signed derivative matrices, wenote that in the formal analysis to follow, we will assume that the true derivative
terms Bt,t′ can be expressed in terms of the signed derivative as
Bt,t′ = Dt (S + Et,t′ )(3.16)

where S is the signed derivative, Dt is a positive diagonal matrix, and Et,t′ is anadditional error term. Note how this captures the notion of sign-correctness: theentries of S do not need to have the correct magnitude, because they can be re-scaledby the Dt matrix; but they do need to have the correct sign, because the diagonalCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

43

matrix Dt has only positive entries, and thus the signs of Bt,t′ (ignoring the errorterm) will be the same as the signs of S. Finally, this error term Et,′ t accounts for thefact, mentioned above, that the smaller-magnitude entries of the derivative terms are
ignored in the signed derivative, and so this term accounts for the fact that Bt,t′ willcontain additional, smaller entries that are not captured by the Dt S term; however,
we will assume that this matrix has relatively small magnitude.
The above expression also highlights an important limitation to the signed derivative, at least as it applies to the theoretical guarantees that we will make about themethod. Because we are pre-multiplying S by a diagonal matrix, we can re-scale therows of S arbitrarily, but we cannot re-scale the columns of S. Thus, if we have morethan one non-zero entry per row of S (i.e., two controls that affect the same futurestate variable), these entries need to have the correct relative magnitudes, and wewould thus need to include fractional entries in the signed derivative unless the twocontrols had the same effect on the future state. Fortunately, a common propertyof many control domains is that each state is primarily affected by only one of thecontrol inputs, and thus we do not need to worry about this issue. Returning one lasttime to the car driving example, we note that lateral deviation and car orientation are
primarily affected by the steering wheel angle, while velocity is primarily controlled
by the throttle. In contrast, imagine trying to drive a car where both the steering
wheel and throttle controlled some different combinations of the car’s orientation andvelocity; while such a control system is technically “equivalent” to a standard car, it
would take much more work to learn. This suggests, at least anecdotally, that humans
also exploit these orthogonal control effects, and so we can expect many control tasks
to be designed in this way. We also note that while the theory below does require
the assumption (3.16), the algorithm could still be applied to situations with morethan one non-zero entry per row in the signed derivative, though the performance oranalysis in this case remains an open question.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

3.3

44

Theoretical Analysis

Before presenting a theoretical analysis of situations where the PGSD algorithm isguaranteed to perform well, we begin by demonstrating why the algorithm may not
perform like typical sign-based gradient optimization techniques. In particular, weconsider the exact form of the policy gradient (3.10), and consider what would happen∂st
if we replaced the ∂uterms with their true sign
′
t



H
t−1
^θ) X
X
∂st
∂J(s;
Φt′
=
(qt + rt Kt )
sign
′
∂θ
∂u
t
′
t=0
t =0

!

+ rt Φt!

.

(3.17)It should be apparent that the signs of this term are not guaranteed to be the sameas the signs of the true gradient ∂J(s;θ), since it is certainly possible that
∂θ
sign

X
i

xi

!

6= signXi!

sign(xi ) .

(3.18)

Thus, there are two potential sources of error for the signed derivative policy gradientapproximation: the error in approximating all the derivative sign terms with a single
matrix S, and the error introduced by putting the sign terms within a summation in
the gradient.
Despite these potential sources of error, there is a informal sense in which we might
still expect the method to perform well: when the dominant derivative terms do keep
consistent signs over a trajectory (as we argued that they would above), replacing
the inner terms with their sign still can capture the general descent directions for thefunction. Indeed, while the standard practice in sign-based optimization is to takethe sign of the final gradient terms, some algorithms do take signs of intermediate
terms, and these can perform well in practice even if they lack the guarantees of thestandard approaches (Anderson, 1986).
Of course, this informal justification alone is not particularly satisfying, and soin the remainder of this section we develop guarantees showing that under certain

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

45

assumptions the PGSD algorithm will perform nearly as well as updating the parameters with the true policy gradient. However, the assumptions needed to makesuch guarantees are indeed rather strong, so we do want to allude to the preceding
informal argument as an additional intuitive justification for the approach.

3.3.1

Overview of the Theoretical Results

In this section we present the basic intuition of our theoretical results. Because theresults deal with the convergence properties of the algorithm, and since convergenceproperties of any policy gradient method depend on the structure (e.g. convexity
properties) of the cost function itself (a non-convex cost function could imply an
unbounded value function, for instance), we assume for the sake of these results thatthe cost function is quadratic, i.e.,C(s, u) = sT Qs + uT Ru.

(3.19)The theory extends without modification to trajectory-dependent cost functions
Ct (s, u) = (s − s⋆t )T Q(s − s⋆t ) + (u − u⋆t )T R(u − u⋆t ),(3.20)

and for general convex cost functions the analysis below extends to the second-order
quadratic expansion of these functions. Note that given these definitions, the qt andrt terms take the form
qt = sTt Q, rt = uTt R.

(3.21)The basic intuition of the theoretical proof is as follows. Suppose that the true
matrix derivative terms Bt,t′ obey the condition described previously, that Bt,t′ =Dt (S + Et,t′ ) for all t′ , with kEt,t′ k ≤ ǫ. Then the gradient given by the signed

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

46

derivative approximation is
H
^θ) X
∂J(s;
=
((qt + rt Kt )SΨt + rt Φt )
∂θ
t=0

=

H
X
t=0

=

H
X

t−1
X
T
T
(st Q + ut RKt )(Dt−1 Bt,t′ − Et,t′ )Φtt′ =0(sTt QDt−1 + uTt RKt Dt−1 )

t=0

t−1
X
t′ =0

Bt,t′ Ψt!

!

+ uTt RΦt

+ uTt RΦt!

!

(3.22)+ O(ǫ).

This term looks almost like true policy gradient (with an added O(ǫ) term), except
for the presence of the Dt−1 terms, which can render the approximation not even adescent direction of the true value function. However, if for all t we can find a Q̃t  0
and R̃t  0 such thatsTt Q̃t = sTt QDt−1 ,and uTt R̃t Kt = uTt RKt Dt−1

(3.23)

then the approximate gradient given by the signed derivative at this point is equal(up to the O(ǫ) term) to the true policy gradient for a different cost function, givenby the Q̃t and R̃t matrices. Classical results (Khatri and Mitra, 1976) show that
positive semidefinite Q̃t and R̃t matrices exist that satisfy these equalities if and only
if2
sTt QDt−1 st ≥ 0,

and uTt RKt Dt−1 K † u ≥ 0.

(3.24)

While these conditions often hold in practice, it is difficult to guarantee them a priori,and it is also difficult to bound the differences between the solutions Q̃t and R̃t and
Q and R. Thus, while this overall procedure provides additional insight into why thealgorithm may perform well, for the precise results below we will make substantiallymore restrictive assumptions, and assume that Q is diagonal and that R is zero (i.e.,the cost function depends only on the state, though we can introduce constraints on
the controls by restricting the allowable controls or regularizing the policy parameters
θ directly). While these may seem to be large restrictions, in practice we almost
2

Here the † symbol denotes the Moore-Penrose pseudoinverse.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

47

always choose Q to be diagonal anyway (populating a full cost matrix Q can be quite
unintuitive), and restrictions on controls by directly penalizing parameters or control
magnitudes are often actually more intuitive than quadratic cost penalties. When Q
is diagonal and R = 0, the above approximate policy gradient takes the much simpler
form

H
^θ) X
∂J(s;
=
sTt Q̃t
∂θ
t=0

t−1
X
t′ =0

Bt,t′ Ψt!

+ O(ǫ)(3.25)

where Q̃t ≡ QDt−1 is naturally also diagonal and positive definite. Thus, the approximate gradient given by the signed derivative is indeed approximating the gradientof a different cost function. Therefore, we expect the procedure to converge to anear local optimum of the value function with this modified cost function, and theonly remaining issue to discuss is how this relates to the policy’s performance on theoriginal (true) cost function.
To understand why optimizing a modified cost function with cost matrix Q̃t =QDt−1 can still lead to a policy that performs well on the original cost function, we canconsider the extreme case where the policy class is chosen such that we can actuallyfind a policy that achieves zero total cost. In this case, it doesn’t matter how we scale
the cost function, since minimizing any quadratic function (globally) will also achieve
zero cost. The reason why the different cost matrices come into play is that often times
we cannot achieve zero cost (i.e., we are restricted by virtue of the system dynamics toa certain subset of allowable state action pairs, and the global optimum is not within
this set) and so the contours of the cost function determine which suboptimal points
look best. This same intuition holds when the policy class can obtain a controller
with merely near-zero cost: in this case, optimizing the modified cost function also
results in a policy with near-zero cost, with an additional scaling factor that may be
as large as κ(diag(D1 , . . . , DH )), the condition number of a diagonal matrix formed
from all the diagonal scaling matrix3 . In other words, (given all the assumptions
above) if we choose a policy class such that true policy gradient could achieve low
cost, and if the control inputs are reasonably well scaled, then we expect the PGSD
3

The conditional number of matrix A is defined as the ratio between the smallest and lowest
singular valueσmax (A)/σmin (A).

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

48

algorithm to perform well.

3.3.2

Formal Results

The following theorem formalizes the intuition we described in the previous section.
For the purposes of the proof, we assume that the dynamics are deterministic andthat the initial state s0 is fixed, and does not depend on the policy (this would be
the case, for instance, if the control task was episodic, and the system was reset to an
initial state before each trial). Although the assumption of deterministic dynamics
may seem quite restrictive, this is mainly done so that we can work with the simpler
notation of deterministic gradient descent methods, rather than stochastic gradientdescent methods, which would be required for stochastic settings. The results can beextended to the stochastic setting, as originally published in Kolter and Ng (2009a),
but the extension requires a great deal of additional machinery, and adds little to theactual intuition of the approach.
The theorem statement to follow requires a number of technical assumptions,which we list here.
Assumption 1. As described above, the true gradients of the system dynamics are
related to the signed derivative by
Bt,t′ = Dt (S + Et,t′ ), kEt,t′ k ≤ ǫ.

(3.26)

Assumption 2. The dynamics function f : Rn × Rm → R is deterministic, and theinitial state s0 is fixed and independent of the policy π.
Assumption 3. The modified value function˜ θ) = E
J(s;

" H
X
t=0

sTt Qt Dt−1 st s0 = s, π(·; θ)#(3.27)

has a Lipschitz continuous gradient4 with Lipschitz constant K (this property will
4

A function f has Lipschitz continuous gradient, with Lipschitz constant K, if k∇f (x1 ) −∇f (x2 )k ≤ Kkx1 − x2 k for all x in the domain of f .

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

49

hold, for example, if the dynamics and policy also have Lipschitz continuous gradientsby the fact that compositions of Lipschitz continuous functions are also Lipschitz
continuous). Furthermore, the gradient step size α satisfies
0<α<

2
.
9K

(3.28)

Given these assumptions, we now present the main theorem.
Theorem 1. Under the assumptions above, the PGSD algorithm will converge tosome region that is close to a local optimum of the modified value function (3.27),i.e.,˜ θ)k ≤ O(ǫ).
k∇θ J(s,(3.29)

Furthermore, if (global) optimization of the true value function would result in ηoptimal policy parameters — i.e., J(θ⋆ ) ≤ η — then (global) optimization of the
PGSD objective will result in a solution θ̃ that is an order η-optimal solutionJ(θ̃) ≤ κ(D)η.

(3.30)

where κ(D) denotes the condition number of the diagonal matrix
D = diag(D1 , D2 , . . . , DT ).

(3.31)

Before turning to the proof of the theorem, we want to address one element in its
statement that may seem odd. In particular, the theorem first states that the PGSD
algorithm converges to a near local optimum of a modified cost function, then claims
that under suitable conditions a global optimum of this modified cost function will
be close to the global optimum of the true value function. Since both the modified
and true value functions are non-convex, we don’t expect to be able to find global
optima of either of these functions in general. However, the theorem merely showsthe expected behavior that optimizing one function also tends to minimize the other:
the same fact would hold for a local optimum of the value functions if we additionallyassume that both gradient procedures (gradient descent on the true value function

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

50

versus the modified value function) were restricted to the same convex region, butsince non-convexity could cause the two gradient descent procedure to converge todifferent convex regions the above is the strongest statement we can make without
additional assumptions.
Our proof uses two lemmas (proved in the next section) regarding the convergenceand solutions of optimization procedures. Recall from the discussion above that undersuitable assumptions, the signed derivative approximate gradient is equal to a gradient of a different function, plus a bounded error term. The following lemma showsthat optimizing a function using gradient descent plus an error term converges to an
approximate (local) optimum. This is a fairly intuitive result, and for simplicity wefocus here on minimizing a deterministic function with Lipschitz continuous gradient.
The result is a straightforward extension of well-known results for the minimization offunction with Lipschitz continuous derivatives (Armijo, 1966). The result generalizes
to more complex situations, such as stochastic gradient descent methods or different
rules for stepsize selection, but these convergence results require much more machinery and assumptions, and don’t add significantly to the actual intuition of the PGSD
algorithm.
Lemma 2. Suppose f : Rn → R is bounded below and has Lipschitz continuous
derivative with Lipschitz constant K, and we employ the approximate gradient descentprocedurext+1 ← xt − αgt ,kgt − ∇f (xt )k ≤ ǫ.

(3.32)

2
Then for constant step size 0 < α < 9L
, as t → ∞, xt converges to a region wherek∇f (xt )k ≤ 2ǫ.

(3.33)The second lemma is a general statement about the optimization of quadratic
functions. Namely, it states that if we globally optimize some positive semidefinite
quadratic function f1 (x) = xT Q1 x over an arbitrary (possibly non-convex) set C, thenthe solution will also be close to the globally optimal solution of another positive
semidefinite quadratic function f2 = xT Q2 x over the same set. The difference in thesolutions depends on how close to the solution is to the zero point, and a ratio of

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

51

certain eigenvalue terms. This captures the following intuition. Since the zero pointx = 0 is the globally optimal unconstrained minimum for both functions, if 0 ∈ C,
then the solutions will coincide. If 0 6∈ C, however, then the global optimum of f1 overC can differ from the globally optimal solution to f2 , but this difference is boundedby 1) how close the optimal point is to the zero point, and 2) a particular ratio of theeigenvalues of the two quadratic forms.
Lemma 3. Consider two positive definite quadratic functions f1 , f2 : Rn → R, definedbyf1 (x) = xT P1 x, f2 (x) = xT P2 x, P1 , P2  0.

(3.34)Let C ⊆ Rn be some arbitrary (and possibly non-convex) subset of Rn , and consider
the solutions of the global optimization problemsx⋆1 = arg min f1 (x), x⋆2 = arg min f2 (x).
x∈C

x∈C

(3.35)

Then

λmax (P1−1 P2 )f1 (x⋆1 ).
−1
λmin (P1 P2 )Given these two lemmas, the proof of Theorem 1 is straightforward.
f1 (x⋆2 ) ≤(3.36)

Proof. (of Theorem 1). First note that from (3.22),
!
H
t−1
^
X
X
∂J(s; θ)=sTt Q
(Dt−1 Bt,t′ − Et,t′ ) Φt
∂θ
t=0
t′ =0
!
!
H
t−1
t−1
H
X
X
X
X
=
sTt QDt−1
Bt,t′ Φt −Et,t′ Φt
sTt Q
t=0

t′ =0
H
X

˜ θ)
∂ J(s,+
kst kkQk
≤
∂θ
t=0

≤

˜ θ)
∂ J(s,+ K1 ǫ
∂θ

t=0

t−1
X
t′ =0

t′ =0

(3.37)!

kEt,t′ k kΦt kwhere we bound the second term using the sub-multiplicative property of matrix
norms and by repeated application of the triangle inequality. Thus, given the assumptions above, PGSD satisfies the conditions of Lemma 2, and we can guaranteeCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

52

that it converges near to a local optimum, as desired.
The second claim of the theorem follows directly from Lemma 3, by noting thatthe true and modified cost function are quadratic in the states with respective cost
matrices
Q = diag(Q, . . . , Q) (T times) ,Q̃ = diag(Q̃1 , . . . Q̃T ).

(3.38)

Thus, applying Lemma 3 we have that optimizing the modified cost function leads tosome factor times the optimal solution for the true cost function, where the factor isgiven byλmax (Q−1 Q̃)λmax (D−1 )λmax (Q̃Q−1 )= κ(D)==
λmin (D−1 )λmin (Q−1 Q̃)λmin (Q̃Q−1 )(3.39)

as desired, where we can exchange the order of multiplication because both Q and Q̃
are diagonal.

3.3.3

Proofs of Technical Lemmas

Proof. (of Lemma 2) By the mean value theorem,
f (xt+1 ) − f (xt ) = (xt+1 − xt )T ∇f (x̃t )(3.40)

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

53

for some x̃t on the line segment connecting xt and xt+1 . Since under our assumptions,
xt+1 − xt = −α(∇f (xt ) + e) with kek ≤ ǫ,
f (xt+1 ) − f (xt ) = −α(∇f (xt ) + e)T ∇f (x̃t )= −α(∇f (xt ) + e)T (∇f (xt ) − ∇f (xt ) + ∇f (x̃t ))= −α(∇f (xt ) + e)T ∇f (xt ) + −α(∇f (xt ) + e)T (∇f (x̃t ) − ∇f (xt ))≤ −αk∇f (xt )k2 + αkekk∇f (xt )k + αk∇f (xt ) + ekk∇f (x̃t ) − ∇f (xt )k≤ −αk∇f (xt )k2 + αkekk∇f (xt )k + αk∇f (xt ) + ekKkx̃t − xt k
≤ −αk∇f (xt )k2 + αkekk∇f (xt )k + αk∇f (xt ) + ekKkxt+1 − xt k
≤ −αk∇f (xt )k2 + αkekk∇f (xt )k + αk∇f (xt ) + ekαKk∇f (xt ) + ek
= −αk∇f (xt )k2 + αkekk∇f (xt )k + α2 Kk∇f (xt ) + ek2= −(α − α2 K)k∇f (xt )k2 + (α + 2α2 K)k∇f (xt )kkek + α2 Kkek2≤ −(α − α2 K)k∇f (xt )k2 + (α + 2α2 K)k∇f (xt )kǫ + α2 Kǫ2 .
(3.41)
Now suppose k∇f (xt )k ≥ 2ǫ. Then
α + 2α2 K
α2 K
f (xt+1 ) − f (xt ) ≤ −(α − α2 K)k∇f (xt )k2 +k∇f (xt )k2 +k∇f (xt )k2
2
4


9K 2
−1
=
α+
α k∇f (xt )k2 .
2
4(3.42)
Since for α > 0,

9K 2
2
−1
α+
α < 0 ⇐⇒ α <2
4
9K(3.43)

2then by our assumption that 0 < α < 9K
, at each iteration of gradient descent wehavef (xt+1 ) ≤ f (xt ) − δk∇f (xt )k2(3.44)

for some δ > 0 independent of xt . Thus, for k∇f (xt )k ≥ 2ǫ, the objective function
must decrease by at least 4δǫ2 at each iteration. Since the function f is bounded
below, this can only happen a finite number of times, implying that as t → ∞, xt

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

54

must converge to a region where k∇f (xt )k ≤ 2ǫ.
Proof. (of Lemma 3) Consider the set C0 = {x : x ∈ C, f2 (x) ≤ f2 (x⋆1 )}. Clearly x⋆2
is a member of this set, so we therefore havef1 (x⋆2 ) ≤ max f1 (x) ≤x∈C0max ⋆ f1 (x) ≡f2 (x)≤f2 (x1 )max

xT P2 x≤f2 (x⋆1 )xT P1 x.

(3.45)

By a standard variational formulation of the generalized eigenvalue problem ?, thisterm can be bounded asmax

xT P2 x≤f2 (x⋆1 )xT P1 x ≤ λmax (P2−1 P1 )f2 (x⋆1 ).

(3.46)

Dividing the previous equations by f1 (x⋆1 ) and again applying the variational formulation of the generalized eigenvalue problem
f1 (x⋆2 )f2 (x⋆1 )
−1
≤
λ
(P
P
)
max
1
2
f1 (x⋆1 )
f1 (x⋆1 )xT P2 x−1
≤ λmax (P2 P1 ) max T
x x P1 x(3.47)≤ λmax (P2−1 P1 )λmax (P1−1 P2 ).
Since λmax (A−1 ) = 1/λmin (A), the lemma follows.

3.4

Experimental Results

3.4.1

Simulated Two-Link Arm

While we will present experiments on real systems shortly, we begin our experimental
analysis by presenting an evaluation of our proposed method on a simulated two-link
arm, in order to rigorously compare to previous policy gradient approaches, and toprovide a readily available implementation of our approach. Code for the all the
results in this section is available at http://cs.stanford.edu/~kolter/rss09sd.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

55

We emphasize that the purpose of this section is to specifically compare PGSD withother policy gradient approaches: the control task itself is fairly straightforward, andmany other approaches such as adaptive control or iterative learning control could
also be applied, though this is beyond the scope of this work.
The two-link pendulum is a well-known control task in robotics and control. The
system, shown in Figure 3.1 consists of two planar links; the state consists of the joint
angles and velocities of both joints and the control specifies a torque at each of thejoints


q1





 q2 
st = 
 q̇  ,
 1 
q̇2

ut =

"

τ1
τ2

#

(3.48)The equations of motion can be easily derived from Lagrangian dynamics, and we
introduce stochasticity to the system by adding Gaussian noise to the torques before
integrating the equations of motion. The task we consider here, also shown in the
figure, is to move the end effector along some desired trajectory. When the model ofthe system is known, it is fairly easy to apply classical control methodologies suchas inverse dynamics or LQR to find an optimal controller, but of course we don’t
provide this model to PGSD or other comparable algorithms. We feel that this isa particularly demonstrative example for the Signed Derivative algorithm, since itis well-known that there are cross terms that cause all joints to be affected by all
the control inputs — for instance, a common (more challenging) task is to swing
the pendulum upright and balance by applying torques only to the elbow — yet
we claim that the Signed Derivative approximation is still reasonable, since joints
are primarily affected by their own control. In particular, since we reason that eachtorque primarily affects both the joint angle and joint velocity of that state, the signed

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

56

1

0.8

0.6

0.4

0.2

0

−0.2

−0.4

−0.6

−0.8

−1

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

Figure 3.1: Two-link pendulum trajectory following task.
derivative matrix for this task is given by


1 0





 0 1 S=
 1 0 .


0 1

(3.49)

The cost function for this domain penalizes deviations from the desired joint angles⋆ 2⋆ 2
Ct (s, u) = (q1 − q1,t
) + (q2 − q2,t)(3.50)(we transform the trajectory to joint space via inverse kinematics), and we use a time
horizon of H = 5. Note that this doesn’t mean that the controller only needs tofollow the trajectory for 5 steps, but rather that at each time the controller should
ideally act optimally with respect to a receding horizon of H = 5; since the costfunction itself “guides” the arm along the trajectory, such a horizon is suitable. We
use a linear control policy ut = θT φ(st , t) where φ(st , t) ∈ R7 contains:⋆
1. Deviations from desired joint angles, q1,2 − q1,2⋆
2. Deviations from desired joint velocities, q̇1,2 − q̇1,2

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

0.16

57

PGSD
REINFORCE (w/ resets)
REINFORCE

0.14
0.12

Cost

0.1
0.08
0.06
0.04
0.02
0
0

2000

4000

6000

8000

10000

Timestep

Figure 3.2: Average cost versus time for different policy gradient methods. Costs areaveraged over 20 runs, and shown with 95% confidence intervals.
⋆
3. Desired joint accelerations q̈1,2

4. A term equal to sin(2πt/ttotal ) where ttotal is total time for the complete trajectory (this was added to account for a visible periodic pattern in the controls).
This leads to a total of 14 parameters for the policy (7 for each different control
input). For algorithms that require a stochastic policy, we added Gaussian noise to
the parameters: ut = (θ + ǫt )T φ(st , t), (ǫt )ij ∼ N (0, σ).
Figure 3.2 compares the performance versus time of PGSD, and a well-known policy gradient RL algorithm, the REINFORCE algorithm.5 All free parameters of thelearning algorithms (gradient step sizes, policy noise, number of episodes) were handoptimized to give that fastest convergence that didn’t cause any divergence issues. As
the figure shows, PGSD drastically outperform the other methods, converging much
faster to a low-cost policy. This improvement is especially notable given that the REINFORCE algorithm is actually given an advantage: since the task we’re considering5

We intentionally scaled the parameters of this control task to be the same order of magnitude,
so more advanced techniques such as natural gradients(Kakade, 2001; Peters and Schaal, 2006)
didn’t improve performance significantly. In preliminary experiments we also evaluated a variety offinite difference and weight perturbation methods, but didn’t notice a substantial improvement over
REINFORCE for this task.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

1.5

58

Desired Position
Initial PD Controller

1

y

0.5
0
-0.5
-1
-1

-0.5

0

0.5

1

x

Figure 3.3: Trajectories from initial controller.
is not episodic (at least not at the time-scale of the horizon), episodic algorithms
don’t immediately apply, and so we instead allow the algorithm the ability to reset
to previous states observed along the trajectory. The REINFORCE without resets inthe figure does not have such an advantage, but also performs much worse. Figures
3.3 and 3.4 show trajectory achieved by the initial controller (used to initialize all thelearning algorithms), and the controller learned by the PGSD algorithm after 2000
time steps (4 times through the trajectory).
We also compare, in Figure 3.5, the performance of the PGSD algorithm, policy
gradient using the true gradient from the model, and an optimal LQR controller.
Not surprisingly, the LQR controller performs best: this controller is built by linearizing around the (known) dynamics at each operating point, then computing aseries of non-stationary policies for each point (in total, the LQR controller has 9000
parameters). However, using only 14 parameters, the true policy gradient and PGSD
algorithm are able to obtain a controller that performs relatively close to this full
LQR controller. Furthermore, the most important result is that the learning curvefor PGSD is virtually indistinguishable from the true policy gradient learning curve;
despite the rather crude approximation made by the signed derivative, this resulting
algorithm performs just as well on this task, and requires no model of the system

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

1.5

59

Desired Position
PGSD Policy

1

y

0.5
0
-0.5
-1
-1

-0.5

0

0.5

1

x

Figure 3.4: Trajectories from controller learned using PGSD.
0.1

True Gradient (from model)
Optimal LQR controller
PGSD

0.08

Cost

0.06
0.04
0.02
0
0

400

800

1200

1600

2000

Timestep

Figure 3.5: Average cost versus time for PGSD versus model-based methods. Costs
are averaged over 20 runs, and shown with 95% confidence intervals.
(and therefore also less computation time, since there is no need for time-consuming
finite difference computations).

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

60

Figure 3.6: RC car used for the driving experiments.

3.4.2

Autonomous RC Driving

In this section we apply the PGSD algorithm to the task of learning to drive anautonomous RC car along a desired trajectory. Figure 3.6 shows the car, a Tamiya
TRF415, which is about 40cm long and 20cm wide. A pattern of LED lights is attached to the car, and tracked by an external PhaseSpace motion capture system forpose estimation. All processing is done on a workstation PC, with controls transmitted to the car at 50hz.
The simplest representation of the car’s state is as six dimensional vector representing the 2D position x, y, the orientation θ, and the time derivatives ẋ, ẏ, θ̇. However,a more natural representation for the signed derivative approach is to represent the
car’s state relative to some desired trajectory — here the trajectory is specified as acontinuous spline that gives the desired state as a function of time. In this alternate
representation, the state consists of the longitudinal, lateral, and angular deviation(and their derivatives) from the desired trajectory. The control is two dimensional,
consisting of a commanded throttle and steering angle. Thus, the signed derivativeCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

2

61

Desired Position
Initial PD Controller

1.5

y

1
0.5
0
-0.5
-1
-2

-1.5

-1

-0.5

0
x

0.5

1

1.5

2

Figure 3.7: Desired trajectory for the autonomous RC driving experiments, withtrajectory for initial controller.
is a 6 × 2 matrix, given by


1

 0


 0
S=
 1


 0

0

0




1 


1 

0 


1 

1

(3.51)We use the same form of linear controller as in the previous sections, but whereφ(s, t) now contains 1) the full state (represented as the deviation terms), 3) thedesired velocities, relative to the car frame, 3) the deviations for a target state 0.5
seconds in the future and 4) a constant term. Some of the θ parameters are forced to
be zero (so that, for instance, the throttle doesn’t depend on the lateral deviation),
for a total of 16 parameters in the policy. The cost function penalizes the longitudinal, lateral, and angular deviation, any control outside a specified valid range, andcontrol that changes more that some amount between two time steps (to minimize
oscillations). We used a time horizon of H = 25.
Figures 3.7 and 3.8 show the control task we consider: driving the car in an

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

2

62

Desired Position
PGSD Policy

1.5

y

1
0.5
0
-0.5
-1
-2

-1.5

-1

-0.5

0
x

0.5

1

1.5

2

Figure 3.8: Desired trajectory for the autonomous RC driving experiments, withtypical trajectory learned using PGSD after approximately 20 seconds of learning.
0.5

PGSD

0.4

Cost

0.3
0.2
0.1
0
0

10

20

30

40

50

60

Time (seconds)

Figure 3.9: Average cost versus time for the PGSD algorithm on the RC car task.
Costs are averaged over 10 runs, and shown with 95% confidence intervals.
irregular figure-eight pattern at varying speeds (2.0 m/s along the larger loop, 1.5 m/salong the smaller loop). The figure also shows the trajectory followed by an initial
controller: while the initial controller follows the overall pattern of the trajectory, it
clearly does not perform very well. Figure 3.9 shows the learning curve of the PGSD
algorithm. As the figure shows, PGSD is able to very quickly — within an averageof 20 seconds, about 3 times around the trajectory — obtain a policy that performs
far better than the initial controller. We show a typical trajectory from one of theseCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

63

Figure 3.10: The desired task for the LittleDog: climb over three large steps.
learned controllers in Figure 3.8. The learned policies do not perform flawlessly —the car still sometimes veers off the desired path — but we feel this is largely due
to the limited policy class itself; to perform better, one might need more complex,
time-varying policies, to capture the fact that the car needs to behave differently at
different points along the path. Nonetheless, PGSD converges to a very reasonable
policy — in fact, better than any we were able to hand tune in the same policy class— in just 20 seconds of learning.

3.4.3

LittleDog Jumping

In this section we present results on applying PGSD to the task of “jumping” thefront legs of a quadruped robot up a large step, as shown in Figure 3.10 The LittleDog
robot, which we use for this task, will be described in much more detail in Chapter
6, but here we briefly describe the jumping task and the challenges involved.
The goal of the front leg jump maneuver is to quickly and simultaneously lift
both front legs onto a step or over a gap. “Jumping” is perhaps a misnomer for theaction, since the robot does not actually have the power to force its front legs off theground from a typical standing position. Rather, the strategy we employ is to shift
the robot’s center of gravity (COG) backwards until the front legs become unloaded

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

64

Figure 3.11: Overview of the front jump maneuver.
and the robot is falling backwards. At this point, we quickly shift the COG forward
again, and raise the front legs. If the maneuver executes as planned, then this willlift the front legs off the ground, and move them simultaneously to a new location by
the time the robot falls forward, as shown in Figure 3.11. A mosaic of the real robot
performing a jump is shown in Figure 3.12.
Due to the nature of the LittleDog, this is a delicate maneuver: shifting the COG
not far enough or too far can either fail to unload the robot’s front legs or cause therobot to flip backward, respectively. Because this is an extremely fast transition, we
have been unable to develop a typical stabilizing controller: by the time we receive
the necessary sensory data from the robot, it would have already entered into oneof these failure modes, and lacks the control authority to recover. Furthermore, theCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

65

Figure 3.12: A properly executed jump.
correct amount to shift the COG depends on very small changes to the initial stateof the robot. While ensuring a successful jump could be done via precise modelingof the robot, or a “calibration” procedure that would put the robot into a known
state (such strategies were employed in (Byl et al., 2008) to achieve a similar jump),
our goal was to develop a single policy that could execute such a jump immediatelyfrom a variety of different initial states. To accomplish this task, we parametrize thejumping maneuver as a function of features of the robot’s initial state, and apply
the PGSD algorithm to learn a policy for shifting the robot’s COG based upon thesefeatures.
Although the full state space for the LittleDog is 36 dimensional, we don’t need totake into account the complete state. Rather, we have found through experimentationthat the correct amount to shift the COG backwards depends mainly on five features,
so the policy we employ determines the amount to shift back as linear function of: 1)
the current shift of the COG, 2) the forward velocity of the dog and 3) the initial pitchof the dog, 4) the rotational velocity around the pitch axis, and 5) a constant term;
intuitively, these feature provide a natural description of the robot’s longitudinalstate, and thus are the primary elements relevant for jumping forward. Since there
is only one control input (how far back to shift) and one state that is relevant to theCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

66

success of the jump (the resulting pitch of the robot), the signed derivative in thiscase is just the singleton matrix S = 1, indicating that shifting the robot further backmakes it pitch more.
Recall that the success or failure of the jump can be quantified by how much therobot pitches. Letting β ⋆ denote the “optimal” pitch angle of the jump letting β
denote the amount that the robot did pitch. We use the cost function that depends
on the absolute error between the desired and actual pitch,
C(s) = |β − β ⋆ |,(3.52)

so that ∂C(s)= 1 if β > β ⋆ and ∂C(s)= −1 if β < β ⋆ — i.e., the gradient is just the∂s∂sdirection in which we should adjust our control. When H = 1, the PGSD updatethen takes on the very simple form: θ − αφ(s)θ←θ θ + αφ(s)robot didn’t clear step
jump succeeded(3.53)

robot flipped backwards

Despite the simplicity of this update rule, it works remarkably well in practice.
We evaluated this PGSD variant on the LittleDog robot, attempting to climb thethree steps as shown in Figure 3.10. After 28 failures (either flipping backwards or
failing to clear the step), the robot successfully jumped all three steps for the firsttime. After 59 failures, the learning process had converged on a sufficiently accurate
maneuver: the robot succeeded in immediately climbing all three steps for 13 out of
the next 20 trials (and failures mostly involved failing to clear the step, where therobot would then retry the jump and typically succeed). This is far better than any
policy we had been able to code by hand. A video of the learning process on the dog
is available at http://ai.stanford.edu/~kolter/ijrr09ld/.

CHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

3.5

67

Summary

In this chapter, we have presented the policy gradient with signed derivative (PGSD)
method, an approximate policy gradient algorithm that can be used to optimize apolicy’s performance without an accurate model of the system. The algorithm exploits
the fact that in many control tasks, the sign of certain model derivative terms (relating
how control inputs affect future states) are obvious, and many control tasks further
have the structure that each state is primarily affected by only one control. In suchsettings, we have shown, both theoretically and empirically, that the PGSD algorithm
can achieve very good performance. In particular, we evaluated the algorithm and anumber of other policy gradient approaches (including those which have knowledgeof the true model) on a two-link arm benchmark task, and demonstrated that on
this task the PGSD algorithm greatly improves upon model free approaches andindeed performs as well as a policy gradient algorithm that is given the true model ofthe system. We additionally demonstrated the approach on two real-world domains:driving an RC car along a fixed route, and the challenging task of learning to jump
up stairs with a quadruped robot.
While the PGSD algorithm can perform well on many domains, we emphasize thatthe algorithm is not applicable to all tasks. In particular, the algorithm exploits thefact that certain derivative signs are obvious (and fixed over time). While this is thecase for many control tasks, there are also many domains where this is not the case.
For instance, consider the two-link arm example considered in the chapter, but where
only the second joint is actuated; this is the well-known “acrobot” domain, a task
studied a great deal in Reinforcement Learning (Sutton and Barto, 1998). While thisdomain can still be controlled, the control input (torque applied to the second joint),
no longer affects all the states in an “obvious” manner; in particular, the control input
affects the first joint in a manner that depends on the other states of the system, andthe sign of this relationship actually changes in different parts of the state space. Thus,
the PGSD algorithm would not be applicable to such a domain. Furthermore, there
are many domains where state variables are largely affected by more than one control.
While we mentioned briefly that the PGSD algorithm could potentially be applied toCHAPTER 3. POLICY GRADIENT VIA THE SIGNED DERIVATIVE

68

such domains, the, both our theoretical and empirical analysis in this chapter does
focus on the situation where this constraint holds. Thus, further analysis would beneeded before we could make any performance claims about the PGSD algorithm indomains where this “orthogonality” of the control inputs does not hold.

Chapter 4
Dimensionality Reduction in Policy
SearchIn the previous chapter we explored how we can use inaccurate models within apolicy search setting. However, we did not previously consider the actual size of theparameter vector θ, and in general a policy with many parameters is significantly
harder to learn on real systems, regardless of the method we use, due to noise and theamount of data needed to accurately learn a large number of parameters; just running
enough trajectories to gather sufficient data for this task is often impractical on thereal system. In contrast, learning such high-dimensional policies is often possible ina model of the system (where there is potentially less noise, and we can simulate asmuch data as we would like), but here the inaccuracy of model is again a problem:
because we would now use the model to actually simulate trajectories in the system,
we need the model to be accurate in a predictive sense.
The main idea that we present in this chapter is to use an inaccurate model
to identify a low-dimensional subspace of policy parameters, which can effectively
decrease the number of parameters we need to learn on the real system. The intuitionis that by considering a large set of different inaccurate models, we can identify asubspace of policy parameters that perform well in all these models, and then search
only within this smaller subspace on the real system (which then typically requires
less data).
69

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

70

The question remains as to how we generate these several different inaccurate
models for use in the dimensionality reduction task. In practice, dynamics models
are typically themselves parameterized by many different free parameters, which wewill denote ψ to distinguish from the policy parameters θ; these could be, for example,
mass parameters of the physical bodies, friction parameters, torque magnitudes, etc.
Thus, a natural way to generate a large number of inaccurate models is to consider
a distribution over these parameters and sample from the distribution to generatesome number of different inaccurate models. Furthermore, if the model of the true
system is known to a certain degree, but has additional unknown elements (such asa robot with known dynamics carrying an object with unknown weight), then we canof course only consider the distribution over these unknown parameters, and fix theknown model parameters.
In this chapter we present the basic algorithm for learning a reduced subspace ofcontrollers from a distribution over inaccurate models. We first present the algorithm
in its generic form as a policy gradient approach, but we will also specifically consider
the special case where the policy search procedure can be solved analytically via aleast-squares problem. In this case we show that we can find the globally optimal
reduced subspace using a dimensionality reduction algorithm known as Reduced Rank
Regression (RRR) (Reinsel and Velu, 1998). Finally, we apply the method to the taskof learning an omnidirectional trotting policy for a quadruped robot: a control lawthat is able to move the robot in any direction while turning in any manner. The
full policy in this domain has almost 100 parameters, but by applying our method
we can exploit an inaccurate model to learn a reduced policy class with only fourparameters, which still works well on the real system.

4.1

Related Work

The work in this chapter relates to a number of areas from both machine learningand reinforcement learning, most notably the areas of transfer learning, specificallyapplied to reinforcement learning domains, and dimensionality reduction applied tocontrol.

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

71

Transfer learning, broadly speaking, is a subfield of machine learning that focuseson the question of how learning in one domain can improve learning in another.
Transfer learning methods have been applied to a number of reinforcement learning
tasks: see e.g., (Taylor and Stone, 2009) for a survey of several approaches. The
particular sub-area of transfer learning that relates most to the approach we present
here is multi-task learning (Thrun, 1996; Caruana, 1997), a setting where a learningalgorithm is presented with several different learning problems, and where each task
has a different optimal solution but similar structure; in this setting, the goal istypically to use the previous tasks to learn some meta-structure of the tasks in generalthat can be used to speed up learning on a new task. The method we propose cancertainly be viewed as an instance of multi-task learning (we learn policy classes inthe different sampled models to improve our performance on the new task: learninga policy on the real system), though it does differ from most standard formulationsof multi-task learning slightly the multiple tasks are constructed automatically and
we do not ultimately care about performance on most of the tasks except insofar
as it helps us learn the one task we care about — i.e., we don’t care how well thepolicies perform in the inaccurate models, just how well the final controller performs
on the real system. This idea of creating artificial “auxiliary problems” in multi-task
learning has also been explored in (Ando and Zhang, 2005), but this was applied
specifically to the task of semi-supervised learning, rather than the control domains
we consider. Similarly, the work of Argyriou et al. (2006, 2007) bears a great dealof resemblance to the strategies we present here: like our algorithm, their work looks
at extracting a feature subspace in the multi-task learning setting. However, theauthors focus specifically on sparse feature constructions that can be expressed asconvex optimization problems, which differs from our focus on rank constraints. More
broadly, however, again their work focuses on a supervised learning setting rather thanthe control setting we consider here.
In addition to the survey described above, multi-task learning for reinforcement
learning and control tasks has received a great deal of interest in recent years. Thesealgorithms typically consider a setting where the agent interacts with a number ofdifferent related MDPs, M1 , . . . MN , and the goal of the algorithm is to use experience

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

72

in past MDPs to improve performance when interacting with a new MDP; this is very
similar to our setup, with the caveat again being that we do not care about performance of the method on any domain other than the real system. Methods for thesesettings differ in terms of what information they store to facilitate faster learning:(Tanaka and Yamamura, 2003; Konidaris and Barto, 2006) store value functions frompast domains, and use these in different ways to speed up learning on a new task;(Mehta et al., 2008) assume identical transition distributions but different rewards
across tasks, which enables them to transfer the reward-independent value function
parameters; (Wilson et al., 2007) use a hierarchical Bayesian approach to learn an
informative prior over MDP parameters themselves; (Taylor et al., 2007) use handcoded functions that map state-action value functions from one task to state-action
value function on another task. Our algorithm differs from these approaches in thatit transfers policy class information between the different tasks, finding a subspaceof control parameters that span good policies across all tasks. Perhaps most similar
to our method is the method of (Li et al., 2009), who also transfer a form of policy
parameters between tasks; however, their work explicitly considers a particular formof policy for partially observable (POMDP) domains, and the details of the approach
are quite different from those we present here.
Our work also relates broadly to approaches for dimensionality reduction, specifically in control settings. Dimensionality reduction as a whole is a very broad topic,
see e.g. (Fodor, 2002) for a survey, but in recent years there have been a number
of applications of these methods to control tasks. In particular, there has been agreat deal of work in recent years on dimensionality reduction for learning suitablebases for value function approximation, using Graph Laplacian methods in particular(Mahadevan and Maggioni, 2007). Also related in work on finding low-dimensional
representation of belief state in POMDPs (Roy et al., 2005). Our work is similar in
spirit to these approaches, but notably differs in that we are specifically looking fora low dimensional representation of the policy class.
Finally, as mentioned in the introduction, the notion of considering a distribution
over possible models bears a great deal of similarity to robust control techniques (Zhouet al., 1996). The difference in our approach, though, is that we are not seeking a

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

73

single control strategy that performs well in all domains. Rather, we are seeking asmall subspace of control strategies, such that, in expectation, when we sample adynamics model from our distribution, we can find a near-optimal controller for thatmodel within the subspace.

4.2

Dimensionality Reduction Policy Search

Here we present our general method for (linear) dimensionality reduction in policy
search algorithms. We first present the generic algorithm for a dimensionality reduction procedure in policy search; the presentation of the algorithm here is quite simple,
but it also involves a non-trivial optimization problem. We then present progressively
more specialized versions of the algorithm: a general policy gradient approach, anda globally optimal version that can be applied when the policy search task can beframed as a least squares problem.
We begin by formalizing the notion of parameterized dynamics models that webriefly described above. Let ψ ∈ Rℓ be a set of real-valued parameters that describe
the dynamics model f : Rn × Rm × Rℓ → Rn . We use the notation
st+1 = f (st , ut ; ψ)

(4.1)

to denote the dynamics model, evaluated at state st and control ut , and parameterizedby ψ. In reality most simulation models we will ever encounter will be of this form,
so it is not a significant additional requirement that we assume a model of this type.
Of course, the real system itself cannot be described in this manner, as there is no
obviously notion of “model parameters” in the real world, but simulated models are
typically of this form.
We also assume some distribution D over these model parameters. Naturally alarge question to answer for our method is how we may come up with this distribution,
because for a suitably broad distribution over models, there may be no coherent
structure within the resulting policies — consider, for instance, a linear model st+1 =Ast +But where we have high uncertainty over all entries of A and B; in such a setting

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

74

there would be no discernible structure in the optimal LQR gains K. However, wehave found in practice that there is often a relatively small subset of model parameters
over which we have a large amount of uncertainty. In physics simulators, for instance,
it can often be fairly easy to obtain an accurate model of robot masses, link lengths,
etc, but properties like friction and mass distribution within the rigid bodies can bemuch harder to model; thus, we would expect to put large uncertainty over these
difficult-to-model parameters, and little to no uncertainty over the easy-to-model
parameters.
Given this distribution, we sample N different sets of parameters from the distribution D,ψ (1) , . . . , ψ (N ) ∼ D.

(4.2)

We denote the value function for the the ith model as J (i) (s; θ),J (i) (s; θ) = E

" H
X

#

C(st , ut ) s0 = s, st+1 = f (st , π(st ; θ); ψ (i) ) .

t=0

(4.3)

Note that while we assume different dynamics models for each sample, we suppose
here that the cost function is the same for all models; if there is some reason to prefera distribution over cost functions, the extension is straightforward.
Our goal now is to find θ(1) , . . . , θ(N ) that minimize these N different value functions. Optimizing these directly would simply be equivalent to solving N different
policy search tasks, but we want to add the additional constraint that all the policy
parameters lie is some low dimensional subspace of the entire set of policy parameters.
In order to enforce this constraint, we form the design matrixΘ ∈ Rk×N ≡ θ(1) · · · θ(N ) .

(4.4)

The constraint that the θ’s all lie in a low dimensional linear subspace of dimensionp, is then equivalent to the constraint that rank(Θ) = p. Thus our dimensionality

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

75

reduction policy search task can be stated generally as the optimization problem[minΘ≡ θ (1) ···θ (N )NX]

J (i) (s; θ(i) )

i=1

(4.5)

s.t. rank(Θ) = p.
Note that the constraint that rank(Θ) = p is equivalent to the constraint that Θ = U V
for some U ∈ Rk×p and V ∈ Rp×N with the assumption being that p ≪ k, so that weare reducing the dimension of the policy class significantly. Using this factorization,and the notation V = [v (1) · · · v (N ) ], we see that
θ(i) = U v (i)(4.6)

so we can interpret the factorization in the following manner: the U matrix corresponds to a set of p “basis functions” (linear combinations of different policy parameters) that are shared across all the tasks, while the v (i) vectors correspond to thelinear coefficients of the ith policy. Using this terminology, we can phrase our optimization problem in a slightly more general way, in terms of the actual distribution
D rather than a set of samples drawn from the distributionhmin Eψ∼D min J(s; U v, ψ)
U

v

i

(4.7)

where J(s; θ, ψ) denotes the value function for policy parameters θ and model parameters ψ. This is a very intuitive formulation of the goal of our dimensionality reduction
procedure: we want to minimize over all possible linear subspaces, such that when
we perform policy search within that linear subspace on a randomly sampled model,
we get good performance.
Before describing a specialization of this algorithm, we make a few observations.
First, the rank constraint in the optimization problem (4.5) is non-convex and soeven if the original policy search procedure was globally solvable, this would evidently
raise the possibility of new local optima in this dimensionality reduction policy searchtask. Equivalently, the factorization is (4.7) would be non-convex jointly in U and v.

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

76

However, given that policy search procedures are usually non-convex to begin with,this is typically not a large concern. And as we shall show shortly, for a certain casewhere the policy search procedure is solvable in a globally optimal way, it turns outthat we are able to solve (4.5) optimally as well.
Second, to further solidify the intuition of our approach, we consider an alternative
procedure, where we first perform policy search to find optimal parameters for each⋆⋆sample θ(1) , . . . , θ(N ) , then run PCA to find a linear subspace of the matrix Θ⋆ =
 (1) ⋆⋆
θ
· · · θ(N ) . This will also procedure a factorization Θ⋆ = Ũ Ṽ , but it should beapparent that

h

i

h

⋆

Eψ∼D min J(s; Ũ v, ψ) ≥ Eψ∼D min J(s; U v, ψ)
v

v

i

(4.8)

where U ⋆ is the solution to (4.5), i.e., the PCA solution does not give the best
linear subspace in terms of minimizing the cost function (this follows trivially since(4.5) minimizes this criterion exactly). Intuitively, this is due to the fact that PCA
produces the optimal reconstruction of the policy coefficients, but the coefficientsthemselves are somewhat irrelevant: what we really care about is the performanceof the policy induced by these coefficients. Thus, PCA is really focusing on thewrong criterion here, and although it has its benefits (a globally optimal solutionthat is easily computed), these mainly indicate that we could potentially use the
PCA solution as an initial point, and then optimize the criterion (4.5).

4.2.1

Dimensionality Reduction Policy Gradient

Of course, the objective function (4.5) is just an optimization problem, and so weneed an actual algorithm for optimizing this objective. The simplest approach hereis just to consider the factorized form Θ = U V and perform joint minimization over
U and V . This could be accomplished either by alternatively optimizing over one of
the matrices until converging to a local optima, or just by taking a gradient step withrespect to both parameters. Since the latter is the conceptually simpler of the two
approaches, and since the potential advantages of alternating minimization techniques(particularly pronounced when the optimization problem can be easily solved in one

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

77

Algorithm 2 Dimensionality Reduction Policy Gradient (DRPG)
Input:
D: distribution over model parameters
N : number of model samples
f : Rn × Rm × Rℓ → Rn : parameterized dynamics modelC : Rn × Rm → R: cost function
H ∈ Z+ : horizon
π : Rn × Rk → Rm : parameterized policy
α ∈ R+ : learning rateU ∈ Rk×p , v (1) , . . . , v (N ) ∈ Rp : initial policy parameters
Initialization:• Draw N samples of model parameters ψ (1) , . . . ψ (N ) ∼ D.
Repeat until convergence:
1. For i = 1, . . . , N , compute gradient: g (i) ← ∇θ(i) J(s; θ(i) , ψ (i) ) (θ(i) ≡ U v (i) ).
2. Take a gradient steps in U and v (i) parameters:!
NX(i) (i) Tg (v ) .
• Update U : U ← U − α
i=1• For i = 1, . . . , N , update v (i) : v (i) ← v (i) − αU T g (i) .

For new dynamics st+1 = f ′ (st , ut ):• Minimize value function over parameters in the span of U : minv′ J(s; U v ′ , f ′ ).

variable while keeping the other fixed) are unclear when the objective is convex inneither variable alone, we adopt this method as our basic algorithm for optimizing
the objective (4.5). We describe the full method in Algorithm 2. We present thealgorithm assuming a deterministic dynamics model, but it can be easily extended tothe stochastic setting via the methods described in Chapter 2.
To see how the algorithm is taking gradient steps in U and v (i) , we discuss here how
to compute the gradient terms ∇U J(s; U v (i) , ψ (i) ) and ∇v(i) J(s; U v (i) , ψ (i) ). While not
identical to previously described terms, these can easily be related to the standard
policy gradient. Using Uj to denote the jth column of U , and θ = U v (i) we have∂J(s; U v (i) )∂J(s; θ) ∂U v (i)∂J(s; θ) (i)(vj I)
=
=
∂Uj
∂θ
∂Uj
∂θ

(4.9)

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

and∂J(s; U v (i) )∂J(s; θ) ∂U v (i)∂J(s; θ)
=
=
U
(i)
(i)
∂v
∂θ
∂v
∂θ

78

(4.10)so∇U J(s; U v (i) ) = (∇θ J(s; θ))(v (i) )T ,and ∇v(i) J(s; U v (i) ) = U T (∇θ J(s; θ)). (4.11)

Thus, we can compute ∇θ J(s; θ, ψ (i )) for θ = U v (i) using the standard (model-based)
methods described in Chapter 2, and then convert these to the factorized parameter
gradients using (4.11). It should be apparent that the algorithm is updating the U
and v (i) terms according to these gradients.

4.2.2

Least Squares Policy Search

In some situations the task of policy search can in fact be expressed as a least squares
problem. While this is obviously a very restricted special case of policy search, given
the preceding discussion in this work, we indeed will soon focus on a control task
(learning an omnidirectional trot gait on a quadruped robot) that can be framed inthis manner. In such a setting, it turns out that we are able to solve the optimization
problem (4.5) for dimensionality reduction policy search optimally, despite the nonconvexity of the problem; we do this using an algorithm known as Reduced Rank
Regression (Reinsel and Velu, 1998).
More formally, we suppose that the optimal parameters for the ith model can besolved (or at least, approximated) via the least-squares problem
min J(θ) ≡ kXθ − y (i) k2
θ(4.12)

for some X ∈ Rq×k , and y (i) ∈ Rq . Setting up a policy search task in such a manner
is not an obvious transformation, so we will shortly describe in some detail how one
policy search task for the quadruped robot can be framed in this manner. For thetime being, though, we will take (4.12) as an assumption, and demonstrate how tosolve the optimization problem (4.5) optimally.
Defining the policy matrix Θ as in (4.4) and defining the design matrix Y ∈ Rq×N

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

79

similarly as
Y = y (1) · · · y (N )(4.13)

then the optimization problem (4.5) becomes equivalent tomin kXΘ − Y k2FΘ(4.14)

s.t. rank(Θ) = p.
The optimal solution to this task, given by the Reduced Rank Regression algorithmis,Θ⋆ = (X T X)−1 X T Y W W T(4.15)

where the columns of W ∈ RN ×p correspond to the p principal eigenvectors of thematrixY T X(X T X)−1 X T Y.

(4.16)

This result is proved in (Reinsel and Velu, 1998, Theorem 2.2). The optimal values
for U and V can be read directly from this solution as
U = (X T X)−1 X T Y W,

V = WT.

(4.17)

Notice that the Reduced Rank Regression solution can be interpreted as the leastsquares solution (X T X)−1 X T Y projected into the subspace spanned by W . When
W is full rank (i.e., there is no rank constraint), then W W T = I, and the solution
coincides with the least squares solution, as we would expect.

4.3

Application to Omnidirectional Path Following

The task we are interested in here is one of omnidirectional path following using
a “trot” gait on a quadruped robot. Again, we will be using the LittleDog robot,
described in greater detail in Chapter 6, but here we briefly describe the particular
task we focus on. Omnidirectional path following refers to the task of following an

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

80

arbitrary spline with the robot’s body, with turning in an arbitrary manner; in otherwords, the robot acts as a holonomic system: able to move in any direction whileorienting itself in any manner. Trot gaits refer to gaits that move two feet of therobot at once (trots move diagonally opposing feet at the same time), as opposed toslower “walking” gaits that move only one foot at a time.
The primary challenging in developing a controller capable of omnidirection trotting is one of balance. Because only two of the robot’s feet are on the ground at one
time, the robot will not be statically stable; furthermore, the LittleDog robot does
not have the requisite power in its legs to maintain any kind of dynamic stability
during the trot. Rather, our approach to a trot gait merely attempts to balance “onaverage”; as soon as the robot raises its legs it will start to fall, but by properly
placing the center of gravity (COG) before taking the step, our goal is to balance therobot as well as possible, such that we can quickly move both moving feet before therobot has tipped to either side.

4.3.1

A Balancing Policy for Omnidirectional Trotting

When the robot is trotting in a fixed direction, then learning a good balancing policy isfairly straightforward. In particular, we can achieve good balance by simply offsetting
the robot’s COG some amount with respect to the average “center” position of themoving feet. In other words, finding a policy for balancing when traveling in a fixed
direction can be framed as a policy search task with two parameters θ = (xoff , yoff ).
We can thus use the signed derivative algorithm from the previous chapter to easily
estimate these parameters. Skipping the precise details of the formulation, the final
form of the signed derivative update for this task is to repeat the update
xoff ← xoff + α ((tFL − tBR ) + (tFR − tBL ))yoff ← yoff + α ((tFL − tBR ) − (tFR − tBL ))(4.18)

where α is the learning rate, and tFL , tFR , tBL , , tBR are the touchdown times for thefour different feet (front left, front right, back left, back right), as measured by footforce sensors on the robot. Intuitively, this update is adjusting the COG location inCHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

81

response to which of the robot’s feet touches down first: for example, if the back left
leg hits before the front right, tFR − tBL > 0, so xoff is increased, shifting the COG
more forward. A video of the robot learning how to balance using this method forforward walking is available at http://ai.stanford.edu/~kolter/ijrr09ld/.
The challenge comes, however, when the robot is not walking in a fixed manner,
but is constantly changing its direction and rate of turn, as is the case for omnidirectional path following. In particular, each step of a trot gait in an omnidirectionalmotion is described by two parameters: a direction χ ∈ [−π, π], which denotes the
direction of travel relative to the robot’s orientation (so that χ = 0 implies we arewalking forward), and a turn angle ω ∈ [−π, π], which denotes the amount to turnper step (so that ω = 0 implies we are not turning, and ω = π/2 implies we turn
90 degrees to the left in one step). Of course, different directions and turn angles
necessitate different COG offsets, denoted
xoff (χ, ω), yoff (χ, ω)(4.19)and through experimentation we have found that it is non-trivial to devise a simple
strategy to choose these COG offsets as a function of the direction and turn angle.
Thus, we parametrize a function to choose these COG offsets, and let the parametersof this function be our policy parameters that we want to find.
Since the direction angle and turning angle are inherently periodic — i.e., a direction of 2π is identical to a direction angle of 0 — the Fourier bases are a natural
means of representing these functions. We therefore represent xoff (χ, ω) and yoff (χ, ω)
asxoff (χ, ω) = θxT φ(χ, ω), yoff (χ, ω) = θyT φ(χ, ω)
where
θ=

"

θx ∈ Rk/2
θy ∈ Rk/2#(4.20)(4.21)

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

82

are the parameters of our policy, andcos(iχ) cos(jω)

 sin(iχ) cos(jω) φ(χ, ω) =  cos(iχ) sin(jω)  , sin(iχ) sin(jω) 


..
.

i, j = 0, 1, . . .

(4.22)

denote the first k/2 principal Fourier basis functions of χ and ω — here the range of iand j are chosen so that the dimension of φ is also k/2. In particular, for this domain
we found that in order to express a sufficiently general policy to balance properly, we
needed to choose the range of i and j above such that there are k = 98 parameters.

4.3.2

Policy Search as Least Squares

Given this class of policies, we can solve for the optimal policy class θ in the following
manner. For any fixed χ and ω, we can run the signed derivative approach to findthe xoff and yoff that are optimal for this direction and turn angle. Then, given acollection of direction angles, turning rates, and their corresponding center offsets,
we can learn the coefficients θx and θy by least squares regression. Specifically, if weare given a set of n direction angles, turning rates, and resulting x center offsets,{χi , ωi , xoff,i }, i = 1 . . . n, then we can learn the parameters θx ∈ Rk by solving the
optimization problem
min ky − Xθx k22
θx(4.23)

where X ∈ Rn×k and y ∈ Rn are design matrices defined as
X = [φ(χ1 , ω1 ) . . . φ(χn , ωn )]Ty = [xoff,1 . . . xoff,n ]T .

(4.24)The solution to this problem is given by θx = (X T X)−1 X T y, and using a well known
sample complexity result (Anthony and Bartlett, 1999), we need Ω(k) data points tofind such a solution.
Unfortunately, computing a sufficient number of center offsets on the real robot

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

83

is a time-consuming task. Although the signed derivative can find an optimal COG
offset in about a minute under ideal circumstances, several difficulties arise if we try
to apply this algorithm more than 100 times to find these different parameters: mostnotably, running the robot this long, especially at the early stages of learning where
the balancing policy is quite poor, causes a great deal of strain on the robot’s gears,
often degrading joint angle calibration by bashing its feet into the ground. And
although it is significantly easier to find proper joint offsets in a simulation model(we can run the same algorithm without any fear of damaging the hardware), it isdifficult to create a simulator that accurately reflects the center offset positions in thereal robot. Indeed, we invested a great deal of time trying to learn parameters forthe simulator that reflected the real system as accurately as possible, but still could
not build a simulator that behaved sufficiently similarly to the real robot. Thus, inorder to learn a policy on the real system we applied our dimensionality reduction
algorithm in the following manner.

4.3.3

Experimental Setup and Results

Here we present experimental results on applying our method to learn a controller
for omnidirectional path following. The simulator we built is based on the physical specifications of the robot and uses the Open Dynamics Engine (ODE) physics
environment.1
Our experimental design was as follows: We first sampled 100 simulation models from a distribution over the simulator parameters. In particular, we varied thesimulators primarily by adding a constant bias to each of the joint angles, wherethese bias terms were sampled from a Gaussian distribution. We also experimented
with varying several other parameters, such as the centers of mass, weights, torques,
and friction coefficients, but found that none of these had as great an effect on the
resulting policies as the joint biases. This is somewhat unsurprising, since the realrobot has constant joint biases. However, we reiterate the caveat mentioned in theprevious section: it is not simply that we need to learn the correct joint biases in
1

ODE is available at http://www.ode.org.

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

84

order to achieve a perfect simulator; rather, the results suggest that perturbing thejoint biases results in a class of policies that is robust to the typical variations inmodel dynamics.
In each of these simulation models, we used the online balancing algorithm described in Section 4.3.1 to find center offsets for a variety of fixed directions and turning rates. For each model, we generated 100 data points, with turning angles spaced
evenly between -1.0 and 1.0, and direction angles from 0 to 2π. We constrained thecentering function (in both the x and y directions), to be a linear combination of thefirst k = 49 Fourier bases of the direction angle and turning rate. We then applied
the Reduced Rank Regression algorithm to learn a low-dimensional representation ofthis function with only ℓ = 2 parameters, effectively reducing the number of parameters by more than 95%. Two bases was the smallest number that achieved a good
controller with the data we collected: one basis vector was not enough, three basis
vectors performed comparably to two, but had p no visible advantage, and four basis
vectors began to over-fit to the data we collected from the real robot, and started toperform worse.
Finally, to learn a policy on the actual robot, we used the online centering algorithm to compute proper center locations for 12 fixed maneuvers on the robot andused these data points to estimate the parameters of the low-dimensional policy. In
greater detail, for 12 different turning angles and direction angles, we ran the online learning algorithm presented in Section 4.3.1, to find the correct x and y center
offsets in the real system. Given these 12 data points (far too few to learn the full
dimensional policy, we searched within the linear subspace found by our algorithm tofind a controller that captured these optimal center locations as closely as possible,
and used this controller for balancing the robot.
To evaluate the performance of the omnidirectional gait and the learned centeringfunction, we used three benchmark path splines: 1) moving in a circle while spinningin a direction opposite to the circle’s curvature; 2) moving in a circle, aligned with thecircle’s tangent curve; and 3) moving in a circle keeping a fixed heading. To quantify
performance of the robot on these different tasks, we used four metrics: 1) the amountof time it took for the robot to complete an entire loop around the circle; 2) the root

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

Figure 4.1: Pictures of the quadruped robot following several paths.
0.8

0.03

Desired Path
Actual Path

Turn Angle:

0.6
0.02

0.0
0.05

0.4

0.1
0.01
Y Center Offset

Y location

0.15
0.2

0.2

0

0.25
0.3
0

0.35
0.4
0.45

−0.2
−0.01

0.5
0.55

−0.4

0.6
−0.02

−0.6

−0.8
−0.8

−0.6

−0.4

−0.2

0
X location

0.2

0.4

0.6

0.8

(a) Desired and actual trajectories for the learned
controller on path 1.

−0.03
−0.03

0.65
0.7

−0.02

−0.01

0
X Center Offset

0.01

0.02

0.03

(b) Learned center offset
curves for several different
turning angles.

Figure 4.2: Trajectory and center offsets for the learned controller.

85

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

MetricLoop Time (sec)Foot Hit RMSE (sec)Distance RMSE (cm)Angle RMSE (rad)

Path
1
2
3
1
2
3
1
2
3
1
2
3

Learned Centering
31.65 ± 2.43
20.50 ± 0.18
25.58 ± 1.46
0.092 ± 0.009
0.063 ± 0.007
0.084 ± 0.006
1.79 ± 0.09
1.03 ± 0.36
1.58 ± 0.11
0.079 ± 0.006
0.070 ± 0.011
0.046 ± 0.007

No Centering
46.70 ± 5.94
32.10 ± 1.79
40.07 ± 0.62
0.120 ± 0.013
0.151 ± 0.016
0.129 ± 0.007
2.42 ± 0.10
2.80 ± 0.41
2.03 ± 0.07
0.075 ± 0.009
0.070 ± 0.002
0.058 ± 0.012

86

Hand-tuned Centering
34.33 ± 1.19
31.69 ± 0.45
28.57 ± 2.21
0.098 ± 0.009
0.106 ± 0.010
0.097 ± 0.006
1.84 ± 0.07
1.98 ± 0.21
1.85 ± 0.16
0.067 ± 0.013
0.077 ± 0.006
0.071 ± 0.009

Table 4.1: Performance of the different centering methods on each of the three benchmark paths, averaged over 5 runs, with 95% confidence intervals.

mean squared difference of of the foot hits (i.e., the time difference between when
the two moving feet hit the ground); 3) the root mean squared error of the robot’s
Euclidean distance from the desired path; and 4) the root mean squared difference
between the robot’s desired angle and its actual angle.
Note that these metrics obviously depend on more than just the balancing controller — speed, for example, will of course depend on the actual speed parametersof the trot gait. However, we found that good parameters for everything but thebalancing controller were fairly easy to choose, and the same values were optimal,
regardless of the balancing policy used. Therefore, the differences in speed/accuracy
between the different controllers we present is entirely a function of how well thecontroller is capable of balancing — for example, if the robot is unable to balance itwill slip frequently and its speed will be much slower than if it can balance well.
We note that prior to beginning our work on learning basis functions, we spenta significant amount of time attempting to hand-code a centering controller for the
robot. We present results for this hand-tuned controller, since we feel it represents
an accurate estimate of the performance attainable by hand tuning parameters. We
also evaluated the performance of the omnidirectional gait with no centering. The
controller using a policy based entirely from the “mean” simulator model performed
comparably to the policy with no balancing at all; this suggests that in this case, oursimulation model was quite different from the real system, but it still enabled us tolearn a suitable subspace.

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

87

Figure 4.1 shows pictures of the robots following some of the benchmark paths,
as well as an additional star-shaped path. Videos of these experiments are available
at: http://ai.stanford.edu/~kolter/omnivideos.
Table 4.1 shows the performance of each centering method, for each of the four
metrics, on all three benchmark paths.2 As can be seen, the learned controller outperforms the other methods in nearly all cases. As the distance and angle errors
indicate, the learned controller was able to track the desired trajectory fairly accurately. Figure 4.2(a) shows the actual and desired position and orientation for thelearned centering controller on the first path. Figure 4.2(b) shows the learned center
offset predictor trained on data from the real robot. This figure partially explains
why hand-tuning a controller can be so difficult: at higher turning angles the proper
centers form unintuitive looping patterns.

4.4

Summary

In this chapter we presented a method for dimensionality reduction in policy searchtasks. The algorithm finds a low dimensional subspace of control parameters that
contains good controllers over a variety of different models: thus, by considering a
distribution over possible models we can find a reduced subspace of possible control
policies. This reduces the dimension of the policy search task on the real system,
and can make such methods much more practical in real domains. The method
is particularly applicable to situations where we have some uncertainty over certain
model parameters (either due to poor modeling or the fact that the system can changeover time), and we want to find a small subspace of controllers that perform well overthis entire distribution. We began the chapter with a general form of the algorithm
applicable to policy gradient methods, then specialized the algorithm to the special
case where the policy search task can be framed as a least squares problem. Using
the latter formulation, we apply our method to the task of learning a low-dimensional
2

The foot hit errors should not be interpreted too literally. Although they give a sense of thedifference between the three controllers, the foot sensors are rather imprecise, and a few bad falls
greatly affect the average. They therefore should not be viewed as an accurate reflection of the foottimings in a typical motion.

CHAPTER 4. DIMENSIONALITY REDUCTION IN POLICY SEARCH

88

control parametrization for omnidirectional path following with the LittleDog robot,
and demonstrate the method is able to learn a highly reduced subset of control lawsthat achieve very good performance on the task.
Of course, we again note that the method we present here is not applicable toall control tasks. In particular, although we are using an inaccurate model to learn
the low-dimensional control parametrization, we still require that the model capturesome degree of accuracy, or else we may be unable to achieve good performance on
the real system using any policy from this subspace. Thus, for domains where thedynamics are difficult to model, even in the sense of determining some distribution
over possible models, our method likely will not find a suitable controller subspace.
Nonetheless, as we demonstrate in this chapter, there are certainly cases where we
can find a good subspace of controllers, even when the exact dynamics of the true
system are very difficult to model, and we have demonstrated the potential of thealgorithm in such a setting.

Chapter 5
Multi-model Control for Mixed
Closed-loop/Open-loop Behavior
The previous two chapters considered methods for exploiting inaccurate models,though in both cases the model still captured some element of the true model correctly: either through the dominant signs of the model, or by capturing some distribution over unknown parameters. In contrast, this chapter deals with the scenario
where a model truly cannot capture the relevant portions of a system, either because
the true system is too complex or because of non-Markovian and/or hidden statevariables. In such settings it may indeed seem as though we would be unable to use amodel in order to obtain good performance on the system. And to some extent this istrue: if the model is unable to capture the relevant portions of the system dynamics,
then it seems unlikely (almost by definition), that we could use the model alone tocreate a good control policy.
Fortunately, there is an aspect of many control tasks that mitigates this problem.
In particular, we repeatedly observe in practice that even if the model is difficult tolearn, real dynamical systems are often remarkably deterministic over short periodsof time: if we execute the same sequence of control inputs from an identical or nearly
identical initial state, the system often behaves in a very similar manner, even if it
is very hard to predict how the system would respond to different inputs. We have89CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

90

repeatedly observed such behavior in the LittleDog robot (many static climbing maneuvers can be executed in an entirely open-loop manner as long as the robot carefully
positions itself first), in helicopter control (aerobatic maneuvers are executed virtually open-loop by skilled pilots, again once the system has been put into a proper
initial state), in the aerodynamic task of landing a hang-glider (approach to the runway involves careful control, but the actual landing is a largely open loop procedurethat stops the glider quickly by inducing an uncontrolled stall), and of course in the
car-driving task that we will describe in great detail. Intuitively, these observations
motivate an alternating control strategy, where we would want to actively control
the system using classical methods in well-modeled regimes, but execute open-loop
trajectories in poorly modeled regions, provided we have seen a previous demonstration of the desired behavior. Indeed, as we will discuss shortly, such strategies havepreviously been used to control a variety of systems, though these have mostly reliedon hand-tuned switching rules to determine when to execute the different types ofcontrol.
In this chapter, we make two contributions. First, we develop a probabilistic
approach to mixed open-loop and closed-loop control that achieves performance far
superior to each of these elements in isolation. In particular, we propose a method for
applying optimal control algorithms to a probabilistic combination of 1) a “simple”
model of the system that can be highly inaccurate in some regions and 2) a dynamics
model that describes the expected system evolution when executing a previouslyobserved trajectory. By using variance estimates of these different models, our method
probabilistically interpolates between open-loop and closed-loop control in an optimal
manner, thus producing mixed controllers without the typical hand-tuning. Second,
we apply this algorithm to the challenging task of a “sliding parallel park” on afull-sized autonomous car — that is, accelerating a car to 25 mph, then slammingon the brakes while turning the steering wheel, skidding the car sideways into a
narrow desired location. To the best of our knowledge, this is the first autonomous
demonstration of such behavior on a car, representing the state of the art in accurate
control for such types of maneuvers.

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

5.1

91

Related Work

There is a great deal of work within both the machine learning and control communities that is relevant to the work we present here. As mentioned previously, themixed use of open-loop and closed-loop control is a common strategy in robotics andcontrol (e.g., Atkeson and Schaal, 1997; Hodgins and Raibert, 1990; Gillula et al.,2010), though typically these involve hand-tuning the regions of closed-loop/openloop control. One exception to this is the work of Gillula et al. (2010), developed
concurrently to the techniques we present here, which use robust control methods todetermine execution regions for the different controllers; however, the algorithms andfocus of this method and our own are quite different. The work of Hansen et al.,(Hansen et al., 1996) also considers a mixture of open-loop and closed-loop control,
though here the impetus for such control comes from a cost to sensing actions, notfrom difficulty of modeling the system, and thus the algorithms are very different.
Our work also relates to work on multiple models for control tasks (Murray-Smithand Johansen, 1997). However, with few exceptions the term “multiple models” istypically synonymous with “local models,” building or learning a collection of models
that are each accurate in a different portion of the state space — for example, locallylinear models, (Schaal, 1994; Christopher G. Atkeson, 1997; Vijayakumar et al., 2005;
Doya et al., 2002) or non-parametric models such as Gaussian Processes (Ko et al.,2007). Standard local models are typically defined such that the model designer must
manually specify the regions of validity for each of the model, and only one modelis used at each point in the state space; this contrasts with our approach, where weuse a Gaussian observation models to combine predictions from all models jointly,
using estimates of their variance. More broadly, though, fundamentally our method
certainly could be considered a local model method, but novelty of our approachcomes largely from the specific nature of the different models we use, and how thisnaturally leads to the desired behavior of mixed open-loop and closed-loop control.
From the control literature, our work perhaps most closely resembles the workon multiple model adaptive control (Narendra and Balakrishnan, 1997; Schott andBequette, 1997). Like our work, this line of research takes motivation from the fact

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

92

that different models can capture the system dynamics with different degrees of uncertainty, but again like the previous work in machine learning, this research has typicallyfocused on learning or adapting multiple local models of the system to achieve better
performance.
Our work also relates somewhat more loosely to a variety of other research inreinforcement learning. For instance, the notion of “trajectory libraries” has been
explored for reinforcement learning and robotics (Stolle and Atkeson, 2006; Stolle
et al., 2007), but this work has primarily focused on the trajectories as a means for
speeding up planning in a difficult task. The notion of learning motor primitives hasreceived a great deal of attention recently (e.g. (Peters and Schall, 2004)), thoughsuch research is generally orthogonal to what we present here. These motor primitives typically involve feedback policies that are not model-based, and we imagine
that similar techniques to what we propose here could also be applied to learn how
to switch between model-based and motor-primitive-based control. Indeed to someextent our work touches on the issue of model-based versus model-free reinforcement
learning (Atkeson and Santamaria, 1997) where our open-loop controllers are simply
a very extreme example of model-free control, but we could imagine applying similar
algorithms to more general model-free policies.
Finally, there has been a great deal of past work on autonomous car control, forexample (Hoffmann et al., 2007). Some of this work has even dealt with slight forays
into control at the limits of handling (Hsu and Gerdes, 2005), but all such publishedwork that we are aware of demonstrates significantly less extreme situations than what
we describe here, or includes only simulation results. We are also aware of anothergroup at Stanford working independently on control at the limits of handling (Gerdes,
2009), but this work revolves more around physics-based techniques for stabilizing thesystem in an unstable “sliding” equilibrium, rather than executing maneuvers withhigh accuracy.

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

5.2

93

A Probabilistic Framework for Multiple Model
Control

Here we present a general method for combining multiple control models, and demonstrate that when we apply this algorithm to two particular types of models, we naturally achieve behavior that trades off between executing a closed-loop maneuverwhen we have a good model of the dynamics, and an open-loop maneuver when ourmodel is inaccurate. In particular, we will first present an extension of LQR, which
we call Multi-model LQR, that can deal with predictions from multiple probabilistic dynamics models. We then develop a simple model for capturing the dynamics
of previously observed trajectories, and we show that when we provide both thismodel and an inaccurate dynamics model to our Multi-model LQR algorithm, thealgorithm will smoothly interpolate between closed-loop and open-loop control in theproper manner.
To formalize our framework, we are operating in the trajectory-following settingfrom Chapter 2, where we want to follow some desired trajectory τ ⋆ = (s⋆0 , u⋆0 , . . . , s⋆H , u⋆H )(which we assume is realizable on the real system), and the cost function is given by
Ct (s, u) = (s − s⋆t )T Q(s − s⋆t ) + (u − u⋆t )T R(u − u⋆t ).

(5.1)

The ability to execute the trajectory on the real system does not imply that we will
necessarily be able to execute the entire sequence repeatedly in an open-loop manner.
In particular, although we motivated our overall approach by appealing to the factthat real system were often remarkably deterministic, we need to add the caveat that
this does of course only apply over relatively short timescales (on the order of a few
seconds), and only when initial states are very similar. In the setting of general
trajectory following, where the trajectory may span many seconds and the initialstate of the system may differ from the initial state in trajectory, we need additional
methods (such as LQR) to control the system.
We also suppose that we have access to an (inaccurate) stochastic model of theCHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

94

form
st+1 = f (st , ut ) + ǫt

(5.2)

and the assumption is that this model may be accurate in certain portions of thestate space, but inaccurate in others. To capture this inaccuracy, we extend ourprevious definitions and assume that the noise term for this model is a state andcontrol dependent Gaussian, i.e.,ǫt ∼ N (0, Σ(st , ut )).

(5.3)

The covariance terms Σi (st , ut ) are interpreted as maximum likelihood covarianceestimates, i.e., for true next state st+1 ,Σ(st , ut ) = E (st+1 − f (st , ut ))(st+1 − f (st , ut ))T .

(5.4)

This notion of the variance as a maximum likelihood estimate is very important,because it implies that the variance term for our model actually captures two sourcesof error: 1) the true stochasticity of the world and 2), the inaccuracy of the model.
Because we assume that the stochasticity of real system is small over short time
periods, this implies that the variance term will typically be dominated by the second
element; thus, the model variance in a sense acts as a proxy for the inaccuracy of themodel, one that algorithms can exploit to determine when to trust the model andwhen to execute open loop controls.

5.2.1

LQR with multiple probabilistic models

Here we present our general extension of LQR, called Multi-model LQR, for combining multiple probabilistic models with the LQR algorithm. We suppose that weare given two approximate dynamical models of the form above, M1 and M2 — thegeneralization to more models is trivial and we consider two just for simplicity of presentation. To combine multiple probabilistic models of this form, we interpret eachprediction as an independent observation of the true next state, and can then compute the posterior distribution over the next state given both models by a standard

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

95

manipulation of Gaussian probabilities,p(st+1 |M1 , M2 ) = N (f¯(st , ut ), Σ̄(st , ut ))

(5.5)

where
−1
Σ̄ = Σ−1
1 + Σ2−1−1, and f¯ = Σ̄ Σ−1
1 f1 + Σ2 f2



(5.6)

and where the dependence on st and ut is omitted to simplify the notation in this lastline. In other words, the posterior distribution over next states is a weighted averageof the two predictions, where each model is weighted by its inverse covariance. This
combination is analogous to the Kalman filter measurement update.
We could now directly apply LQR to this joint model by simply computingf¯(s⋆t , u⋆t ) and its derivatives at each point along the trajectory. Specifically, we could
run LQR exactly as described in Chapter 2, using the linear approximation of theerror dynamics
δst+1 = At δst + Bt δut(5.7)

where δst ≡ st − s⋆t and δut ≡ ut − u⋆t , where At and Bt are the Jacobians of f¯evaluated at s⋆t and u⋆t ,∂ f¯(s⋆t , u⋆t )
At =
,
∂s⋆t

∂ f¯(s⋆t , u⋆t )
Bt =
,
∂u⋆t

(5.8)

and the noise term is given by wt ∼ N (0, Σ̄(s⋆t , u⋆t )). However, combining these models
in this manner will lead to poor performance. This is due to the fact that we would
be computing Σ1 (s⋆t , u⋆t ) and Σ2 (s⋆t , u⋆t ) only at the desired location, which can givea very inaccurate estimate of each model’s true covariance. For example, consider
a learned model that is trained only on the desired trajectory; such a model would
have very low variance at the actual desired point on the trajectory, but much higher
variance when predicting nearby points. Thus, what we really want to compute is
the expected covariance of each model, in the region where we expect the system tobe. We achieve this effect by maintaining a distribution Dt over the expected state(errors) at time t (i.e., a distribution over δst ). Given such a distribution, we canCHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

96

approximate the average covarianceΣi (Dt ) ≡ Eδst ,δut ∼Dt [Σi (s⋆t + δst , u⋆t + δut )](5.9)

via sampling or other methods. This notion of maintaining a distribution over expected states is well-known in reinforcement learning (Bagnell et al., 2004), but wehave not seen a specialization of such ideas to this form of LQR algorithm.
The last remaining element we need is a method for computing the state (error)
distributions Dt . Fortunately, given the linear model assumptions that we already
employ for LQR, computing this distribution analytically is straightforward. In particular, we first assume that our initial state distribution D0 is a zero-mean Gaussianwith mean zero and covariance Γ0 . Since LQR outputs a closed-loop controller of theform δut = Kt δst , our closed-loop state error dynamics evolve according to the linear
model δst+1 = (At + Bt Kt )δst , the covariance of Dt , Γt , is updated byΓt+1 = (At + Bt Kt )Γt (At + Bt Kt )T + Σ̄(Dt ).

(5.10)

Of course, since we average the different models according to the Σi (Dt ), changing Dt
will therefore also change At and Bt . Thus, we iteratively compute all these quantities
until convergence. A formal description of the algorithm is given in Algorithm 3.

5.2.2

A dynamics model for open-loop trajectories

The method above is a general algorithm for combining probabilistic models with an
LQR-based approach, but recall that our overall goal is to combine closed-loop control
in well-modeled regions with open-loop control in poorly modeled regions. Thus, inthis section we develop a probabilistic model that describes how the state will evolve
when executing a sequence of previously observed controls; combining this with atypical inaccurate dynamics model using the algorithm above will then naturally leadto the desired behavior. While generally one would want to select from any number ofpossible trajectories to execute, for the simplified algorithm in this section we consider
only the question of executing the control actions of the ideal trajectory u⋆0:H .

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

97

Algorithm 3 Multi-model LQR (MM-LQR)
Input:
Γ0:H : initial state error covariance
M1 , M2 : probabilistic dynamics modelss⋆0:H , u⋆0:H : desired trajectory
Q, R: LQR cost matrices
Repeat until convergence:
1. For t = 0, . . . , H, compute dynamics models• For i = 1, 2, compute expected covariances:
Σi (Dt ) ← Eδst ∼N (0,Γt ) [Σi (s⋆t + δst , u⋆t + Kt δst )] .
• Compute averaged model:
−1Σ̄t ← Σ−1 (Dt ) + Σ−1 (Dt ), f¯ ← Σ̄t Σ−1 (Dt )f1 + Σ−1 (Dt )f2 .
1

2

1

2

• Linearize dynamics of averaged model:∂ f¯(s⋆t , u⋆t )∂ f¯(s⋆t , u⋆t )At ←, Bt ←.
∂s⋆t∂u⋆t

2. Run LQR to find optimal controllers Kt :K0:H−1 ← LQR(A0:H−1 , B0:H−1 , Q, R).
3. For t = 0, . . . , H − 1, update state distributions:Γt+1 ← (At + Bt Kt )Γt (At + Bt Kt )T + Σ̄t

To allow our model to be as general as possible, we assume a very simple probabilistic description of how the states evolve when executing these fixed sequences ofactions. In particular, we assume that the error dynamics evolve according toδst+1 = ρδst + wt
where ρ ∈ R (typically ≈ 1) indicates the stability of taking such trajectory actions,and where wt is a zero-mean Gaussian noise term with covariance Σ(δst , δut ), which
depends only on the state and control error and which captures the covariance of themodel as a function of how far away we are from the desired trajectory. This model
captures the following intuition: if we are close to a previously observed trajectory,
then we expect the next error state to be similar, with a variance that increases theCHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

98

more we deviate from the previously observed states and actions. While it may seem
odd to suppose that the next predicted mean state is independent of the control,a single trajectory couldn’t convey any additional information: we only know how
the system responded to a particular control input u⋆t for a particular state, s⋆t , andwe have no information about how the system would have responded had we acted
otherwise.
To see how this model naturally leads to trading off between actively controllingthe system and largely following known trajectory controls, we consider a situation
where we run the Multi-model LQR algorithm with an inaccurate model1 M1 and thisdescribed trajectory model, M2 . Consider a situation where our state distribution Dt
is tightly peaked around the desired state, but where M1 predicts the next statevery poorly. In this case, the maximum likelihood covariance Σ1 (Dt ) will be large,
because M1 predicts poorly, but Σ2 (Dt ) will be much smaller, since we are still close
to the desired trajectory. Therefore f¯ will be extremely close to the trajectory model
M2 , and so will lead to system matrices At ≈ ρI and Bt ≈ 0 (since these are thederivatives of the trajectory model). Therefore, since no delta can affect the statevery much, LQR will choose controls δut ≈ 0 — i.e., execute controls very close to u⋆t ,as this will minimize the expected cost function. In contrast, if we are far away fromthe desired trajectory, or if the model M1 is very accurate, then we would expect tolargely follow this model, as it would have lower variance than the naive trajectorymodel. In practice, the system will smoothly interpolate between these two extremes
based on the variances of each model.

5.2.3

Estimating Variances

Until now, we have assumed that the covariance terms Σi (st , ut ) have been given,though in practice these will need to be estimated from data. Recall that the variances
we want to learn are ML estimates of the form
Σi (st , ut ) = E (st+1 − fi (st , ut ))(st+1 − fi (st , ut ))T1
For the purposes of this discussion it does not matter how M1 is obtained, and could be built,
for example, from first principles, or learned from data, as we do the car in Section 5.3.

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

99

so we could use any number of estimation methods to learn these covariances, and ouralgorithm is intentionally agnostic about how these covariances are obtained. Somemodeling algorithms, such as Gaussian Processes, naturally provide such estimates,
but for other approaches we need to use additional methods to estimate the covariances. Since we employ different methods for estimating the variance in the two setsof experiments below, we defer a description of the methods to these sections below.

5.3

Experiments

In this section we present experimental results, first on a simple simulated cartpole domain, and then on our main application task for the algorithm, the task ofautonomous sideways sliding into a parking spot.

5.3.1

Cart-pole Task

To easily convey the intuition of our algorithm, and also to provide a publicly available
implementation, we evaluated our algorithm on a simple cart-pole task (where thepole is allowed to freely swing entirely around the cart). The cart-pole is a well-studied
dynamical system, and in particular we consider the control task of balancing an upright cart-pole system, swinging the pole around a complete revolution while moving
the cart, and then balancing upright once more. Although the intuition behind thisexample is simple, there are indeed quite a few implementation details, and the sourcecode for this example is available at: http://ai.stanford.edu/~kolter/icra10.
The basic idea of the cart-pole task for our setting is as follows. First, we provide
our algorithm with an inaccurate model of the dynamical system; the model uses a
linear function of state features and control to predict the next state, but the features
are insufficient to fully predict the cart-pole dynamics. As a result the model isfairly accurate in the upright cart-pole regions, but much less accurate during theswing phase. In addition, we provide our algorithm with a single desired trajectory(the target states and a sequence of controls that will realize this trajectory under azero-noise system). Because we are here focused on evaluating the algorithm without

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

1

1

1

0.5

0.5

0.5

0

0

0

−0.5

−0.5

−0.5

−1

−2.5

−1

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

2.5

−2.5

100

−1

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

2.5

−2.5

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

2.5

Figure 5.1: (left) Trajectory followed by the cart-pole under open-loop control (middle) LQR control with an inaccurate model and (right) Multi-model LQR with boththe open loop trajectory and inaccurate model.
MethodLQR (true model)
LQR (inaccurate model)
LQR (GP model)
Open Loop
Multi-model LQR
Hand-tuned Switching Control

Avg. Total Cost
18.03 ± 1.61
96,191 ± 21,327
96,712 ± 21,315
67,664 ± 13,585
33.51 ± 4.38
73.91 ± 13.74

Table 5.1: Total average cost at the last time step for different algorithms on the
cart-pole task.
consideration for the method used to estimate the variances, for this domain we
estimate the variances exactly using the true simulation model and sampling.
Figure 5.1 shows the system performance using three different methods: 1) fully“open loop” control, which just replays the entire sequence of controls in the desired
trajectory, 2) running LQR using only the inaccurate model, and 3) using the Multimodel LQR algorithm with both the inaccurate model and the trajectory. As can beseen, both pure open-loop and LQR with the inaccurate model fail to control the system, but Multi-model LQR is able to reliably accomplish the control task. Figure 5.2
and Table 5.1 similarly show the total cost achieved by each of the methods, averaged
over 100 runs. Although open loop and inaccurate LQR fail at different points, they
are never able to successfully swing and balance the pole, while Multi-model LQR
performs comparably to LQR using the actual model of the system dynamics by naturally interpolating between the two methods in order to best control the system.
In the figure we also show the error of a hand-tuned switching policy that switches
between purely model-based and open-loop control; despite exhaustive search to find

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

101

100
LQR, inaccurate Model

Open Loop90

LQR, GP Model80
Hand−tuned switching controller

Average total cost

70

60

50

40

Multi−model LQR

30

20
LQR, true model

10

0

50

100

150

200

250

300

350

400

450

500

550

Time

Figure 5.2: Average total cost on cart-pole task, versus time. Shaded regions indicate
95% confidence intervals.
the optimal switch points, the method still performs worse here than Multi-model
LQR.
In Figure 5.2, we also compare to a Gaussian process (GP) model (see, e.g. (Rasmussen and Williams, 2006) for detailed information about Gaussian processes) that
attempted to learn a better dynamics model by treating the inaccurate model as
the “prior” and updating this model using state transitions from the desired trajectory. However, the resulting model performs no better than LQR with the inaccurate
model. We emphasize that we are not suggesting that Gaussian processes cannot
model this dynamical system — they can indeed do so quite easily given the proper
training data. Rather, this shows that the desired trajectory alone is not sufficient
to improve a GP model, whereas the Multi-model LQR algorithm can perform wellusing only these two inputs; this is an intuitive result, since observing only a single
trajectory says very little about the state and control derivatives along the trajectory,
which are ultimately what is needed for good fully LQR-based control. Indeed, weCHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

102

have been unable to develop any other controller based only on the inaccurate modeland the desired trajectory that performs as well as Multi-model LQR.

5.3.2

Extreme Autonomous Driving

Finally, in this section we present our chief applied result of the chapter, an applicationof the algorithm to the task of extreme autonomous driving: accurately sliding a car
sideways into a narrow parking space. Concurrent to this work, we have spent agreat deal of time developing an LQR-based controller for “normal” driving on thecar, based on a non-linear model of the car learned entirely from data; this controller iscapable of robust, accurate forward driving at speeds up to 70 mph, and in reverse at
speeds up to 30 mph. However, despite significant effort we were unable to successfully
apply the fully LQR-based approach to the task of autonomous sliding, which was
one of the main motivations for this current work.
Briefly, our experimental process for the car sliding task was as follows. We provided to the system two elements; first we learned a driving model for “normal”
driving, learned with linear regression and feature selection, built using about 2 minutes of driving data. In addition, we provided the algorithm an example of a humandriver executing a sideways sliding maneuver; the human driver was making no attempt to place the car accurately, but rather simply putting the car into an extreme
slide and seeing where it wound up. This demonstration was then treated as thetarget trajectory, and the goal of the various algorithms was to accurately follow thesame trajectory, with cones placed on the ground to mark the supposed location of
nearby cars.
For this domain, we learned domain parameters needed by the Multi-model LQR
algorithm (in particular, the covariance terms for the inaccurate and open-loop models, plus the ρ term) from data of a few executions of the sliding maneuver on the realsystem. To reduce the complexity of learning the model variances, we estimated thecovariance terms as follows: for the inaccurate model we estimated a time-varying(but state and control independent) estimate of the variance by computing the error

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

103

of the model’s predictions for each point along the trajectory, i.e.,
et = (st+1 − f1 (st , ut ))(st+1 − f1 (st , ut ))Tthen averaged these (rank-one) matrices over a small time window to compute thecovariance for time t. It is possible to let this term depend on the time index alone
because, since we are executed a time-indexed trajectory, the time index itself also
implies the state and control that the system should be in; thus, by looking at how well
the inaccurate model predicts the trajectory, we can develop a good estimate of themodel’s variance along this trajectory without attempting to estimate its variance overthe entire space (a challenging task, as much of the space is never experienced by thesystem, and the model’s variance would therefore be difficult to model). For the openloop trajectory model, we employ the opposite approach, and learn a state and control
dependent (but time independent) estimate of the covariance of the form Σ2 (st , ut ) =(w1 kδut k2 + w2 kδst k2 + w3 ) I, where we learned the parameters w1 , w2 , w3 > 0 via
least-squares by executing the open-loop maneuver one again from a slightly different
starting point, and observing how the two trajectories diverged; this model captures
the intuition that the variance of the open-loop model increases for points that are
farther from the desired trajectory, but that this divergence does not depend on where
we are along the trajectory (i.e., we assume that the true stochasticity of the worldis constant along the trajectory). Finally we selected ρ = 1 due to the fact that thesystem rarely demonstrates extremely unstable behavior, even during the slide.
Figure 5.3 shows snapshots of the car attempting to execute the maneuver under the three methods of control: open-loop, pure LQR, and our Multi-model LQR
approach integrating both the inaccurate model and the trajectory. Videos of thedifferent slides are available at: http://ai.stanford.edu/~kolter/icra10car. It
is easy to understand why each of the methods perform as they did. Purely open-loop
control actually does perform a reasonable slide, but since it takes some distance forthe car to build up enough speed to slide, the trajectory diverges significantly fromthe desired trajectory during this time, and the slide slams into the cones. Pure LQR

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

104

Figure 5.3: Snapshots of the car attempting to slide into the parking spot using(top) open-loop control, (middle) pure LQR control, and (bottom) Multi-model LQR
control. The desired trajectory in all cases is to slide in between the cones.
15
15
Desired Trajectory
Open Loop

10

5

0

0

0

−5

−5

−5

−10

−10

0

10

20

30

40

50

60

70

5

−15

−10

10

20

30

40

50

60

70

5

−15

0

−5

−5

−5

−10

−10

−10

4

6

8

10

12

14

16

18

20

−15

20

30

40

50

60

70

Desired Trajectory
Multi−Model LQR

0

2

10

Desired Trajectory
LQR, inaccurate model

0

0

0

5

Desired Trajectory
Open Loop−15

Desired Trajectory
Multi−Model LQR

10
5

5

−15

15

Desired Trajectory
LQR, inaccurate model

10

0

2

4

6

8

10

12

14

16

18

20

−15

0

2

4

6

8

10

12

14

16

18

20

Figure 5.4: Plots of the desired and actual trajectories followed by the car under(left) open-loop control, (middle) pure LQR control, and (bottom) Multi-model LQR
control. Bottom plots show a zoomed-in view of the final location.
control, on the other hand, is able to accurately track the trajectory during the backward driving phase, but is hopeless when the car begins sliding: in this regime, the
LQR model is extremely poor, to the point that the car executes completely different behavior while trying to “correct” small errors during the slide. In contrast, theMulti-model LQR algorithm is able to capture the best features of both approaches,CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

105

resulting in an algorithm that can accurately slide the car into the desired location.
In particular, while the car operates in the “normal” driving regime, Multi-model
LQR is able to use its simple dynamics model to accurately control the car along the
trajectory, even in the presence of slight stochasticity or a poor initial state. However, when the car transitions to the sliding regime, the algorithm realizes that thesimple dynamics model is no longer accurate, and since it is still very close to thetarget trajectory, it largely executes the open-loop slides controls, thereby accurately
following the desired slide. Figure 5.4 shows another visualization of the car for thedifferent methods. As this figure emphasizes, the Multi-model LQR algorithm is bothaccurate and repeatable on this task: in the trajectories shown in the figure, the final
car location is about two feet from its desired location.

5.4

SummaryThis chapter presented a method for combining inaccurate models of the system withtrajectories, previously observed demonstrations of certain behaviors, in order to obtain better performance than what is possible by using either element in isolation. In
particular, we present an algorithm that uses a variance-based criterion to determine
how to properly weight the different models, which has the effect of executing largely
closed-loop controls when the system is in a well-modeled states, but open-loop controls when the system is in a state that is poorly modeled. We evaluate the approachon a cart-pole swinging task, and on the challenging task of powersliding a full-sizedautonomous car into a parking spot. Our performance on this latter task represents
the state of the art in terms of accurately placement of an autonomous full-sized carin this type of maneuver.
The major drawback of our proposed approach is that in order to achieve such
performance without an accurate model of the system, we do require that we havepreviously observed behavior that accomplishes the desired goal for the control task.
For the car, for instance, we require that we have previously seen a sliding maneuver(though not necessarily one executed in a precise manner). In the event that thesystem enters a state where there is no accurate model, and if the algorithm does not

CHAPTER 5. MIXED CLOSED-LOOP/OPEN-LOOP CONTROL

106

have a demonstration of any behavior that would perform well when executed openloop, then the variance both for any models and for all trajectories would be verylarge, resulting in behavior that would almost certainly not accomplish the desiredtask. More broadly speaking, our algorithm will not plan entirely new trajectories
in difficult-to-model regions, it will simply use trajectories is has already seen in
conjunction with the models that are accurate only in certain parts of the state space.
Despite this restriction, the algorithm can achieve impressive performance when it isgiven such trajectories at its disposal.

Chapter 6
Application to the LittleDog Robot
One of the primary application domains in the previous chapters has been the LittleDog robot, a quadruped robot built to traverse challenging terrain. While thealgorithms we have discussed were crucial to their respective tasks on the LittleDog(learning dynamic maneuvers and trotting), there are naturally many other components to the system that were crucial to the overall performance of the robot. This
chapter provides a general overview of our work on the LittleDog robot, highlighting several additional elements that were needed to achieve good performance, anddemonstrating the complete system crossing a wide variety of terrains. As such, thepresentation in this chapter differs from the previous three chapters. While the overall notion of inaccurate modeling is certainly a prevailing theme in the LittleDog
robot (indeed, the difficulty of creating an accurate physical simulator of the robot
has affected virtually all our design choices on this platform), in this chapter we are
not focusing on a particular algorithm based upon the use of inaccurate modeling.
Rather, the material in this chapter can be viewed as a case study in developing a fullcontrol architecture for a system where fully accurate modeling is not feasible. We
will particularly highlight areas where the inaccuracy of our models has influenced
our design decisions.

107

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

6.1

108

Introduction to Legged Locomotion

Legged robots offer a simple promise: the potential to navigate areas inaccessible totheir wheeled counterparts. While wheeled vehicles may excel in regards to speed andfuel efficiency, they are only able to access about one half of the earth’s land mass
(Raibert, 1986). Contrast this with legged animals, which are able to access virtually
100% of the earth’s land surface. Thus, to enable robotic applications in a variety
of rugged terrains, such as search and rescue operations in hard-to-access locations,
legged locomotion is a promising approach. However, while there has been a great
deal of work on legged locomotion, current legged robots still lag far behind their
biological cousins in terms of the ability to navigate challenging, previously unseen
terrain.
In this chapter we specifically consider the task of navigating a quadruped robot
over a variety of challenging terrain, including terrain that the robot has not previously seen until execution time. At run-time, we assume that the robot obtains
a model of the terrain to cross, and that we have very accurate localization duringexecution; thus, the problem we are focusing on is the planning and control tasks ofquadruped locomotion in highly irregular terrain.
The central methodological theme in this chapter is the ubiquitous use of rapid
recovery and replanning methods. Often times robotic control tasks are framed as
lengthy search problems, where we use a model of the system to explore possible control sequences to move the system from its initial state to the goal; probabilistic roadmaps (Kavraki et al., 1996) and rapidly-exploring random trees (LaValle and Kuffner,1999) are classic examples of such methods. However, much like the control methods
we have discussed previously, these algorithms are best applied when we have an accurate model of the system; if the model is not accurate, then the robot will likely
deviate from the plan as it executes its motion, and due to the computationally intensive planning process, the system cannot quickly replan a new trajectory. Instead, we
designed our system to allow for some degree of failure in the robot’s execution, andfocus on extremely fast replanning methods (within one or two control cycles) thatwould allow the robot to continue even after most failures. This strategy mitigates

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

109

the harm that inaccurate models may cause in the planning process, and as we willshow, we are able to use very inaccurate models to successfully and reliably navigate
over challenging terrain.

6.2

Related Work

6.2.1

Background on legged locomotion

Research in legged robotics has a long history, dating back to the beginning of modern
robotics. One of the first major achievements in legged robots was a human-operated
robot developed by GE in the 60s (Mosher, 1968). Despite the fact that the robot
relied on a human driver, it was capable of walking, climbing over small obstacles,
and pushing large obstacles such as trucks.
The mathematical study of autonomous legged robot gaits began short thereafter with the work of McGhee and others (McGhee, 1967; McGhee and Frank, 1968;
McGhee, 1968). This work focused mainly on what is known as static gaits, gaits
where the robot maintains static stability, which involves keeping its center of gravity (COG) within the support triangle formed by the non-moving feet; thus, for aquadruped, a static gait implies that only one leg can be moved at a time, with theremaining three resting on the ground. McGhee implemented many of these principles in a six-legged walking machine that was able to navigate over a nominal amountof roughness in the terrain (McGhee, 1985). Another milestone in the development oflegged robots came with a series of robots (known as the TITAN robots), developed
by Hirose et al. (1984), that could walk up stairs, again using a static gait.
Another vein of research that began at this time was the work by Raibert onbalancing robots (Raibert, 1986). Unlike the static gaits described previously, theserobots were capable of dynamic gaits, where fewer than three legs were on the groundat a time, including the extreme case of a single hopping leg, though at the timethese robots only operated on flat ground. Recent work in this vein includes the
KOLT robot (Nichol et al., 2004), the Scout II robot (Poulakakis et al., 2005), andthe BigDog robot (Raibert et al., 2008); some of these robots are now able to navigate

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

110

over ground with significant irregularities. However, the obstacles that these robots
are able to navigate over are still small (relative to the size of the robot) compared
to what we consider in this work.
Returning to static gait legged robots, a number of system have been built in recent
years. The Ambler (Krotkov et al., 1995) and Dante II (Bares and Wettergreen,1999) robots were large-scale legged robots built for testing planetary exploration
techniques and for volcanic exploration respectively. Although sometimes partiallyoperated by humans, these robots had modes of fully autonomous behavior in rugged
environments, and represented another significant improvement in the state of theart for the time.
The Sony Aibo robot, and in particular the RoboCup competitions (which involve
playing soccer games with teams of small quadruped robots), have spawned a great
deal of work on learning fast and efficient gaits (Hengst et al., 2002; Hornby et al.,2005; Kohl and Stone, 2004), as well as more high-level work on robot cooperationand strategy. Many of these systems explicitly focused on learning techniques toimprove the performance of the robot. However, these works have focused mainly on
locomotion over flat ground, due to both the physical capabilities of the Aibo and to
the fact that the RoboCup involved moving only over flat ground.
Another branch of research in quadruped locomotion has focused on so-called“Central Pattern Generators” or CPGs. This work is inspired by biological evidence
that animals regulate locomotion by relatively simple, reflexive systems located in the
spinal chord rather than the brain (Grillner, 1985). CPGs are neural-like control lawsthat produce period behavior to drive leg motion, a technique that can be particularly
well suited to robots with built-in compliant mechanisms. A number of robots havebeen built using such behavior, including some which can adapt to some degree ofroughness and irregularity in the terrain (Fukuoka et al., 2003; Kimura et al., 2007).
However, again these robots typically can only handle a relatively small amount of
irregularity in the terrain, not the large obstacles that we consider.
Finally, as we mentioned briefly in the introduction, a separate thread of researchin legged locomotion has been to develop mechanical systems that are naturally much
more robust to irregular terrain, or specifically suited to a certain type of challenging

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

111

Figure 6.1: The LittleDog robot, designed and built by Boston Dynamics, Inc.
locomotion. Such work includes the Rhex hexapedal robot (Saranli et al., 2001),
which uses six flexible legs to rapidly move over relatively large obstacles, and theRiSE climbing robot (Saunders et al., 2006), which uses special leg and foot design toscale vertical surfaces. These robots can achieve very impressive locomotion, but theirdesign strategy is roughly orthogonal to our work: these robots demonstrate thatclever mechanical design, even with largely open-loop behavior, can achieve good
performance in a variety of scenarios. However, these robots can fail in scenarios
where careful sensing and foot placement are a necessity, which is the focus of our
work.

6.2.2

The Learning Locomotion program and LittleDog robot

The robotic platform for the DARPA Learning Locomotion program was the LittleDog robot, shown in Figure 6.1, a small quadruped designed and built by Boston
Dynamics, Inc. While the robot underwent a sequence of small upgrades during the
program, at all points each team working in the program had access to the same
hardware system, so that the capabilities of the different systems resulted entirely
from the different software developed by the different teams.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT112

The LittleDog robot is a small (roughly 3kg) robot, with a 40cm long body and15 cm legs. Each leg has three degrees of freedom, two hip joints and a knee joint,that together allow for free placement in 3D space, subject to the kinematic limitsof the joints. The hip motors provide 1.47 Nm of torque, while the knee provides
1.02 Nm, enough power to move the robot relatively quickly in static gaits, but notenough power to truly jump off the ground; due to this constraint, the majority ofthe program focused either on static gaits (keeping three feet on the ground at onetime), or limited dynamic gaits, such as a trot and two-legged jumps, rather than the
more dynamic “jumping” gaits exhibited, for example, by the BigDog robot (Raibert
et al., 2008).
Control for the robot consisted of two control cycles. An internal processor on
the robot runs a simple PD controller at 500 hz, applying torques to achieve specified
joint angles. Meanwhile, a separate workstation computer runs a control loop at
100 hz, wirelessly sending commands to the robot. While the workstation may send
either PD angle setpoints (which are then executed by the aforementioned on-board
PD controller) or actual motor torques, all teams that we are aware of primarily used
the PD setpoint interface, as the higher bandwidth of the on-board control loop thenallowed for quicker feedback control of the robot.
Although the robot has some degree of onboard sensing (an internal IMU, footforce sensors, and an IR proximity sensor) most of the perception for the Learning
Locomotion project was performed offboard. The robot operates in a Vicon motion
capture system, with retro-reflective markers on the dog’s body and terrain. This
gives the system real-time estimates of the robot’s pose in relation to the terrain. Together with scanned 3D models of the terrain and joint encoder readings, this systemprovides a very accurate estimate of the robot’s state, even without any advanced
filtering techniques. Such “ideal” perception is an admitted benefit for these robots,
which would not be present to such a high degree in a real quadruped walking outdoors, but the goal of the Learning Locomotion program was to focus on the planningand control elements of locomotion, leaving the challenging perception task to otherwork. However, in addition and separate from the official government tests of the program, we have conducted extensive experiments using only an onboard stereo camera

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

113

Figure 6.2: Typical quadruped locomotion task: navigate robot over terrain to goal.
for vision. We will present these results briefly in a later section, but they suggestthat many of the techniques developed for this work by both ourselves and otherteams are indeed applicable to realistic situations where the robot has only onboard
sensing.

6.3

A software architecture for quadruped locomotion

Our goal for quadruped locomotion is to execute a sequence of joint torques (or,if using the PD controller, desired joint angles) that move the robot from its initial
location to the goal. A typical setup of the robot and terrain is pictured in Figure 6.2.
Given the complex obstacle shapes and high dimensionality of the state space (36-D,
including position and velocity variables), naively discretizing the state space would
not scale. Instead, we develop a hierarchical control approach, which decomposes the
problem into several layers.
Figure 6.3 shown the overall architecture of our system. We will spend the restof this section describing the different components of this system in detail, but froma high level the process is fairly straightforward. Before execution, the system firstplans an approximate route over terrain. Next, in an online manner, the systemselects which type of gait to use: a static walk, a trot, or a specialized maneuver
policy. For the static walk and trot gaits, we then plan footsteps for the robot, planmotion paths for the body and feet, and execute these plans using closed-loop control.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

114

Figure 6.3: Hierarchical software architecture for quadruped planner and controller.

6.3.1

Route Planner

The goal of the route planner is to plan an approximate path for the robot’s bodyacross the terrain. The actual path followed by the robot will of course deviate fromthis planned path (for example, when using a static walking gait, the robot’s actual
body path will be adjusted to maintain stability of the robot), but this initial route
allows the robot to better focus its search for footsteps or maneuvers.
A overview of the route planning process is shown in Figure 6.4. The method
uses a route cost map of the terrain that quantifies the goodness or badness of therobot’s body center being at a specific location on the terrain. Given this body costmap, the route planner uses value iteration (using a finely discretized state, with ≈1

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

115

Figure 6.4: Overview of route planning element.
million states) to find a 2D path across the terrain. Since the state transitions arevery sparse, we can solve this planning task using value iteration in an average offive seconds.1 An advantage of using value iteration for this task, which relates to1

Here and in the remainder of the chapter, all run times correspond to run times on thegovernment-provided host machine, running an Intel Xeon processor at 3.0 Ghz

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT116

the aforementioned “rapid replanning” philosophy, is that we can compute the valuefunction once, prior to execution, and subsequent replanning then is extremely fast;if, during execution, the robot falls significantly off its desired path, we simply replan
a new route using this value function, and continue execution. We also note thatthe value iteration is the only part of the planning process that is run offline: all
subsequent elements are run as the robot is crossing the terrain, and thus execution
time is of paramount importance.
The efficacy of this approach rests chiefly on the quality of the cost map: since weare not checking kinematic feasibility along the path, the process has the potential
to lead to a “dead end” — in contrast, global footstep planning techniques (e.g.,(Chestnutt et al., 2003)) can guarantee a full solution at the footstep level, but are
correspondingly more computationally expensive. However, we have found that forreasonable cost maps, the resulting routes work very well in practice, guiding the robot
over the most reasonable portions of the terrain, thus speeding up planning without
significant negative effects. Of course, manually specifying such a cost function is very
difficult in practice, so instead we rely on a learning approach to learn an approximate
cost map as a linear function of certain features that describe the center location;
which we will discuss at greater length in Section 6.6.

6.3.2

Gait Selector

The next step in the execution process is to select, before each step, a gait to use forthe current situation, either a slow static walk (for highly irregular terrain), a faster
dynamic trot (for relatively flatter terrain), or a maneuver specialized to a specificclass of obstacles. Although preliminary experiments indicate that the best gait typecan be accurately predicted using a learning algorithm (where the input is a local
height map of terrain near the robot, and the output is the type of gait or maneuver
to execute), we did not use such an approach for the official Learning Locomotion
submission. Because the project stipulated that our software was provided, a priori,
with terrain IDs that indicated the terrain type, we were able to devise a fairly small
set of rules based upon the terrain ID and height differential of the robot’s legs that

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

117

were very accurate in predicting the best gait type.

6.3.3

Static Walking Gait

For highly irregular terrain, the robot typically uses a static walking gait, a relatively
slow mode of locomotion that moves one leg at a time and maintains static stability
by keeping the robot’s center of gravity (COG) within the supporting triangle formedby the remaining feet. However, even given the desired route from the higher levelsof the system, robustly executing a static walking gait remains a challenging task,
and so we once again decompose the problem into multiple levels: first we plan an
upcoming footstep for the robot; we then plan trajectories for the moving foot andbody that move the desired foot while maintaining static stability of the robot; finally,
we execute this plan on the robot using a controller that constantly checks for loss ofstability, and recovers/replans when necessary.
Walking Gait Footstep Planner
To plan footsteps for the static walk, we use a common fixed repeating sequenceof leg movements: back-right, front-right, back-left, front-left. In addition to being
the gait typically by biological animals during static walking, it has the benefit ofmaximizing the kinematically feasible distance that each foot can move — for moredetailed discussion of the benefits of this pattern, see (McGhee and Frank, 1968).
The planning process is as follows: to take a step, the system first averages thecurrent positions of the four feet to determine the “center” of the robot — in quotations because of course the true COG need not be located at this point; this centeris merely used for planning purposes. Then, we find the point some distance dbody
ahead of this center in the route line, and find the “home” position of the moving
foot relative to this new point (the “home” position here just denotes a fixed position
for each foot relative to the robot’s center, in a box pattern). Finally, because this
precise location may coincide with a poor location on the terrain, we search in a box
around this location and find the footstep with the lowest cost. Again, the cost here
quantifies the goodness of the terrain, this time at the individual footstep level, andCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

118

Figure 6.5: Overview of the footstep planning process.
we will describe in Section 6.6 how we learn this footstep cost simultaneously with the
body cost mentioned above. The complete planning system is illustrated in Figure
6.5.
Finally, because selecting only one footstep at a time can lead to overly myopic
behavior, we use a branching search of some fixed horizon, then choose the footstep
that leads to the least total cost To ensure that the search is tractable, we use aCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

119

relatively small branching factor (typically 3 and 4), and perform a greedy search ateach step to find the 3 or 4 best points in the search box that are not within 3 cmof each other. Because the process can still be somewhat computationally intensive,
we plan the robot’s next step in a separate thread while it executes its current step
(assuming that the current step will be achieved). In cases where the step is notachieved and we need to quickly replan anew, then we use just a single step horizonin the search.
The advantage of this approach is that each foot movement can be planned independent of any previous footsteps: all that determines the next footstep is the moving
foot and the mean of the four current footsteps. Despite it’s simplicity, it is possible
to show that this simple method will quickly converge to a symmetric pattern thatstaggers in the footsteps in an optimal manner. Because we check kinematic feasibility and collisions only at the beginning and end of each proposed footstep, there issome chance that no kinematically feasible, non-colliding path exists between these
positions, though as before we find that this is rarely the case in practice.
Walking Gait Foot/Body Motion Planner
The foot/body motion planner is tasked with determining a sequence of joint angles
that achieve the planned footstep while maintaining static stability of the robot.
Motion planning in such high dimensional state spaces is typically a challenging andcomputationally intensive problem in robotics. However, following our theme of fast
replanning necessitates a very quick method for planning such motions; if the robot
deviates from its desired trajectory and we need to replan its motions, then we do
not want to wait for a slow planner to finish executing before we begin moving again.
Thus, as part of our system we developed a novel motion planning approach, basedon convex optimization and cubic splines, that enables us to quickly (in a matter ofmilliseconds, on the same time scale as the control loop) plan motions that satisfy
the above constraints. However, we defer the discussion of this method until Section
6.5.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

120

Walking Gait Controller
Finally, after planning the precise joint motions that will move the foot to its desired
location while maintaining static stability, the final task of the walking gait is to
execute these motions on the robot. Due to the challenging nature of the terrains we
consider, using PD control alone is highly unreliable: regardless of how well we plan,and regardless of how well the individual joints track their desired trajectories, it isalmost inevitable that at some point the robot will slip slightly and deviate from its
desired trajectory. Therefore, a critical element of our system is a set of closed-loop
control mechanisms that detect failures and either stabilize the robot along its desired
trajectory or re-plan entirely. In particular, we found three elements to be especiallycrucial for the walking gait: 1) stability detection and recovery, 2) body stabilization,and 3) closed-loop foot placement. Again, to simplify the discussion here we defer
discussion of these elements until Section 6.4.

6.3.4

Trot Gait

When the terrain is flatter, a static walking gait is unnecessary, and the robot canmove much faster using a dynamic trotting gait, which moves two feet at a time.
Our approach to a trot gait differs from many other approaches in that we do not
explicitly try to maintain even some measure of dynamic stability, but merely learna gait that tends to balance well “on average.” As with the walking gait, the trot
gait is also subdivided hierarchically into a footstep planner, a joint planner, and acontroller, but due to the nature of the trot (specifically the fact that we will only
execute the gait on relatively flat ground), these elements are considerably simpler
than for the walking gait, so we describe them only briefly.
The trot footstep planner operates in the same manner as the walking footstep
planner, with the exception that we are now planning two moving feet at a timerather than one. We again use a fixed alternating foot pattern, this time alternating
moving back-right/front-left and back-left/front-right. To plan footsteps we again use
the current foot locations to determine the effective center of the robot, then find thepoint some distance dbody ahead on the route, find the “home” position of the moving

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

121

feet relative to this new point, and search in a box around these desired positions tofind the foot location with lowest cost. Further differences from the walking footstep
planner is that 1) we use a smaller dbody , to take smaller steps, 2) we don’t searchin as large a box as for the walking gait and 3) we don’t use any receding horizon
search, but simply use the minimal greedy one-step costs. As with the walking gait,
this process will quickly converge to a symmetric trot pattern, regardless of the initialconfiguration of the feet.
The joint planner and controller for the trot is similarly simplified from the static
walk. We move the moving feet in ellipses over the ground, and use inverse kinematics to determine the joint angles that move the feet along their desired location,
while linearly interpolating the body position between the center locations for thedifferent footsteps. The controller in this case uses PD control alone; indeed, we havefound that closed-loop mechanisms actually degrade performance here, since the trot
is quick enough such that the natural periodic motion will tend to stabilize the robot
and interrupting this periodic motion with additional closed-loop mechanisms typically causes more harm than good. The one challenging aspect to designing the trot
controller is to position the COG in a manner that maintains balance as much as
possible; this is the task we discussed at length in Chapter 4, so we will not discuss
it further here.

6.3.5

Specialized Maneuvers

Finally, in addition to the static walk and dynamic trot, we have developed a number of specialized maneuvers, each intended to cross some specific class of obstacles.
While these were admittedly specialized to the types of obstacles prescribed by the
Learning Locomotion project (for instance, steps or gaps), they are general enoughto cross a wide variety of obstacles within their intended class. We use a total of four
specialized maneuvers for the Learning Locomotion terrains: a front leg jump (forquickly jumping both front legs onto a step or over a gap), a stair climb (for climbing
the back legs onto a stair), a gap cross (for sliding the back legs over a gap), and abarrier cross (for bringing the back legs over a barrier).

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT122

The challenge for the dynamic maneuvers, such as the front jump, is devising a
policy that properly executes the maneuvers without falling forward or backward;
we learned the dynamic maneuvers using the Policy Search with Signed Derivativealgorithm, as described in Chapter 3, so again we don’t discuss these further here.
The non-dynamic specialized maneuvers, such as the stair climb or gap cross, weremanually designed to cross their respective obstacles while maintaining static stabilityof the robot, usually by using the robot’s body itself to balance. While an importantpart of our overall system, these maneuvers were fairly easy to hand-tune, as thestatic motion made them less sensitive to parameter choice, and thus we also don’t
discuss them further.

6.3.6

Introduction to Rapid Replanning Methods

This section has described our software system for the quadruped robot, but wedeferred discussion of several novel methods, related to our central theme of rapid
replanning, that we have developed over the course of this program. In the remainderof this chapter we will present each of these methodologies. In particular, we present
and analyze three approaches that we have developed over the course of the program:
1) a method for recovery and stabilization at the control level, 2) a cubic spline
optimization approach to fast foot and body motion planning, and 3) a method for
Hierarchical Apprenticeship Learning, used to learn the cost functions for route andfootstep planning.

6.4

Recovery and Stabilization Control

As discussed in the previous section, even after planning a full trajectory for thefoot or leg, it is undesirable to simply execute these motions open-loop. During thenatural course of execution, the robot’s feet may slip and possibly loose stability.
Thus, we have implemented a number of low-level recovery and stabilization methods
that continuously monitor the state of the robot and try to either maintain the current
plan, or notify the system when it must replan entirely. We discuss three elements:

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

123

1) stability detection and recovery, 2) body stabilization, and 3) closed-loop footplacement.

6.4.1

Control Elements

Stability Detection and Recovery. Recall that (ignoring friction effects, which do
not play a major role in stability for the LittleDog) the robot is statically stable only
if the projection of the COG onto the ground plane lies within the triangle formedby the supporting feet. If the robot slips while following its trajectory, the COG canmove outside the supporting triangle, causing the robot to tip over. To counteract
this effect, we compute the current support triangle at each time step, based on thecurrent locations of the feet as determined by state estimation. If the COG lies
outside this triangle, then we re-run the walking gait foot and body motion planner.
This has the effect of lowering all the robot’s feet to the ground, then re-shifting the
COG back into the inset support triangle.
Body Stabilization. While sometimes the recovery procedure is unavoidable,
as much as possible we would like to ensure that the COG does not move outside thesupporting triangle, even in light of minor slips. To accomplish this, we adjust thecommanded positions of the supporting feet so as to direct the COG toward its desired
trajectory. In particular, we multiply the commanded positions of the supporting feetby a transformation that will move the robot’s COG from its current position andorientation to its desired position and orientation (assuming the supporting feet are
fixed to the ground).
More formally, let Tdes be the 4 × 4 homogeneous transformation matrix specifying the desired position and orientation of the robot relative to the world frame, andsimilarly let Tcur be the homogeneous transformation specifying the current positionand orientation of the robot relative to the world frame. In addition, let f eet denote the default commanded positions of the supporting feet expressed in the robot’s
frame of reference, based on the desired trajectory for the COG. If we transform thecommanded positions for the feet by−1
Tcur f eet
Tdes

(6.1)

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

124

then (assuming the supporting feet remain fixed) this would move the COG to its desired position and orientation. In practice, to avoid oscillations we apply the smoothedcommand−1(1 − α)f eet + αTdes
Tcur f eet(6.2)

for some 0 < α < 1 (in our experiments we found α = 0.1 to be a good value).
This causes the robot’s COG to move gradually to track the desired trajectory, even
if the robot slips slightly. In addition, we project the desired position Tdes into thecurrent supporting triangle. During our development we found this approach to be
more robust than attempting to move the supporting feet individually to stabilize thebody, as our method keeps intact the relative positions of the supporting feet.
Closed-loop Foot Placement. Finally, we want to ensure that the moving foottracks its desired trajectory as closely as possible, even if the body deviates from its
desired path. To accomplish this, at each time step we compute the desired location of
the foot along its (global) trajectory, and use inverse kinematics based on the current
pose of the robot’s body to find a set of joint angles that achieves the desired footlocation. This is particularly important in cases where the robot slips downward. If
the robot’s body is below its desired position and we merely execute an open loop
trajectory for the moving foot, then the foot can punch into the ground, knocking
the robot over faster than we can stabilize it. Closed-loop foot tracking avoids thisproblem.
It may seem as if there are also cases where closed-loop foot placement could
actually hinder the robot rather than help. For example, if the robot is falling, thenit may be best to simply put its foot down, rather than attempt to keep its foot along
the proper (global) trajectory. However, in our experience this nearly always occurs
in situations where the recovery procedure mentioned previously will catch the robot
anyway, so the closed-loop mechanism rarely affects the system negatively in practice.

6.4.2

Experimental Evaluation

To evaluate the three methods proposed above, we conducted experiments on different
terrains of varying difficulty. Pictures of the terrains and their corresponding heightCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrain #Max Height1
6.4 cm2
8.0 cm3
10.5 cm1254
11.7 cm

PictureHeightmap

Table 6.1: The four terrains used for evaluation of recovery and stabilization procedures.
maps are shown in Table 6.1. We evaluated the performance of our system with andwithout each element described above. In addition, we evaluated the performance ofthe system with none of these elements enabled. As shown in Table 6.2, the controller
with all elements enabled substantially outperforms the controller when disabling anyof these three elements. This effect becomes more pronounced as the terrains become
more difficult: Terrain #1 is easy enough that all the controllers achieve 100% successrates, but for Terrains #3 and #4, the advantage of using all the control elements isclear. Statistically, over all four terrains the full controller outperforms the controller
with no recovery, with no stabilization, with no closed-loop foot placement, and withnone of these elements in terms of success probability with p-values of p = 2.2×10−13 ,p = 0.0078, p = 0.0012, and p = 5.8 × 10−11 respectively, via a pairwise Bernoulli
test.
Subjectively, the failure modes of the different controllers are as expected. Without the stability detection and recovery, the robot frequently falls over entirely afterslipping a small amount. Without body stabilization, the robot becomes noticeably
less stable during small slips, which sometimes leads to falls that even the recovery
routine cannot salvage. Without closed-loop foot placement, the feet can punch into
the ground during slips, occasionally flipping the robot. One interesting effect is thatwithout recovery, the controller actually performs worse with body stabilization andCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrain
1
2
3
4
Total

All
100%
100%
95%
95%
97.5%

w/o Rec.
100%
60%
25%
0%
46.25%

w/o Stab.
100%
95%
55%
75%
81.25%

w/o CLF
100%
95%
75%
85%
88.75%

126

None
100%
55%
35%
35%
56.25%

Table 6.2: Success probabilities out of 20 runs across different terrains for the controller with and without recovery, body stabilization, and closed-loop foot placement.
closed loop foot movement enabled, especially on the more challenging terrains. Thisappears to be due to the fact that when the robot falls significantly (and makes noattempt to recover) both the body stabilization and closed-loop foot placement attempt to make large changes to the joint angles, causing the robot to become lessstable. However, with recovery enabled the robot never strays too far from its desired
trajectory without attempting to re-plan; in this case the advantage of using the bodystabilization and closed-loop foot placement is clear from the experiments above.

6.5

Motion Planning via Cubic Spline Optimization

We now return to the problem of the static walk foot/body motion planner, planning
full foot and body trajectories that move the moving foot from its initial to desired
location while maintaining static stability of the robot. In order to plan smooth
motions, we use cubic splines to parametrize these trajectories, a common approachin robotic applications (Lin et al., 1983). However, the typical usage of cubic splines
within motion planning algorithms suffers from a number of drawbacks. Typically,
one uses a standard motion planning algorithm, such as a randomized planner, togenerate a sequence of feasible waypoints, then fits a cubic spline to these waypoints.
However, due to the stochastic nature of the planner, these waypoints often do notlead to a particularly nice final trajectory. Trajectory optimization techniques (Betts,
1998) can help mitigate this problem to some degree, but they usually involve a slow

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

127

search process, and still typically do not take into account the final cubic spline formof the trajectory.
The basic insight of the method we develop here is that if we initially parametrize
the trajectory as a cubic spline, then in many cases we can accomplish both theplanning and trajectory fitting simultaneously. That is, we can directly optimize thelocation of the cubic spline waypoints while obeying many of the same constraints(or approximations thereof) required by a typical planning algorithm. Specifically,
we show how to plan smooth task-space trajectories — that is, trajectories where
we care primarily about the position of the robot’s end effector — while maintaining
kinematic feasibility, avoiding collision, and limiting velocities or accelerations, all
via a convex optimization problem. Convex optimization problems are beneficial inthat they allow for efficiently finding global optimums (Boyd and Vandenberg, 2004)— this allows us to solve the planning tasks in a few milliseconds using off-the-shelf
software, suitable for real-time re-planning and control.

6.5.1

The Cubic Spline Optimization Algorithm

Cubic Splines Preliminaries
Here we review the standard methods for fitting cubic splines to a series of waypoints
output by a planner. Suppose that a planner outputs some path specified by T + 1
desired time-location pairs(t0 , x⋆0 ), (t1 , x⋆1 ), . . . , (tT , x⋆T )(6.3)

where x⋆i ∈ Rn denotes the desired location of the robot at time ti ∈ R, specified intask space.
Given these waypoints, there is a unique piecewise-cubic trajectory that passes
through the points and satisfies certain smoothness criteria. Specifically, we model
the trajectory between times ti and ti+1 , denoted xi (t) : R → Rn , as a cubic functionxi (t) = ai + bi (t − ti ) + ci (t − ti )2 + di (t − ti )3(6.4)

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

128

where ai , bi , ci , di ∈ Rn are parameters of the cubic spline. The final trajectory
x(t) : R → Rn is a piecewise-cubic function that is simply the concatenation ofthese different cubic trajectories
 x0 (t)..
x(t) =.
 x (t)if t0 ≤ t < t1
(6.5)
if tT −1 ≤ t ≤ tT

T −1

where we can assume that the trajectory is undefined for t < t0 and t > tT .
Given the desired waypoints, there exists a unique set of coefficients {ai , bi , ci , di }i=0,...,T −1such that the resulting trajectory passes through the waypoints and has continuous
velocity and acceleration profiles at each waypoint.2 To compute these coefficients,
we first define the matrices x, a, b, c, d ∈ RT +1×n
x =
a =

h

h

x⋆0

x⋆1

···

a0 a1 · · ·

x⋆T
aT

iT

iT

(6.6)
(6.7)

with b, c, and d defined similarly (we define T + 1 sets of parameters in order tosimplify the equations, though we will ultimately only use the 0, . . . , T −1 parameters,
as described above). Given the x matrix, we can find the parameters of the cubic
splines using the following set of linear equations
a = x

(6.8)

H1 b = H2 x

(6.9)

c = H3 x + H4 b

(6.10)

d = H5 x + H6 b

(6.11)

where the Hi ∈ R(T +1)×(T +1) matrices depend only (non-linearly) on the times t0 , . . . , tT .
The Hi matrices are somewhat complex, but are also well-known, so for brevity we2Technically, in order to ensure uniqueness of the spline we also need to impose a constraint on
the velocity or acceleration of the endpoints, but we ignore this for the time being.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

129

omit the full definitions here; explicit formulas for the matrices as used here are available in the appendix of (Kolter and Ng, 2009b). However, the important point toglean from this presentation is that the parameters of the cubic splines are linear in
the desired locations x. Furthermore, the Hi matrices are all either tridiagonal orbidiagonal, meaning that we can solve the above equations to find the parameters intime O(T ).
Cubic Spline Optimization
In this section we present our algorithm: a method for optimizing task-space cubic
spline trajectories using convex programming. As before, we assume that we are given
an initial plan, now denoted(t0 , x̂0 ), (t1 , x̂1 ), . . . , (tT , x̂T ).

(6.12)

However, unlike the previous section, we will not require that our final cubic trajectory
pass through these points. Indeed, most of the real planning is performed by the
optimization problem itself, and the initial plan is required only for some of theapproximate constraints that we will discuss shortly; an initial “plan” could simply
be a straight line from the start location to the goal location.
The task of optimizing the location of the waypoints while obeying certain constraints can be written formally as
min

f (x)

subject tox∈Cx

where x is the optimization variable, representing the location of the waypoints,
f : R(T +1)×n → R is the optimization objective, and C represent the set of constraints
on the waypoints. In the subsequent sections, we discuss several possible constraints
and objectives that we use in order to ensure that the resulting trajectories are bothfeasible and smooth. The following is not an exhaustive list, but conveys a generalidea of what can be accomplished in this framework.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

130

Additional Variables and Constraints
Spline derivatives at the waypoints. Often we want objective and constraint
terms that contain not only the position of the waypoints, but also the velocity,
acceleration, and/or jerk (derivative of acceleration) of the resulting cubic spline.
Using (6.8) – (6.11), these terms are linear functions of the desired positions, and cantherefore be included in the optimization problem while maintaining convexity. For
instance, since ẋi (ti ) = bi , we can add the constraint
H1 ẋ = H2 x

(6.13)and constrain the these ẋ variables. The same procedure can be used to create
variables representing the acceleration or jerk at each waypoint.
Spline position and derivatives at arbitrary times. Oftentimes we may also
want to constrain the position, velocity, etc, of the splines not only at the waypoints,
but also at the intermediate times. Using the cubic spline formulation, such variables
are also a linear function of the waypoint locations. For example, suppose we wanted
to add a variable x(t′ ) representing the position of the trajectory at time ti < t′ < ti+1 .
Using equations (6.4) and (6.5),x(t′ ) = ai + bi (t′ − ti ) + ci (t′ − ti )2 + di (t′ − ti )3 .

(6.14)

But from (6.8)–(6.11), ai , bi , ci and di are all linear in the desired positions x, so thevariable x(t′ ) is also linear in these variables. The same argument applies to adding
additional variables that represent the velocity, acceleration, or jerk at any time.3
Thus, it should be clear from the discussion above that if we use x′ ∈ RN ×n to denotethe spline positions at a variety of intermediate times, where N denotes the numberof additional times that we are constraining, we can solve for these positions via a3

In theory, if we wanted to ensure that the entire spline obeys a position or derivative constraint,
we would have to add an infinite number of such variables. However, as we will show, in practice we
can obtain good results by introducing a very small number of additional variables, greatly increasing
the practicality of the approach. This same consideration applies to the kinematic feasibility andcollision constraints.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT     

 

(a)

131



(b)

Figure 6.6: Illustration of kinematic feasibility constraints. (a) Kinematically feasible
region for q1 ∈ [−π/2, π/2], q2 ∈ [−2.6, 2.6]. (b) Convex subset of the feasible region.
linear system
x′ = G1 x + G2 ẋ

(6.15)and similarly for other derivatives.
Kinematic feasibility constraints. Since we are specifically focused on planning trajectories in task-space, a key requirement is that points on the spline must
be kinematically feasible for the robot. While the kinematic feasibility region of anarticulated body with joint stops is not typically a convex set, we can usually find asuitable subset of this kinematic region that is convex.
For example, consider the double pendulum shown in Figure 6.6 (which has very
similar kinematics to a 2D view of the LittleDog’s leg). The kinematically feasible
region, when joint one is restricted to the range [−π/2, π/2] and joint two is restricted
to the range [−2.6, 2.6], is shown in Figure 6.6 (a). Although this region is not convex,
we can easily find a convex subset, such as the region shown in Figure 6.6 (b). Thus,
if we constrain motion to occur in some convex subset of the kinematically feasible
region, we can ensure kinematic feasibility while retaining benefits of the convex
optimization procedure.
Collision constraints. Although general collision constraints can be quite difficult to handle in our framework, in many simple cases we can approximate such
constraints using a simple method shown in Figure 6.7. Here Figure 6.7 (a) shows
the initial plan used by the cubic spline optimizer (recall from above such a planneed to be feasible). Two waypoints on this initial trajectory violate the collision
constraint, so we simply add the constraint, at each of these times, that the resulting

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT      
 

(a)

(b)

(c)

132

Figure 6.7: Illustration of collision constraints. (a) Initial (infeasible) plan. (b) Height
constraints imposed to avoid collision with obstacle. (c) Resulting optimized cubic
spline trajectory.
waypoint must lie above the the obstacle by some margin; Figure 6.7 (b) shows thisconstraint, and Figure 6.7 (c) shows the resulting trajectory. This technique is anapproximation, because 1) it only constrains the end-effector position and still could
lead to a collision with the articulated body, 2) it assumes that the x-position of the
waypoints after optimization doesn’t change, when in fact it can and 3) as mentioned
in Footnote 3, these collision constraints are only imposed at a finite number of points,
so we have to insure that the “resolution” of these points is smaller than any thinobstacles. Nonetheless, as we show, this simple approximation works quite well inpractice, and allows us to maintain convexity of the optimization problem.
For some planning problems, adding enough constraints of any of the preceding
types can lead to an infeasible optimization problem. Thus, this approach is notsuited to all planning situations; if plans must traverse through non-convex, narrow“corridors” in the robot’s configuration space, then slower, traditional motion planning algorithms may be the only possible approach. Furthermore, the technique as
described is somewhat specialized to domains, like the LittleDog, where the “up”
direction tends to move the end effector away from obstacles; to handle more general collision constraints it would be necessary to constrain spline positions based on
normals from arbitrary surfaces, but for these types of more complex situations it islikely that the non-convexity of the robot’s free space would cause additional concerns.
However, for situations where our method can be applied, such as the LittleDog planning tasks, our method can produce highly-optimized trajectories extremely quickly.
Optimization Objectives Given the variables and constraints described above,
we lastly need to define our final optimization objective. While we have experimented

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

133

with several different possible optimization objectives, one that appears to work quite
well is to penalize the squared velocities at the waypoints and at a few intermediate
points between each waypoint. More formally, we use the optimization objectiveTf (ẋ, ẋ′ ) = tr ẋT ẋ + tr ẋ′ ẋ′(6.16)

where ẋ represents the velocity at each waypoint and ẋ′ represents the velocities at
the midpoint between each waypoint. This objective has the effect of discouraging
very large velocities at any of the spline points, which leads to trajectories that travel
minimal distances while keeping fairly smooth. However, while this objective works
well for our settings, there are many other possible objective functions that might work
better in other cases such as minimizing the maximum velocity, average or maximum
acceleration, average distance between spline points, or (using approximations basedon the Jacobians along the initial trajectory) average or maximum joint velocities or
torques.
One objective that cannot be easily minimized is the total time of the trajectory,
because equations (6.8)–(6.11) involve non-linear, non-convex functions of the times.
However, there has been previous work in approximately optimizing the times of cubic
splines (Cao et al., 1997; Park et al., 1997; Vaz and Fernandes, 2006), and if the total
time of the trajectory is ultimately the most important objective, these techniques
can be applied.
Application to Fast Foot/Body Motion Planning
Here we describe how the cubic spline optimization technique can be applied to thetask of planning foot and body trajectories for the static walking gait. Recall thatthe basic planning task that we are considering is as follows: given a current positionof the robot and an upcoming footstep, plan trajectories for the feet and robot centerof gravity (COG) that achieves this footstep, while requiring that the COG andfoot locations are kinematically feasible, collision free, and maintain static stability.
Although the footstep planner plans one footstep at a time, in practice we plan
trajectories here for two steps at a time to ensure that the COG ends in a desirable

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

134

Figure 6.8: Foot planning task, and initial trajectory.
location for the next step.

6.5.2

Planning Foot Trajectories

An illustration of the foot trajectory planning task is shown in Figure 6.8, alongwith the initial plan we supply to the cubic spline optimization. The initial plan
is a simple trapezoid, with three waypoints allocated for the upward and downward“ramps”, and the remaining waypoints in a line, spaced in 2cm intervals. We use theCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

135

following optimization problem to plan the foot trajectories:min′′

x,x ,ẋ,ẋ ,ẍT

tr ẋT ẋ + tr ẋ′ ẋ′(6.17)

subject to H1 ẋ = H2 x
1ẍ = (H3 x + H4 ẋ)2′x = G1 x + G2 ẋ

(6.18)(6.19)(6.20)ẋ′ = G3 x + G4 ẋ

(6.21)

x0,: = x̂0 , xT,: = x̂T , ẋ0,: = 0, ẋT,: = 0(6.22)

ẍt,x ≥ 0, ẍt,y ≥ 0, t = 0, 1

(6.23)

ẍt,x ≤ 0, ẍt,y ≤ 0, t = T − 1, T)ẍt,x ≥ ẍt+1,xt = 2, . . . , T − 3ẍt,y ≥ ẍt+1,y(6.24)

ẍt,z < 0, t = 2, . . . , T − 2(xt,x − xt+2,x )2 + (xt,y − xt+2,y )2≤ (3cm)2 ,t = 0, T − 2

x′ i,z ≥ x̂z (t′i ) + 2cm,

i = 1, . . . , N

xt,z ≤ max x̂z (t′i ), t = 1, . . . T.
i=1,...,N(6.25)(6.26)(6.27)(6.28)(6.29)

While there are many different terms in this optimization problem, the overall idea isstraightforward. The optimization objective (6.17) is the squared velocity objective
we discussed earlier; constraints (6.18)–(6.21) are the standard cubic spline equations
for adding additional variables representing respectively the velocity at the waypoints,
the acceleration at the waypoints, additional position terms, and additional velocity
terms;4 (6.22) insures that the spline begins and ends at the start and goal, with zero
velocity; (6.23) and (6.24) ensure that the x, y accelerations are positive (negative) at
the start (end) ramp, which in turn ensures that the trajectory will never overshoot4

In greater detail, we add four additional velocity terms, in the midpoints of the waypoints on
the “ramp” portion of the initial trajectory. We add N additional position terms, one at each 1cm
interval along the top portion of the initial trajectory.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

136

the start and end locations;5 (6.25) extends the previous constraint slightly to also
ensure that the x, y accelerations during the main trajectory portion are monotonic;(6.26) forces the z accelerations during the main portion of the trajectory to be
negative, which ensures that the spline moves over any obstacles in one single arch;(6.27) ensures that the last waypoints in the ramp don’t deviate from the start andend positions by more than 3cm; finally, (6.28) and (6.29) ensure that the z positionof the spline is 2cm above any obstacle, and that no waypoint is more than 2cm higher
than the tallest obstacle (here x̂z (ti ) denotes the height of the terrain at time ti along
the initial trajectory). This particular set of objectives and constraints were developed
specifically for the foot trajectory planning task, and many of the constraints weredeveloped over time in response to specific situations that caused simpler optimization
problems to produce sub-optimal plans.
Planning COG Trajectories
The aim of planning a trajectory for the COG is twofold: maintaining stability of therobot while allowing the feet to reach their targets. Thus, we want to position the
body so as to maintain kinematic feasibility for the moving feet, and keep the robot’s
COG in the support triangle; since we are planning for two steps, when planning the
body movement for a back foot step we require the COG to be in a double support
triangle, which is stable for both steps (see, e.g., (Kolter et al., 2008b)). We always
use nine waypoints in the COG trajectory splines: three to move the COG into the
supporting triangle, and three for each foot movement. Since planning the COG
trajectory requires knowledge of the foot locations, we first use the method above toplan trajectories for the moving feet, which we denote xf1 (t) and xf2 (t). We then use
5This constraint and next assume that the x̂0,x ≤ x̂T,x and x̂0,y ≤ x̂T,y . In the case that theseinequalities are reversed, the corresponding inequalities in the constraints are also reversed.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

137

the following optimization problem to plan the COG trajectory:T

tr ẋT ẋ + tr ẋ′ ẋ′Pmin′ +λ 5i=3 feas(xi,: , xf1 (ti ), f1 )x,ẋ,ẋP+λ 7i=5 feas(xi,: , xf2 (ti ), f2 )subject to H1 ẋ = H2 x(6.30)(6.31)ẋ′ = G3 x + G4 ẋ

(6.32)

x0,: = x̂0 , ẋ0 , x2,: = x̂2 , x8,: = x̂8(6.33)

ẋ0,: = ẋinit(6.34)

xi,: ∈ S, i = 3, . . . , 7(6.35)

feas(xbody , xfoot , f )(6.36)

where

denotes the squared distance from xfoot to the kinematically feasible region of foot f ,given that the COG is positioned at point xbody , and where S denotes the support triangle. Intuitively, the optimization objective (6.30) is a weighted combination of thekinematic infeasibility of the moving feet plus the velocity terms we discussed earlier— in practice, we choose λ = 100 to try to make the system as close to kinematicallyfeasible as possible, and only later try to minimize the velocities; constraints (6.31)
and (6.32) are again the standard cubic spline equations for velocity terms — here
we add eight additional velocity terms, one at the midpoint of each two waypoints;(6.33) ensures that the trajectory begins, enters the supporting triangle, and ends at
the initially specified waypoints, while (6.34) ensures that the initial velocity of the
spline is equal to the COG’s current velocity; finally, (6.35) ensures that the COG
waypoints will be inside the supporting triangle during the times that the feet are
moving. Since the optimization problem treats distance to the feasible set as an optimization objective rather than a constraint, there is no concern that the optimizer
will fail to find a solution.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

0.6

x (m)

0.06
0.05
0.04

0.5
0.4
0.3

0.03

0.1

0.2

0.3

0.4

0.5

0.6

0

0.1

0.2

0.3

0.4

0.5

0.6

0

0.1

0.2

0.3

0.4

0.5

0.6

−0.06

y (m)

0.02

z (m)

138

0.01
0

TerrainDesired Trajectory

−0.01

−0.08
−0.1
−0.12

Trajectory Waypoints

0.1

z (m)

−0.02
−0.03
−0.04
0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0.16

0.05

0.18
0

xy (m)

Time (s)Figure 6.9: Typical example of a foot trajectory generated by the algorithm. The
top figure shows the resulting trajectory in 3D space, while the bottom shows eachcomponent as a function of time.
0

Desired Trajectory

0.1

x(m)

Trajectory Waypoints−0.02

Support Triangle

0.05

0

−0.04

0

0.2

0.4

0.6

0.8

1

1.2

1.4

0

0.2

0.4

0.6

0.8

1

1.2

1.4

0

0.2

0.4

0.6

0.8

1

1.2

1.4

y (m)

y (m)

0
−0.06

−0.08

−0.02
−0.04
−0.06
0.04

−0.12
−0.02

z (m)

−0.1

0

0.02

0.04

0.06

0.08

0.1

0.12

x (m)

0.03
0.02
0.01
0

Time (s)Figure 6.10: Typical example of a COG trajectory generated by the algorithm.

6.5.3

Experimental Evaluation

The cubic spline optimization procedure is used for all the experiments reported in
Section 6.7, but here we evaluate this specific component of the system. We begin
with a qualitative look at the trajectories generated by this method. Figure 6.9 showsa typical footstep trajectory generated by this method. As we can see, the trajectory
moves the foot from its initial location to the desired location in one fluid motion,
stepping high enough to avoid any obstacles. Likewise, Figure 6.10 shows a typically
COG trajectory generated by the algorithm. Notice that the trajectory inside thesupporting triangle is not just a straight line: the algorithm adjusts the trajectory inthis manner to maximize the kinematic feasibility of the moving feet.
Of course, while examining the splines in this manner can help give an intuition
about kind of trajectories generated by our algorithm, we are ultimately interested

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrainMax Height1
6.4 cm139

2
10.4 cm

PictureHeightmap

Table 6.3: The training and testing terrains used to evaluate the cubic spline trajectory planning on LittleDog..

Metric% Successful Trials
Speed (cm/sec)
Avg. Tracking Error (cm)Avg. # Recoveries

Easy Terrain(1)CSO
Previous
100%
100%
7.02 ± 0.10 5.99 ± 0.07
1.28 ± 0.03 1.40 ± 0.06
0.0
0.0

Challenging Terrain(2)CSO
Previous
100%
70 %6.30 ± 0.12 5.59 ± 0.31
1.27 ± 0.05 1.55 ± 0.09
0.5 ± 0.37 2.22 ± 1.45

Table 6.4: Performance of cubic spline optimization on the two quadruped terrains.
Terms include 95% confidence intervals where applicable.

in whether or not the method actually improves performance on the LittleDog. To
evaluate this, we tested the system on two terrains of varying difficulty, shown in
Table 6.3. We compare the cubic spline optimization approach to an older trajectory
planning method described in (Kolter et al., 2008b), which uses simple box-shapes tostep over terrain, and linear splines for moving the COG.
Table 6.4 shows the performance of the quadruped both with and without the
cubic spline optimization. We ran 10 trials on each of the terrains, and evaluated thesystems using 1) fraction of successful runs, 2) speed over terrain, 3) average numberof “recoveries,” as specified by the method of the previous section and 4) average
tracking error (i.e., distance between the planned and actual location) for the moving

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

140

foot. Perhaps the most obvious benefit of the cubic spline optimization method isthat the resulting speeds are faster; this is not particularly surprising, since the splines
output by our planner will clearly be more efficient than a simple box pattern overobstacles. However, equally important is that the cubic spline optimization also leads
to more robust behavior, especially on the challenging terrain: the previous method
only succeeds in crossing the terrain 70% of the time, and even when it does succeed
it typically needs to execute several recoveries, whereas the cubic spline optimization
method crosses the terrain in all cases, and executes many fewer recoveries. We
believe that this is because the cubic spline method attempts to maintain kinematic
feasibility of the moving foot at all times. This is seen in Table 6.4 from the fact thatthe cubic spline optimization approach has lower tracker error, implying more accurate
placement of feet, and therefore greater robustness is challenging environments.

6.6

Cost Learning via Hierarchical Apprenticeship
Learning

Recall that both the route planner and footstep planner make use of cost maps,
functions which indicate, for every point on the terrain, the goodness of placing therobot’s center or a foot at that location. However, it is very challenging to specify
a proper cost function manually, as this requires quantifying the trade-off between
many features, including progress toward a goal, the height differential between feet,the slope of the terrain underneath the feet, etc. Because of this, we adopt a method
known as apprenticeship learning, based upon the insight that often it is easier foran “expert” to demonstrate the desired behavior than it is to specify a cost functionthat induces this behavior. In the footstep planning example, for instance, it may
be challenging to manually specify the weights of a cost function that leads to goodfootsteps; however, it is much easier, for example after seeing the robot step in a poor
location on the terrain, to indicate a better location for its footstep. Apprenticeshiplearning has been successfully applied to many other robotics domains, and is anatural fit for such problems (Abbeel and Ng, 2004; Ratliff et al., 2006; Neu andCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

141

Szepesvári, 2007).
However, a difficulty arises in applying existing apprenticeship learning methods
to a task like the LittleDog. Typical apprenticeship learning algorithms require theexpert to demonstrate a complete trajectory from the start to the goal, which in thiscase corresponds to a complete set of footsteps across the terrain; this itself is a highly
non-trivial task, even for an expert. Motivated by these difficulties, we developed forthis task an algorithm for hierarchical apprenticeship learning. Our approach is basedon the insight that, while it may be difficult for an expert to specify entire optimal
trajectories in a large domain, it is much easier to “teach hierarchically”: that is, if
we employ a hierarchical control scheme to solve our problem, it is much easier forthe expert to give advice independently at each level of this hierarchy. At the lower
levels of the control hierarchy, our method only requires that the expert be able todemonstrate good local behavior, rather than behavior that is optimal for the entire
task. This type of advice is often feasible for the expert to give even when the expert
is entirely unable to give full trajectory demonstrations. Thus the approach allows
for apprenticeship learning in extremely complex, previously intractable domains. We
first present the general hierarchical apprenticeship learning algorithm, then describe
its application to route and footstep planning.

6.6.1

The Hierarchical Apprenticeship Learning Algorithm

Definitions
To describe the hierarchical apprenticeship learning algorithm (abbreviated HAL),
we use the formalism of Markov Decision Processes (MDPs), as described briefly in
Chapter 2. To review, an MDP is a tuple (S, A, P, D, H, C), where S is a set of states;
A is a set of actions, P : S × A → S is a set of state transition probabilities; D isa distribution over initial states; H is the horizon which corresponds to the numberof time-steps considered; and C : S → R is a cost function.6 We use the notation
MDP\C to denote an MDP minus the cost function. A policy π is a mapping from
6

Here we assume the cost does not depend on the action, though the extension to state-action
costs is straightforward.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

142

states to a probability distribution
overhP
i actions. The value or cost-to-go of a policy π
His given by J(s, π) = E
t=0 C(st )|π , where the expectation is taken with respect tothe random state sequence s0 , s1 , . . . , sH , with s0 drawn from D, and picking actions
according to π.
Often the cost function C can be represented more compactly as a function of thestate. Let φ : S → Rn be a mapping from states to a set of features. We consider thecase where the cost function C is a linear combination of the features
C(s) = wT φ(s)(6.37)

for parameters w ∈ Rn . Then we have that the value of a policy φ is linear in thesecost function weights
J(π) = E

" H
X
t=0

C(st ) π

#

=E

" H
X
t=0

T

w φ(st ) π

#

T

=w E

" H
X
t=0

#

φ(st ) π ≡ wT µφ (π)

where we used linearity of expectation to bring w outside of the expectation. The
P
last quantity defines the vector of feature expectations µφ (π) = E[ Ht=0 φ(st )|π].
Cost Decomposition in HAL
At the heart of the HAL algorithm is a simple decomposition of the cost function thatlinks the two levels of control. Suppose that we are given a hierarchical decompositionof a control task in the form of two MDP\Cs — a low-level and a high-level MDP\C,denoted Mℓ = (Sℓ , Aℓ , Tℓ , Hℓ , Dℓ ) and Mh = (Sh , Ah , Th , Hh , Dh ) respectively — and apartitioning function ψ : Sℓ → Sh that maps low level states to high-level states (theassumption here is that |Sh | ≪ |Sℓ | so that this hierarchical decomposition actuallyprovides a computational gain). For example, for the LittleDog planner task the
low-level MDP\C is the footstep planning domain, where the state consists of all four
foot locations, whereas the high-level MDP is the route planning domain, where thestate consists of only the robot’s center. As standard in apprenticeship learning, we
suppose that the cost in the low-level MDP\C can be represented as a linear functionof state features, C(sℓ ) = wT φ(sℓ ). The HAL algorithm then assumes that the cost

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

143

of a high-level state is equal to the average cost over all its corresponding low-levelstates. Formally
C(sh ) ==1
N (sh )1
N (sh )

X

C(sℓ )

XwT φ(sℓ ) =sℓ ∈ψ −1 (sh )sℓ ∈ψ −1 (sh )1wT
N (sh )

X

(6.38)
φ(sℓ )sℓ ∈ψ −1 (sh )where ψ −1 (sh ) denotes the inverse image of the partitioning function and N (sh ) =|ψ −1 (sh )|. While this may not always be the most ideal decomposition of the costfunction in many cases—for example, we may want to let the cost of a high-levelstate be the minimum of its low level state costs to capture the fact that an ideal
agent would always seek to minimize cost at the lower level, or alternatively the
maximum of its low level state costs to be robust to worst-case outcomes—it captures
the idea that in the absence of other prior information, it seems reasonable to assume
a uniform distribution over the low-level states corresponding to a high-level state.
An important consequence of (6.38) is that the high level cost is now also linear in the
low-level cost weights w. This will enable us in the subsequent sections to formulatea unified hierarchical apprenticeship learning algorithm that is able to incorporate
expert advice at both the high level and the low level simultaneously.
Expert Advice and a Convex Formulation
As in standard apprenticeship learning, expert advice at the high level consists offull policies demonstrated by the expert. However, because the high-level MDP\C
can be significantly simpler than the low-level MDP\C, this task can be substantially(i)easier. If the expert suggests that πh,E is an optimal policy for some given MDP\C(i)

Mh , then this corresponds to the following constraint, which states that the expert’s
policy outperforms all other policies:
(i)

(i)

(i)

J (i) (πh,E ) ≤ J (i) (πh ) ∀πh .

(6.39)

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

144

Equivalently, using (6.38), we can formulate this constraint as follows
(i)

(i)

(i)

(i)

wT µφ (πh,E ) ≤ wT µφ (πh ) ∀πh .
(i)(6.40)(i)and where in practice we will use observed feature counts µ̂φ (πh,E ) in lieu of the true
expectations.
Our approach differs from standard apprenticeship learning when we consider
advice at the low level. Unlike the apprenticeship learning paradigm where an expert
specifies full trajectories in the target domain, we allow for an expert to specify single,
greedy actions in the low-level domain. Specifically, if the agent is in state sℓ and theexpert suggests that the best greedy action would move to state s′ℓ , this corresponds
directly to a constraint on the cost function, namely thatC(s′ℓ ) ≤ C(s′′ℓ )(6.41)

for all other states s′′ℓ that can be reached from the current state (we say that s′′ℓis “reachable” from the current state sℓ if ∃a s.t.Psℓ a (s′′ℓ ) > ǫ for some 0 < ǫ ≤ 1).
This is equivalent to the following constraint on the constraints on the cost function
parameters w,
wT φ(s′ℓ ) ≤ wT φ(s′′ℓ )(6.42)

for all s′′ℓ reachable from sℓ .
Since the high level and low level expert advice are both given as linear constraints on the features w, we can combine both types of advice into a single convex
optimization problem. To resolve the ambiguity in w, and to allow the expert toprovide noisy advice, we use regularization and slack variables (similar to standard
SVM formulations), which results in the optimization problem
m
n
X
X
1
kwk22 + λℓ
ξ (j) + λh
η (i)w,η≥0,ξ≥0 2
j=1
i=1

min

(j)

(j)

(j)

s.t.wT φ(s′ℓ ) ≤ wT φ(s′′ℓ ) − 1 + ξ (j) ∀s′′ℓ , j
(i)

(i)

(i)

(i)

wT µ̂φ (πh,E ) ≤ wT µφ (πh ) − 1 + η (i) ∀πh , i.

(6.43)

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

145

(i)

where πh indexes over all high-level policies, ηi and ξi are slack variables, i indexes
over all MDPs, s′′ℓ (j) indexes over all states reachable from s′ℓ (j) and j indexes over all
low-level demonstrations provided by the expert, and λh and λℓ are a regularization
parameters. Despite the fact that there are an exponential number of possible policies
we can solve this optimization problem using a number of techniques, including dual
formulations (Taskar et al., 2005), subgradient algorithms (Ratliff et al., 2006), andconstraint generation (Tsochantaridis et al., 2005). We use a method based on thislast approach, and use the following constraint generation algorithm:
1. Begin with no expert path constraints.
2. Find the current cost weights by solving the current optimization problem.
3. Solve the reinforcement learning problem at the high level of the hierarchy tofind the optimal (high-level) policies for the current cost for each MDP\C, i. If
the optimal policy violates the current (high level) constraints, then add thisconstraint to the current optimization problem and go to Step (2). Otherwise,
no constraints are violated and the current cost weights are the solution of the
optimization problem.
Solving this optimization problem provides us with a single cost function that is
consistent with the expert advice both for the low and high levels.

6.6.2

Application to Cost Map Learning

As mentioned briefly in the previous section, the application of the HAL algorithm toroute and footstep planning is conceptually straightforward: the route planner takes
the place of the high-level planner and the footstep planner takes the place of the
low-level planner.
Of course, a crucial element of the actual implementation of this approach isdetermining what features to use to represent the cost function for the footstep andhigh-level planner. We use the following set of features (note that for a given pointon the terrain we actually form four feature vectors, one corresponding to each foot,with local features properly reflected to account for symmetry of the robot):

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT146• At each point in the height map (discretized at a resolution of 0.5 cm), we
consider local heights maps of different sizes (squares of 5, 7, 11, and 21 gridcells around the current point), and generate five features for each of thesemaps: 1) standard deviation of the heights, 2) average slope in the x direction,3) average slope in the y direction 4) maximum height relative to the center
point and 5) minimum height relative to the center point, for a total of 20
features.
• A boolean feature indicating whether or not the foot location leads to a collision
when the robot is placed in its default position.
• The distance of the point from the desired foot location (i.e., the location thatthe footstep planner would place its foot if all costs were equal).
• The area and in-radius of the support triangle formed by the stationary feet for
the upcoming step.
• A constant value.
While the first two features above can be generated once before execution, the second
two require the actual pose of the robot, and so are generated in real time by thefootstep planning mechanism. This leads to a cost function that is a linear functionof 25 state features.
To form the cost for the high-level route planner, we aggregate features fromthe footstep planner. In particular, for a given center location of the robot’s body
we consider all the footstep features within a 3 cm radius of the each foot’s default
position, and aggregate these features to form the features for the route planner. Notethat the features above that can only be generated during execution (the distancefrom the desired footstep, the area and in-radius of the support triangle) will be thesame for each high-level center location, and so can be ignored, allowing us to run
the route planner prior to any execution. While this cost function is naturally anapproximation, we found that it performed very well in practice, possibly due to its
ability to account for stochasticity of the domain.

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrainMax Height

Training
8.0 cm147

Testing
11.7 cm

PictureHeightmap

Table 6.5: The training and testing terrains used to evaluate HAL.

Figure 6.11: High-level (route) expert demonstration.

6.6.3

Experimental Evaluation

While the results that we present in Section 6.7 will all use the cost function learned
using this algorithm, in this section we present results explicitly demonstrating theperformance of the system with and without the HAL algorithm. All experiments
were carried out on two terrains: a relatively easy terrain for training, and a significantly more challenging terrain for testing, shown in Table 6.5. To give advice at
the high level, we specified complete body trajectories for the robot’s center of mass,
as shown in Figure 6.11. To give advice for the low level we looked for situations

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

148

Figure 6.12: Low-level (footstep) expert demonstration.
HAL
Feet Only
Path Only
No Learning

Training
31.03
33.46
—
45.70

Testing
33.46
45.70
—
—

Table 6.6: Execution times for different constraints on training and testing terrains.
Dashes indicate that the robot fell over and did not reach the goal.
in which the robot stepped in a suboptimal location, and then indicated the correct
greedy foot placement (by clicking on a point in the terrain in a computer interface),as shown in Figure 6.12. The entire training set consisted of a single high-level pathdemonstration across the training terrain, and 20 low-level footstep demonstrations
on this terrain; it took about 10 minutes to collect the data. The general cost map
that was learned, as expected, typically preferred flat areas over areas close to a cliff,
but the precise trade-offs implied by the learned cost function are difficult to evaluate
except with respect to the resulting performance.
Even from this small amount of training data, the learned system achieved excellent performance, not only on the training board, but also on the much more difficult
testing board. Figure 6.13 shows the route and footsteps taken for each of the different
possible types of constraints, which shows a very large qualitative difference between
the footsteps chosen before and after training. Table 6.6 shows the crossing times foreach of the different types of constraints. As shown, the HAL algorithm outperforms

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

149

Figure 6.13: Body and footstep plans for different constraints on the training(left) and testing (right) terrains: (First/Red) No Learning, (Second/Green) HAL,
(Third/Blue) Path Only, (Fourth/Yellow) Footstep Only.
all the intermediate methods. Using only footstep constraints does quite well on the
training board, but on the testing board the lack of high-level training leads the robot
to take a very roundabout route, and it performs much worse. The LittleDog fails at
crossing the testing terrain when learning from the path-level demonstration only or
when not learning at all.

6.7

Learning Locomotion Program Results

While the previous sections have included results as a means of evaluating the various
approaches, here we present the results of our system in the official tests of the
Learning Locomotion program. As discussed in Section 6.2, the Learning Locomotion
program consisted of three phases, each with specific metrics in terms of the speed
and terrain height: for Phase I, the metric was 1.2 cm/s over 4.8 cm obstacles; forPhase II, 4.2 cm/s over 7.8 cm obstacles; and for Phase III, 7.2 cm/s over 10.8 cm

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrain Type
Rocks
Slope
Steps
Modular Rocks
BarrierModular Logs
Gap
Average

150

Average Speed
5.6 cm/s
6.5 cm/s
5.4 cm/s
7.4 cm/s
5.9 cm/s
7.2 cm/s
5.9 cm/s
6.3 cm/s

Table 6.7: Speeds for Phase II system and terrains. Average speed is based upon
the best two out of three runs. We received no information as to whether the system
based all 3/3 test or only 2/3, but all test passed at least 2/3 of the runs.
obstacles. As the metric evaluations were much more standardized in Phases II and
III than in Phase I, we present here our results for these later phases of the project,along with analysis about how we obtained these results.
For Phase II and Phase III, the testing procedures operated as follows. Throughout each phase, all the teams had access to seven terrain boards of various types (thedifferent types are listed in the tables below), known as the “A” terrains. For the
final metric evaluations, all teams were tested on a different set of terrains (the “B”
terrains) that were informally from the same “class” of obstacles as the A boards,
but which were not available prior to the tests. Teams did have the opportunity test
a very limited number of times on these boards prior to the final metric tests, but received no information other than the number of times the system successfully crossed
and the speed of the gait. Thus, the tests below represent an evaluation on terrainthat truly was novel to the robot, and required that the robot be able to adapt tosituations that we could not simply hand-engineer.
Table 6.7 shows our performance on the Phase II metrics. For Phase II, ourresearch was focused entirety on static gaits: the static gait described in Section 6.3
was built in its entirely during Phase II, with only small changes in Phase III to allow
for the ability to switch to other gaits in real-time. We made use of no specialized
maneuvers or trotting, so run times for all the different terrains were similar (themore challenging rocks and steps were slightly slower, but there was ultimately little

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOTTerrain TypeGap
Barrier
Sloped Rocks
Modular Rocks
Logs
Steps
Average
Side Slope
V-ditchScaled Steps

151

Average Speed Success13.1 cm/s
3/3
13.2 cm/s
3/3
5.7 cm/s
3/3
11.3 cm/s
3/3
4.8 cm/s
3/3
6.2 cm/s
3/3
9.7 cm/s
3/3
23.7 cm/s
2/3
16.8 cm/s
3/3
6.6 cm/s
2/3

Table 6.8: Speeds and success rates for Phase III system and terrains. Average speed
is based upon best two runs. The first six terrains represent the “standard” Phase
III tests, while the last three represent three additional optional terrains. The video
references in the text shows all nine terrains.
variation in the run times).
Table 6.8 shows our performance on the Phase III metrics. Unlike Phase II, forPhase III our focus was entirely on dynamic gaits, in particular the trot and thespecialized maneuvers. Ultimately, we were able to develop controllers that allowed
us to use trots and specialized maneuvers for all but two of the terrains: the sloped
rocks and the logs. Predictably, our running times on these terrains were similar
to our Phase II running times (even a bit slower for the logs, owing to the added
difficulty of the higher obstacles), but were much faster for terrains where we could
exploit dynamic gaits. Nonetheless, the results from this phase also served to convince
us that, while dynamic gaits are suitable to many scenarios, static walking still serves
a genuine purpose for robots similar to the LittleDog: despite extensive development,
we were unable to achieve reliable performance from dynamic behavior on either thesloped rocks or the logs terrains. Thus, we feel that robots which can exhibit boththese modes of locomotion will be the most interesting research testbeds in the years
to come.
Detailed performance results for all teams during the testing have not been officially released, so we compare only briefly to the other teams. Our average speedin Phase II was the highest of all six competing Learning Locomotion teams, andCHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

152

we crossed all terrains above metric speed; our average speed was the second highest
during Phase III though other teams crossed more terrains above the metric speed.
Videos of the our robot crossing all the Phase III terrains (only the “A” boards, but
the performance on these boards was virtually identical to the performance on themetric “B” boards), are available at: http://ai.stanford.edu/~kolter/ijrr09ld.

6.8

Summary

In this chapter we have presented a software system for a quadruped robot that allows
it to quickly and reliably negotiate a wide variety of challenging terrain, using both
static and dynamic modes of locomotion. The techniques we apply to this task, inparticular the constant use of rapid recovery and replanning methods, are motivatedby the inability to develop an accurate model of the LittleDog system. Despite thisdifficulty in modeling, we show our system is able to quickly and robustly cross awide variety of challenging terrains. While we have developed a substantial system
for this work, capable of navigating terrains well beyond what quadrupeds robots
could handle when this work began, the research has also lead to new topics anddirections.
Advanced robot hardware and compliance. Although the LittleDog is acapable robotic platform, other legged robots have significantly greater physical capabilities. Compliant legs, in particular, able to store energy from impacts and providing a purely mechanical means of adjusting to some level of irregularity, offer alarge potential advantage over the relatively stiff legs of LittleDog. An important
topic for future work involves how to extend the careful planning methods developedon the LittleDog to these more compliant and mechanically robust robotic systems.
And while these additions further the mechanical capability of the robot, they canbe correspondingly harder still to model accurately, and thus methods that function
with inaccurate models are a priority here.
Onboard vision. Related to the goal of bringing these robots into the realworld, we do of course have to recognize that most of the work we present in thischapter has been conducted in a highly idealized setting, where we have full knowledge

CHAPTER 6. APPLICATION TO THE LITTLEDOG ROBOT

153

Figure 6.14: Prototype system with onboard stereo camera, and snapshots of thesystem crossing one of the more difficult terrains, using only onboard vision.
of the terrain at run-time, and nearly flawless sensing. If the robots are to moveoutside the lab, we need vision which is completely on-board. We have pursued this
topic a fair amount in tandem with the research presented here, and in Kolter et al.
(2009) we present a prototype of a stereo vision system for the LittleDog, which
is able to cross one of the more challenging terrains from the Learning Locomotion
project (the Phase II rocks terrain, used as the challenging terrain in Section 6.5)
using only onboard vision for both localization and mapping. Figure 6.14 shows thisprototype system, as well as snapshots of it crossing this terrain. However, the robot
admittedly moves much slower and less robustly when it uses only onboard vision,and a major direction for future research involves increasing the capability of visionsystems such that they can compete with the offboard vision systems we have used
for the majority of this work. In addition, such systems could be integrated withthe existing system to provide a smooth degradation in the quality of perception,
making it possible to determine with greater precision how trade-offs in perception
accuracy affect performance. Finally, this work again raises the issue of inaccurate
models, as imperfect knowledge of the terrain near the robot corresponds exactly to
an inaccurate or uncertain model of the robot’s dynamics; thus, techniques that canhandle such imperfect information are key to this work.

Chapter 7
Conclusion
A key challenge in applying model-based Reinforcement Learning and optimal control
methods to complex dynamical systems, such as those arising in many robotics tasks,
is the difficulty of obtaining an accurate model of the system. These algorithms
perform very well when they are given or can learn an accurate dynamics model, but
often times it is very challenging to build an accurate model by any means: effects
such as hidden or incomplete state, dynamic or unknown system elements, and othereffects, can render the modeling task very difficult.
This work has proposed a number of algorithms and empirical demonstrations
for dealing with such situations. In particular, we have develop three algorithms for
exploiting inaccurate models in different manners. We presented the Policy Gradientwith the Signed Derivative algorithm, an approximate policy gradient method thatenables us to learn policy parameters using a model that must only capture the correct
signs of certain matrix derivative terms. We also presented a dimensionality reduction
method for policy search, which uses a distribution over inaccurate models to identify
a linear subspace of controllers, then learns an element from this subspace on thereal system. Finally, we developed a probabilistic method for combining inaccurate
models and observed trajectories, using a method we call Multi-model LQR, to achievea mixture of open-loop and closed-loop behavior for control tasks where we cannot
model the system accurately in certain regions.
In addition to these algorithms, a key contribution of this work has been the154CHAPTER 7. CONCLUSION

155

application of these methods to challenging tasks in robotic control. In particular,
several of the algorithms we present here were applied to the LittleDog robot, a small
quadruped robot, and have enabled it to cross a wide variety of complex terrain,including jumping over large obstacles, and quickly following complex motion paths.
We also use the methods to enable a full-sized autonomous car to perform a “powerslide” maneuvers, accurately skidding the car sideways into a narrow parking spot. In
both cases, the applications demonstrate state-of-the-art results on these challenging
control tasks.
Looking forward, several key challenges emerge as directions for future work. Algorithmically, one of the key challenges for such methods is finding the proper integration with learning or adaptive control approaches. While the work in this thesis
avoided the issue of directly learning a model, or tried to exhaust all options for modelbuilding before applying the described algorithms, the fields of machine learning forcontrol and adaptive control have also shown great abilities to control and model
complex systems. While this work has specifically looked at the question of what canbe done without learning any accurate model (and rather learning an control policy
directly, in many cases), the most powerful techniques are likely to come from aniterative combination of both using these algorithms to address those model elementsthat truly cannot be learned, and adaptive control or machine learning techniques toaddress those elements that can be modeled.
From an application standpoint, there remains many challenging problems in both
quadruped locomotion and “extreme” autonomous driving. One of the primary challenges with the LittleDog robot is that it was not intended for the high-speed dynamic
maneuvers that we focus on for much of this work. Indeed, more capable robotic systems will both greatly enhance the ability of quadruped robots, and also will likely
require yet more methods for dealing with inaccurate models, as the additional mechanical complexity only compounds the difficulties in modeling. Likewise, accurate
control of autonomous vehicles in all modes at the limits of handling remains a challenging open problem, and one which will likely require a combination of advanced
modeling techniques, along with algorithms that can deal with inaccurate models to
overcome these difficulties.

Bibliography
Abbeel, P. and Ng, A. Y. (2004). Apprenticeship learning via inverse reinforcement
learning. In Proceedings of the International Conference on Machine Learning.
Abbeel, P. and Ng, A. Y. (2005). Exploration and apprenticeship learning in reinforcement learning. In Proceedings of the International Conference on Machine
Learning.
Abbeel, P., Quigley, M., and Ng, A. Y. (2006). Using innaccurate models in reinforcement learning. In Proceedings of the International Conference on Machine
Learning.
Anderson, B. D. O. and Moore, J. B. (1989). Optimal Control: Linear Quadratic
Methods. Prentice-Hall.
Anderson, C. W. (1986). Learning and Problem Solving with Multilayer Connectionist
Systems. PhD thesis, University of Massachusetts.
Ando, R. K. and Zhang, T. (2005). A framework for learning predictive structuresfrom multiple tasks and unlabeled data. Journal of Machine Learning Research,
6:1817–1853.
Anthony, M. and Bartlett, P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge University Press.
Argyriou, A., Evgeniou, T., and Pontil, M. (2006). Multi-task feature learning. In
Neural Information Processing Systems.

156

BIBLIOGRAPHY

157

Argyriou, A., Micchelli, C. A., Pontil, M., and Ying, Y. (2007). A spectral regularization framework for multi-task structure learning.
Armijo, L. (1966). Minimization of functions having Lipschitz continuous first partial
derivatives. Pacific Journal of Mathematics, 16(1):1–3.
Astrom, K. J. and Wittenmark, B. (1994). Adaptive Control. Prentice Hall.
Atkeson, C. G. and Santamaria, J. C. (1997). A comparison of direct and model-based
reinforcement learning. In International Conference on Robotics and Automation.
Atkeson, C. G. and Schaal, S. (1997). Learning tasks from a single demonstration.
In Proceedings of the International Conference on Robotics and Automation.
Bagnell, J. A., Kakade, S., Ng, A. Y., and Schneider, J. (2004). Policy search by
dynamic programming. In Neural Information Processing Systems 16.
Bagnell, J. A. and Schneider, J. (2003). Covariant policy search. In Proceedings ofthe International Joint Conference on Artificial Intelligence.
Bares, J. and Wettergreen, D. (1999). Dante II: Technical description, results andlessons learned. International Journal of Robotics Research, 18(7):621–649.
Bertsekas, D. P. (2005a). Dynamic Programming and Optimal Control, Vol I. Athena
Scientific.
Bertsekas, D. P. (2005b). Dynamic Programming and Optimal Control, Vol II. Athena
Scientific.
Betts, J. (1998). Survery of numerical methods for trajectory optimization. Journalof Guidance, Control, and Dynamics, 21(2):193–207.
Boyd, S. and Vandenberg, L. (2004). Convex Optimization. Cambridge University
Press.
Boyd, S. P. (2003). Linear quadratic regulator: Discrete-time finite horizon. Lecture
Notes.

BIBLIOGRAPHY

158

Byl, K., Shkolnik, A., Prentice, S., Roy, N., and Tedrake, R. (2008). Reliable dynamic
motions for a stiff quadruped. In Proceedings of the 11th International Symposium
on Experimental Robotics.
Cao, B., Dodds, G., and Irwin, G. (1997). Constrained time-efficient smooth cubic spline trajectory generation for industrial robots. In Proceedings of the IEE
Conference on Control Theory and Applications.
Caruana, R. (1997). Multitask learning. Machine Learning, 28(1):41–75.
Chestnutt, J., Kuffner, J., Nishiwaki, K., and Kagami, S. (2003). Planning bipednavigation strategies in complex environments. In Proceedings of the International
Conference on Humanoid Robotics.
Christopher G. Atkeson, Andrew W. Moore, S. S. (1997). locally weighted learningfor control. artificial intelligence review, 11:75–113.
Dasgupta, S. and Johnson, C. R. (1986). Some comments on the behavior of sign-sign
adaptive identifiers. Systems and Control Letters, 7:75–82.
Doya, K., Samejima, K., ichi Katagiri, K., and Kawato, M. (2002). Multiple modelbased reinforcement learning. Neural Computation, pages 1347–1369.
Dyer, P. and McReynolds, S. R. (1970). The Computation and Theory of OptimalControl. Academic Press.
Fodor, I. (2002). A survey of dimension reduction techniques. Technical report, US
DOE Office of Scientific and Technical Information.
Fukuoka, Y., Kimura, H., and Cohen, A. H. (2003). Adaptive dynamic walking of aquadruped robot on irregular terrain based on biological concepts. The International Journal of Robotics Research, 22:187–202.
Gerdes, C. (2009). Personal communication.

BIBLIOGRAPHY

159

Gillula, J., Huang, H., Vitus, M. P., and Tomlin, C. J. (2010). Design of guaranteed safe maneuvers using reachable sets: Autonomous quadrotor aerobatics intheory and practice. In Proceedings of the International Conference on Robotics
and Automation.
Glynn, P. (1987). Likelihood ratio gradient estimation: an overview. In Proceedignsof the 1987 Winter Simulation Conference.
Greensmith, E., Bartlett, P. L., and Baxter, J. (2004). Variance reduction techniques
for gradient estimates in reinforcement learning. Journal of Machine Learning
Research, 5:1471–1530.
Grillner, S. (1985). Neurobiological bases of rhythmic motor acts in vertebrates.
Science, 228(4696):143–149.
Hansen, E., Barto, A., and Zilberstein, S. (1996). Reinforcement learning for mixed
open-loop and closed-loop control. In Neural Information Processing Systems.
Hengst, B., Ibbotson, D., Pham, S. B., and Sammut, C. (2002). Omnidirectional
locomotion for quadruped robots. In RoboCup 2001: Robot Soccer World Cup V,
pages 368–373.
Hirose, S., Nose, M., Kikuchi, H., and Umetani, Y. (1984). Adaptive gait control of aquadruped walking vehicle. International Journal of Robotics Research, 1:253–277.
Hodgins, J. K. and Raibert, M. H. (1990). Biped gymnastics. International Journalof Robotics Research, 9(2):115–128.
Hoffmann, G. M., Tomlin, C. J., Montemerlo, M., and Thrun, S. (2007). Autonomous
automobile trajectory tracking for off-road driving: Controller design, experimental
validation and racing. In Proc. 26th American Control Conf.
Hornby, G. S., Takamura, S., Yamamoto, T., and Fujita, M. (2005). Autonomous
evolution of dynamic gaits with two quadruped robots. IEEE Transactions on
Robotics, 21(3):402–410.

BIBLIOGRAPHY

160

Hsu, Y.-H. J. and Gerdes, J. C. (2005). Stabilization of a steer-by-wire vehicle at thelimits of handling using feedback linearization. In Proceedings of the 2005 ASME
International Mechanical Engineering Congress and Exposition.
Ioannou, P. A. and Sun, J. (1995). Robust Adaptive Control. Prentice Hall.
Jacobson, D. H. and Mayne, D. Q. (1970). Differential Dynamic Programming. American Elsevier.
Jordan, M. I. and Rumelhart, D. E. (1992). Forward models: Supervised learningwith a distal teacher. Cognitive Science, 16:307–354.
Kakade, S. (2001). A natural policy gradient. In Neural Information Processing
Systems 14.
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H. (1996). Probabilisitc roadmaps for path planning high-dimensional configuration spaces. IEEE
Transactions on Robotics and Automation, 12(4):566–580.
Kearns, M. and Singh, S. (2002). Near-optimal reinforcment learning in polynomial
time. Machine Learning, 49(2–3):209–232.
Khatri, C. G. and Mitra, S. K. (1976). Hermitian and nonnegative definite solutionsof linear matrix equations. SIAM Journal on Applied Mathematics, 31(4):579–585.
Kimura, H., Fukuoka, Y., and Cohen, A. H. (2007). Adaptive dynamic walking of aquadruped robot on natural ground based on biological concepts. The International
Journal of Robotics Research, 26(5):475–490.
Ko, J., Klein, D. J., Fox, D., and Hhnel, D. (2007). Gaussian processes and reinforcement learning for identification and control of an autonomous blimp. In
International Conference on Robotics and Automation.
Kohl, N. and Stone, P. (2004). Machine learning for fast quadrupedal locomotion. In
The Nineteenth Conference on Artificial Intelligence.

BIBLIOGRAPHY

161

Kolter, J. Z., Abbeel, P., and Ng, A. Y. (2008a). Hierarchical apprenticeship learning, with application to quadruped locomotion. In Neural Information Processing
Systems 20.
Kolter, J. Z., Kim, Y., and Ng, A. Y. (2009). Stereo vision and terrain modeling for
quadruped robots. In Proceedings of the International Conference on Robotics andAutomation.
Kolter, J. Z. and Ng, A. Y. (2007). Learning omnidirectional path following using
dimensionality reduction. In Robotics Science and Systems.
Kolter, J. Z. and Ng, A. Y. (2009a). Policy search via the signed derivative. In
Proceedings of Robotics: Science and Systems.
Kolter, J. Z. and Ng, A. Y. (2009b). Task-space trajectories via cubic spline optimization. In Proceedings of the International Conference on Machine Learning.
Kolter, J. Z., Plagemann, C., Jackson, D. T., Thrun, S., and Ng, A. Y. (2010). A
probabilistic approach to mixed open-loop and closed-loop control, with application
to extreme autonomous driving. In Proceedings of the International Conference on
Robotics and Automation.
Kolter, J. Z., Rodgers, M. P., and Ng, A. Y. (2008b). A complete control architecturefor quadruped locomotion over rough terrain. In Proceedings of the International
Conference on Robotics and Automation.
Konidaris, G. and Barto, A. (2006). Autonomous shaping: Knowledge transfer inreinforcement learning. In Proceedings of the International Conference on Machine
Learning.
Krotkov, E., Simmons, R., and Whittaker, W. L. (1995). Ambler: Performance of a
Six-Legged Planetary Rover, 35(1):75–81.
LaValle, S. M. and Kuffner, J. J. (1999). Randomized kinodynamic planning. In
Proceedings of the International Conference on Robotics and Automation.

BIBLIOGRAPHY

162

Li, H., Liao, X., and Carin, L. (2009). Multi-task reinforcement learning in partially observable stochastic environments. Journal of Machine Learning Research,
10:1131–1186.
Li, W. and Todorov, E. (2005). Iterative linear qaudratic regulator design for nonlinear biological movement systems. In Proceedings of the International Conferenceon Informatics in Control.
Lin, C.-S., Chang, P.-R., and Luh, J. (1983). Formulation and optimization of cubic
polynomial joint trajectories for industrial robots. IEEE Transactions on AutomaticControl, 28(12):1066–1074.
Ljung, L. (1999). System Identification: Theory for the User. Prentice Hall.
Lucky, R. W. (1966). Techniques for adaptive equalization of digital communication
systems. Bell Systems Technical Journal, 45:255–286.
Mahadevan, S. and Maggioni, M. (2007). Proto-value functions: A laplacian framework for learning representation and control in markov decision processes. Journalof Machine Learning Research, 8:2169–2231.
McGhee, R. (1985). Vehicular legged locomotion. In Advances in Automation andRobotics, pages 259–284.
McGhee, R. B. (1967). Finite state control of quadruped locomotion. Simulation,
5:135–140.
McGhee, R. B. (1968). Some finite state aspects of legged locomotion. Mathematical
Biosciences, 2:67–84.
McGhee, R. B. and Frank, A. A. (1968). On the stability properties of quadruped
creeping gaits. Mathematical Biosciences, 3:331–351.
Mehta, N., Natarajan, S., Tadepalli, P., and Fern, A. (2008). Transfer in variablereward hierarchical reinforcement learning. Machine Learning, 73(3):289–312.

BIBLIOGRAPHY

163

Montemerlo, M., Becker, J., Bhat, S., Dahlkamp, H., Dolgov, D., Ettinger, S.,
Haehnel, D., Hilden, T., Hoffman, G., Huhnke, B., Johnston, D., Klumpp, S.,
Langer, D., Levandowski, A., Levinson, J., Marcil, J., Orenstein, D., Paefgen, J.,
Penny, I., Petrovskaya, A., Pflueger, M., Stanek, G., Stavens, D., Vogt, A., andThrun, S. (2008). Junior: The stanford entry in the urban challenge. Journal of
Field Robotics, 25(9):569–597.
Moore, K. L. (1999). Iterative learning control: an expository overview. Applied andComputational Controls, Signal Processing, and Circuits, 1(1):151–214.
Mosher, R. S. (1968). Test and evaluation of a versatile walking truck. In Proceedings
of off-road mobili6ty research symposium, pages 359–379.
Murphy, M. P., Saunders, A., Moreira, C., Rizzi, A. A., and Raibert, M. (2010). The
littleDog robot. To appear in The International Journal of Robotics Research.
Murray-Smith, R. and Johansen, T. A. (1997). Taylor and Francis.
Narendra, K. S. and Balakrishnan, J. (1997). Adaptive control using multiple models.
IEEE Transactions on Automatic Control, pages 171–187.
Neu, G. and Szepesvári, C. (2007). Apprenticeship learning using inverse reinforcement learning and gradient methods. In Proceedings of Uncertainty in Artificial
Intelligence.
Ng, A. Y. and Jordan, M. (2000). Pegasus: A policy search method for large mdps andpomdps. In Proceedings of the Conference on Uncertainty in Artificial Intelligence.
Nichol, J. G., Singh, S. P., Waldron, K. J., III, L. R. P., and Orin, D. E. (2004). System design of a quadrupedal galloping machine. International Journal of Robotics
Research, 23(10–11):1013–1027.
Park, J.-H., Kim, H.-S., and Choi, Y.-K. (1997). Trajectory optimization and control
for robot manipulator using evolution strategy and fuzzy logic. In Proceedings ofthe IEEE International Conference on Systems, Man, and Cybernetics.

BIBLIOGRAPHY

164

Peters, J. and Schaal, S. (2006). Policy gradient methods for robotics. In Proceedingsof the IEEE Conference on Intelligent Robotics Systems.
Peters, J. and Schall, S. (2004). Learning motor primatives with reinforcement learning. In Proceedings of the 11th Joint Symposium on Neural Computation.
Peters, J., Vijayakumar, S., and Schaal, S. (2005). Natural actor-critic. In Proceedingsof the European Conference on Machine Learning.
Poulakakis, I., Smith, J. A., and Buehler, M. (2005). Modeling and experiments ofuntethered quadrupedal running with a bounding gait: The scout ii robot. The
International Journal of Robotics Research, 24(4):239–256.
Putterman, M. L. (2005). Markov Decision Processes: Discrete Stochastic Dynamic
Progamming. Wiley Interscience.
Raibert, M., Blankespoor, K., Nelson, G., and Playter, R. (2008). Bigdog, the roughterrain quadruped robot. In Proceedings of the International Federation of Autonomous Control.
Raibert, M. H. (1986). Legged Robots that Balance. MIT Press.
Rasmussen, C. E. and Williams, C. K. I. (2006). Gaussian Processes for Machine
Learning. The MIT Press.
Ratliff, N., Bagnell, J. A., and Zinkevich, M. (2006). Maximum margin planning. In
Proceedings of the International Conference on Machine Learning.
Reinsel, G. C. and Velu, R. P. (1998). Multivariate Reduced-Rank Regression: Theory
And Appplications. Springer-Verlag.
Riedmiller, M. and Braun, H. (1992). RPROP – a fast adaptive learning algorithm.
In Proceedings of the International Symposium on Computer and Information Sciences.
Roy, N., Gordon, G., and Thrun, S. (2005). Finding approximate pomdp solutions
through belief compression. Journal of Artificial Intelligence Research, 23:1–40.

BIBLIOGRAPHY

165

Saranli, U., Buehler, M., and Koditschek, D. (2001). Rhex: A simple and highly
mobile hexapod robot. Int. Journal of Robotics Research, 20:616–631.
Sastry, S. and Bodson, M. (1994). Adaptive Control: Stability, Convergence, andRobustness. Prentice-Hall.
Saunders, A., Goldman, D., Full, R., and Buehler, M. (2006). The RiSE climbing
robot: Body and leg design. Proc. SPIE Int. Soc. Opt. Eng., 6230:623017.
Schaal, S. (1994). Nonparametric regression for learning. In Proceedings of the Conference on Adaptive Behavior and :earning.
Schott, K. D. and Bequette, B. W. (1997). Multiple model adaptive control. In
Multiple Model Approaches to Modelling and Control.
Sideris, A. and Bobrow, J. E. (2005). An efficicent sequential linear quadratic algorithm for solving nonlinear optimal control problems.
Stengel, R. F. (1994). Optimal Control and Estimation. John Wiley and Sons.
Stolle, M. and Atkeson, C. G. (2006). Policies based on trajectory libraries. In
International Conference on Robotics and Automation.
Stolle, M., Tappeiner, H., Chestnutt, J., and Atkeson, C. G. (2007). Transfer ofpolicies based on trajectory libraries. In International Conference on Intelligent
Robots and Systems.
Strehl, A. L., Li, L., and Littman, M. (2009). Reinforcement learning in finite mdps:
Pac analysis. Journal of Machine Learning Research, 10:2413–2444.
Sutton, R. S. and Barto, A. G. (1998). Reinforcement Learning: An Introduction.
MIT Press.
Tanaka, F. and Yamamura, M. (2003). Multitask reinforcement learning on the distribution of mdps. In Proceedings of the International Symposium on Computational
Intelligence in Robotics and Automation.

BIBLIOGRAPHY

166

Taskar, B., Chatalbashev, V., Koller, D., and Guestrin, C. (2005). Learning structured prediction models: A large margin approach. In Proceedings of the International Conference on Machine Learning.
Taylor, M. E. and Stone, P. (2009). Transfer learning for reinforcement learning
domains: A survey. Journal of Machine Learning Research, 10:1633–1685.
Taylor, M. E., Stone, P., and Liu, Y. (2007). Transfer learning via inter-task mappings
for temporal different learning. Journal of Machine Learning Research, 8:2125–
2167.
Thrun, S. (1996). Is learnging the n-th thing any easier than learning the first? In
Neural Information Processing Systems.
Tsochantaridis, I., Joachims, T., Hofmann, T., and Altun, Y. (2005). Large margin
methods for structured and interdependent output variables. Journal of Machine
Learning Research, 6:1453–1484.
Vaz, A. I. F. and Fernandes, E. M. (2006). Tools for robotic trajectory planning
using cubic splines and semi-infinite programming. In Seeger, A., editor, Recent
Advances in Optimization, pages 399–413. Springer.
Vijayakumar, S., D’Souza, A., and Schaal, S. (2005). Incremental online learning inhigh dimensions. Neural Computation, 17:2602–2634.
Widrow, B. and Hoff, M. E. (1960). Adaptive switching circuits. In IRE WESCON
Convention Record.
Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229–256.
Williams, R. J. and Zisper, D. (1989). A learning algorithm for continually running
fully recurrent neural networks. Neural Computation, 1:270–280.
Wilson, A., Fern, A., Ray, S., and Tadepalli, P. (2007). Multi-task reinforcement
learning: A hierarchical bayesian approach. In Proceedings of the International
Conference on Machine Learning.

BIBLIOGRAPHY

167

Zhou, K., Doyle, J., and Glover, K. (1996). Robust and Optimal Controler. PrenticeHall.