Pareto Genetic Path Planning Hybridized with Multi-objective Dijkstra's Algorithm

This paper presents an evolutionary approach to multi-objective path planning. The paths are defined on continuous scenes with disjoint and/or non-convex obstacles, for robots moving towards their destinations along linearly piecewise trajectories with any number of vertices. The fastest feasible route is genetically selected via a simultaneous minimization of path length and path steering angle. In order to assure an effective partial sorting of the potential solutions, the genetic algorithm makes use of a self-adaptive Pareto ranking scheme, based on individuals' grouping and dominance analysis. Before ranking, all the unfeasible solutions are corrected, by replacing the sub-paths which intersect the obstacles. The feasible segments are chosen from graphs generated with Delaunay triangulation, by applying a new multi-objective ranking-based fastest path procedure derived from the classical Dijsktra's algorithm. This new procedure is compatible with any nonlinear objective functions and allows using the same ranking scheme during the evolutionary search and correction of paths, thus making possible to guarantee the feasibility of the paths without any significant intrusion in the evolutionary exploration. The proposed algorithm can also be used for solving any graph based path planning problem, involving any number of objectives. The experiments show the usefulness of the suggested techniques on working scenes with different layouts of obstacles.