A Knowledge Based Genetic Algorithm for Path Planning in Unstructured Mobile Robot Environments

Abstract

This paper proposes a knowledge based genetic algorithm (GA) for path planning of a mobile robot in unstructured environments. The algorithm uses a unique problem representation method to represent 2-dimensional robot environments with complex obstacle layouts of arbitrary obstacle shapes. An effective evaluation method is specially developed for the proposed genetic algorithm. The evaluation method is able to accurately detect collisions between a robot path and an arbitrarily shaped obstacle, and assigns costs that is very effective for the proposed genetic algorithm. The proposed GA uses problem-specific genetic algorithms for robot path planning instead of the standard GAs. The proposed knowledge based genetic algorithm incorporates the domain knowledge of robot path planning into its specialized operators, where some also combine a local search technique. The effectiveness and efficiency of the proposed genetic algorithm is demonstrated by simulation studies. The irreplaceable role of the specialized genetic operators for solving robot path-planning problem is shown by a comparison study.