AGTB-RRT^(*):一种基于近似测地线避障策略的目标双向3D RRT^(*)路径规划算法

AGTB-RRT^(*):A target bidirectional 3D RRT^(*)path planning algorithm based on approximate geodesic obstacle avoidance strategy

针对传统3D RRT^(*)全局路径规划算法存在的采样基数大、父节点重选计算量大、节点扩展盲目、搜索路径不平滑等问题,提出一种基于近似测地线避障策略的目标双向3D RRT^(*)路径规划算法(approximate geodesic target bidirectional RRT^(*),AGTB-RRT^(*)).首先,在双向目标点的连接路径上设置近似中位节点,并建立朝起点和目标点双向扩展的随机树,有效提高算法的搜索效率;建立基于单叶双曲面的启发式采样空间,有效减小采样基数和父节点重选计算量并降低内存占用.其次,对目标点和随机点进行阈值切换,并建立目标引力势场,有效降低节点扩展盲目性,提高算法的收敛速度.再次,对3D障碍物建立三角网格包络,并基于近似测地线方法使节点沿3D障碍物包络表面快速绕行,进而规划出一条代价小、速度快的局部避障路径.最后,采用B样条曲线拟合方法对整个生成路径进行优化处理,以得到一条平滑的最优可行路径.仿真实验结果验证了所提出AGTB-RRT^(*)算法在三维空间下用于路径规划的有效性和可行性.

Aiming at the problems of the traditional 3D RRT^(*)global path planning algorithm,such as large sampling base,large calculation of parent node reselecting,blind node expansion,and unsmooth search path,a target bidirectional 3D RRT^(*)path planning algorithm based on the approximate geodesic obstacle avoidance strategy(AGTB-RRT^(*))is proposed.Firstly,the approximate median node is set on the connection path of the bidirectional target point,and the random tree is built to extend bidirectional towards the starting point and target point,which effectively improves the search efficiency of the algorithm.The heuristic sampling space is established based on the one leaf hyperboloid,which effectively reduces the sampling base and the calculation of parent node reselecting,and reduces the memory occupation.Secondly,threshold switching is performed on the target point and random points,and the target gravitational potential field is established,which effectively reduces the blindness of node expansion and improves the convergence speed of the algorithm.Thirdly,the triangular mesh envelope is established for the 3D obstacles,and the approximate geodesic method is used to make the nodes quickly detour along the 3D obstacles envelope surface,and then a local obstacle avoidance path with low cost and high speed is planned.Finally,the B-spline curve fitting method is used to optimize the entire generated path to obtain a smooth and optimal feasible path.Simulation results verify the effectiveness and feasibility of the proposed AGTB-RRT^(*)algorithm for path planning in 3D space.