Space-indexed Dynamic Programming:
Learning to Follow Trajectories

J. Zico Kolter
Adam Coates
Andrew Y. Ng
Yi GuCharles DuHadway
Computer Science Department, Stanford University, CA 94305

Abstract
We consider the task of learning to accurately follow a trajectory in a vehicle suchas a car or helicopter. A number of dynamic
programming algorithms such as Differential
Dynamic Programming (DDP) and Policy
Search by Dynamic Programming (PSDP),
can efficiently compute non-stationary policies for these tasks — such policies in general
are well-suited to trajectory following since
they can easily generate different control actions at different times in order to follow the
trajectory. However, a weakness of thesealgorithms is that their policies are timeindexed, in that they apply different policies
depending on the current time. This is problematic since 1) the current time may notcorrespond well to where we are along the
trajectory and 2) the uncertainty over states
can prevent these algorithms from finding
any good policies at all. In this paper we
propose a method for space-indexed dynamic
programming that overcomes both these difficulties. We begin by showing how a dynamical system can be rewritten in terms of a
spatial index variable (i.e., how far along the
trajectory we are) rather than as a functionof time. We then use these space-indexed dynamical systems to derive space-indexed version of the DDP and PSDP algorithms. Finally, we show that these algorithms perform
well on a variety of control tasks, both in simulation and on real systems.
Appearing in Proceedings of the 25 th International Conference on Machine Learning, Helsinki, Finland, 2008. Copyright 2008 by the author(s)/owner(s).

kolter@cs.stanford.edu
acoates@cs.stanford.edu
ang@cs.stanford.edu
guyinet@stanford.edu
duhadway@stanford.edu

1. Introduction
We consider the task of learning to accurately follow
a trajectory, for example in a car or helicopter. Thisis one of the most basic and fundamental problems inreinforcement learning and control. One class of approaches to this problem uses dynamic programming.
These algorithms typically start at the last time-step
T of a control task, and compute a simple (say, linear) controller for that time-step. Then, they use dynamic programming to compute controllers for timesteps T − 1, T − 2 and so on down to time-step 1.
Some examples of algorithms in this family include(Jacobson & Mayne, 1970; Bagnell et al., 2004; Atkeson & Morimoto, 2003; Lagoudakis & Parr, 2003), andall of them output time-varying/non-stationary policies that choose the control action as a function oftime. Given that following a trajectory requires one tochoose very different control actions at different partsof the trajectory — for example, the controls whiledriving a car on a straight part of the trajectory arevery different from the controls needed during a turn –these dynamic programming algorithms therefore initially seem well-suited for trajectory following.
However, a weakness in the naive dynamic programming approach is that the control policies are timeindexed. That is, these algorithms output a sequenceof controllers π1 , π2 , . . . , πT and execute controller πt
at time t. However, as time passes, the uncertainty
over the state increases, and this can greatly degrade
controller performance. For example, suppose we are
driving a car around a track with both straight andcurved portions, and suppose that the controller attime t assumed the car was on a curved portion. If,
due to the natural stochasticity of the environment,
the car was actually on a straight portion of the trackat this time, the resulting controller would perform
very poorly, and this problem increases over time. This

Space-indexed Dynamic Programming

problem can be alleviated slightly be “re-indexing” thecontrollers by state during execution. That is, at time
t we do not necessarily execute controller πt , but instead we examine all the controllers π1 , . . . , πT , andexecute the controller whose corresponding state isclosest to the current state — several variations on
this approach exist, and we will discuss them further
in Section 5. However, there are two fundamental limitations of this general method. First, because we are
executing a different policy from the one learned bydynamic programming, it is difficult to provide anyof the performance guarantees that often accompany
the purely time-indexed dynamic programming algorithms. Second, and more fundamentally, the uncertainty over states in the distant future often make it
extremely difficult to learn any good policy using thetime-indexed algorithms. This means that regardlessof how we re-index the controllers during execution,
we are unlikely to obtain good performance.
In this paper we propose a method for space-indexed
dynamic programming that addresses both these concerns. More precisely, we will define a spatial index
variable d that measures how far we have traveledalong the target trajectory. Then, we will use policies
πd that depend on d — where we are along the trajectory — rather than the current time t. In order to learnsuch policies, we define the notion of a space-indexed
dynamical system, and show how various dynamicalsystems can be rewritten such that their dynamics areindexed by d instead of by time t. This then allows us
to extend various dynamic programming algorithms
to produce space-indexed policies — in particular, wedevelop a space-indexed versions of the Differential
Dynamic Programming (DDP) (Jacobson & Mayne,1970) and Policy Search by Dynamic Programming(PSDP) algorithms (Bagnell et al., 2004). Finally, we
successfully apply this method to several control tasks,
both in simulation and in the real world.
The remainder of this paper is organized as follows.
In Section 2 we show how to transform a standard(time-indexed) dynamical system into a space-indexed
dynamical system. Using this transformation, in Section 3 we develop space-indexed versions of the DDP
and PSDP algorithms. In Section 4 we present experimental results on several control tasks. Finally, in
Sections 5 and 6 we discuss related work and conclude
the paper.

2. Space-indexed Dynamical Systems
Standard dynamic programming algorithms are very
efficient because they know in advance that the policies
π1 , . . . , πT will be executed in a certain sequence (andthat each policy will be executed only once), and canthus solve for them in reverse order. The key difficultyof generalizing a dynamic programming algorithm tothe space-indexed setting is that it is difficult to know
in advance where in space (i.e., how far along the trajectory) the vehicle will be at each step, and thus whichspace-indexed policy will be executed when. For example, if the vehicle is currently at space-index d, thenthere is no guarantee that executing policy πd for one
time-step will put the vehicle in space-index d+1. But
if πd might be executed multiple times before switching to πd+1 , then in general its parameters cannot be
solved for in closed form during the dynamic programming backup step, and require some complex policy
search instead. In this section we discuss a method for
addressing this problem. Specifically, we will rewrite
the dynamics of a system so that the states and transitions are indexed by the spatial-index variable d rather
than by the time t.
Suppose we are given a general non-linear dynamics
model in the form of a (possibly stochastic) differential equation ṡ = f (s, u), where s ∈ Rn denotes thestate vector u ∈ Rm denotes the control input, and ṡ
denotes the derivative of the state vector with respect
to time. While some classical control algorithms operate directly on this differential equation, a common
technique in reinforcement learning and control is tocreate a discrete-time model of the system
st+1 = F (st , ut ) + wt
by numerical integration, where st and ut denote thestate and input at time t respectively, and wt is a zeromean IID noise term (typically taken to be Gaussianwith some prespecified covariance, for example). A
simple but very common method for achieving thisdiscretization is by Euler integration. In this case thestate evolves as
st+∆t = st + f (st , ut )∆t + wt
where ∆t is the integration time constant (the variance of wt will scale linearly with the time constantas well). Note that even though the system evolves incontinuous time, by making the decision to model it
as a discrete-time system, we have made a decision to
explicitly represent the state only at certain instantsin time (t = ∆t, t = 2∆t, . . .).
When transitioning to a space-indexed dynamical system, we instead will explicitly represent the state
only when it is at certain points along the trajectory.
We begin by representing the time-indexed state asT
st = [xt , θt ] , where x ∈ Rp represents what we referto as the spatial portions of the state (in this paper
we typically consider the spatial portions of the state
to be the 2D or 3D position). Now, assume we areSpace-indexed Dynamic Programming

11
00
000
111
00
11
000
111
000
111
000
111
000
111
000
111
2
000
111

l

001
11
110
00
00
11
00
11
00
11
3
00
11

l

d=3

d=4

d=2
d=1

tion, and this is unlikely given any reasonable controller. When ∆t > 0 does exist, we can computest+∆t = st + f (st , ut )∆t and use this to find the next
space-indexed states̃d+1 = [td + ∆t, ℓd+1 , θt+∆t ]where ℓd+1 is xt+∆t − x⋆d+1 expressed in the Rp−1 subspace defined by the plane through x⋆d+1 . This gives
us our final space-indexed simulator in the forms̃d+1 = F̃ (s̃d , ud ) + w̃dFigure 1. Figure illustrating space-indexed dynamics.

given a target trajectory in the space of x, such as thecurved path shown in Figure 1. We choose a total of
D discrete points along the trajectory, and designate
the target state at these points as x⋆1 , x⋆2 , . . . , x⋆D . In
the space-indexed dynamical system, we will explicitly
represent the state only when the state lies on a hyperplane which is orthogonal to the target direction of
travel and which passes through the one of the target
points x⋆d . More formally, we let ẋ⋆d be the instantaneous direction of motion (along the target trajectory)at point d. We will then explicitly represent the state
only when (x − x⋆d )T ẋ⋆d = 0. This situation is depicted
in Figure 1.
Because we constrain the state in this manner, ourspace-indexed state will have a different set of variables
as our time-indexed state. In particular, we representTthe space-indexed state as s̃d = [td , ℓd , θd ] where td ∈R denotes the time of the system, ℓd ∈ Rp−1 denotes
the lateral deviation from the target trajectory — forx ∈ Rp a point satisfying the constraint that (x −x⋆d )T ẋ⋆d = 0 can be represented using p − 1 dimensions
and this gives the lateral deviation term — and θddenotes the non-spatial portions of the state as before.
The time variable td is kept for completeness, but it
can be ignored if the policies do not depend on time.
Now we can rewrite the dynamics so that they are indexed by space rather than time; this will give us anequation for computing s̃d+1 from s̃d . For simplicity,
we develop an Euler integration-like method, but thetechnique could also be extended to higher-order numerical integration methods. Rather than simulating
the system forward by a fixed time step, we solve for∆t such that the next state will lie exactly on the d + 1
plane. Temporarily ignoring the noise term, we solve(ẋ⋆d+1 )T (x + ẋ∆t − x⋆d+1 ) = 0
for ∆t. Note that a positive solution for ∆t may notalways exist, but it typically does except in degenerate cases, when the vehicle starts moving perpendicular or backward with respect to the desired direc-T(1)

where w̃d is a noise term. Although the distributionof w̃d is in general quite complex, we can apply methods from stochastic calculus to efficiently draw samples from this distribution. However, in practice wefind that a simpler approximate approach works just as
well: we compute st+∆t as above, assuming no noise,then add noise as in the time-indexed model. This will
result in a point that may no longer lie exactly on thespace-index plane, so lastly we form the line between
the states st and st+∆t and let s̃d+1 be the point where
this line intersects the d + 1 plane.

3. Space-indexed Dynamic
Programming
In this section we use the techniques presented in theprevious section to develop space-indexed versions of
the Differential Dynamic Programming (DDP) and
Policy Search by Dynamic Programming (PSDP) algorithms. We begin by defining notation. Let S be
the state space and A be the action space (so that in
the context of the dynamical system above, S = Rn
and A = Rm ). Since, as described above, there exists a one-to-one mapping from time-indexed states tospace-indexed states, all the quantities below can beequivalently expressed in terms of the space-indexedstate. A reward function is a mapping R : S → R
and a policy is a mapping π : S → A. Given a nonstationary sequence of policies (πt , . . . , πT ) we define
the value functionPTVπt ,...πT (s) = T1 E[ i=t R(si )|st = s; (πt , . . . , πT )].
3.1. Space-indexed DDP
We first review (time-indexed) DDP briefly. DDP approximates the dynamics and cost function of a systemalong a specific sequence of states. Given an initial
controller πinit , DDP simulates the system to generate a sequence of states s1 , . . . , sT . It then linearizes
the dynamics around these points to obtain a timevarying linear dynamical system, and forms a secondorder (quadratic) approximation to the reward function. This system can then be solved by the LinearSpace-indexed Dynamic Programming

Quadratic Regulator (LQR) algorithm (Anderson &Moore, 1989), which results in a new controller and a
new sequence of states. This process is repeated untilconvergence.

each step the algorithm obtains πd such thatEs∼µd [Vπd ,πd+1 ,...,πD (s)] ≥arg max Es∼µd [Vπ,πd+1 ...πD (s)] − ǫπ∈ΠSpace-indexed DDP proceeds in the same manner.
Given some initial controller πinit and space-indexed
dynamical system of the form (1)1 , we simulate thesystem forward for D space-indexes, resulting in a setof states s̃1 , . . . , s̃D . Using our dynamics model, we
form the first order Taylor expansion of the dynamics
at each point along the trajectory, which results in the(space-indexed) linearized dynamics:s̃d+1 = Ad s̃d + Bd ud .
As in standard DDP, we form a quadratic approximation of the reward function Rd (s̃) = −s̃T Qd s̃, where
Qd is some (usually PSD) matrix. This reduces the
problem to an LQR problem, which can be solved efficiently using a backward recursion.
3.2. Space-indexed PSDP
We now briefly review PSDP. As input, PSDP takes atime horizon T , a restricted policy class Π, and a sequence of baseline distributions over the states spaceµ1 , . . . , µT , where we can informally think of µt as
providing a distribution over which states would bevisited at time t by a “good” policy. Given policies
πt+1 , . . . , πT , PSDP computes (or approximates via
Monte-Carlo sampling and parameter search)
πt = arg maxπ∈Π Es∼µt [Vπ,πt+1 ...πT (s)].

(2)

By starting with t = T and proceeding down to t = 1,
the algorithm is able to generate a sequence of policies
that can perform well on the desired task. The spaceindexed version of PSDP proceeds exactly as above,
replacing the time t with the space index d and using
the space-indexed simulator to generate the MonteCarlo samples.
Just as in the time-indexed version, the space-indexed
version of PSDP comes with nontrivial performance
guarantees, formalized by the theorem below. The
theorem follows immediately from the equivalent theorem for the time-indexed version of PSDP, and fromthe fact that the space-indexed dynamics and reward
function do not depend on time.
Theorem 3.1 [following (Bagnell et al., 2004)] Suppose π = (π1 , . . . , πD ) is a policy returned by an ǫapproximate version of state-indexed PSDP where on
1
For the DDP algorithm, we ignore the noise term w̃dbecause by the principle of certainty equivalence, the optimal controller for LQR does not depend on the variance/magnitude of the noise (Anderson & Moore, 1989).

Then for all πref ∈ ΠD ,Vπ (s0 ) ≥ Vπref (s0 ) − Dǫ − Ddvar (µ, µπref )where µ is the baseline distribution over space-index
states (without the time component) provided to
SI-PSDP, dvar denotes the average variational distance, and µπref is the state distribution induced by
πref .
This bound not only provides a performance guarantee
for the space-indexed PSDP algorithm, it also helps toelucidate the advantage of space-indexing over timeindexing. The bound implies that to make PSDP and
SI-PSDP perform as well as possible, it would be best
to provide them with µπ⋆ , the baseline distributionof the optimal controller, as the baseline distribution.
But for time-indexed PSDP, the natural stochasticityof the environment can cause this distribution to behighly spread out over the state space, even for the
optimal policy. Therefore, when performing the maximization (2), it is likely that no policy in the class will
perform very well, since this would require a policythat could operate well over many different regions of
the state space. Thus, regardless of whether or not we
re-index the resulting controllers by state during execution, the time-indexed version of PSDP would fail tofind a good policy. In contrast, if we are doing a goodjob following the trajectory, then we would expect thatthe distribution over states at each space-index would
be much tighter, allowing the space-indexed PSDP to
perform much better.

4. Experiments
4.1. Autonomous Driving
We begin by considering the problem of autonomously
and accurately following a trajectory with a car, suchas that shown in Figure 4. Our first set of experiments
were carried out in a simulator of the vehicle, built
following (Rossetter & Gerdes, 2002) (with model parameters such as the vehicle dimensions, total weight,etc). To follow the desired trajectory, we applied thespace-indexed DDP algorithm described above.
Prior to the work presented in this paper, significant
engineering effort went into a hand-designed trajectory following controller; this was an initial versionof the controller described in (Hoffmann et al., 2007),
which was a hand-optimized, linear, regulation controller that computes its actions as a function of stateSpace-indexed Dynamic Programming
50

Target trajectory
Space−indexed DP

10

40

0

−10

Y [m]

Y [m]

30
Target trajectory
Linear regulation controller
Space−indexed DP

20

−20

−30

−40

10

−50

0
−20

−10

0

10

20

30

40

50

60

70

X [m]

−10

−20

20

−10

0

10

20
X [m]

30

40

50

Figure 4. Picture of the vehicle used for experiments (left),
and trajectory from a run on the actual car (right).

60

Target trajectory
Linear regulation controller
Space−indexed DP

18
16

Y [m]

14
12
10
8
6
4
2
40

45

50

55
X [m]

60

65

70

Figure 2. Comparison of the regulation controller andspace-indexed controller. The figure below is a magnification of one of the turns.
50

Target trajectoryTime−indexed DP

Target trajectoryTime−indexed DP

Figure 5. Autonomous RC car.

40

20
30
20

10

Y [m]

10
0

0

−10

−10
−20

−20

−30
−40

−30
−50
−50

−40

−30

−20

−10

0

10

50

20

30

40

−40

−30

−20

−10

50

0
X [m]

10

20

30

40

Target trajectory
Linear regulation controller
Space−indexed DP

40

20
30
20

10

Y [m]

Y [m]

10
0

0

−10

−10

Target trajectory−20

Linear regulation controller−30Space−indexed DP

−20
−40
−50

−30
−50

−40

−30

−20

−10

0
X [m]

10

20

30

40

50

−40

−30

−20

−10

0
X [m]

10

20

30

40

Figure 3. Two example trajectories where a time-indexed
controller (above) performs significantly worse than thespace-indexed controller (below).

features such as lateral error, orientation error, andso on. We used this controller to generate an initial
trajectory for our space-indexed DDP algorithm; however, the results of space-indexed DDP were actually
very insensitive to the choice of this initial controller.
Figure 2 shows the performance of the space-indexed
DDP algorithm and the hand-tuned controller in simulation, when following an oval-like track at 30mph,
along with a magnified view of the show the performance on one of the turns. We see that space-indexed
DDP outperforms the hand-tuned controller; our controller has an RMS lateral error 0.26m, whereas thehand-tuned controller’s RMS error is 1.18m.
Figure 3 shows a comparison between the performanceof space-indexed and time-indexed dynamic program-

ming. Due to the stochasticity of the simulator, theactual state st , for large t, is increasingly unlikely to
be close to where the t-th step of the linearization occurred. Therefore the linearized approximation is lesslikely to be an accurate approximation of the “local”
dynamics at time t. This is reflected in the figures:the time-indexed controllers initially perform well, but
as time passes the controllers start to be executed atincorrect points along the trajectory, eventually leading the vehicle to veer off course. Using the spaceindexed controller, however, the vehicle is able to accurately track the trajectory even for an arbitrarily
long amount of time. For this relatively simple trajectory following task, re-indexing the time-indexed
controllers by their spatial state, as described in the
introduction, does perform well. However, as we will
demonstrate in the next section, for more complex control tasks this is not the case.
We also tested our method on the actual vehicle; thevehicle itself is described further in (Thrun & al.,2006). Figure 4 shown a typical result from an actual run on the vehicle moving at 10mph. The RMS
error on the actual vehicle was about 0.17m, and thetarget and actual trajectories are indistinguishable in
the figure.
4.2. Autonomous Driving with Obstacles
We next consider the more challenging control taskof following a trajectory in the presence of obstacles. For this task we evaluated our methods on an
RC car, shown in Figure 5. Since we want to learn
a single controller that is capable of avoiding obsta-

Space-indexed Dynamic Programming
1.5

1.5

1.5

1

Target Trajectory1

1

Obstacles
Target Trajectory

0.5Time−Indexed PSDP

Target Trajectory

0.5

Obstacles

0.5

Obstacles0Space−Indexed PSDP
0

Time−Indexed PSDP w/ Reindexing
0

−0.5
−1

−0.5

−0.5

−1.5

−1

−1
−2

−1.5

−1.5
−2.5
−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

−3

−2.5

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

Figure 6. Trajectories taken by the real RC car on a course with obstacles, using space-indexed PSDP (left), time-indexed
PSDP (middle), and time-indexed PSDP with re-indexing by space (right).

cles placed at arbitrary points along the trajectory,
DDP is a poor algorithm (DDP learns a controller
for a single fixed trajectory, but in this task we need
to follow different trajectories depending on the location of the obstacles). Therefore, we apply the
space-indexed version of PSDP to this task. Videos of
the resulting controllers for this task are available at:
http://cs.stanford.edu/∼kolter/icml08videos.
In greater detail, we applied the space-indexed PSDP
algorithm as follows. The native action space for the
car domain is a two-dimensional input specifying thevelocity and steering angle (between -28 degrees and
28 degrees), but for our task we kept the velocity fixedat 1.5 m/s and discretized the commanded steering
angle into five equally spaced angles. To generate theinitial distribution for PSDP, µ1 , . . . , µD , we sampled
2000 different trials in a simulator of the car, using a
PD controller. Then, for each space index from D − 1
down to 1, we (approximately) solved the optimization
problem (2) by first trying each possible action for eachof the 2000 sampled states, then executing the learned
controller for all subsequent space-indices to computethe resulting cost of the policy.2 We then tried tolearn the optimal action as a linear function of various state features; in particular, each controller wasof the form: usteer = arg maxi wiT φ(s) where wi ∈ Rn
is a weight vector learned by a multi-class SVM-likealgorithm3 , and φ(s) ∈ Rn is a feature vector. In our2

We used a cost function (i.e., negative reward), ofC(sd ) = θ1 ℓ2 + θ2 (1 − dist/θ3 )1{dist < θ3 }where dist denotes the distance to the nearest obstacle, 1 is
the indicator function, and θ1 , . . . , θ3 are parameters that
trade off the relative cost of deviating from the trajectoryand getting close to obstacles. For our experiments, weused θ1 = 1000, θ2 = 500 and θ3 = 0.5.
3Algorithmic details: the PSDP algorithm with discrete
actions leads to a cost-sensitive, k-class learning problem
with examples form {φ(s(i) ) ∈ Rn , c(i) ∈ Rk }, i = 1, . . . m(i)where φ(s(i) ) are the features, and cj represents the costof classifying example i as belonging to class j. We approximately solve this problem with a support vector machinelike algorithm, which bears some similarly to previous work

Table 1. Average costs and collision counts for the simulated RC car with obstacles, averaged over 1000 runs.

Algorithm
SI-PSDPTI-PSDPTI-PSDP w/
re-indexing
Hand-tuned
PD Controller

Cost
56.17 ± 0.43
58.39 ± 0.40
58.19 ± 0.37

Collisions
51
181
212

58.35 ± 0.34

231

setting the features comprised of 1) the x and y location of the car, 2) the sine and cosine of the current carorientation, 3) 16 exponential RBF functions, spaced
uniformly around the car, indicating the presence ofan obstacle, and 4) a constant term. In addition to
the space-indexed version, we also evaluated the performance of a pure time-indexed version, and a timeindexed version where we re-index the controllers as
follows: at time t rather than execute the controller
πt , we examine all the controllers π1 , . . . , πT and execute the controller πt′ with minimum distance fromthe current state to the mean of the distribution µt′ .
Table 1 shows the average cost incurred and total number of collisions for the different controllers in 1000
simulated trials, where each trial had three randomly
placed obstacles on the trajectory. As can be seen,
the space-indexed version outperforms all the othervariants of the algorithm as well as a hand-tuned PD
controller that we previously spent a good deal of timetrying to tune. The performance benefits of the spaceindexed controller become even more pronounced on
the real system. Figure 6 shows typical resulting trajectories from the space-indexed controller, the puretime-indexed controller, and the time-indexed controller with re-indexing. Due to the stochasticity ofin cost-sensitive SVM earning (Geibel et al., 2004). The
algorithm finds the solution to the optimization problem:
Pk 1
Pm Pk
(i)
(i) +
2
min
j=1 2 kwj k + C
i=1
j,l=1 (cj − cl ) ξi,j,l
w,ξ≥0

s.t.

(wl − wj )T φ(s(i) ) ≥ 1 − ξi,j,l ∀i, j, k.

Space-indexed Dynamic Programming
12

10

Y [m]

8

6

4

Target trajectory
Space−indexed DP
Linear regulation controller

2

Figure 7. Tempest autonomous helicopter.

4.3. Autonomous Helicopter Flight
We also apply these ideas to a simulated autonomous
helicopter. This work used a stochastic simulator of
the autonomous helicopter shown in Figure 7, and we
considered the problem of making accurate, high-speed(5m/s) turns on this helicopter. We applied the spaceindexed PSDP algorithm to this task due to the factthat the policy search setting allowed us to greatly
restrict the class of control policies πd under consideration (the space of all control policies for helicopter
flight is very large, so we wanted to limit the risk of unexpected behavior). In particular, the “actions” of thecontrollers corresponded to picking a location of set
point x⋆ which is then fed into a regulation controller,
such as those described in (Bagnell & Schneider, 2001;
Ng et al., 2004). Space constraints preclude a full description of the environment and algorithm, but theoverall algorithm proceeds as in the previous section.
Figure 8 shows a typical result of applying the spaceindexed PSDP algorithm to this task, along with the
trajectory taken by a simple linear regulation controller. By varying the set point differently at different
points along the trajectory, the space-indexed PSDP
algorithm follows the trajectory much more accurately.

5. Related Work
The idea that a control policy should be dependent on
the system’s spatial state is by no means a new idea inthe reinforcement learning and control literature. In
the Markov Decision Process (MDP) formalism (Puterman, 1994), a policy is a mapping from states (which
typically describe the spatial state of the system) toactions. In light of this observation, many classicaldynamic programming algorithms such as value iter-

−2

0

2

4

6

8

10

12

X [m]

2
Z [m]

the real domain, the pure time-indexed approach performs very poorly. Re-indexing the controllers helps
significantly, but the space-indexed version still performs substantially better (an incurred cost of 49.32
for space-indexed versus 59.74 for time-indexed with
re-indexing, and the latter controller will nearly always
hit at least one of the obstacles on the track). As seenin the figure, the space indexed version is able to track
the trajectory well, while reliably avoiding obstacles.

0

1
0
12

10

8

6

Y [m]

4

2

0

0

2

4

6

8

10

X [m]

Figure 8. Comparison of the regulation controller andspace-indexed controller in the helicopter simulation. The
figure below shows the trajectories in three dimensions.

ation or policy iteration can be viewed as performing dynamic programming on spatial states. However,in high-dimensional, continuous state spaces, the wellknown “curse of dimensionality” renders a naive application of these algorithms intractable. Indeed, it is thisreality that often motivates the jump to the trajectory
following approach, where we want to find polices that
perform well along the trajectory in particular.
There are also a number of methods for trajectory following. A common approach is to design a “regulation
controller” that can keep the vehicle stable at a specified position x⋆ . By smoothly moving x⋆ along thetarget trajectory, we can cause the vehicle to movealong this path (Franklin et al., 1995; Dorf & Bishop,
2000). This approach works well when the regulation
controller has very high bandwidth – i.e., if it can trackx⋆ almost exactly as it varies — and is successful inapplication areas such as control of robot arms. But
in more general settings in which the actual state x ofthe vehicle tends to lag well behind changes to x⋆ , one
often ends up manually and laboriously adjusting theregulation controller to try to obtain proper trajectory
following performance. There are methods for compensating for this lag such as feedback linearization(Sastry, 1999), and there have also been many methods devised for trajectory following on specific systems(Egerstedt & Hu, 2000; Johnson & Calise, 2002). However, we know of no method for trajectory following in
the general case of the nonholonomic, underaccuatedvehicles that we consider.
The idea of partitioning the state space into regions,and using different controllers in the different regions,is a common practice in control, and often is referred
to as gain-scheduling (Leith & Leithead, 2000). Taken

Space-indexed Dynamic Programmingin the general sense, the algorithm we present in thispaper can be viewed as a method for gain-scheduling,
though more often the term is used for a particularapplication of this approach to the contexts of linear parameter varying systems. Such methods typically linearize the dynamical system around certain
operating points, learn controllers at each point, andsmoothly interpolate between controllers at various locations. However, the focus of this work is often to
prove stability of such controllers using Lyapunov theory, and the overall approach is substantially different
from what we consider here.

Atkeson, C., & Morimoto, J. (2003). Nonparametric representation of policies and value functions: A trajectorybased approach. NIPS 15.

Model predictive control (MPC) (Garcia et al., 1989)(indirectly) addresses the issue of state uncertainty increasing over time, by explicitly computing new controllers at every time step in an online manner. However, MPC is generally orthogonal to the ideas we
present here, since one could just as easily use a spaceindexed dynamic programming method for the local
controller in MPC. Furthermore, MPC can often times
be computationally impractical to run real-time. An
alternative approach is to use a local control method,such as DDP, in order to estimate the value function
along several trajectories, and use these local estimatesto build an approximate global model of the valuefunction (Atkeson, 1994; Tassa et al., 2007). However, since these methods employ DDP, which is atime-indexed algorithm, they can potentially suffer thesame problems as time-indexed methods in general.

Dorf, R., & Bishop, R. (2000). Modern control systems,
9th edition. Prentice-Hall.

6. Conclusions
In this paper we presented a space-indexed dynamic
programming method for trajectory following. We
showed how to convert standard time-indexed dynamical systems into equivalent space-indexed dynamicalsystems, and used this formulation to derive spaceindexed versions of two well-known dynamic programming algorithms, DDP and PSDP. Finally, we successfully applied these methods to several control tasks,
and demonstrated superior performance compared totheir time-indexed counterparts.
Acknowledgments. This work was supported by
the DARPA Learning Locomotion program under contract number FA8650-05-C-7261. We thank the anonymous reviewers for helpful comments, Sam Schreiber
and Quan Gan for assistance with the RC car, Pieter
Abbeel for assistance with the helicopter domain,Mark Woodward, Mike Montemerlo, Gabe Hoffmann,
David Stavens and Sebastian Thrun for assistance with
the DARPA Grand Challenge vehicle.

References
Anderson, B. D. O., & Moore, J. B. (1989). Optimal control: Linear quadratic methods.

Atkeson, C. G. (1994). Using local trajectory optimizers to
speed up global optimization in dynamic programming.
Neural Information Processing Systems 6.
Bagnell, J., & Schneider, J. (2001). Autonomous helicopter control using reinforcement learning policy searchmethods. Proceedings of the International Conference on
Robotics and Automation.
Bagnell, J. A., Kakade, S., Ng, A. Y., & Schneider, J.
(2004). Policy search by dynamic programming. Neural
Information Processing Systems 16.

Egerstedt, M., & Hu, X. (2000). Coordinated trajectory
following for mobile manipulation. Proceedings of theInternation Conference on Robotics and Automation.
Franklin, G., Powell, J., & Emani-Naeini, A. (1995). Feedback control of dynamic systems. Addison-Wesley.
Garcia, C., Prett, D., & Morari, M. (1989). Model predictive control: theory and practice — a survey. Automatica, 25, 335–348.
Geibel, P., Brefeld, U., & Wysotzki, F. (2004). Perceptron and SVM learning with generalized cost models.
Intelligent Data Analysis, 8.
Hoffmann, G., Tomlin, C., Montemerlo, M., & Thrun, S.
(2007). Autonomous automobile trajectory tracking foroff-road driving: Controller design, experimental validation and racing. Proc. 26th American Control Conf.
Jacobson, D., & Mayne, D. (1970). Differential dynamic
programming. Elsevier.
Johnson, E., & Calise, A. (2002). A six degree-of-freedom
adaptive flight control architecture for trajectory following. Proceedings of the AIAA Guidance, Navigation, andControl Conference.
Lagoudakis, M., & Parr, R. (2003). Reinforcement learning
as classification: Leveraging modern classifiers. Proceedings of the Int’l Conf on Machine Learning.
Leith, D., & Leithead, W. (2000). Survey of gainscheduling analysis and design. International Journalof Control, 73, 1001–1025.
Ng, A. Y., Kim, H. J., Jordan, M., & Russell, S. (2004).
Autonomous helicopter flight via reinforcement learning.
Neural Information Processing Systems 16.
Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. Wiley.
Rossetter, E., & Gerdes, J. (2002). Performance guarantees for hazard based lateral vehicle control. Proceedingsof the International Mechanical Engineering Conference
and Exposition.
Sastry, S. (1999). Nonlinear systems. Springer.
Tassa, Y., Erez, T., & Smart, W. (2007). Receding horizon
differential dynamic programming. NIPS 20.
Thrun, S., & al. (2006). Winning the DARPA Grand Challenge. J. of Field Robotics. accepted for publication.