WIAS Preprint No. 1900, (2013)

A coupling of discrete and continuous optimization to solve kinodynamic motion planning problems


  • Landry, Chantal
  • Welz, Wolfgang
  • Gerdts, Matthias

2010 Mathematics Subject Classification

  • 49J15 49M25 49N90 70E60 90C30 90C35


  • trajectory planning, optimal control problem, collision avoidance, graph search algorithm, initialization, robotics




A new approach to find the fastest trajectory of a robot avoiding obstacles, is presented. This optimal trajectory is the solution of an optimal control problem with kinematic and dynamics constraints. The approach involves a direct method based on the time discretization of the control variable. We mainly focus on the computation of a good initial trajectory. Our method combines discrete and continuous optimization concepts. First, a graph search algorithm is used to determine a list of via points. Then, an optimal control problem of small size is defined to find the fastest trajectory that passes through the vicinity of the via points. The resulting solution is the initial trajectory. Our approach is applied to a single body mobile robot. The numerical results show the quality of the initial trajectory and its low computational cost.

Appeared in

Download Documents