Robotics and Autonomous Systems 88 (2017) 142–153
Contents lists available at ScienceDirect
Robotics and Autonomous Systems
journal homepage: www.elsevier.com/locate/robot
Integrated online trajectory planning and optimization in distinctive
topologies
Christoph Rösmann *, Frank Hoffmann, Torsten Bertram
Institute of Control Theory and Systems Engineering, Technical University of Dortmund, 44227 Dortmund, Germany
h i g h l i g h t s
• An integrated online trajectory optimization approach is proposed.
• Maintaining and optimization of admissible candidate trajectories of distinctive topologies in order to seek the overall best solution.
• An exploration strategy based on Voronoi diagrams provides the complete set of alternative trajectories.
• An alternative proposed sampling based strategy generates a sufficient subset for small to medium sized environments under limited computational
budgets.
• The Timed-Elastic-Band trajectory optimization method complies with non-holonomic kinematics of differential-drive and carlike robots.
a r t i c l e i n f o
Article history:
Received 31 January 2016
Accepted 10 November 2016
Available online 12 November 2016
Keywords:
Online trajectory optimization
Mobile robot motion planning
Distinctive topologies
Homology classes
Timed-Elastic-Band
Model predictive control
a b s t r a c t
This paper presents a novel integrated approach for efficient optimization based online trajectory
planning of topologically distinctive mobile robot trajectories. Online trajectory optimization deforms an
initial coarse path generated by a global planner by minimizing objectives such as path length, transition
time or control effort. Kinodynamic motion properties of mobile robots and clearance from obstacles
impose additional equality and inequality constraints on the trajectory optimization. Local planners
account for efficiency by restricting the search space to locally optimal solutions only. However, the
objective function is usually non-convex as the presence of obstacles generates multiple distinctive local
optima.
The proposed method maintains and simultaneously optimizes a subset of admissible candidate
trajectories of distinctive topologies and thus seeking the overall best candidate among the set of
alternative local solutions. Time-optimal trajectories for differential-drive and carlike robots are obtained
efficiently by adopting the Timed-Elastic-Band approach for the underlying trajectory optimization prob-
lem. The investigation of various example scenarios and a comparative analysis with conventional local
planners confirm the advantages ofintegratedexploration,maintenance and optimization of topologically
distinctive trajectories.
© 2016 Elsevier B.V. All rights reserved.
1. Introduction
In the context of service robotics and autonomous transporta-
tion systems, mobile robots are required to navigate in highly
dynamic environments while accomplishing complex tasks. On
this occasion, one of the fundamental challenges in mobile robotics
is concerned with the development of universally applicable mo-
tion planning strategies. Online planning is preferred over offline
approaches since they immediately respond to changes in the
environment or perturbations of the robot motion at runtime. The
well known elastic band approach [1] locally deforms a path online.
*
Corresponding author.
E-mail address: christoph.roesmann@tu-dortmund.de (C. Rösmann).
Predefined internal forces contract the path while external forces
maintain a separation from obstacles. An alternative established
path planning approach based on an optimization technique is
presented in [2]. However, conventional path planning does not
explicitly incorporate temporal and (kino-)dynamic aspects of mo-
tion, therefore ignoring constraints imposed by kinematic or dy-
namic motion models with bounded velocities and accelerations.
Kurniawati et al. extend the elastic band approach to the online
deformation of trajectories rather than paths [3]. The approach
consists of two stages that at first repel discrete trajectory points
from obstacles and secondly enforce connectedness w.r.t. a dy-
namic motion model. Delsart et al. combine both stages into a
single operation [4].
http://dx.doi.org/10.1016/j.robot.2016.11.007
0921-8890/© 2016 Elsevier B.V. All rights reserved.