关键词: 路径规划, 移动机器人, Quick-RRT* , 初始路径, 收敛速度

Abstract: The optimal rapid expansion randomized tree ( RRT* ) is an asymptotically optimal path planning method for mobile robots． Quick-RRT* reduces the initial path length of RRT* and increases the path convergence speed． In order to further improve the convergence speed of Quick-RRT* ，this paper proposed a dual-tree Quick-RRT* ( Quick-RRT* -Connect) algorithm． Firstly，two random trees were generated at the start and end points respectively based on the Quick-RRT* algorithm． Two trees grew in turn and they were connected with greedy method． Then， the probability completeness and asymptotic optimality of the proposed algorithm were analyzed and testified． Finally，based on the Matlab platform，Quick-RRT* -Connect was compared with RRT* ，Quick-RRT* and RRT* - Connect in three environments． The results show that the improved algorithm can not only find initial path and suboptimal path in a shorter time，but also reduce the initial path length．

Key words: path planning, mobile robot, Quick-RRT* , initial path, convergence speed