Path-planning with obstacle-avoiding minimum curvature variation B-splines

Sammanfattning: We study the general problem of computing an obstacle-avoiding path that, for a prescribed weight, minimizes the weighted sum of a smoothness measure and a safety measure of the path. We consider planar curvature-continuous paths, that are functions on an interval of a room axis, for a point-size vehicle amidst obstacles. The obstacles are two disjoint continuous functions on the same interval. A path is found as a minimizer of the weighted sum of two costs, namely 1) the integral of the square of arc- length derivative of curvature along the path (smoothness), and 2) the distance in L2 norm between the path and the point-wise arithmetic mean of the obstacles (safety). We formulate a variant of this problem in which we restrict the path to be a B-spline function and the obstacles to be piece-wise linear functions. Through implementations, we demonstrate that it is possible to compute paths, for different choices of weights, and use them in practical industrial applications, in our case for use by the ore transport vehicles operated by the Swedish mining company Luossavaara-Kiirunavaara AB (LKAB). Assuming that the constraint set is non-empty, we show that, if only safety is considered, this problem is trivially solved. We also show that properties of the problem, for an arbitrary weight, can be studied by investigating the problem when only smoothness is considered. The uniqueness of the solution is studied by the convexity properties of the problem. We prove that the convexity properties of the problem are preserved due to a scaling and translation of the knot sequence defining the B-spline. Furthermore, we prove that a convexity investigation of the problem amounts to investigating the convexity properties of an unconstrained variant of the problem. An empirical investigation of the problem indicates that it has one unique solution. When only smoothness is considered, the approximation properties of a B-spline solution are investigated. We prove that, if there exists a sequence of B-spline minimizers that converge to a path as the number of B-spline basis functions tends to infinity, then this path is a solution to the general problem. We provide an example of such a converging sequence.