Trajectory Planning for Car-Like Robots in
Unknown, Unstructured Environments
Dennis Fassbender, Andr
´
e Mueller and Hans-Joachim Wuensche
∗
Abstract— We describe a variable-velocity trajectory plan-
ning algorithm for navigating car-like robots through unknown,
unstructured environments along a series of possibly corrupted
GPS waypoints. The trajectories are guaranteed to be kine-
matically feasible, i.e., they respect the robot’s acceleration
and deceleration capabilities as well as its maximum steering
angle and steering rate. Their costs are computed using LiDAR
and camera data and depend on factors such as proximity
to obstacles, curvature, changes of curvature, and slope. In a
second step, velocities for the least-cost trajectory are adjusted
based on the dynamics of the vehicle. When the robot is faced
with an obstacle on its trajectory, the planner is restarted to
compute an alternative trajectory. Our algorithm is robust
against GPS error and waypoints placed in obstacle-filled
areas. It was successfully used at euRathlon 2013
1
, where
our autonomous vehicle MuCAR-3 took first place in the
“Autonomous Navigation” scenario.
I. INTRODUCTION
In the years following the 2005 DARPA Grand Challenge
(DGC) as well as the 2007 DARPA Urban Challenge (DUC),
a variety of methods of trajectory planning for car-like robots
have been proposed. However, the bulk of the publications in
this field focuses on vehicles operating in highly structured
environments such as highways or urban roads, where ele-
ments like lane markings and traffic barriers guide the vehicle
and constrain the planner’s solution space. In contrast, the
algorithm presented here was developed for autonomous nav-
igation in unstructured, obstacle-rich environments. Although
it expects a series of GPS waypoints as input, it does not
assume that all of the waypoints are actually reachable or that
the lines between adjacent points represent driveable paths.
Even if these assumptions were correct, strictly following the
path formed by the waypoints could still cause collisions due
to poor GPS reception, e.g. in a forest. Instead, the algorithm
relies on grid maps constructed from LiDAR and camera data
to analyze its surroundings and generate trajectories that take
it closer to the next waypoint.
The paper is structured as follows: Section II covers related
work. The planning algorithm itself is described in detail in
section III. Section IV presents experimental results gathered
by running the planner on our autonomous robot MuCAR-3
(Munich Cognitive Autonomous Robot Car, 3rd Generation).
Finally, section V concludes the paper and gives some ideas
for future extensions.
∗
All authors are with Department of Aerospace Engineering,
Autonomous Systems Technology (TAS), University of the
Bundeswehr Munich, Neubiberg, Germany. Contact author email:
dennis.fassbender@unibw.de
1
http://www.eurathlon.eu/
Fig. 1. MuCAR-3 navigating around obstacles at the euRathlon 2013
competition.
II. RELATED WORK
Thrun et al. [1], who won the 2005 DGC with their robot
Stanley, used a rather simple method of trajectory planning
that relied on the road data definition format (RDDF) file
provided to them. Before the race started, they computed
a base trajectory from the available data. In order to avoid
obstacles, the vehicle’s lateral offset to this base trajectory
was adjusted during the race. The necessary maneuvers
were computed by a search algorithm that minimized a cost
function while respecting the vehicle’s kinematic constraints.
Urmson et al. [2] (2nd & 3rd place) similarly computed a
global pre-planned path and then used A* search to find a
local path in a search graph constructed from the pre-planned
path. Finally, Trepagnier et al. [3] (4th place) constructed
obstacle-free, dynamically feasible trajectories by adjusting
the control points of a cubic B-spline that initially runs along
the center of the corridor defined by the RDDF file.
Von Hundelshausen et al. [4] implemented a set of pre-
computed trajectories (“tentacles”) that were evaluated on
the same kind of grid maps used by the algorithm described
here. An early version of the planner was used by Team
AnnieWAY’s entry to the 2007 DUC as a low-level fallback.
Later on, the approach was successfully demonstrated at the
ELROB
2
competitions. However, it was only able to generate
simple trajectories computed for fixed velocities. Complex
maneuvers had to be handled by a higher-level module.
Ziegler et al. [5] describe an A*-based algorithm that
constructs trajectories from clothoid-like arcs assuming con-
stant speed. The algorithm was used at the 2007 DUC by
Team AnnieWAY’s higher-level planning module to navigate
unstructured areas such as parking lots. Its A* heuristic is
2
http://www.elrob.org/
2014 IEEE/RSJ International Conference on
Intelligent Robots and Systems (IROS 2014)
September 14-18, 2014, Chicago, IL, USA
978-1-4799-6934-0/14/$31.00 ©2014 IEEE 3630
评论0