GRRT*-DWA: fast path search algorithm for mobile robot navigation in dynamic complex maps
摘要
In this paper, we propose a novel algorithm, called Greedy Random Tree * -Dynamic Window Method (GRRT*-DWA), which aims to address the dual optimization challenge of real-time path planning for mobile robots in dynamic and complex environments. The existing algorithms based on rapidly-exploring Random Tree * (RRT*) achieve path optimization through node sampling and tree expansion. However, they are limited by the inability to avoid unknown dynamic obstacles in real time. In addition, the traditional dynamic window method is easy to fall into local optimum in local path planning. To overcome these problems, this study uses feedback partial sampling instead of traditional random sampling in RRT*, so that the random tree can dynamically adjust the sampling probability according to the feedback of obstacles, and preferentially sample in the area close to the known optimal path, thereby optimizing the path and improving efficiency. In the expansion process, node filtering and adaptive step strategy are combined, and a greedy algorithm is used to select waypoints to eliminate redundant points and shorten the global path. Finally, in order to ensure that the path planned in the dynamic and complex environment does not deviate from the global optimum, the key points are extracted from the global path generated by the GRRT* algorithm as the guide points of the DWA algorithm. A new sub-evaluation function is introduced to optimize the DWA algorithm, and the weighted method is used to fully consider the influence of the global optimum in the path planning process, which enhances the applicability of the algorithm and improves the planning efficiency. The proposed method combines the global path of GRRT* with the local optimization of DWA, making full use of the symmetry principle in path planning. The algorithm can effectively adjust the mobile path under symmetric constraints, which fully reflects the symmetric relationship between efficiency and energy consumption in path planning, that is, find a balance between path search time and path length, so as to achieve more efficient path search and more stable navigation performance. Finally, simulation experiments verify that the proposed GRRT*-DWA algorithm improves the efficiency by 56.5%compared with the current mainstream algorithms, and the final result is optimized by 4.6%. and it has higher path search stability in complex scenes with static and dynamic mixed obstacles.