Improved bi-directional rapidly-exploring random tree path planning for USV
赵贵祥 1周健 2李云淼 1王晨旭1
扫码查看
点击上方二维码区域，可以放大扫码查看
作者信息
1. 天津大学海洋科学与技术学院,天津 300110
2. 江苏自动化研究所,北京 100036
折叠
摘要
针对双向快速搜索随机树(bidirectional rapidly-exploring random tree,BI-RRT)算法在全局路径规划时存在搜索效率低、路径拐点较多等问题,提出一种改进BI-RRT的水面无人艇(unmanned surface vehicle,USV)全局路径规划算法.该算法采取了极度贪心的思想、高斯偏置随机点采样方法以及启发式的节点扩展策略,同时对节点扩展和搜索树连接进行角度约束,将生成的路径进行剪枝和3次B样条优化处理.结果表明,相对于改进前,改进的BI-RRT在平均时间、随机采样点和平均路径上分别减少了 40.5％、65.0％和24.0％.改进后的算法时间、采样点和搜索树扩展大幅度减少,路径平滑度提高且路径更短.
Abstract
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.
关键词
路径规划/水面无人艇/双向快速搜索随机树/高斯偏置随机点/角度约束
Key words
path planning/unmanned surface vehicles(USV)/bi-directional rapidly-exploring random tree(BI-RRT)/Gaussian biased random points/angular constraints
维普
万方数据