基于自适应步长快速搜索随机树算法的船舶避碰路径规划

An Ada-RRT-based ship collision avoidance path planning algorithm

快速搜索随机树算法被广泛应用于船舶避碰路径规划。针对传统快速搜索随机树算法在复杂水域条件下搜索效率低的问题,提出了基于自适应步长快速搜索随机树算法的船舶避碰路径规划模型。首先,引入船舶领域模型,并基于《国际海上避碰规则》为让路船设置虚拟障碍。其次,引入时间序列并建立动态障碍检测机制。采用启发式采样策略,减少无效节点的生成。最后,建立障碍物密集度与搜索步长的映射关系,以上一步采样步长作为已知条件预测当前步采样步长,并利用采样点周围障碍物密集程度修正当前最优的采样步长。仿真试验结果表明,相较于传统的快速搜索随机树算法,采用自适应步长快速搜索随机树算法的船舶避碰路径规划模型在采样成功率、搜索路径耗时、路径段数和路径总长度等四个方面均表现最优,在提高算法效率的同时能够实现更高质量的路径规划。

A collision avoidance path planning model is developed based on Adaptive step Rapidly-exploring Random Tree(Ada-RRT)algorithm instead of conventional RRT.The latter may experience low sampling efficiency in complex environments.The ship domain model is introduced to guarantee safety.Virtual obstacles are generated to ensure that the planned path complies with COLREGs.The time series is introduced to establish a dynamic obstacle detection mechanism.Heuristic sampling strategy is adopted to prevent the generation of invalid nodes.The mapping function between obstacle density and RRT searching step size is established.With the linear dynamic model,the preliminary current searching step size is calculated according to the previous searching step size.The preliminary step size is optimized according to the obstacle density information.Simulation is carried out.The results show that,compared with the conventional RRT model,the ship collision avoidance path planning model using Ada-RRT algorithm performs is superior in four aspects:sampling success rate,path searching time,number of path segments and total length of path.