A knowledge-based genetic algorithm for path planning of mobile robots.

摘要

In this thesis, a knowledge-based genetic algorithm for path planning of mobile robots is proposed. Problem-specific knowledge and heuristic knowledge are incorporated into encoding, evaluation and genetic operators of the genetic algorithm.; The mobile robot environment is represented in a 2-D workspace, where obstacles are represented by the coordinates of their vertices, and can be arbitrary shapes including convex, concave and combined polygons. A mobile robot path is represented by line segments connected by nodes in the 2-D workspace, and the intermediate nodes are formed by grids applied to the environment. An evaluation method is designed according to the environment and path representation, and specifically aimed at easily evolving better solutions with specialized genetic operators. The evaluation features an effective and accurate collision detection algorithm that detects collisions between line segments and an arbitrarily shaped obstacle. The knowledge-based genetic algorithm is characterized by specialized genetic operators that incorporate domain knowledge. These operators use a small-scale local search based on heuristic knowledge. These operators play a crucial role in evolving feasible and good quality solutions.; The knowledge-based genetic algorithm is effective and efficient for mobile robot path planning in complex static environments including clustered unstructured environments and complicated structured environments, and dynamic environments with suddenly appearing obstacles, moving obstacles and moving targets. By considering other mobile robots as moving obstacles, the algorithm can be applied to real-time multi-robot path planning applications. The effectiveness and efficiency of the genetic algorithm are proved by simulation studies.