Optimal Trajectory Generation for Dynamic Street Scenarios in a
Fren
´
et Frame
Moritz Werling, Julius Ziegler, S
¨
oren Kammel, and Sebastian Thrun
Abstract— Safe handling of dynamic highway and inner city
scenarios with autonomous vehicles involves the problem of
generating traffic-adapted trajectories. In order to account for
the practical requirements of the holistic autonomous system,
we propose a semi-reactive trajectory generation method, which
can be tightly integrated into the behavioral layer. The method
realizes long-term objectives such as velocity keeping, merging,
following, stopping, in combination with a reactive collision
avoidance by means of optimal-control strategies within the
Fren
´
et-Frame [12] of the street. The capabilities of this ap-
proach are demonstrated in the simulation of a typical high-
speed highway scenario.
I. INTRODUCTION
A. Motivation
The past three decades have witnessed ambitious research
in the area of automated driving. As autonomous vehicles
advance toward handling realistic road traffic, they face street
scenarios where dynamics of other traffic participants must
be considered explicitly. This i ncludes every day driving
maneuvers like merging into traffic flow, passing with on-
coming traffic, changing lanes, or avoiding other vehicles.
Under simplified conditions, such as during the 2007 DARPA
Urban Challenge
1
, this can be tackled with fairly simple
heuristics and conservative estimates [18]. However, these
approaches quickly reach their limits in nose-to-tail traffic
and at high driving speeds resulting in poor performance or
even accidents [5]. This is where trajectory concepts come
into play, which explicitly account for the time t on the
planning and execution level.
The presented method embarks on this strategy and sets
itself apart from previous work in that it is especially
suitable for highway driving, as it generates velocity invari-
ant movement
2
and transfers velocity and distance control
M. Werling is with the Department of Applied Computer Science and
Automation (AIA), University of Karlsruhe, 76131 Karlsruhe, Germany
moritz.werling@iai.fzk.de
J. Ziegler is with the Department of Measurement and Control (MRT),
University of Karlsruhe ziegler@mrt.uka.de
S. Kammel is with Robert Bosch LLC Research and Technology Center,
Palo Alto, California 94304 soeren.kammel@us.bosch.com
S. Thrun is with Stanford Artificial Intelligence Laboratory, Stanford
University, Stanford, California 94305 thrun@stanford.edu
The authors gratefully acknowledge the cooperation between the “Valley
rally” project of Stanford University and the German Transregional Col-
laborative Research C enter 28 Cognitive Automobiles. Both projects cross-
fertilized each other and revealed significant synergy.
1
The DARPA Urban Challenge is a research program conducted in a
competitive format to address the challenges of autonomous driving, see
http://www.darpa.mil/grandchallenge.
2
It is highly desirable to generate lane change and merging maneuvers,
which are timed completely independently from the absolute travelling
speed.
to the planning level. Additionally, the algorithm provides
for reactive obstacle avoidance by the combined usage of
steering and breaking/acceleration.
B. Related work
Several methods for trajectory planning have been pro-
posed [11], [19], [2], [4] that find a global trajectory con-
necting a start and a - possibly distant - goal state. However,
these methods fail to model the inherent unpredictability
of other traffic, and the resulting uncertainty, given that
they rely on precise prediction of other traffic participant’s
motions over a long time period. Other approaches taken
towards trajectory planning follow a discrete optimization
scheme (e. g. [16], [1], [7]): A finite set of trajectories is
computed, typically by forward integration of the differential
equations that describe vehicle dynamics. From this set, the
trajectory is chosen that minimizes a given cost functional.
For generation of the trajectory set a parametric model is
chosen, like curvature polynomials of arbitrary order. While
this reduces the solution space and allows for fast planning, it
may introduce suboptimality. We will show in Sec. II that this
can lead to both overshoots and stationary offsets in curves.
In [9], a tree of trajectories is sampled by simulating the
closed loop system using the rapidly exploring random tree
algorithm [10]. The system incorporates many heuristics in
the form of sampling biases to assert well behaved operation.
An approach that is in a similar spirit to our method but
only considers the free problem that is not constrained by
obstacles has been taken by [17]. Here, the optimal control
trajectory for an aero dynamic system is found within a
function space that is spanned by a Galerkin base.
For the above mentioned reasons and to, at least partly,
overcome the limitations of the approaches described in the
literature, we propose a local method, which is capable of
realizing high-level decisions made by an upstream, behav-
ioral layer (long-term objectives) and also performs (reactive)
emergency obstacle avoidance in unexpected critical situa-
tions. One aspect that sets our method especially apart from
other schemes is the guaranteed stability (temporal consi-
tency) of the non-reactive maneuvers that follows directly
from Bellman’s principle of optimality. Within this work
we adhere with the strategy of strictly decoupling feedback
from planning. We demonstrated before that it is advantagous
to separate the navigation task into real time trajectory
generation and subsequent local stabilization through trajec-
tory tracking feedback control. This is in contrast to some
other approaches that close the control loop by feeding the
observed state of the system directly back into the planning
2010 IEEE International Conference on Robotics and Automation
Anchorage Convention District
May 3-8, 2010, Anchorage, Alaska, USA
978-1-4244-5040-4/10/$26.00 ©2010 IEEE 987