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

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

doi:10.11993/j.issn.2096-3920.2019.06.014

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

doi: 10.11993/j.issn.2096-3920.2019.06.014

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

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

详细信息

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

中图分类号: U664.82; TP301.6
计量
- 文章访问数: 599
- HTML全文浏览量: 1
- PDF下载量: 418
- 被引次数: 0
出版历程
- 收稿日期: 2019-03-09
- 修回日期: 2019-04-04
- 刊出日期: 2019-12-31

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

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

摘要

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

HTML全文

参考文献(16)

[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.