In this thesis, we focus on high dimensional trajectory planning problems subject to geometric obstacle avoidance, mainly arising in robotic motion planning. Due to their non-differential and non-convex structure, we identify the modeling of the collision avoidance constraints as an essential first step towards a feasible solution. Focusing especially on their efficient evaluation, we theoretically verify a well known collision detection strategy based on separating axis. Subsequently, we propose an extension to efficiently compute the penetration distance of two intersecting convex polygons. Striving for a global solution, we derive a discrete dynamic programming algorithm based on a backward Semi-Lagrangian approximation proposed in [21] and generalize the corresponding convergence proof for a weaker set of assumptions. Characterizing the curse of dimensionality as our main issue in the arising numerical procedure, we investigate parallelisation, as well as adaptive state space refinement to lower its effect. In variable end time problems, we additionally exploit the representation in terms of optimal stopping to derive an efficient discrete dynamic programming strategy equipped with proofs on convergence. We proof a reasonable execution time of our accelerated algorithm on an industrial four dimensional robotic arm, as well as real time capability on a three dimensional task arising from autonomous driving. As this methods never the less remains limited to tasks of dimension three to four, we subsequently propose a planning method combining dynamic and nonlinear programming to handle high dimensional systems. Exploiting dynamic programming to handle collision avoidance as well as nonlinear programming to deal with the high dimensional system dynamics, our strategy aims to combine best of both worlds. Based on the original strategy, we additionally propose an extension to allow consideration of moving environments. Considering the example of an acceleration controlled robotic manipulator with six degrees of freedom, we proof efficiency of our combined strategy as well as its variant compared to state of the art solvers. Finally, we demonstrate the extended version to allow trajectory planning towards a tumbling target within the context of space debris removal.     «

In this thesis, we focus on high dimensional trajectory planning problems subject to geometric obstacle avoidance, mainly arising in robotic motion planning. Due to their non-differential and non-convex structure, we identify the modeling of the collision avoidance constraints as an essential first step towards a feasible solution. Focusing especially on their efficient evaluation, we theoretically verify a well known collision detection strategy based on separating axis. Subsequently, we propos...     »