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

翁 磊, 杨 扬, 钟雨轩

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

翁 磊1, 杨 扬1, 钟雨轩2*

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

为了实现对岛礁及周围海域水下地貌信息的获取, 同时使用多个无人扫测艇进行协同测绘以提高测绘效率, 文中提出一种协同遍历路径规划算法: 采用扫描线多边形方法得到动态栅格地图, 建立水域环境模型, 基于-means++算法对任务区域进行分配, 分配区域内使用启发式路径规划算法得到完全遍历路径。仿真结果满足区域分配的均匀性和遍历路径的连通性要求。在此基础上提出了动态重规划算法, 根据实时可工作无人艇数量对未遍历区域进行重分配。仿真结果证明, 在不同间距的栅格地图中, 协同遍历算法均提高了测绘效率, 路径重复率较低, 可以快速高效地实现动态重规划。

无人扫测艇; 协同;-means++算法; 遍历路径规划; 动态重规划

0 引言

由于岛礁周围水域地形复杂, 使用传统人工测绘方式效率低下且有人员安全风险, 因此亟需一种智能海洋勘测装备。无人扫测艇[1]具有吃水浅, 机动性强, 路径跟随稳定等特点, 非常适用于岛礁测绘。面对一些复杂且广阔的岛礁环境, 使用单个无人扫测艇对作业区域进行扫测时间较长, 鲁棒性差, 因此使用多个无人扫测艇组成多无人艇系统对作业区域进行协同测绘可以提高整体扫测效率和实验系统的鲁棒性[2-3]。

目前, 多智能体协同区域遍历问题多采用基于神经网络的方法和粒子群算法等[4], 这些智能算法易于在多无人车和多无人机等全驱动的系统中实现且计算量大。彭辉等[5]采用将协同遍历问题分解为任务区域分配和遍历路径规划2个部分进行求解, 降低了问题计算量和复杂度。

考虑到多无人艇系统的欠驱动系统特性, 为实现多无人艇协同遍历的高效性, 文中采用将协同遍历问题分解为任务区域分配和遍历路径规划两部分来求解。任务区域分配应用最为广泛的是聚类算法, 通过将总体测绘区域划分为每个无人艇测绘的子任务区域达到高效便利的目的。任务区域分配完成后需要对任务区域进行遍历, 当单机器人完全遍历路径规划通常采用A*算法[6]、神经网络算法[7]等, 这些算法存在计算量大, 路径规划效果不佳等缺点。因此, 针对多无人艇协同遍历问题, 文中提出了协同遍历路径规划算法。流程图如图1所示。首先基于电子海图使用扫描线多边形填充算法进行环境建模得到栅格地图; 接着使用-means++算法对任务区域进行分配; 然后在分配的区域内使用启发式路径规划算法[8]规划出完全遍历路径, 在此基础上, 进一步提出动态重规划算法, 根据实时的可工作无人艇数量对任务区域进行重分配, 体现了协同遍历路径规划算法的鲁棒性。

图1 协同遍历路径规划算法流程图

1 环境建模与任务区域分配

环境建模是任务区域分配和路径规划的前提, 常用的环境地图有栅格地图[9]、拓扑地图和几何特征地图等。考虑到无人扫测艇对路径精度的要求和遍历路径的有序性, 文中使用栅格地图显示作业环境信息。

在电子海图中选定测绘区域后, 根据获得的障碍物信息和边界信息填充栅格地图, 常用的区域填充算法有扫描线多边形填充算法[10]、边填充算法和种子填充算法等。因为电子海图显示的岛礁区域多为不规则多边形, 因此文中采用扫描线多边形填充算法建立环境模型。

1.1 扫描线多边形填充算法

扫描线多边形填充算法的过程如下: 1) 将环境地图按照一定间隔距离离散为独立栅格; 2) 在栅格地图中以同样的间距生成多条平行扫描线, 若扫描线与环境地图中的障碍物边界存在交点, 那么交点将成对存在, 记录这些成对交点所在的位置; 3) 判断各个栅格点与成对交点之间的位置关系, 若栅格处于交点之间则标记为障碍物栅格, 否则标记为自由栅格。

图2为简化岛礁地图的建模过程。外围边框为所选择的待测绘区域, 多边形区域为岛礁所在的障碍物膨化区域, 对此区域按一定间距离散后得到图2(a)所示的栅格地图; 图2(b)中按栅格行数生成多条扫描线后, 扫描线与障碍物边界形成7对交点; 最后判断每个栅格是否处于交点之内, 如图(c)所示, 若是, 则该栅格处于障碍物区域, 标记为“–1”; 否则栅格处于可行区域, 标记为“1”, 检测障碍物区域周围自由栅格点间的连线和障碍物区域是否存在交点, 将存在交点的自由栅格设置为障碍物栅格。

扫描线多边形算法实现简单, 运行效率高, 适用于处理岛礁类多边形地图, 可以通过调节离散间隔改变单位路径长度, 满足不同精度的实际测绘需求, 基于多边形扫描线算法产生的栅格地图易于实现聚类和遍历路径规划。

1.2 K-means++聚类算法

在完成对作业区域建模后, 接下来需对作业区域进行划分。考虑到多无人艇协同遍历区域的连通性和均匀分配要求, 使用-means++聚类算法[11]对作业区域进行划分。

图2 扫描线多边形算法过程图

1) 根据任务场景分配的无人艇数量设置值;

4) 重复步骤3)直到选出个质心元素;

7) 不断对步骤5)和步骤6)进行迭代, 直到聚类结果不再发生变化。

图3 K-means++聚类效果图

2 路径规划算法

完成作业区域环境建模和区域划分后, 需对划分后的区域进行完全遍历路径规划。完全遍历路径规划[12]是一种特殊的路径规划, 其目的是在工作区域内寻找一条经过所有可达点的连续路径。其中应用较广的是基于神经网络模型[13]的方法。该算法存在计算量大和路径规划效果非最优等缺点, 因此针对无人扫测艇对测绘路径的要求, 文中采用动态栅格法与优先级启发式路径规划相结合的方法。

2.1 动态栅格法

通过扫描线多边形填充算法得到栅格地图后, 完成了地图中可通过性栅格点的提取和初始化赋值。在无人艇作业过程中, 随着无人扫测艇的运动, 通过改变已遍栅格点的收益值对环境进行动态描述, 引导无人扫测艇在动态栅格中对未遍历区域进行扫测。

在单个无人扫测艇遍历过程中的栅格点收益值呈现3种属性状态: 已遍历区域收益值为0; 待扫测可行区域收益值为1; 障碍物区域收益值为–1。图4为无人扫测艇作业过程中的某一时刻的动态栅格模型图, 其中实心栅格点为无人艇当前所在位置。

图4 扫测过程中动态栅格模型图

2.2 优先级启发式路径规划算法

获取动态栅格地图后需对路径点进行选取, 为了保证完全遍历路径的有序性, 文中采用一种优先级启发式路径点选取规则, 其优先级定义如图5所示。

图5 方向优先级定义图

无人扫测艇工作过程中, 在以八邻域方式通行的情况下, 其可行区域为8个相邻点, 按照优先级高低将其划分为4等, 由高至低分别为: 上、下、左侧(左上、左、左下)、右侧(右上、右、右下)。定义上、下2个方向优先级较高以使竖直方向为主要运动方向, 定义左侧优先级高于右侧则使无人扫测艇的遍历路径由左往右推移, 保证规划路径的有序性。

图6为优先级启发式路径规划在动态栅格地图中的遍历路径规划示意图。由图可知, 优先级启发式路径规划算法理论上可以在动态栅格地图中有序地实现遍历路径规划。

2.3 基于A*的启发式搜索算法

当无人艇处于图6所示的八邻域栅格中时, 其中2个栅格为障碍物, 其余6个栅格皆为已遍历, 此时优先级启发式路径规划方法不再适用, 定义为“死锁”状态。基于动态栅格模型, 使用搜索临时目标点并结合A*启发式搜索算法产生最优路径走出“死锁”状态。

图6 启发式路径规划动态栅格图

1) 搜索临时目标点

图7 搜索临时目标点

2) 建立代价地图

在确定临时目标点后, 需要定义A*搜索算法所需的代价地图, 此时处于非测绘状态, 只需要区分非障碍物栅格和障碍物栅格即可: 设置非障碍物栅格距离代价为1; 障碍物栅格代价为1 000, 如图8所示。

图8 A*代价地图

3) 利用A*算法搜索路径

在无人艇处于死锁状态下则激活A*启发式搜索算法, 图9为使用A*算法走出死锁状态的最优路径示意图, 将优先级启发式路径规划算法和A*启发式路径规划算法结合起来, 得到如图10所示的岛礁地图环境中遍历路径规划的效果。

图10 遍历路径规划整体效果图

根据整体遍历路径可以看出, 将优先级启发式算法和A*启发式路径规划相结合可以实现相对有序、规律的遍历路径规划效果, 及时走出“死锁”状态, 达到快速遍历的效果。

3 动态重规划

无人艇在岛礁区域进行测绘时, 由于海洋中存在暗礁等障碍物和风、浪、涌等复杂环境因素的影响, 可能致使无人艇自身系统出现干扰和故障等情况。在多无人艇协同遍历过程中, 如果出现单个或多个无人艇系统发生故障后失联的问题, 会导致部分地图遍历无法完成, 因此需要使用动态重规划算法完成任务重分配[15]。

因此, 基于-means++聚类算法提出动态重规划算法, 在多无人艇协同遍历过程中, 根据实时的多无人艇系统状态, 动态地对未完全遍历的任务区域进行重规划, 以提高协同遍历搜索的效率, 体现多无人艇系统的鲁棒性和文中所提协同遍历算法的适应性。

图11为动态重规划的过程: 1) 当检测到单个或多个无人艇系统出现故障无法继续工作时, 激活动态重规划模块; 2) 更新当前未遍历区域、可工作的无人艇数量及实时位置坐标; 3) 以当前可工作无人艇数量作为值, 其实时位置作为个初始质心元素, 使用-means++聚类算法对未遍历区域进行聚类, 使划分区域靠近无人艇实时位置, 以满足路径连通性要求; 4) 任务区域重分配完成后, 使用路径规划算法对每块重分配区域进行遍历路径规划; 5) 得到每块重规划区域中的遍历路径输出给可工作的无人艇。动态重规划算法的伪代码如下所示。

图11 动态重规划算法过程

动态重规划方法不仅适用于解决多无人艇协同遍历过程中, 部分无人艇因故障原因无法继续执行当前剩余任务的问题, 同时还能用于解决各单艇工作效率不一致导致的整体作业效率下降问题。为实现整体任务区域遍历的快速性, 当1艘无人扫测艇完成路径遍历后, 可以使用动态重规划方法对未作业任务区域进行重分配, 缩短整体遍历时间, 体现多无人艇协同遍历的高效性优势。

4 仿真结果与分析

利用MATLAB对协同遍历路径规划算法进行仿真验证。首先对协同遍历路径规划算法进行任务区域分配和路径规划仿真验证, 并对分配结果和设置的栅格大小的关系进行分析; 其次将协同遍历路径规划算法和基于神经网络模型的路径规划算法进行对比; 最后对动态重规划算法进行仿真验证。

4.1 协同遍历路径规划算法

设置如图12所示的初始测绘岛礁区域, 其中的多边形区域和栅格为障碍物区域, 为了验证协同遍历路径规划算法的有效性, 分别验证无人艇数量为2、3、4、5时的任务区域分配效果和遍历路径质量。

图12为设置栅格为10×10时无人艇数量聚类区域分配和遍历路径规划效果, 不同形状的节点表示不同聚类区域内的路径点。由任务区域分配效果可知, 区域分配基本满足均匀性要求, 路径满足连通性要求。

在不同间隔大小的栅格地图中设置不同作业数量的无人艇, 通过分析平均任务路径长度, 比较艇群作业效率。

对同一岛礁环境地图分别设置不同间距的扫描线, 产生栅格地图大小分别为10×10, 20×20, 40×40, 80×80, 并设置无人艇数量为2,3,4,5, 取10次试验结果的平均值作为平均任务路径长度值。图13为平均路径长度对比折线图, 根据图中标注的路径长度值可以看出, 在栅格划分数量最多80×80时, 随着分配无人艇数量的增加, 单个无人艇分配的路径长度减小最多。此外, 随着作业无人艇数量的增加, 单个无人艇的任务路径长度快速减少, 尤其是在整体任务路径较长时, 体现了多无人艇协同遍历的高效性。

图12 协同遍历路径规划效果图

图13 动态栅格法对比图

4.2 遍历算法比较分析

在通过-means++算法得到聚类结果后, 分别使用启发式路径规划算法和基于神经网络的路径规划算法对分配区域进行遍历, 以路径长度、转弯次数、路径点重复率和遍历覆盖率作为评价指标比较路径规划质量。表1为=5时2种路径规划算法分别进行10次试验结果的平均值, 通过结果可以分析得出, 启发式路径规划算法和基于神经网络的路径规划算法都能实现100%的地图覆盖率, 启发式路径方法平均路径长度更短, 转弯次数更少, 尤其是路径点重复率更低。

表1 路径规划结果对比

图14为=5时2种算法遍历路径效果对比图, 由图可知, 启发式路径规划算法的遍历路径更加有序, 重复路径点更少, 更适用于解决基于聚类算法分配任务区域的多无人艇协同遍历问题。

图14 遍历算法对比图

4.3 任务重规划

对第3章提出的动态重规划算法进行仿真验证。图15为任务重规划对比图, 将地图栅格设置为10×10, 设置初始可工作无人艇的数量为5。如果5艘无人艇均为正常工作状态, 在进行初始协同遍历任务任务分配后, 5艘无人艇按照分配的路径完成遍历任务。在任务完成4个单位长度后, 有1艘无人艇发生障碍无法继续任务, 此时激活动态重规划模块, 对未遍历区域内的56个未遍历路径点基于可工作的4艘无人艇进行任务重规划, 如图所示为任务重规划模块输出得到的遍历路径。根据如图所示效果, 星形栅格点为重分配区域遍历路径起点, 不同形状的栅格点表示不同的聚类区域, 路径长度分别为14、16、15、15个单位长度, 重分配路径满足连通性和均匀性要求, 验证了动态重规划算法的有效性。

图15 动态重规划效果图

在当前栅格大小的地图中, 基于随机聚类结果在设置初始路径长度为4后分别进行10次动态重规划算法, 得到平均重规划时间为0.8 s, 由此数据可知该动态重规划算法的快速性。

5 结束语

文中以多个无人扫测艇对岛礁区域进行协同遍历路径规划为背景, 提出了多无人艇协同遍历路径规划算法, 使用K-means++算法对任务区域进行分配, 对分配的任务区域使用优先级和启发式相结合的路径规划算法进行完全路径遍历, 并在此基础上提出动态重规划算法。根据仿真结果分析, 协同遍历路径规划算法分配的任务区域满足均匀性要求, 遍历路径满足连通性, 动态重规划算法可动态地对实时未遍历区域进行重分配, 体现了协同遍历路径规划算法的鲁棒性和高效性。

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

Collaborative Traversal Path Planning Algorithm of for Multiple Unmanned Survey Vessels

WENG Lei1, YANG Yang1, ZHONG Yu-xuan2*

(1. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200444, China; 2. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China)

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-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;-means++ algorithm; traversal path planning; dynamic reprogramming

翁磊, 杨扬, 钟雨轩. 多无人艇协同遍历路径规划算法[J]. 水下无人系统学报, 2020, 28(6): 634-641.

TJ630; U675.7; P217

A

2096-3920(2020)06-0634-08

10.11993/j.issn.2096-3920.2020.06.007

2020-09-02;

2020-11-03.

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

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

(责任编辑: 许 妍)