Numerical path optimization for path planning with cell decomposition methods

Many path planning systems designed for the use in autonomous mobile robots are based on cell decomposition methods combined with a subsequent graph search due to their efficiency and ease of handling. Furthermore, even more sophisticated methods such as the quadtree decomposition method can be applied prosperously Spline interpolation is often used to attain a feasible trajectory by interpolating the centerpoints of the cells which belong to the found free channel. Nevertheless, there are some negative effects using such interpolating spline functions. First, they may introduce oszillations between the control-points. Second, strong curvatures can be the result at some distinguished control-points. Furthermore, suboptimal trajectory lengths and step function behaviour of the spline may be present, too. The remedy of such problems can be given by a subsequent optimization step with the goal to obtain smooth trajectories without strong curvatures. This is done by moving the control-points of the spline in the respective cells of the cell decomposition. Such an optimization method using the Nelder-Mead-Algorithm is presented in this paper. Examples of successful path planning tasks demonstrating this optimization method are also presented.