基于四叉树自适应分辨率算法的智能船舶路径规划

    Intelligent ship path planning based on quadtree adaptive resolution algorithm

    • 摘要: 为了优化智能船舶路径问题,提高在数据量大的地图上的运行速度,考虑船舶的航行特点,提出一种基于四叉树栅格模型下改进的A*算法。首先,利用四叉树自适应分辨率图像处理算法,将海图中的航行信息进行分析整合,更高效率地将可航行区域、航行限制区域和不可航行区域标记划分。其次,综合考虑船舶航行自身特性和环境特性,在传统A*算法中加入距离惩罚函数,基于候选节点与障碍物节点之间的距离计算惩罚值,并在四叉树自适应分辨率栅格对象中建立对象成本模型。最后,利用一艘单螺旋桨高速集装箱船在两个海图上进行路径规划,得出的结合四叉树图像分割技术的A*算法自适应分辨率海图路径规划模型在运算速度和保证与障碍物之间的距离方面表现良好。

       

      Abstract: In order to optimize the intelligent ship routing problem, improve the speed of operation on maps with large amounts of data, and consider the navigation characteristics of ships, an improved A* algorithm based on a quadtree grid model is proposed. Firstly, the quadtree adaptive resolution image processing algorithm is employed to analyze and integrate navigation information in the chart. And the navigable area, restricted navigation area and unnavigable area are marked and divided more efficiently. Secondly, in consideration of the characteristics of ship navigation and environment,the distance penalty function is added to A* algorithm. The penalty value is calculated by use of the distance between candidate nodes and obstacle nodes. And the cost model of grid object is established in the quadtree adaptive resolution raster object. Finally, The proposed algorithm is illustrated for the path planning of a container ship with single propeller on two charts. The proposed A* path planning algorithm performs well in terms of computing speed and ensuring safety between obstacles.

       

    /

    返回文章
    返回