基于改进A*算法的水面无人艇路径规划

来源:用户上传      作者:舒伟楠　赵建森　谢宗轩　张学生　马欣

　　摘要：为解决水面无人艇（unmanned surface vessel， USV）在碍航物比较密集水域的全局路径规划问题，提出一种基于改进A*算法的路径规划方法。利用像素阈值法剔除船载雷达图像中的冗余信息，并使用栅格法进行环境建模;提出节点碍航物检测法，用于优化无人艇路径规划，同时改进评价函数来减少遍历的节点总数;对规划路径上的冗余节点进行平滑处理。仿真结果表明：相较于A*算法，本文提出的改进A*算法能够确保USV远离碍航物，且算法遍历节点总数和规划路径上的转折点都较少。
　　关键词： 水面无人艇（USV）; 路径规划; A*算法; 碍航物检测
　　中图分类号： U675.7; TP273文献标志码： A
　　Path planning for unmanned surface vessels based on
　　improved A* algorithm
　　Abstract： To address the global path planning issue of unmanned surface vessels （USVs） in waters with dense obstacles， this paper proposes a path planning method based on the improved A* algorithm. The redundant information of shipborne radar images is removed by the pixel threshold method， and the grid method is used to carry out the environment modeling. The node obstacle detection method is proposed to optimize the path planning of USVs， and the evaluation function is improved to reduce the total number of traversal nodes. The redundant nodes on the planned path are smoothed. The simulation results show that， compared with A* algorithm， the proposed improved A* algorithm can ensure that USVs are away from obstacles， the total number of traversal nodes is fewer， and the turning nodes on the planned path are fewer.
　　Key words： unmanned surface vessel （USV）; path planning; A* algorithm; obstacle detection
　　引言
　　S着人工智能技术的快速发展，路径规划在移动机器人领域的应用取得了很大的成就。水面无人艇（unmanned surface vessel， USV）是一种能够实现自主避碰的水上舰艇。当前对USV的研究主要集中在路径规划和自主避障等方面。USV在复杂水域完成全局路径规划和在特殊情况下避障的能力越突出，则说明其智能化水平越高。[1]
　　路径规划是指在有障碍物的情况下，在起点与终点之间寻找出一条尽可能短的安全路径[2-3]。按照对周围环境感知情况的不同，路径规划可以分为环境信息全部掌握的全局路径规划和环境信息部分未知的局部路径规划。A*算法具有搜索效率高的优点，被广泛应用于多种类型的搜索问题中。国内外学者已经对A*算法及其改进算法做了广泛的研究，并且取得了一定的成果。薛双飞[2]将人工势场法与A*算法相结合，根据不同的障碍物类型建立不同的斥力势场，并将该方法应用于东海大桥风机维护船舶的路径规划。王红卫等[4]提出平滑A*算法，解决了规划路径转折次数多的问题。陈豪等[5]基于A*算法，引入方向矢量以优化开放列表。WANG等[6]将船舶转弯半径融入A*算法，在估值函数中引入限制搜索方向的角度成本，生成与船舶实际转弯角度更加契合的路径。余必秀等[7]针对船舶避碰后无法快速回到预设航线的问题，在估值函数中增加一个代价值，让无人航道测量船在估值函数的使用上有不同的选择。王锦川[8]利用二叉堆对A*算法中的Open列表进行维护，加快了A*算法的搜索效率。杨瑶等[9]将车辆的最大转向角约束和最大曲率约束加入启发式函数中，同时提出车身轮廓代价改进拓展节点，使路径更符合车辆的运动学特性。荣少巍[10]将最小转弯半径作为约束条件对传统A*算法进行改进，同时使得A*算法可以实现高速与低速结合的应用。
　　USV具有惯性大、时滞大的特性，且在恶劣海况下易受风浪流的影响。USV只有与碍航物保持一定的安全距离，才能在碰撞危险出现时有足够的反应时间和操纵空间。A*算法的搜索特点可能会使规划路径贴近碍航物，影响USV航行安全。邓博文等[11]对障碍物做膨胀处理，王中玉等[12]在障碍物周围设置禁止搜索区，虽然效果都较好，但都需要对环境中的障碍物进行处理。针对A*算法应用在USV上的缺陷，本文提出碍航物检测方法：首先对A*算法遍历的候选节点进行筛选，使路径上的每个节点都能与碍航物保持一定的安全距离;然后对评价函数进行改进，使算法遍历的节点数更少;最后对所规划路径上的冗余节点进行平滑处理。
　　1环境模型建立
　　USV路径规划的前提是搭建出合适的环境模型。目前，常用的环境建模方法有栅格法、几何法和拓扑法[1]。由于采用栅格法规划的环境能够表现出一致性、规范性、简单性，所以本文使用栅格法建立环境模型。栅格法将环境空间划分为多个大小相同的栅格，每个栅格都用二进制数值表示。设整个环境空间S被划分为a×b个大小相同的栅格，每个栅格都对应着一个环境状态，用Nij表示，则S可以表示为（1）每个栅格的环境状态信息如下：Nij=0，自由空间

nlc202206292048

转载注明来源:https://www.xzbu.com/4/view-15435011.htm