Hierarchical spline path planning method for complex environments

Path planning and obstacle avoidance algorithms are requested for robots working in more and more complicated environments. Standard methods usually reduce these tasks to the search of a path composed from lines and circles or the planning is executed only with respect to a local neighborhood of the robot. Sophisticated techniques allow to find more natural trajectories for mobile robots, but applications are often limited to the offline case. The novel hierarchical method presented in this paper is able to find a long path in a huge environment with several thousand obstacles in real time. The solution, consisting of multiple cubic splines, is optimized by Particle Swarm Optimization with respect to execution time and safeness. The generated spline paths result in smooth trajectories which can be followed effectively by nonholonomic robots. The developed algorithm was intensively tested in various simulations and statistical results were used to determine crucial parameters. Qualities of the method were verified by comparing the method with a simple PSO path planning approach.