Genetic Algorithm-based Path Planning In Complex Environment

Path planning is one of the popular research problems in robot field and the quality of the planned path may significantly affect the most applications of mobile robots.In the future,the application environment of mobile robots will be increasingly complex and diverse.How to plan a reasonable path effectively catering to various complex environments has become a new challenge in the field of path planning of mobile robots.An improved bidirectional rapidly-exploring random tree(Bi-RRT)-based population initialization method is proposed in this thesis in order to improve the performance of the genetic algorithm-based robot path planning(GARPP)algorithm in complex environment.First,the extension process and the connection process of Bi-RRT algorithm are improved to create multi-cluster connections between the starting point and the goal point,and a RRT is constructed based on the connections.Second,in order to obtain a set of widespread feasible paths,the RRT is queried repeatedly by using a backtracking method,and thus a diversified initial population is generated.Subsequently,the GA combining with the proposed population initialization method is adopted to find the optimal path.To quantitatively analyze the diversity of initial population,a new breadth-based population performance index is defined in terms of the Hausdorff distance among different paths.Finally,the optimal path is further smoothed with the help of the technique of B-spline curves to facilitate the practical application.In order to improve the efficiency of path planning of the mobile robots in complex environment,a Multi i Compact-RRT and GA based path planning algorithm is proposed in this thesis.First,a new map preprocessing idea,a new sampling polarization technique and a new extension strategy are proposed,which improves the robustness and efficiency of the extension of the Compact-RRT algorithm in complex environment.Second,a Multi i Compact-RRT algorithm is proposed where multiple Compact-RRTs are capable of extending the original map concurrently and offline,without the need of specifying the starting and goal points.Third,after the starting and the goal points are determined according to the mobile robot's real tasks,the RRT is queried effectively by using the hierarchical search method proposed in this thesis and then the feasible paths connecting the starting and goal points are obtained.Finally,a new path planning algorithm is formed by combining the Multi i Compact-RRT and the GA.Two groups of simulation experiments are designed to verify the effectiveness of the above two path planning algorithms.A group of experiment results shows that the proposed improved Bi-RRT based population initialization method is capable of generating a more diversified initial population with less execution time,and the performance of the GA with the improved Bi-RRT is improved significantly.The other group of experimental results shows that the extension ability of the i Compact-RRT algorithm proposed in this thesis is superior to other RRT algorithms,and the extension ability is improved further for the proposed Multi i Compact-RRT algorithm.Moreover,the experimental results also show that the Multi i Compact-RRT and GA based path planning algorithm outperforms other algorithms obviously and effectively improve the path planning performance for robots in the complex environment.