基于覆盖路径弧的无人机桥梁激光扫描路径规划

刘春磊; 张宏立; 王聪

doi:doi:10.3788/LOP202158.0828003

激光与光电子学进展, 2021, 58 (8): 0828003, 网络出版: 2021-04-16

基于覆盖路径弧的无人机桥梁激光扫描路径规划下载： 811次

UAV Bridge Laser Scanning Path Planning Based on Coverage Path Arcs

论文大纲

刘春磊张宏立 ^*王聪

作者单位

新疆大学电气工程学院, 新疆乌鲁木齐 830047

传感器覆盖路径规划激光扫描弧规划 CRSOM SC-CBBA 任务分配 sensors coverage path planning laser scanning arc planning CRSOM SC-CBBA task assignment

AI 词云图 AI一句话精读 AI短摘要

注：本部分内容由 AI 自动生成，请您知悉。

摘要

针对桥梁激光扫描巡检覆盖路径规划问题,提出基于点云切片的大型桥梁检查覆盖路径规划通用模型,这为多无人机系统桥梁覆盖路径规划提供了新的思路。首先,在点云切片的建模方法中增加补充视点,用于解决点云切片模型覆盖不完全的问题,将凸包集和补充视点转化为三维空间弧集,以弧为最小优化对象,解决大型建筑遍历搜索空间庞大的问题;其次,结合SC-CBBA (split and combine-consensus based bundle algorithm)和CRSOM (clustering characteristic of cluster growing ring self-organizing map)算法,实现多无人机任务的分配以及检查路径的弧序列规划;最后,通过仿真验证了该方法可以有效解决桥梁覆盖路径规划问题。

Abstract

Aiming at the problem of coverage path planning of bridge laser scanning inspection, a general model of large-scale bridge inspection coverage path planning based on point cloud slices is proposed in this work, which provides a new idea for bridge coverage path planning by multi-UAV systems. First, we add supplementary viewpoints to the point cloud slice modeling method to solve the problem of incomplete coverage of the point cloud slice model, then we convert the convex hull set and supplementary viewpoints into three-dimensional arc sets, and we use arcs as the minimum optimization object to solve the problem of huge search space for large-scale building traversal. Second, we combine the SC-CBBA (split and combine-consensus based bundle algorithm) and CRSOM (clustering characteristic of cluster growing ring self-organizing map) algorithm to realize the assignment of multi-UAV tasks and check the arc sequence planning of inspection path. Finally, simulations verify that this method can effectively solve the problem of bridge coverage path planning.

1 引言

桥梁周期检查是桥梁维护不可或缺的环节,也是交通安全的重要保证。中国国土面积广大,地形复杂,桥梁往往承载着较为重要的交通任务。因此,恶劣地形环境下桥梁检查困难成为亟待解决的问题。

目前,应用于桥梁检查的主要方式为人工目视检查,该方式需要庞大的脚架和防护装备,这在交通不畅的地区难以实现,况且依靠人工的检查方式不仅存在危险,也不能保证检查结果可靠^[1]。无人机造价低廉,在三维空间中灵活度高,以其机载传感器和智能算法在人类难以参与或不可能参与的环境中被广泛应用,如环境监测^[2]、勘探^[3]、搜救^[4]、巡检^[5]、农林^[6]等。2007年Metni等^[7]提出了运用无人机进行桥梁检查的概念,随着研究人员对光学传感器在空间定位^[8]、轮廓遥感^[9]、表面检测^[10]等方面应用的深入研究,无人机群搭载光学传感器进行桥梁检查逐渐成为当前研究与应用的热点。覆盖路径规划(CPP)是桥梁检查过程的重要步骤,要求无人机能够在复杂的三维桥梁上空自主规划出一条可以完全覆盖桥表面最优的航线,本质上讲,CPP问题是一个具有约束和巨大搜索空间的复杂优化问题。

目前,搜索空间庞大、寻优收敛缓慢仍然是解决CPP问题的关键难点。对此,国内外学者提出了不同的解决方案,彭辉等^[11]在2007年针对多无人驾驶飞机(UAV)协同区域覆盖问题进行了相关研究,采用多无人机任务区和完全覆盖分解的办法,在多边形区域得出覆盖路径。陈海等^[12]于2010年证明无人机覆盖路径规划中能耗与转弯次数成正比,并在之后提出了一种基于凸多边形区域覆盖算法,该方法将凸多边形区域覆盖规划问题转化为凸多边形宽度求解问题^[13-14],并于2016年提出以转弯次数最少作为评价指标的覆盖方法,该方法基于任务性能评价函数和子区域宽度的任务划分方法,在多边形区域中得出无人机协同最优路径^[15];Pham等^[16]提出一种根据有无障碍物的区域分解方法,在无障碍区域规划完毕后采用旅行商问题(TSP)模型和遗传算法得到覆盖区域最优路径。

以上研究通常基于平面覆盖路径规划,相对于二维CPP问题,三维CPP规划的运算复杂度和数据量急剧增加,庞大的工作空间致使其寻优速度相对于二维寻优低得多,寻优结果往往也不尽人意,对此,许多学者基于不同的三维CPP规划背景进行了研究,Cheng等^[17]针对城市覆盖路径规划问题将建筑建模为简单的三维体,如球体、圆柱体,通过规划简单立方体获得最优路径;Bircher等^[18]基于体素建模产生考虑传感器和相机角度的视点集,借助旅行商问题(TSP)模型求解完整路径;Dogru等^[19]考虑了除障碍以外的地形因素,利用遗传算法优化能耗,从而得到规划路径;Hameed等^[20]采用无人机改变姿态的方法解决了因将二维规划结果投影至三维空间造成的跳跃重叠问题,通过扩展“种子”曲线得到最终的规划路径。Phung等^[21]基于图论和体素视点模型,设计新型增强粒子群算法(ESPO)迭代机制,并使用图形处理器(GPU)加速获得建筑遍历最优路径;Mansouri等^[22]提出了一种基于空间切片模型的建筑建模方法,利用凸包线代替必经航迹,逐层跟随凸包线航迹得到规划路径;陈影等^[23]将空间切片想法应用于激光熔覆过程,实现了对逆向扫描点云的路径规划。

虽然CPP问题近年来得到了研究者们的广泛关注,但研究人员在解决超大型体积对象的CPP问题的过程中面临搜索空间缩减有限、没有较为优质的通用模型的问题。Mansouri等^[22]虽然提出了建筑遍历建模的基础方法,但是对于带有水平面遍历任务的建筑,没有提出良好的解决方案,在多种建筑形状下不能够保证遍历的有效性且没有建立配套的优化模型。

针对上述问题,考虑到桥梁形状的复杂性,为使系统全面地对各类桥梁进行建模、保证无人机Agent顺利完成遍历检查任务,本文将CPP问题分为建模和求解两部分:1) 受到Mansouri等^[22]的启发,在原有理论基础上提出一种建筑通用遍历建模方法;2) 根据模型改进任务分配和路径规划算法,完成最终路径规划。

2 协同覆盖路径规划模型

本节对无人机群桥梁检查问题进行数学建模。无人机群搭载深度相机和激光雷达,对桥梁进行基于实时地图构建(SLAM)的三维点云数据采集,获得桥梁点云模型后执行桥梁遍历路径规划任务。任务目标是在满足性能约束的前提下为无人机群系统(U={u₁,u₂,…,u_N},其中N为无人机数量)规划出一组合理的全覆盖平滑路径点序列集P={P₁,P₂,…,P_N},并使得无人机群系统总用时min C=max(C_U),其中C_U表示无人机群每个个体用时集合,两路径点之间的最大距离D受搭载激光扫描覆盖范围限制。

2.1 问题分析

文献[ 22]介绍了三维点云切片模型的详细步骤,如图1所示。其建模核心是对三维空间进行切片,利用水平面集Β将三维点云数据切割为多个水平面上的二维点集γ,并分别对每个二维点集进行聚类、快速凸包操作,从而得到三维空间中的凸包线集H={H₁,H₂,…,H_Q},其中H_i表示凸包线点集,i={1,2,…,Q},Q表示凸包个数,这种建模方法仍然有缺陷,如图1中缺失部分(missing parts),其更适用于直立的细长建筑物。对于桥梁等具有较大水平面的建筑物,这种建模方法将会造成大面积遗漏,并且模型本身没有匹配的最优规划算法。本文在此基础上进行改进,增加了补充平面,并将弧作为优化对象,对桥梁检查问题建立优化模型。

图 1. 点云切片模型建模与缺陷。(a)切片;(b)交叉;(c)聚类与凸包

Fig. 1. Modeling and defects of point cloud slice model. (a) Slicing; (b) intersection; (c) clustering and convex hull

下载图片查看所有图片

2.2 补充平面建立

补充平面Α^comp的建立分为视点补充和上下层筛选两个部分,如图2所示。第一部分利用Α_i层与Α_j层凸包线包围的面积 $S_{i}^{area}$ 与 $S_{j}^{area}$ 判断是否需要补充层,当 $S_{i}^{area}$ > $S_{j}^{area}$ ,需对平面Α_i增加补充视点,以达到对切层完全遍历的目的,反之对Α_i层增加补充视点,补充视点的方式是针对所需补充层产生均匀点集I。为保证算法速度,第二部分采用弧长法^[24],时间复杂度为O(n),根据Α_i层与Α_j层中凸包线从I中筛选所需补充视点集V。

图 2. 补充视点筛选

Fig. 2. Screening of additional view points

下载图片查看所有图片

2.3 初始化弧集

弧集定义为L_arc={L_arc,1,L_arc,2,…,L_arc,_M},L_arc,_m是三维空间中的弧,m={1,2,…,M},凸包集H是三维空间中的闭合曲线集,利用凸包线分割、构建弧集。无人机跟随凸包线时,必须要考虑进入凸包和离开凸包的点,即凸包的穿入点P_in和穿出点P_out,一种较为理想的方案是根据凸包贪婪原则确定P_in和P_out作为凸包层间分割为弧的端点;补充平面中视点构建弧集,如图3所示。为避免弧集长度方差过大,采用视点短边化弧,即以补充矩形平面中视点较少的方向作为补充弧平行方向生成补充弧。

P_{in / out}^{ij} = \underset{(x, y, z)}{argmin} |H (Α_{i}) - H (Α_{j})|, (1)

式中:i,j={1,2,…,Q}; ${P^{ij}}_{in / out}$ 为Α_i层与Α_j层间穿入穿出的点矩阵的元素;H(A_i)、H(A_j)分别表示A_i、A_j层中凸包线上的点。

图 3. 视点转化弧集

Fig. 3. Viewpoint transformation arc set

下载图片查看所有图片

2.4 弧集拆分

初始弧集利用P_in和P_out作为弧的端点进行分割得到,L_arc中弧跨越空间距离并不均匀,N=1时,所有L_arc由单个Agent执行,问题仅考虑Agent最优路径规划即可完成规划任务;N>1时,必须考虑L_arc元素合理分配的问题,即弧集可根据Agent数量拆分为均匀元素,如图4所示,L_arc可增加断点P^s∈ℝ^l^×3,l表示断点数量。

图 4. 弧拆分

Fig. 4. Splitting of arc

下载图片查看所有图片

2.5 广义多旅行商(GMTSP)模型

弧集构建将原遍历路径规划问题转化为弧集L_arc元素顺序组合优化问题,基于经典GTSP(generalized traveling salesman problem)^[25],桥梁检查路径规划问题可描述为:任务由Agent系统合作完成,定义任务集O_Task=L_arc, $T_{u_{i}}$ 表示分配至无人机u_i的所有任务,u_i飞过任务集 $T_{u_{i}}$ 中所有L_arc,即完成自身任务,其中 $L_{arc} = \overset{N}{\sum_{i}} T_{u_{i}}$ ,N表示Agent总数,通过协同优化u_i的任务执行序列P_i,使总体路径最短。每个Agent必须参与工作,定义总路径长度为D^is, $D_{i}^{is}$ 表示u_i行进的总路程,即 $\min D^{is} = \overset{N}{\sum_{i = 1}} D_{i}^{is}$ 。为进一步使得模型标准化,将协同桥梁覆盖路径规划(CBCPP)转化为GMTSP问题,设Agent初始位置为原点,弧集L_arc={L_arc,1,L_arc,2,…,L_arc,_M}分别表示需要被N个旅行商合作访问的M个城市群,取P_in和P_out分别作为城市群穿入、穿出点集,则节点总数为2M。

设p₁,p₂⊂P_in/out,定义旅行花费C如下:

C (p_{1}, p_{2}) \{\begin{array}{l} |L (p_{1})| & if L (p_{1}) ☉ L (p_{2}) = 0 \\ \min |L (p_{1}) - L (p_{2})| & others \end{array}, (2)

式中:L(·)表示(·)点所在弧;☉表示同或运算。

至此,GMTSP模型建立完成,只需分配每个Agent的任务节点集,并分别计算每个Agent哈密顿回路即可获得路径,下面介绍任务分配和路径生成方式。

3 检查路径生成

本节根据建立的GMTSP模型,通过拆分联合一致性束算法(SC-CBBA)分配每个Agent任务集,利用聚类特性增长环自组织映射(CRSOM)生成最终路径序列。

3.1 SC-CBBA

CBBA于2009年由麻省理工学院的Choi等^[26]提出,主要用于多智能体任务分配决策过程,算法主要思想有两部分:1)针对智能体建立任务束集,这个过程是贪婪的;2)利用一致性算法对所有任务束集冲突进行消解。CBBA主要考虑每个任务仅由单一智能体完成,在实际任务场景下具有一定的局限性。本文将CBBA扩展为SC-CBBA,由于文章篇幅所限,这里仅介绍算法扩展部分,详细算法可参考孙家广等^[24]的研究。

SC-CBBA中,每个Agent将参与决策,定义无人机系统U={u₁,u₂,…,u_N}为决策者;L_arc={L_arc,1,L_arc,2,…,L_arc,_M}为原始任务集合,定义T为工作任务集合,与CBBA不同,SC-CBBA任务集T由L_arc任务集拆分和扩展所得,定义任务集邻接矩阵A_T用于描述任务之间是否由L_arc,_m拆分所得,元素A_T(k,L)可表示为

A_{T} (k, L) = L [T (k)] ☉ L [T (L)], (3)

式中:L[T(k)]表示T中第k个工作任务属于原始任务集L_arc中的元素;k,L={1,2,…,T'},T'表示T中的任务数。

下面给出SC-CBBA在桥梁检查中的任务分配过程:

1) 计算T,按照任务量拆分原始任务集L_arc,更新工作任务集T,更新任务集邻接矩阵A_T:

T = \{\begin{array}{l} T \oplus {\min L_{arc}}, L_{arc, q} - \min L_{arc}, if L_{arc, q} > \min L_{arc} \\ T \oplus {\mod L_{arc, q}}, q (n + 1) = q (n) + 1 \end{array}, (4)

式中:初始T=Ø;n表示迭代次数;q(n)表示n代原始任务集索引,q(0)=1;T⊕{·}表示添加任务{·}至集合T;L_arc,_q为任务拆分间距。

2) 计算u_i选择任务T(k)的边际得分c_ik(P_i)。

3) 确定u_i待竞拍任务,以确定T(k)是否待拍:

h_{ik} = \{\begin{array}{l} 1, c_{ik} > y_{ik} \\ 0, c_{ik} \leq y_{ik} \end{array}, T (k) \in T, (5)

式中:h_ik=1表示第i个无人机竞拍到任务集中第k个任务,h_ik=0表示没有获拍;y_ik表示目前u_i对T(k)的最高出价。

4) 求得得分最高任务T(k^*)与最大得分任务执行位置 $L_{k}^{*}$ :

\begin{array}{l} T (k^{*}) = \underset{T (k) \in T}{argmax} c_{ik} (P_{i}) \cdot h_{ik}, (6) \\ L_{k}^{*} = \underset{L \in {0,1, 2, \dots, M}}{argmax} S_{i}^{P_{i} \oplus_{n} T (k^{*})}, (7) \end{array}

其中

\begin{array}{l} c_{ik} (P_{i}) = \{\begin{array}{l} \max_{L \leq |p_{i}| + 1} S_{i}^{p_{i} \oplus_{L} {T (k)}} - S_{i}^{p_{i}} & T (k) \notin P_{i} \\ 0 & T (k) \in P_{i} \end{array}, (8) \end{array}

S_{i}^{P_{i}} = \max \overset{M_{i}}{\sum_{k = 1}} S_{i}^{P_{ik}} A_{T} (L, k), (9)

式中:P_i表示u_i执行T(k)的贪婪路径序列; $S_{i}^{P_{ik}}$ 为第i个无人机执行任务序列P_i所获得分,即执行任务集收益。

5) 如果c_ik<0,则退出,否则继续执行。

6) 更新任务束集b_i与路径集P_i:

b_{i} = b_{i} \oplus_{M} T (k^{*}), P_{i} = P_{i} \oplus_{L_{m}^{*}} T (k^{*}) 。 (10)

7) 与存在通信链路的邻近Agent通信交换任务T(k^*)、获胜者出价 $y_{i k^{*}}$ 与竞拍状态 $h_{i k^{*}}$ 信息,消解Agent之间任务束集b的任务冲突,保证同一任务只分配至出价最高的Agent^[24]。

8) 根据A_T矩阵将束集b_i任务联合:

b_{i} = \{\begin{array}{l} {\dots [T (k) \oplus T (k + 1)] \dots} & if A_{T} [T (k), T (k + 1)] = 1 \\ {\dots T (k), T (k + 1) \dots} & others \end{array}, (11)

式中:k=1,2,…,|b_i|-1;[T(·)⊕T(·)]表示任务联合成为同一任务。

3.2 聚类特性增长环自组织映射网络路径规划

任务分配完成后,将弧集元素分配至各无人机L_arc= $\{L_{ar c_{1}^{u_{n_{1}}}}, L_{ar c_{2}^{u_{n_{2}}}}, \dots, L_{ar c_{M}^{u_{n_{n}}}}\}$ ,其中 $L_{ar c_{m}^{u_{n_{i}}}}$ 表示L_arc,_m被分配给无人机 $u_{n_{i}}$ 。再对每个无人机分别进行路径规划,视L_arc,_m两端点为自组织映射(SOM)同类输入层节点,运用CRSOM。

不同于传统的SOM,增长环自组织映射(RSOM)拥有可增长的输出层,与传统SOM相比,RSOM可以自适应地确定输出层节点数量。但RSOM对于GTSP仍具有局限性,本文基于RSOM算法^[27],通过引入聚类特性,提出一种新的CRSOM,与RSOM不同,CRSOM神经元的自组织、自适应机制将映射至同类的多个节点。

基于欧氏距离竞争的获胜神经元可表示为

X (A) = \arg \min_{j} (A - W_{j} (t)), j = 1,2, \dots, J, (12)

式中:J表示输出层神经元总数;A表示输入层同类节点的聚类中心;t表示时间变量;W_j(t)表示t时刻的输出层权值。获胜神经元和邻域神经元的修正强度函数为高斯函数,即

h_{j, X (A)} (t) = \exp \{- d_{j, X (A)}^{2} / [2 σ^{2} (t)]\}, (13)

式中:d_j_,_X₍_A₎为获胜神经元X(A)与神经元j的欧氏距离;σ(t)的大小与获胜神经元对邻域神经元影响的大小相关,σ(t)越大,获胜神经元对邻域神经元的影响越大。神经元权值修正方式为

\begin{array}{l} W_{j} (t + 1) = W_{j} (t) + η (t) h_{j, X (A)} (t) \times \\ [X (A) - W_{j} (t)], (14) \end{array}

式中:η(t)表示学习率。CRSOM继承了RSOM算法的增长特性,增长公式为

J (t + Δ t) = J (t) + 1, (15)

式中:J(t)为t时刻输出层神经元数量。为保证算法的收敛性,σ(t)与η(t)将随时间不断减小:

\begin{array}{l} σ (t) = σ_{0} \exp (- t / τ_{1}), t = 0, Δ t, 2 Δ t, \dots, k Δ t, \\ k \in Z^{+}, (16) \\ η (t) = η_{0} \exp (- t / τ_{2}), t = 0, Δ t, 2 Δ t, \dots, k Δ t, \\ k \in Z^{+}, (17) \end{array}

式中:σ₀为获胜神经元对邻域影响系数的初值;η₀为学习率初值;τ₁为常数,与获胜神经元影响系数的衰减速度相关,τ₁越大则影响系数的衰减速度越慢;τ₂为常数,与学习率衰减速度相关,τ₂越大则学习率衰减速度越慢; Δt为离散时间间隔。算法收敛后,可得出最终路径。

4 仿真

本节给出了算法仿真以验证本文算法的有效性。所有仿真在Matlab R2019b中进行,计算机环境配置为CPU Intel(R) Core(TM) i7-4710HQ CPU @2.5 GHz,内存为12 GB,操作系统为Windows 10。

4.1 弧集建立仿真

本仿真采用桥梁表面蒙特卡罗采样的稀疏数据点作为SLAM先验点云数据,首先构建点云切片模型,取激光覆盖范围的最大宽度D=5 m,弧集构建如图5所示,其中不同颜色实线和虚线代表不同弧,圆点表示穿入穿出点。图5(a)中凸包线和弧仅存在于桥梁垂直面,而水平面建模被遗漏,Mansouri等^[22]提出的模型存在不足。最后增加补充平面,构建弧集,桥面部分空缺被大量路径弧覆盖,弧集遍布整个桥面,由图5(b)可知,添加补充平面可有效弥补基于点云切片思想建立的模型无法100%覆盖的问题。

图 5. 覆盖路径弧模型建模结果。(a)点云切片建模; (b)增加补充平面弧

Fig. 5. Modeling results of covering path arc model. (a) Point cloud slice modeling; (b) adding supplementary arc

下载图片查看所有图片

为进一步验证覆盖路径弧模型在桥梁检查路径规划中的性能,对比覆盖路径弧模型与单元分解模型^[21]在D为3,4,5 m的情况下的建模时间和搜索复杂度,定义搜索空间复杂度O_s=(Q-1)!/2,其中Q表示N=1时任务序列长度。同一对比实验进行3次,以保证结果的可靠性。单元分解模型建模结果如图6所示,不同颜色的圆点为单元分解的视点,图6(b)中线条为视点通路。对比结果如表1所示。实验结果表明,本文提出的覆盖路径弧模型与单元分解模型相比在对同目标达到完全覆盖的情况下,建模时间更短,后续寻优复杂度更低,对传感器感知范围的敏感度影响小,更适用于大型建筑遍历建模场景。

图 6. 单元分解模型建模结果。 (a) 视点;(b) 视点通路

Fig. 6. Unit decomposition model modeling results. (a) Viewpoint; (b) Viewpoint pathway

下载图片查看所有图片

表 1. 建模对比实验统计表

Table 1. Statistical table of modeling comparison experiment

Sensor range /m	Covered path arc model			Unit decomposition model
Sensor range /m	Modeling time /s	Search complexity	Coverage rate /%	Modeling time /s	Search complexity	Coverage rate /%
D=3	71.748	331!/2	100	670.976	3982!/2	100
D=4	44.674	253!/2	100	253.521	2148!/2	100
D=5	40.526	205!/2	100	130.547	1321!/2	100

查看所有表

弧集建立后,为每个无人机均匀分配任务,以验证SC-CBBA的有效性,分别假设无人机数量N=3,4,5,6进行任务分配。

如图7所示,圆圈代表无人机初始位置,不同颜色和形状点代表不同任务弧位置。根据任务色块位置分布情况,可以看出SC-CBBA任务分配较为均匀,并且存在任务就近执行的趋向,这验证了SC-CBBA的可行性。

图 7. 任务分配结果。 (a) N=3;(b) N=4;(c) N=5;(d) N=6

Fig. 7. Task assignment results. (a) N=3; (b) N=4; (c) N=5; (d) N=6

下载图片查看所有图片

为进一步说明SC-CBBA解决不同均匀程度任务集的任务分配性能,定义任务分配均匀性评价指标E:

E = \frac{N}{\overset{N}{\sum_{i = 1}} (T_{u_{i}} {- μ)}^{2} + N}, (18)

式中: $μ = \overset{N}{\sum_{i = 1}} T_{μ_{i}} / N$ 。评价指标与任务分配结果方差相关,评价指标E的值域范围为[0,1],且任务分配均匀程度与E的值正相关。

在N=2,3,4,5,6,7,8,9,10、不同均匀程度任务集情况下对SC-CBBA与CBBA的任务分配性能进行分析。将以补充矩形平面中视点较少的方向作为补充弧平行方向生成的补充弧称为短边化弧模型,将短边化弧模型生成弧集定义为任务集均匀程度高,反之,将以补充矩形平面中视点较多的方向作为补充弧平行方向生成的补充弧称为长边化弧,将长边化弧模型生成弧集定义为任务集均匀程度低。对比结果如图8所示,实验结果表明,任务集均匀程度相同时,在相同的情况下,采用SC-CBBA得到的计算结果的均匀程度较高,任务集均匀程度不同时,SC-CBBA在任务分配中更具有稳定性,CBBA则受任务集均匀程度的影响较大。SC-CBBA更适用于任务均匀分配问题,对任务集均匀性要求较低,其分配结果在任务集均匀程度较低的情况下仍然较好。

图 8. 分配均匀程度对比图。(a) 任务集均匀程度高;(b) 任务集均匀程度低

Fig. 8. Comparison of allocation uniformity. (a) Task set with high uniformity; (b) task set with low uniformity

下载图片查看所有图片

4.2 CRSOM算法仿真

为验证CRSOM的可行性,本节给出算例TSPLIB标准库仿真,实验采用库函数集合模拟GTSP。根据数据集城市数量选取9个数据集(att48、eil101、ch150、d198、rand200、gil262、a280、lin318、pcb442),其中城市数量为偶数的数据集将所有城市每2个城市为1组进行分组聚类,模拟城市群输出优化路径序列。城市数量为奇数的数据集将数据集中某城市随机复制,将数据集扩展成城市数为偶数的数据集,然后将扩展后的数据集每2个城市为1组进行分组聚类,模拟城市群输出优化路径序列。图9为CRSOM算法输出的所有测试数据集路径图。由图10可以看出,CRSOM算法求解的数据集路径几乎没有交叉点,在城市数量上升的情况下仍然具有较好的结果,适用于GTSP的求解。

图 9. CRSOM规划结果。(a) att48; (b) eil101; (c) ch150; (d) d198; (e) rand200; (f) gil262; (g) a280; (h) lin318; (i) pcb442

Fig. 9. CRSOM planning results. (a) att48; (b) eil101; (c) ch150; (d) d198; (e) rand200; (f) gil262; (g) a280; (h) lin318; (i) pcb442

下载图片查看所有图片

图 10. 规划路径结果。(a) N=3;(b) N=4;(c) N=5;(d) N=6

Fig. 10. Planning path results. (a) N=3; (b) N=4; (c) N=5; (d) N=6

下载图片查看所有图片

为进一步评估CRSOM在桥梁检查路径规划中的性能,在相同数据集下将CRSOM算法与遗传算法(GA)、粒子群算法(PSO)和蚁群算法(ACO)进行对比。为保证实验的可靠性,进行20次蒙特卡罗仿真并求取均值,以此验证CRSOM解决GTSP的可靠性。统计结果如表2所示,结果表明,CRSOM算法与其他算法相比,在寻优最优值差值较小的情况下的寻优时间较短,寻优误差稳定,对多种数据集适应性较好,更适用于处理大规模场景的路径规划任务。

表 2. CRSOM蒙特卡罗实验结果

Table 2. Experimental results of CRSOM Monte Carlo

Data sets	CRSOM		GA		ACO		PSO
Data sets	Optimization time /s	Ratio ofdifference to optimal value /%	Optimization time /s	Ratio ofdifference to optimal value /%	Optimization time /s	Ratio ofdifference to optimal value /%	Optimization time /s	Ratio of difference to optimal value /%
att48	0.253	0.058000	4.687	0.075211	18.662	0.045893	16.167	0.120052
eil101	0.439	0.056214	10.719	0.093546	53.281	0.116037	43.234	0.102549
ch150	1.072	0.046320	16.652	0.125231	88.261	0.042151	100.561	0.186523
d198	1.468	0.061089	22.658	0.118900	142.869	0.051575	116.635	0.143790
rand200	2.031	0.043950	21.462	0.162420	142.373	0.099392	115.258	0.215457
gil262	2.438	0.070638	78.107	0.321450	239.882	0.100234	268.101	0.209810
a280	1.911	0.118066	82.157	0.312690	259.315	0.122540	251.527	0.138931
lin318	3.203	0.055971	25.362	0.871511	291.866	0.094059	447.075	0.274100
pcb442	6.589	0.110984	16.423	0.892595	569.625	0.154351	600.043	0.335440

查看所有表

4.3 桥梁覆盖路径规划仿真

为验证本文方法在工程应用中的有效性,以SC-CBBA分配的桥梁覆盖弧集为对象,使用CRSOM算法为路径规划算法,在N=3,4,5,6情况下仿真得到的最终路径如图10所示,其中圆圈代表无人机初始位置,不同颜色和不同线型用来区分不同无人机路径,其中平均规划时间为29.019 s,桥梁覆盖率为100%,这验证了CRSOM算法的有效性。

图11给出了有限无人机数量N=2,3,4,5,6,7与系统运行时间的关系,其中无人机飞行速度v=1 m·s^-1。实验结果表明,若有限增加无人机的数量,则系统的总运行时间会减少,这进一步验证了SC-CBBA分配结果与CRSOM算法规划的合理性。图中IQR为四分位差,表示数据分散程度。

图 11. 无人机数量与系统完成任务时间的变化关系

Fig. 11. Relationship between number of agents and task completion time of system

下载图片查看所有图片

5 结论

提出了一种适用于多无人机参与大型桥梁检查的路径规划方法,对多无人机桥梁检查覆盖路径规划问题中桥梁环境建模、任务分配机制和路径序列规划三部分提出了如下改进:

1) 基于点云切片想法,利用补偿视点与弧长法进行快速筛选,提出了覆盖路径弧模型,将桥梁覆盖路径规划问题建模为以弧为节点的广义多旅行商问题,仿真结果表明,相对于点云切片模型和传统单元分解模型,覆盖路径弧模型解决了点云切片建模不适用于水平面建筑的问题,并有效降低了寻优复杂度。

2) 提出SC-CBBA,改进CBBA,设计任务拆分合并机制,仿真结果表明,相对于CBBA,SC-CBBA对任务集均匀程度要求低,解决多种任务集时有着更为稳定的性能。

3) 对RSOM算法增加聚类特性,以求解广义旅行商节点的覆盖弧路径序列。仿真结果表明,所提出的方法能够为无人机团队快速规划出满意的路径序列,这保证了在桥梁表面的100%覆盖情况下缩小算法搜索空间、提高路径求解速度、减少计算资源消耗。分析了不同无人机数量的分配结果,并验证了在无人机数量增多时系统运行时间减少。

参考文献

[1] Phares B, Rolander D D, Graybeal B A, et al. Reliability of visual bridge inspection[J]. Public Roads, 2001, 64(5): 22-29.

[2] 张冬晓, 陈亚洲, 程二威, 等. 适用于无人机数据链电磁干扰自适应的环境监测系统[J]. 高电压技术, 2020, 46(6): 2106-2113.

Zhang D X, Chen Y Z, Cheng E W, et al. Environmental monitoring system suitable for electromagnetic interference adaptation of UAV's datalink[J]. High Voltage Engineering, 2020, 46(6): 2106-2113.

[3] Jakob S, Zimmermann R, Gloaguen R. The need for accurate geometric and radiometric corrections of drone-borne hyperspectral data for mineral exploration: MEPHySTo: a toolbox for pre-processing drone-borne hyperspectral data[J]. Remote Sensing, 2017, 9(1): 88.

[4] DangT, MascarichF, KhattakS, et al.Autonomous search for underground mine rescue using aerial robots[C] //2020 IEEE Aerospace Conference, March 7-14, 2020, Big Sky, MT, USA.New York: IEEE Press, 2020: 1- 8.

[5] 韩建峰, 张妍. 基于无人机航拍路面的拼接算法研究[J]. 激光与光电子学进展, 2020, 57(20): 201003.

Han J F, Zhang Y. Research on stitching algorithm based on UAV based on aerial photography[J]. Laser & Optoelectronics Progress, 2020, 57(20): 201003.

[6] 滕文秀, 温小荣, 王妮, 等. 基于深度迁移学习的无人机高分影像树种分类与制图[J]. 激光与光电子学进展, 2019, 56(7): 072801.

Teng W X, Wen X R, Wang N, et al. Tree species classification and mapping based on deep transfer learning with unmanned aerial vehicle high resolution images[J]. Laser & Optoelectronics Progress, 2019, 56(7): 072801.

[7] Metni N, Hamel T. A UAV for bridge inspection: visual servoing control law with orientation limits[J]. Automation in Construction, 2007, 17(1): 3-10.

[8] 林嘉睿, 徐鑫, 任永杰, 等. 室内空间测量定位系统扫描激光面模型优化[J]. 光学学报, 2019, 39(3): 0315002.

Lin J R, Xu X, Ren Y J, et al. Model optimization of scanning laser surface for workshop measurement positioning system[J]. Acta Optica Sinica, 2019, 39(3): 0315002.

[9] 常京新, 王双喜, 杨元维, 等. 高分遥感影像建筑物轮廓的逐级优化方法[J]. 中国激光, 2020, 47(10): 1010002.

Chang J X, Wang S X, Yang Y W, et al. Hierarchical optimization method of building contour in high-resolution remote sensing images[J]. Chinese Journal of Lasers, 2020, 47(10): 1010002.

[10] 谷艳红, 张振振, 高先和, 等. 激光超声结合电磁超声在铝板无损检测中的应用研究[J]. 中国激光, 2020, 47(5): 0504002.

Gu Y H, Zhang Z Z, Gao X H, et al. Application of nondestructive detection of aluminum using laser ultrasonic technology and EMAT method[J]. Chinese Journal of Lasers, 2020, 47(5): 0504002.

[11] 彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19(11): 2472-2476.

Peng H, Shen L C, Huo X H. Research on multiple UAV cooperative area coverage searching[J]. Journal of System Simulation, 2007, 19(11): 2472-2476.

[12] 陈海, 王新民, 焦裕松, 等. 无人机覆盖路径规划中转弯机动的运动学分析[J]. 飞行力学, 2010, 28(2): 31-34.

Chen H, Wang X M, Jiao Y S, et al. Kinematics analysis of UAV turning motion in coverage path planning[J]. Flight Dynamics, 2010, 28(2): 31-34.

[13] 陈海, 王新民, 焦裕松, 等. 一种凸多边形区域的无人机覆盖航迹规划算法[J]. 航空学报, 2010, 31(9): 1802-1808.

Chen H, Wang X M, Jiao Y S, et al. An algorithm of coverage flight path planning for UAVs in convex polygon areas[J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(9): 1802-1808.

[14] Li Y, Chen H, Er M J, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876-885.

[15] 陈海, 何开锋, 钱炜祺. 多无人机协同覆盖路径规划[J]. 航空学报, 2016, 37(3): 928-935.

Chen H, He K F, Qian W Q. Cooperative coverage path planning for multiple UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3): 928-935.

[16] Pham TH, BestaouiY, MammarS. Aerial robot coverage path planning approach with concave obstacles in precision agriculture[C] //2017 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED-UAS), October 3-5, 2017, Sweden.New York: IEEE Press, 2017: 43- 48.

[17] ChengP, KellerJ, KumarV. Time-optimal UAV trajectory planning for 3D urban structure coverage[C] //2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, September 22-26, 2008, Nice, France.New York: IEEE Press, 2008: 2750- 2757.

[18] Bircher A, Kamel M, Alexis K, et al. Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots[J]. Autonomous Robots, 2016, 40(6): 1059-1078.

[19] DogruS, MarquesL. Energy efficient coverage path planning for autonomous mobile robots on 3D terrain[C] //2015 IEEE International Conference on Autonomous Robot Systems and Competitions, April 8-10, 2015, Vila Real, Portugal.New York: IEEE Press, 2015: 118- 123.

[20] Hameed I A, la Cour-Harbo A, Osen O L. Side-to-side 3D coverage path planning approach for agricultural robots to minimize skip/overlap areas between swaths[J]. Robotics and Autonomous Systems, 2016, 76: 36-45.

[21] Phung M D, Quach C H, Dinh T H, et al. Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J]. Automation in Construction, 2017, 81: 25-33.

[22] Mansouri S S, Kanellakis C, Fresk E, et al. Cooperative coverage path planning for visual inspection[J]. Control Engineering Practice, 2018, 74: 118-131.

[23] 陈影, 孙文磊, 黄勇, 等. 激光熔覆曲面零件再制造的机器人路径规划[J]. 中国激光, 2017, 44(5): 0502001.

Chen Y, Sun W L, Huang Y, et al. Robot path planning of laser cladding and remanufacturing of curved surface parts[J]. Chinese Journal of Lasers, 2017, 44(5): 0502001.

[24] 孙家广, 胡事民. 计算机图形学基础教程[M]. 2版. 北京: 清华大学出版社, 2009: 49- 51.

Sun JG, Hu SM. Basic course of computer graphics[M]. 2nd ed. Beijing: Tsinghua University Press, 2009: 49- 51.

[25] Gendreau M, Laporte G, Semet F. A branch-and-cut algorithm for the undirected selective traveling salesman problem[J]. Networks, 1998, 32(4): 263-273.

[26] Choi H L, Brunet L, How J P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Transactions on Robotics, 2009, 25(4): 912-926.

[27] SasamuraH, OhtaR, SaitoT. A simple learning algorithm for growing ring SOM and its application to TSP[C] //Proceedings of the 9th International Conference on Neural Information Processing, 2002. ICONIP'02, November 18-22, 2002, Singapore, Singapore.New York: IEEE Press, 2002: 1287- 1290.

3.2 聚类特性增长环自组织映射网络路径规划

刘春磊, 张宏立, 王聪. 基于覆盖路径弧的无人机桥梁激光扫描路径规划[J]. 激光与光电子学进展, 2021, 58(8): 0828003. Chunlei Liu, Hongli Zhang, Cong Wang. UAV Bridge Laser Scanning Path Planning Based on Coverage Path Arcs[J]. Laser & Optoelectronics Progress, 2021, 58(8): 0828003.

基于覆盖路径弧的无人机桥梁激光扫描路径规划 下载： 811次

1 引言

2 协同覆盖路径规划模型

2.1 问题分析

图 1. 点云切片模型建模与缺陷。(a)切片;(b)交叉;(c)聚类与凸包

Fig. 1. Modeling and defects of point cloud slice model. (a) Slicing; (b) intersection; (c) clustering and convex hull

2.2 补充平面建立

图 2. 补充视点筛选

Fig. 2. Screening of additional view points

2.3 初始化弧集

图 3. 视点转化弧集

Fig. 3. Viewpoint transformation arc set

2.4 弧集拆分

图 4. 弧拆分

Fig. 4. Splitting of arc

2.5 广义多旅行商(GMTSP)模型

3 检查路径生成

3.1 SC-CBBA

3.2 聚类特性增长环自组织映射网络路径规划

4 仿真

4.1 弧集建立仿真

图 5. 覆盖路径弧模型建模结果。(a)点云切片建模; (b)增加补充平面弧

Fig. 5. Modeling results of covering path arc model. (a) Point cloud slice modeling; (b) adding supplementary arc

图 6. 单元分解模型建模结果。 (a) 视点;(b) 视点通路

Fig. 6. Unit decomposition model modeling results. (a) Viewpoint; (b) Viewpoint pathway

表 1. 建模对比实验统计表

Table 1. Statistical table of modeling comparison experiment

图 7. 任务分配结果。 (a) N=3;(b) N=4;(c) N=5;(d) N=6

Fig. 7. Task assignment results. (a) N=3; (b) N=4; (c) N=5; (d) N=6

图 8. 分配均匀程度对比图。(a) 任务集均匀程度高;(b) 任务集均匀程度低

Fig. 8. Comparison of allocation uniformity. (a) Task set with high uniformity; (b) task set with low uniformity

4.2 CRSOM算法仿真

图 9. CRSOM规划结果。(a) att48; (b) eil101; (c) ch150; (d) d198; (e) rand200; (f) gil262; (g) a280; (h) lin318; (i) pcb442

Fig. 9. CRSOM planning results. (a) att48; (b) eil101; (c) ch150; (d) d198; (e) rand200; (f) gil262; (g) a280; (h) lin318; (i) pcb442

图 10. 规划路径结果。(a) N=3;(b) N=4;(c) N=5;(d) N=6

Fig. 10. Planning path results. (a) N=3; (b) N=4; (c) N=5; (d) N=6

表 2. CRSOM蒙特卡罗实验结果

Table 2. Experimental results of CRSOM Monte Carlo

4.3 桥梁覆盖路径规划仿真

图 11. 无人机数量与系统完成任务时间的变化关系

Fig. 11. Relationship between number of agents and task completion time of system

5 结论

Article Outline

相关论文

相关资讯

关于本站 Cookie 的使用提示

全站搜索

基于覆盖路径弧的无人机桥梁激光扫描路径规划下载： 811次