Generating optimized paths for motion planning

This paper addresses the optimization of paths generated using randomized algorithms. We shall present an iterative algorithm to optimize raw paths. However, unlike local post-processing optimizers, our method aims at a more global optimization of the initial path, if possible, performing a drastic topological update, but instead of re-planning in the whole robot configuration space (CC), it uses the initial path to limit the search within an optimal subset of CC. Should a better solution be found, the subspace is further reduced. A lazy A∗ search is used to efficiently search the graph representing the optimal subspace connectivity. The algorithm is designed to achieve a satisfactory and general optimization, while remaining computationally attractive. This paper also exposes some of the issues associated with shortcuts-like post-processing algorithms, namely, the problem of local shortcuts and their effect on the final solution. In order to assess the performance of this iterative re-planning algorithm, it is compared to the well established random shortcuts technique. Extensive experimental results are provided, these include different optimization criteria, a variety of robotic systems and environments, and different statistical measures.

► An Iterative Local Re-planning algorithm for post-optimizing randomized paths.
► The algorithm is computationally competitive with local methods but less sensitive to initial solutions.
► A lazy collision checking A∗ graph search algorithm.
► A generic path optimization technique, with respect to the cost function or robot type.