Voronoi Strains - A Spline Path Planning Algorithm for Complex Environments

M. Saska, M. Hess, and K. Schilling (Germany)


Voronoi graph, path planning, Particle swarm optimization, spline functions, mobile robotics


Path planning and obstacle avoidance methods are often re quired for robots working in more and more complicated environments. This paper introduces a novel approach called Voronoi Strains for solving this task. The algorithm applies particle swarm optimization of cubic splines which are connected to strings. The initialization of the evolution ary algorithm is based on the Voronoi graph method as well as on strains of bacteria. Strains whose evolution is stuck in a dead end because of a local optimum die off. Only the strain located close to the global optimum or the biggest local optimum will survive the evolutionary process. Different settings of PSO parameters have been tested in various simulation experiments. The Voronoi Strains ap proach was also compared with other PSO methods using a different kind of initialization.

Important Links:

Go Back