多无人艇协同遍历路径规划算法

翁 磊; 杨 扬; 钟雨轩

doi:10.11993/j.issn.2096-3920.2020.06.007

多无人艇协同遍历路径规划算法

doi: 10.11993/j.issn.2096-3920.2020.06.007

翁磊¹,
杨扬¹,
钟雨轩^2*,

上海大学机电工程与自动化学院, 上海, 200444 2. 上海大学计算机工程与科学学院, 上海, 200444

基金项目: 国家重点研发计划资助项目(2017YFC0806700) 科技部重点研发计划(2018YFF0103400) .

详细信息

通讯作者:
钟雨轩(1994-), 男, 硕士, 实验员, 主要研究方向为无人艇导航、制导和控制等.

中图分类号: TJ630 U675.7 P217
计量
- 文章访问数: 323
- HTML全文浏览量: 25
- PDF下载量: 365
- 被引次数: 0
出版历程
- 收稿日期: 2020-09-02
- 修回日期: 2020-11-03
- 刊出日期: 2020-12-31

Collaborative Traversal Path Planning Algorithm of for Multiple Unmanned Survey Vessels

School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China 2. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China

摘要

摘要: 为了实现对岛礁及周围海域水下地貌信息的获取, 同时使用多个无人扫测艇进行协同测绘以提高测绘效率, 文中提出一种协同遍历路径规划算法: 采用扫描线多边形方法得到动态栅格地图, 建立水域环境模型, 基于K-means++算法对任务区域进行分配, 分配区域内使用启发式路径规划算法得到完全遍历路径。仿真结果满足区域分配的均匀性和遍历路径的连通性要求。在此基础上提出了动态重规划算法, 根据实时可工作无人艇数量对未遍历区域进行重分配。仿真结果证明, 在不同间距的栅格地图中, 协同遍历算法均提高了测绘效率, 路径重复率较低, 可以快速高效地实现动态重规划。
- 无人扫测艇 /
- 协同 /
- K-means++算法 /
- 遍历路径规划 /
- 动态重规划
Abstract: To obtain underwater geomorphological information of islands, reefs, and surrounding waters and improve surveying and mapping efficiency, collaborative surveying, and mapping using multiple unmanned survey vessels should be employed. In this study, a collaborative traversal path planning algorithm in conjunction with the scanline polygon method is used to obtain a dynamic grid map. A water environment model is then constructed, task areas are allocated based on the K-means++ algorithm, and a full traversal path is obtained by the heuristic path planning algorithm. Simulation results meet the requirements of uniformity and connectivity of the traversal path. A dynamic reprogramming algorithm is then proposed to reallocate the untraversed areas based on the number of unmanned vessels that can work in real time. The collaborative traversal algorithm is shown to improve the mapping efficiency of the grid map with different spacing, and the path repetition rate is low, meaning that dynamic reprogramming can be realized quickly and efficiently.
- unmanned survey vessel /
- collaborative /
- K-means++ algorithm /
- traversal path planning /
- dynamic reprogramming

HTML全文

参考文献(15)

[1]	申云磊, 高霄鹏. 无人艇的研究现状与进展[J]. 船电技术, 2018, 38(9): 7-10. Shen Yun-lei, Gao Xiao-peng. Research Status and Progress of Unmanned Surface Vehicle[J]. Marine Electric & Electronic Engineering, 2018, 38(9): 7-10.
[2]	罗代超. 多水面无人艇协同区域搜索策略研究[D]. 哈尔滨: 哈尔滨工程大学, 2019.
[3]	梁宏晨. 基于蜂窝结构的多无人艇协同区域探测研究[D]. 广州: 华南理工大学, 2019.
[4]	刘庆周, 吴锋. 多智能体路径规划研究进展[J]. 计算机工程, 2020, 46(4): 1-10. Liu Qing-zhou, Wu Feng. Research Progress of Multi-Agent Path Planning[J]. Computer Engineering, 2020, 46(4): 1-10.
[5]	彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19(11): 2472-2476. Peng Hui, Shen Lin-cheng, Huo Xiao-hua. Research on Multiple UAV Cooperative Area Coverage Searching[J]. Journal of System Simulation, 2007, 19(11): 2472-2476.
[6]	吕霞付, 程啟忠, 李森浩, 等. 基于改进A算法的无人船完全遍历路径规划[J]. 水下无人系统学报, 2019, 27(6): 695-703. Lü Xia-fu, Cheng Qi-zhong, Li Sen-hao, et al. Unmanned Surface Vehicle Full Traversal Path Planning Based on Improved A Algorithm[J]. Journal of Unmanned Undersea Systems, 2019, 27(6): 695-703.
[7]	刘晶, 姚维, 章玮. 移动机器人全覆盖路径规划算法研究[J]. 工业控制计算机, 2019, 32(12): 52-54. Liu Jing, Yao Wei, Zhang Wei. Research on Complete Coverage Path Planning Algorithm of Mobile Robots[J]. Industrial Control Computer, 2019, 32(12): 52-54.
[8]	钟雨轩, 葛磊, 张鑫, 等. 无人水面艇岛礁海域完全遍历路径规划[J]. 上海大学学报(自然科学版), 2017, 23(1): 17-26. Zhong Yu-xuan, Ge Lei, Zhang xin, et al. Complete Coverage Path Planning of USV Used for Mapping Round Island[J]. Journal of Shanghai University(Natural Science), 2017, 23(1): 17-26.
[9]	范云生, 赵永生, 石林龙, 等. 基于电子海图栅格化的无人水面艇全局路径规划[J]. 中国航海, 2017, 40(1): 47-52, 113. Fan Yun-sheng, Zhao Yong-sheng, Shi Lin-long, et al. Global Path Planning for Unmanned Surface Vehicle Based on Grid Model of Electronic Chart[J]. Navigation of China, 2017, 40(1): 47-52, 113.
[10]	卫洪春, 彭小利. 扫描线多边形区域填充算法研究[J].四川文理学院学报, 2012, 22(5): 77-82. Wei Hong-chun, Peng Xiao-Li. Study on the Algorithm of Scanning Line Filling in Polygon Area[J]. Sichuan University of Arts and Science Journal, 2012, 22(5): 77-82.
[11]	肖尚华, 胡灿林. 基于加权K-means聚类与路网无向图的地图分割算法[J]. 现代计算机, 2018(8): 78-81. Xiao Shang-hua, Hu Can-lin. Map Segmentation Based on Weighted K-means Clustering and Undirected Road Graph[J]. Modern Computer, 2018(8): 78-81.
[12]	Senthilkumar K S, Bharadwaj K K. Multi-robot Exploration and Terrain Coverage in an Unknown Environment[J]. Robotics & Autonomous Systems, 2012, 60(1): 123-132.
[13]	王仲民, 井平安, 朱博. 基于神经元激励的移动机器人遍历路径规划[J]. 控制工程, 2017, 24(2): 283-286. Wang Zhong-min, Jing Ping-an, Zhu Bo. Coverage Path Planning of Mobile Robot Based on Neuronal Excitation[J]. Control Engineering of China, 2017, 24(2): 283-286.
[14]	谢坤霖, 李宗根, 代宇航, 等. 基于启发式搜索算法的扫地机器人路径规划[J]. 西华大学学报(自然科学版), 2019, 38(4): 69-76. Xie Kun-lin, Li Zong-gen, Dai Yu-hang, et al. Sweeping Robot Path Planning Based on Heuristic Search Algo-rithm[J]. Journal of Xihua University(Natural Science Edition), 2019, 38(4): 69-76.
[15]	马向峰, 韩玮, 谢杨柳. 水面无人艇任务规划系统分析[J]. 舰船科学技术, 2019, 41(23): 54-57. Ma Xiang-feng, Han Wei, Xie Yang-liu. Analysis and Research on Misson Planning System of USV[J]. Ship Science and Technology, 2019, 41(23): 54-57.