A hierarchical genetic algorithm for path planning in a static environment with obstacles

In this paper, a new hierarchical genetic algorithm for path planning in a static environment with obstacles is presented. The algorithm of path planning in this paper is inspired by the Dubins\´ theorem regarding shortest paths of bounded curvature in the absence of obstacles. The algorithm is based on the Dubins\´ theorem to simplify the problem model, the genetic algorithm to search the best path, a special hierarchical structure of chromosome to denote a possible path in the environment, the special genetic operators for each module, and a penalty strategy to "punish" the infeasible chromosomes during searching. The performance results presented have shown that the approach is able to produce high quality solutions in reasonable time.