基于改进A*算法的无人船完全遍历路径规划

吕霞付, 程啟忠, 李森浩, 林 政

基于改进A*算法的无人船完全遍历路径规划

吕霞付, 程啟忠, 李森浩, 林 政

(重庆邮电大学 工业互联网与网络化控制教育部重点实验室, 重庆, 400065)

针对无人船在复杂环境下完全遍历路径规划算法效率差、普适性低的问题, 文中提出了一种基于改进A*算法的无人船完全遍历路径规划方法。首先通过地面站上位机电子地图界面发布任务区域, 将该任务区域转换为栅格地图; 然后通过内螺旋算法开始对栅格地图进行遍历; 最后当无人船陷入死角时, 通过改进A*算法搜索最优路径, 逃逸死角继续遍历, 直到完成所有可达区域的遍历。仿真结果表明, 相比现有完全遍历的优化方法, 该方法规划的路径步数从814步减少到784步, 重复率从优化前的7.8%改善至3.98%, 改善了性能指标, 具有较好的应用前景。

无人船; 路径规划; 完全遍历; A*算法

0 引言

随着人类对水资源的保护、对深海区域的探索和海上军事的开展, 无人船(unmanned surface vehicle, USV)的研究和开发越来越受到关注与重视[1]。

USV作为水域交通系统的重要个体, 其路径规划一直是研究热点[2]。根据全局和局部的不同, 将USV路径规划分为2种类型: 完全遍历路径规划和点对点路径规划[3]。其中, USV完全遍历路径规划主要应用于水面漂浮物清理, 水底地形探测, 海湾水域扫雷等方面。不同的完全遍历算法效果也不一样。

Balch[4]采用随机式遍历算法让机器人直线行走, 当遇到障碍物随机转动一个角度后继续行驶, 该算法比较简单, 但局限性很大, 会出现重复清扫相同区域并且有的区域没有清扫的情况; 王琦斐等[5]采用内螺旋覆盖算法让机器人按约定的方向顺时针或逆时针进行遍历, 当前方区域为障碍物或已经被遍历过, 则向右(或向左)旋转90°继续行驶, 该算法过于简单, 容易陷入局部死角或有些区域未被遍历; 许兴军[6]提出了一种改进反复式全区域覆盖算法, 并引入了区域分割的方式, 根据障碍物分布将任务区域分割成多个子区域, 再通过往复式算法遍历子区域, 该方法完成了在实际应用中完全遍历的路径规划, 比较简单易用, 但该方法不适用其他环境, 重复率高, 区域划分不明显, 算法精度低。

近些年来, 随着搜索算法的发展, 出现了模糊控制、人工势场法、神经网络、蚁群算法、遗传算法和A*算法等, 能够应付复杂和多变的工作环境, 解决了死角和漏扫的问题, 实现了在未知环境中的运动和规划[7]。张赤斌等[8]将蚁群算法应用于完全遍历中, 但该算法运算量大、实时性差; Mohamed等[9]提出了一种改进的遗传算法, 通过改变种群的编码方式, 在传统遗传算法的步骤上增加3个新的遗传操作: 复原、重构和录优, 使得寻优的路径更加平滑, 但该算法需要大量的遗传迭代, 增加的3个遗传操作使得迭代次数更多, 遗传过程被重复, 运算量变大; 陈超等[10]提出了一种基于可视图的A*算法, 将起点与障碍物的特征点相连, 去除中间因其他障碍物遮挡的线段, 将A*算法与可视图法相结合, 提高了对环境的适应性, 但该可视图法需要用线段连接所有起点到障碍物特征点, 当环境中出现动态变化的障碍物, 需要通过可视图法重新建立环境模型, 普适性差。USV路径规划技术取得了丰硕的成果, 但每一种方法都由于其自身的优点和不足不能应用于所有场合。目前USV完全遍历路径规划算法创新之处在于多传感器、多种路径规划技术的融合。

针对上述问题, 文中提出了一种改进A*算法的USV内螺旋完全遍历路径规划算法。首先采用内螺旋遍历算法进行遍历, 当陷入死角时, 通过改进A*算法逃逸死角, 行进至最近的未被遍历的栅格并继续完成遍历。仿真结果表明, 该方法行驶步数少、覆盖率高、重复率小, 在复杂环境中性能更强。

1 基于栅格法的USV环境建模

1.1 栅格法环境建模概述

环境建模就是将能够表示环境的数据信息进行抽象化, 以数学方法描述物体和它们之间的空间关系。栅格法环境建模容易实现, 是当前研究和应用最为广泛的环境建模方法[11]。栅格法USV环境建模就是将USV工作的二维水面环境地图划分成若干个大小相同的栅格, 并根据可达区域和不可达区域的情况, 确定每个栅格的占有值。栅格法建模过程简单, 运算量小, 更能直观表示环境地图遍历的情况, 并且栅格坐标系的坐标点与经纬度坐标系一一对应, 能够准确定位, 方便于环境建模和算法规划。文中将采用栅格法完成USV环境建模, 为客观地表示栅格法环境建模, 作如下定义。

定义1:

1.2 栅格大小选取

在栅格环境建模过程中, 栅格大小的选取[12]是一个很重要的问题, 其直接影响环境地图信息的精度, 也同样影响着完全遍历路径规划算法的性能和效率。栅格大小的选取需要考虑以下4个因素: 环境地图的大小与障碍物的复杂程度; USV的船身尺寸; 实际应用情况以及不同的应用场景和用途; 计算机的运算和存储能力。

1.3 环境建模过程

11) 重复步骤1)、步骤3)和步骤6), 栅格化障碍物;

13) 基于栅格法的环境建模完成。

1.4 环境建模试验

为验证上述环境建模方法的可行性, 在地面站上位机电子地图软件选出4个坐标点, 经纬度如下:

用线段依次把这些坐标点连接形成的四边形就是边界。图1中P1~P4围成的不规则四边形即地面站上位机软件发布的任务区域。

2 基于栅格地图的完全遍历算法

在建立的栅格地图中, 在满足一项或多项评价指标最优的情况下, 通过完全遍历算法可以遍历所有可达区域, 并规划出一条最优路径。

2.1 算法性能评价指标

USV完全遍历算法的性能主要采用以下5个性能指标来衡量。

1) 遍历覆盖率

遍历覆盖率是指路径规划完成后, USV所行驶过的面积与可达区域的比值, 即

完全遍历时, 尽可能保证所有可达安全区域都要遍历, 接近100%。遍历覆盖率百分比越高, 说明该算法的性能越好。

2) 遍历重叠率

遍历重叠率是指路径规划完成后, USV行驶中出现2次或多次重复遍历的面积总和与可达安全区域面积的比值, 即

完全遍历时, 在保证覆盖率达到100%时, 出现重复遍历的情况, 该数值越小, 完全遍历算法性能越好。

3) 转弯次数

4) 步数或路径总长度

相同的遍历覆盖率下, 路径总长度越小, 控制USV的算法性能越好。

5) 总用时间

2.2 完全遍历算法比较

图3 3种完全遍历算法示意图

表1为3种遍历算法评价指标结果。由表中可知, 3种遍历算法覆盖率都为100%。传统的往复前进算法, 虽然重复率为0, 但其以牺牲路径总长度为代价, 遍历时间和遍历路径远远大于其他2种遍历算法。相比于改进往复前进算法, 螺旋式算法步数为350步, 减少了116步, 重复率只有2.94%, 远低于改进往复前进算法的24.12%, 并且总用时减少了114 s。螺旋式遍历算法不仅达到了完全覆盖的效果, 而且极大地降低了重复率, 减少了USV的航行步数。

表1 3种完全遍历算法评价指标

2.3 死角情况

在遍历规划时, 死角是USV特别需要注意的局部环境, 也是体现算法有效性和优越性的环境模型[16]。死角是指USV执行遍历任务到达栅格地图某处时, 相邻的8个栅格是障碍物或者已经遍历。陷入死角有2种情境, 情境1: USV行驶到某位置时, 所在栅格周围相邻的8个栅格除了上一步经过的栅格外其余都是障碍栅格, 如图4(a)所示; 情境2: USV所在的栅格相邻8个栅格都已经被遍历过, 如图4(b)所示。当USV陷入上述死角时, 需要搜索算法搜索最近的可达栅格, 并规划一条最短路径, 使得USV可以逃逸死角。

图4 USV陷入死角示意图

2.4 改进A*算法的完全遍历路径规划算法

A*算法是一种启发式搜索算法[13], 它结合了Dijkstra算法的迭代式检查和最佳优先算法(best-first search, BFS)的方向性, 提高了效率, 减少了路程。由于其具有较好的性能和准确性, 可适用于各种环境, 经常被用于最优路径的求解。

2.4.1 A*算法成本估计函数

A*算法成本估计函数为

利用A*算法在栅格地图上进行规划时, 选取2个节点中心点间的欧几里得距离（直线距离）作为估计代价, 即

2.4.2 改进A*算法

1) 模型再分析

图5 A*算法流程图

图6 栅格模型分析

2) 改进A*算法过程

改进A*算法的过程如下。

⑥算法结束, BestList链表中的节点为最优路径。

3) 改进A*算法实例分析

BestList链表存放的节点即为改进A*算法的最优路径。结合图7说明改进A*算法的过程。

图7 利用改进A*算法寻求最优路径过程示意图

根据点到线段的距离公式

由表2可知, 同传统的A*算法相比, 改进A*算法可使USV朝任意角度转向, 减少了不必要的节点, 路径总长度变短。

表2 传统A*算法与改进A*算法数据对比

2.4.3 改进A*算法的USV完全遍历

为了完成栅格地图的完全遍历, 现将内螺旋遍历算法与改进A*算法融合, USV执行完全遍历任务时, 首先执行内螺旋遍历算法, 当陷入死角时, 通过改进A*算法跳出死角, 继续遍历。改进A*算法的USV完全遍历框架如图8所示。

图8 改进A*算法的USV完全遍历框架

3 仿真试验与分析

为了验证文中完全遍历算法的有效性, 建立与文献[16]相似的环境栅格地图。地图由32×32个栅格组成, 其中黑色区域为边界或障碍物。当USV进行完全遍历任务时, 内螺旋遍历时陷入死角, 坐标点为(17, 19), 如图9所示。

图10为遍历陷入死角时传统A*算法与改进A*算法搜索路径示意图。图10(a)中的黄色路径为传统A*算法的路径节点示意图, 将栅格(12, 16)作为终点, 路径包括19个节点。将这19个黄色节点存放在BestList链表中, 去掉中间不必要的节点并搜索最近未遍历的栅格, 图10(b)中绿色栅格路径为改进A*算法的路径节点示意图, 终点从(12, 16)变成(12, 12), 路径减少到3个节点, 大大减少了路程总长度。

图9 USV内螺旋遍历陷入死角

图10 2种算法路径示意图

图11为USV完全遍历路径规划完成示意图。由图可以看出, 在复杂环境模型中, USV的完全遍历路径规划的覆盖率为100%, 在遍历时USV遇到2次死角, 坐标点为(12, 21)、(17, 19), 通过改进A*算法逃逸死角, 继续完成遍历。

图11 USV完全遍历路径规划示意图

表3为在环境栅格地图下, 2种完全遍历算法评价指标结果。由表可知, 基于改进A*算法的完全遍历规划路径步数为784步, 重复率为3.98%。相比文献[16]遍历算法步数814步, 重复率为7.8%的结果, 文中方法不仅达到了完全覆盖的效果, 而且降低了重复率、减少了步数和路径长度, 因此更具优越性。

表3 2种完全遍历算法评价指标

4 结束语

针对USV在复杂环境下完全遍历路径规划算法效率差、普适性低的问题, 提出了一种改进A*算法的内螺旋完全遍历路径规划算法。将电子地图边界转化为栅格环境模型, 并在建立的栅格地图中比较3种遍历算法的优缺点, 得出内螺旋遍历算法性能更优。USV执行遍历任务时, 首先通过内螺旋遍历算法开始遍历, 若在行进过程中遇到死角, 采用改进A*算法实现USV以最短路径逃逸死角并继续完成遍历。仿真结果表明, 文中方法不仅能够有效地实现USV100%的完全遍历, 而且降低了重复率, 减少了步数和路径长度, 在复杂环境下具有较高的规划效率。下一步将通过实物测试, 验证该算法。

[1] 曹娟, 王雪松. 国内外无人船发展现状及未来前景[J]. 中国船检, 2018, 1(5): 94-97.

[2] 杨俊成, 李淑霞, 蔡增玉. 路径规划算法的研究与发展[J]. 控制工程, 2017, 24(7): 1473-1480.Yang Jun-cheng, Li Shu-xia, Cai Zeng-yu. Research and Development of Path Planning Algorithm[J]. Control Engineering of China, 2017, 24(7): 1473-1480.

[3] 张月. 清洁机器人全覆盖路径规划研究[D]. 重庆: 重庆大学, 2015.

[4] Balch T. The Case for Randomized Search[C]//Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation, San Francisco, CA: IEEE, 2000: 213-215.

[5] 王琦斐, 杨军. 基于内螺旋覆盖算法的多AUV协作反水雷路径规划研究[J]. 计算机测量与控制, 2012, 20(1): 144-146, 160.

Wang Qi-fei, Yang Jun. Path Planning of Multiple AUVs for Cooperative Mine Countermeasure Using Internal Spiral Coverage Algorithm[J]. Computer Measurement & Control, 2012, 20(1): 144-146, 160.

[6] 许兴军. 智能割草机的区域全覆盖算法设计与仿真[J]. 机电工程, 2012, 29(3): 302-306.

Xu Xing-jun. Design and Simulation on Regional All-covered Algorithm of Intelligent Mower[J]. Mechanical & Electrical Engineering Magazine, 2012, 29(3): 302-306.

[7] Yan R, Pang S, Sun H, et al. Development and Missions of Unmanned Surface Vehicle[J]. Journal of Marine Science and Application, 2010, 9(4): 451-457.

[8] 张赤斌, 王兴松. 基于蚁群算法的完全遍历路径规划研究[J]. 中国机械工程, 2008, 19(16): 1945-1949.Zhang Chi-bin, Wang Xing-song. Complete Coverage Path Planning Based on Ant Colony Algorithm[J]. China Mechanical Engineering, 2008, 19(16): 1945-1949.

[9] Mohamed A Y, Mohamed T L. The Path Planning of Cleaner Robot for Coverage Region Using Genetic Algorithms[J]. Journal of Innovation in Digital Ecosystems, 2016, 3(1): 37-43.

[10] 陈超, 唐坚. 基于可视图法的水面无人艇路径规划设计[J]. 中国造船, 2013, 54(1): 129-135.Chen Chao, Tang Jian. A V-Graph Based Path Planning for Unmanned Surface Vehicle[J]. Shipbuilding of China, 2013, 54(1): 129-135.

[11] Arleo A, Millan J R, Floreano D. Efficient Learning of Variable Resolution Cognitive Maps for Autonomous Indoor Navigation[J]. IEEE Transactions on Robotics and Automation, 1999, 15(6): 990-1000.

[12] 彭刚, 沈宇. 一种变栅格地图的巡检机器人路径规划方法研究[J]. 智能机器人, 2017, 1(4): 41-43, 68.

[13] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[14] 姚雨, 李庆, 陈曦. 优化的A*算法在航迹规划上的应用[J]. 微电子学与计算机, 2017, 34(7): 51-55.Yao Yu, Li Qing, Chen Xi. Optimization of the Application of A* Algorithm in Path Planning[J]. Microelectronics & Computer, 2017, 34(7): 51-55.

[15] 赵晓, 王铮, 黄程侃, 等. 基于改进A*算法的移动机器人路径规划[J]. 机器人, 2018, 40(6): 903-910.Zhao Xiao, Wang Zheng, Huang Cheng-kan, et al. Mobile Robot Path Planning Based on an Improved A* Algorithm[J]. Robot, 2018, 40(6): 903-910.

[16] 温志文, 杨春武, 蔡卫军, 等. 复杂环境下UUV完全遍历路径规划方法[J]. 鱼雷技术, 2017, 25(1): 22-26, 31.Wen Zhi-wen, Yang Chun-wu, Cai Wei-jun, et al. A Complete Coverage Path Planning Method of UUV under Complex Environment[J]. Torpedo Technology, 2017, 25(1): 22-26, 31.

Unmanned Surface Vehicle Full Traversal Path Planning Based on Improved A* Algorithm

LÜ Xia-fu, CHENG Qi-zhong, LI Sen-hao, LIN Zheng

(Chongqing University of Posts and Telecommunications, Key Laboratory of Industrial Internet of Things & Network Control, Ministry of Education, Chongqing 400065, China)

To improve the efficiency and universality of full traversal path planning algorithm for unmanned surface vehicle(USV) in complex environment, a new full traversal path planning algorithm based on the improved A* algorithm is proposed. Firstly, user publishes the task area through the electronic map interface of the host computer in ground station, and converts the task area into a grid map. Then, the grid map is traversed through the inner spiral algorithm. Finally, when the USV is going into the dead angle, optimal path is searched through the improved A* algorithm, and the escape dead angle is traversed until all the reachable areas are traversed. Simulation results show that compared with the existing full traversal optimization method, the proposed algorithm reduces the planned path steps from 814 to 784, and improves the repetition rate from 7.8% to 3.98%. The algorithm improves the performance and has a good application prospect.

unmanned surface vehicle(USV); path planning; full traversal; A* algorithm

U664.82; TP301.6

A

2096-3920(2019)06-0695-09

10.11993/j.issn.2096-3920.2019.06.014

2019-03-09;

2019-04-04.

国家自然科学基金(61071117); 重庆市研究生科研创新项目(CYS14151).

吕霞付(1966-), 男, 博士, 教授, 主要研究方向为智能仪器仪表.

吕霞付, 程啟忠, 李森浩, 等. 基于改进A*算法的无人船完全遍历路径规划[J]. 水下无人系统学报, 2019, 27(6): 695-703.

(责任编辑: 许 妍)