改进双向快速搜索随机树的无人艇路径规划

Improved bi-directional rapidly-exploring random tree path planning for USV

针对双向快速搜索随机树(bidirectional rapidly-exploring random tree, BI-RRT)算法在全局路径规划时存在搜索效率低、路径拐点较多等问题,提出一种改进BI-RRT的水面无人艇(unmanned surface vehicle, USV)全局路径规划算法。该算法采取了极度贪心的思想、高斯偏置随机点采样方法以及启发式的节点扩展策略,同时对节点扩展和搜索树连接进行角度约束,将生成的路径进行剪枝和3次B样条优化处理。结果表明,相对于改进前,改进的BI-RRT在平均时间、随机采样点和平均路径上分别减少了40.5%、65.0%和24.0%。改进后的算法时间、采样点和搜索树扩展大幅度减少,路径平滑度提高且路径更短。

Aiming at the problems of bi-directional rapidly-exploring random tree(BI-RRT)algorithm in global path planning,such as low search efficiency and many turning points,an improved BI-RRT algorithm for global path planning of unmanned surface vehicle(USV)is proposed.The proposed algorithm adopts the idea of extreme greed,a Gaussian biased random point sampling method and a heuristic node expansion strategy.The node expansion and search tree connection are also angularly constrained,and the generated paths are cut and optimized with three B-samples.The results show that the improved BI-RRT reduces the average time,random sampling points,and average path by 40.5%,65.0%,and 24.0%,respectively,compared to the previous BI-RRT.The improved algorithm has a significant reduction in time consumption,sampling points and search tree expansion,with improved path smoothing and shorter paths.