Path planning for formations using global optimization with sparse grids

Abstract

This paper proposes an original path planning method developed for leader following formations of car-like robots. In this approach a reference path calculated by the leader should be feasible for all following robots without changing a relative distance in the formation. This requirement can be satisfied using a solution which is composed of smoothly connected cubic splines and can be calculated in real time. Qualities of the result like the length and minimal radius of the resulting path as well as the distance to obstacles are merged into a discontinuous penalty function. The resulting global minimization problem is solved with a deterministic approach based on sparse grids. This algorithm has been tested for several applications in real robotics environments and compared with the results from a stochastic Particle Swarm Optimization method. Some of the determined solutions were then verified by simulations of formation movements.