Thesis Snapshot: Planning of collision-free trajectories for UAVs and optimization using uniform B-splines. (Bachelor thesis by Alexander Bast)

Autonomous vehicles will be an integral part of our environment and will have a significant impact on transportation and other industries. In this context, drones, so-called UAVs will be used for aerial transportation. Due to the high information density, motion planning is a fundamental problem in the autonomous movement of vehicles.
In the future, drones should transport goods or perhaps people in a fast, safe and thus collision-free manner. In doing so, the drone should be able to perform all calculations quickly, accurately and autonomously. Therefore, it makes sense to develop algorithms that meet these requirements.
As part of a bachelor thesis, a method [1] was investigated that uses uniform B-splines to replan a drone’s trajectory in the presence of a potential collision. This method formulates the task of replanning the trajectory as the solution to a non-linear optimization problem.
\begin{align*}
E=\lambda_{ep}(p(t_{ep})-p_{ep})^{2}+\lambda_{ep}(p'(t_{ep})-p’_{ep})^{2} + \lambda_{c} \int_{t_{min}}^{t_{max}}c(p(t))||p'(t)||dt + \sum_{i=2}^{4}\int_{t_{min}}^{t_{max}}\lambda_{q}(p^{(i)}(t))^{2}dt
\end{align*}
With this simplified equation, three cost terms are considered: Endpoint error, collision cost and quadratic derivative cost. With the goal of computing an efficient and collision-free trajectory, an iterative process is used to construct a B-spline curve such that it follows a pre-planned and optimal trajectory. The focus of the analysis was on the selection of the control parameters λep, λc, λq, as well as the number of control points to be optimized and the resulting properties of the optimized trajectory. Using a uniform knot vector, the B-spline is expanded to include control points whose spatial coordinates are determined using nonlinear optimization so that the objective function is minimized. Due to the properties of B-splines, upcoming segments can be locally optimized so that a collision is prevented. The use of a uniform knot vector allows an efficient replanning of the trajectory in real time, which can be performed autonomously by a drone. The following figure shows one result.

[1] Vladyslav Usenko, Lukas von Stumberg, Andrej Pangercic, Daniel Cremers, Real-Time Trajectory Replanning for MAVs using Uniform B-splines and a 3D Circular Buffer, Technical University of Munich, 2017, https://arxiv.org/abs/1703.01416.