Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms

• Published in: Soft computing (Berlin, Germany) Germany), 2013-07, Vol.17 (7), p.1283-1299
• Main Authors: Ahmed, Faez, Deb, Kalyanmoy
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Barriers; Computational Intelligence; Control; Elitism; Engineering; Genes; Genetic algorithms; Mathematical Logic and Foundations; Mechatronics; Methodologies and Application; Multiple objective analysis; Optimization; Optimization algorithms; Optimization techniques; Path planning; Representations; Robotics; Safety; Smoothness; Soft computing; Sorting algorithms
• ISSN: 1432-7643; 1433-7479
• DOI: 10.1007/s00500-012-0964-8

A multi-objective vehicle path planning method has been proposed to optimize path length, path safety, and path smoothness using the elitist non-dominated sorting genetic algorithm—a well-known soft computing approach. Four different path representation schemes that begin their coding from the start point and move one grid at a time towards the destination point are proposed. Minimization of traveled distance and maximization of path safety are considered as objectives of this study while path smoothness is considered as a secondary objective. This study makes an extensive analysis of a number of issues related to the optimization of path planning task-handling of constraints associated with the problem, identifying an efficient path representation scheme, handling single versus multiple objectives, and evaluating the proposed algorithm on large-sized grids and having a dense set of obstacles. The study also compares the performance of the proposed algorithm with an existing GA-based approach. The evaluation of the proposed procedure against extreme conditions having a dense (as high as 91 %) placement of obstacles indicates its robustness and efficiency in solving complex path planning problems. The paper demonstrates the flexibility of evolutionary computing approaches in dealing with large-scale and multi-objective optimization problems.