SCI论文（www.lunwensci.com）
摘 要：近年来,随着无人机技术的飞速发展,旋翼无人机由于具有灵活机动、轻量化、成本低等优点在搜救领域得到了 广泛应用。本文面向未知环境研究无人机群执行区域覆盖搜索任务,以任务耗时最短为算法评价指标,提出了回字形扩展搜索 算法。首先对传统区域覆盖搜索算法和本文所提出的算法进行了介绍,之后针对算法建立了仿真环境模型和算法模型,并基于 NetLogo 仿真环境通过蒙特卡罗方法进行了试验及结果分析。与传统随机游走覆盖搜索算法进行对比,结果显示本文提出的基 于搜索图的协同模式下的回字形扩展覆盖搜索算法区域覆盖耗时短、重叠率低,具有分布式、自主性、在线实时规划、抗毁性 等特点。
关键词 ：区域覆盖,未知环境,回字形扩展搜索算法,无人机群,搜索图,分布式
Research on Area Coverage Search Algorithm for UAVs in Unknown Environment
LIU Jiansheng1.2. XU Sai1.2. WANG Chen1.2. HE Tao1.2. LI Zhi1.2. WEN Yingyou1.2
(1.Cyberspace Security Professional Technology Innovation Center of Liaoning Province, Shenyang Liaoning 110169;
2.Neusoft Reserch, Northeastern University, Shenyang Liaoning 110169)
【Abstract】： In recent years, with the rapid development of UAV technology, rotor UAV has been widely used in the field of search and rescue due to its advantages of flexibility, light weight and low cost. In this paper, the area coverage search task of UAV swarm is studied for unknown environment. Taking the shortest task time as the evaluation index of the algorithm, a backtracking extended search algorithm is proposed. Firstly, the traditional area coverage search algorithm and the algorithm proposed in this paper are introduced. Then the simulation environment model and algorithm model are established for the algorithm, and the experiment and result analysis are carried out by Monte Carlo method based on NetLogo simulation environment. Compared with the traditional random walk coverage search algorithm, the results show that the Hui extended coverage search algorithm based on the search graph cooperative mode proposed in this paper has short coverage time and low overlap rate. It has the characteristics of distribution, autonomy, online real-time planning and invulnerability.
【Key words】： regional coverage;unknown environment;backtracking extended search algorithm;UAV group;search graph;distributed
0 引言
近年来,自然灾害、人为事故频发,给人们的生命 和财产带来了巨大的损失。无人机具有小型、造假低 廉、环境适应能力强、使用便捷、起飞方式灵活、飞行 方式多样等特点,在各类灾害、事故救援中发挥了重要的作用 [1]。而在灾害、事故救援中,如何快速进行区域 覆盖搜索,及时发现未知区域内的待救援目标,以便为 后续救援人员提供目标位置,已成为重要的研究内容。 基于无人机群的区域覆盖搜索主要研究无人机群如何按 照某种搜索方法在待侦察区域飞行侦察中完成整个区域的完全覆盖搜索以找到待救援目标。
目前,面向未知环境的区域覆盖搜索算法,比较主 流的是之字形扫描和螺旋形扫描等,在实际区域覆盖搜 索中暴露出了鲁棒性低、抗毁性差、搜索效率低、任务 成本高、搜索面积不均等多种问题 [2]。本文提出了基于 搜索图的回字形扩展覆盖搜索算法, 基于 NetLogo 仿 真环境,结合以往的随机搜索算法进行了仿真对比。对 比结果表明,回字形扩展覆盖搜索算法区域覆盖耗时 短,大大提高了无人机群的区域覆盖搜索效率,突出了 该算法的优势。
1 区域覆盖算法介绍
1.1 区域覆盖算法发展现状
基于无人机的区域覆盖搜索算法,按照控制方式的 不同主要分为集中式和分布式两种。
集中式区域覆盖搜索算法需要中心控制节点,在事 先知道待覆盖区域的形状、面积等先验信息的前提下, 提前规划好各无人机的飞行路线,往往需要离线规划。 集中式区域覆盖算法优点是重复覆盖区域少甚至完全没 有。缺点是当通信距离受限时,需要线下规划,实时性 较差。同时,由于事先规划好各无人机飞行路线,一旦 某个无人机出现故障,则分配给该无人机的搜索任务则 无法完成,无人机抗毁性较差。目前比较常见的算法是 之字形搜索算法 [3]、螺旋形扫描搜索算法 [4]、分区域搜 索算法 [5] 和基于 Voronoi 图的分区搜索算法 [6]。
分布式区域覆盖搜索算法是分布式去中心化的,不 需要提前知道待覆盖区域的形状、面积等先验信息。各 无人机的搜索路线是自主规划的,无人机之间的协同是 自组织的,不需要知道全局信息,只利用局部信息的共 享就能做好下一步的搜索路线规划,实时性较强。在 通信受限的情况下,也能很好地完成搜救任务。虽然有 一定几率出现重复搜索问题,但可以通过无人机间的协 同,极大降低这样的概率。由于灾难、事故现场往往通 信条件差,现场环境比较复杂,分布式覆盖搜索算法以 其能较好适应复杂环境的特点,成为目前主要研究趋 势。文献 [7] 提出了一种一致性协议,实现多智能体协 同的一致性,该算法虽然一定程度上符合分布式,但由 于需要局部无人机之间进行协商,实际已经形成了一定 的集中控制因素,并非完全的分布式方式。文献 [8] 通 过对深海鱼群的聚集行为的研究,发现鱼群间保持着一 定的吸引和排斥区,但吸引和排斥区的选择对算法的效 果影响很大。此外,近年来有些研究人员尝试将深度 学习、强化学习的方法应用到分布式无人机搜索算法 中 [9],但由于无人机现有硬件条件的限制,这些方法存在对训练和运行环境计算资源要求较高、算法验证周期 长、算法泛化能力弱,不太适用于无人机特别是小型、 微型无人机。
1.2 本文算法介绍
为了更好的阐述各覆盖搜索算法,这里先介绍几个 概念 ：搜索图、通信半径和感知半径。
(1) 搜索图 ：无人机在搜索过程中, 会以列表形式 不断记录已搜索的区域的坐标点信息,形成搜索图。
(2) 通信半径 ：无人机在协同搜索过程中,会涉及 到通信半径。通信半径即无人机之间通信时最长的有效 通信距离。为了简化,本文假设通信半径范围内无人机 之间的通信是理想的,不存在延迟、信息丢失等现象。
(3) 感知半径 ：也是无人机的搜索半径, 是无人机 能够通过传感器感知到待搜索区域内目标的最长距离。 本文无人机的感知半径为九宫格范围,即围绕无人机周围的 8 个坐标点和无人机所在位置的坐标点形成的 9 个坐标点。
在对现有算法研究基础上,本文设计了回字形扩展 区域覆盖搜索(Hui Diffusion,HD) 算法。HD 是以 当前无人机为中心,以回字形方式不断向外逐渐扩大查 询范围。HD 看似与螺旋形搜索很相似,但实际完全不 一样。HD 查询过程中无人机是不动的,确定下一步要 移向的坐标点之后无人机才会移动,极大降低了无人机 的搜索试错成本和能源消耗。
为了简化算法运行场景,将待覆盖搜索区域设置为 正方形区域,对区域进行坐标离散栅格化,且有边界。 待搜索区域内的坐标点均为整数值,无人机飞行经历的 点是连续的,坐标值可以是浮点数。算法初始时,无人 机聚集在待搜索区域的正中心坐标原点附近,飞机朝向 随机。搜索开始后,无人机按照各算法的设计飞向不同 的方向,无人机存储各自曾经搜索过的区域的坐标信息 形成搜索图。无人机有区域边界检测能力,遇到边界会 进行搜索路线调整。非协同模式下,各无人机之间不会 共享各自存储的搜索图 ;协同方式下,无人机会将各自 的搜索图共享给通信半径范围内的其他无人机。后文仿 真环境章节会进行更为详细的描述。
为了与传统算法对比,本文在设计回字形扩展覆盖搜 索算法时,也设计了经典的随机游走区域覆盖搜索算法。
1.2.1 随机游走区域覆盖搜索算法
随机游走区域覆盖搜索算法以当前无人机为中心, 以某个扇形角度范围为转向区间进行转向,比如转向左 右各 30°形成 60°范围内的转向范围,在转向范围内随 机生成转向值进行转向,之后按照某个步长移动,移动 过程中进行搜索操作并形成搜索图。无人机移动到下一个点之后,继续转向、移动、搜索,如此周而复始直至 完成整个区域的覆盖搜索。具体算法如下 ：
初始化时各无人机聚集在原点(0.0) 附近, 设转 向角范围为 Φ,初始值 Φ=30°。
(1)将当前 UAV 所在的坐标点标记为已搜索,并 加入到自己的搜索图中。
(2)无人机在 [-Φ,Φ] 闭区间范围内随机生成角度 θ,无人机转动 θ,移动一个步长,移动到下一个坐标点, 进入步骤 3.
(3)记录周围九宫格范围内的点的坐标加入到搜索 图中。判断整个区域是否搜索完毕,如果是则停止算 法,整个区域搜索完毕记录搜索耗时 ;如果否,则继续 步骤 2.
随机游走算法中各无人机各自进行随机搜索,无人 机之间不进行协同操作,不会共享搜索图信息。
1.2.2 回字形扩展覆盖搜索算法
回字形扩展覆盖搜索算法,各无人机以自己当前坐 标为中心点,以 1 个单位的坐标距离为扩展查询距离 呈回字形向外逐渐扩展查询。查询过程中,无人机是保 持在当前位置瞬时不动的,查询到坐标点的集合中尚有 未在自己搜索图中的点,则在这些点中寻找与当前无人 机欧式距离最近的点作为下一步移向的点之后再进行移 动。距离当前无人机最近回字形扩展算法步骤如下 ：
初始化时无人机聚集在原点(0.0) 附近, 设搜索 圈数为 n,初始值为 n=1.
(1)将当前 UAV 所在的坐标点标记为已搜索,并 加入到自己的搜索图中。
(2)是否为协同方式,如果否,进入步骤 3.如果 是,则获取通信半径范围内的其他无人机共享的搜索图 与自己的搜索图融合形成新的搜索图,进入步骤 3.
(3)搜索当前 UAV 外围第 n 圈的坐标点,对比搜 索图判断是否有未被搜索的点。如果没有进入步骤 4. 如果有,则停止搜索,从这些点中选出距离当前 UAV 欧式距离最小的点作为当前 UAV 下一个搜索点,并且 当前 UAV 移向该点,到达该点后依据本算法开启新一 轮搜索。
(4) 判断区域内所有坐标点是否已被搜索, 如果是, 则算法停止,无人机完成整个区域的覆盖搜索任务。如 果否,则 n=n+1.跳转到步骤 3.
如图 1 所示,当前无人机 A 的坐标为(5.5),向外 扩展搜索,首先将无人机 A 所在的坐标点(5.5)设置为 已搜索加入到搜索图。当搜索圈数 n=1 时,无人机 A 搜 索其周围的 8 个点, 即点(4.6)、(5.6)、(6.6)、(4.5)、
(5.5)、(6.5)、(4.4)、(5.4)、(6.4), 假设这些点 已经 被搜索过,即在搜索图中存有这些点的信息,跳转到步 骤 3. n=n+1. 此时 n=2.开始搜索第二圈, 即搜索点 (3.7) 到点(7.7) 再到点 (7.3) 再到点(3.3), 最后回 到 (3.7) 点形成的矩形。搜索这个矩形中的点,假设发 现有未搜索的点,本示例为(7.5)和(3.3)两个点。将 这两个点与当前无人机 A 的坐标(5.5)做欧式距离计算, 发现(7.5) 离(5.5) 更近, 则无人机将(7.5) 点作为下一 个飞向的坐标点,停止搜索算法(7.5)点,到达该点 后按上述算法开启新的搜索。以上步骤不断重复,直至 区域内所有坐标点均已被搜索算法停止。
该算法的主要思想是让无人机尽量以当前无人机为 中心向外围逐渐扩大搜索范围,让无人机每一步的移动 距离最短。
2 算法仿真
2.1 仿真环境介绍
本文算法仿真环境采用的是 NetLogo 仿真平台。 NetLogo 是研究基于多 Agent 的面向群体智能的主流 仿真平台。经过 20 多年的发展, NetLogo 已被全球数 千万学生、教师和研究人员用于教学、学习和研究当中。
2.2 仿真环境模型
2.2.1 仿真环境假设
为了重点关注算法核心内容,对仿真环境进行了一 些假设,如下 ：
(1)仿真环境为二维平面 ;
(2)无人机为四旋翼无人机且均飞行在同样高度 上,不考虑无人之间的碰撞。无人机匀速飞行,不考虑 加速和减速阶段,飞行途中可以随意转向 ;
(3)无人机间的通信有效性是 0 和 1.超过某个通 信半径,完全不能通信。在通信半径范围内,通信是理 想的,不考虑通信延迟和信号衰减 ;
(4) 无人机感知范围,感知范围只包含周围一圈的坐 标范围。比如当前无人机坐标为(0.0),则其感知范围为(-1.1), (0.1)(1.1), (-1.0), (0.0), (1.0), (-1. -1), (0.-1), (1.-1),即九宫格范围 ;
(5) 相对待覆盖区域, 无人机群密度较为稀疏。每 个时刻各无人机可覆盖面积之和,相较于待覆盖区域面 积小 1 ~ 2 个数量级 [10] ;
(6)区域内不存在无人机需要规避的危险区域,无 人机可在待侦察区域任意飞行。
2.2.2 仿真环境设计
本文仿真区域为二维平面,在 NetLogo 仿真环境里称 为世界World。如图 2 所示,世界为正方形平面,是离散 化、栅格化的, 尺寸为 41 patch×41 patch。每个 patch 为 1 个小正方形,尺寸是 16 像素 ×16 像素。坐标原点(0.0) 位于世界的正中心位置,左上角坐标为(-20.20)。世界 是有边界的,无人机无法飞跃世界最外侧的四条边。无 人机数量为 20 架四旋翼无人机,因为在抢险救灾过程 中往往很难短时间内调集相对救灾场景高密度的无人机 群,这个数量比较贴近无人机密度较小的实际场景需 求。无人机的每次移动的步长 step-size 为 1 个栅格的 边长长度。设置完成后的图如图 2 所示。
初始化时 20 架无人机聚集在世界原点位置,二维 地图黑色部分代表无人机未搜索过的区域。无人机开始 搜索时,会根据算法,飞向世界的各个区域,搜索到的 区域会变为白色。无人机之间可以进行通信,通信半径 可动态设置。
NetLogo 仿真环境有时间概念,以 ticks 嘀嗒来计 时,每嘀嗒一次,时间向后推进一个单位。仿真过程 中,各个算法利用 NetLogo 自带的行为空间工具,采 用蒙特卡洛模拟统计方法进行大量重复试验。每个试验 重复 3000 次, 区域全覆盖耗时取 3000 次的算数平均 值。部分算法存在迟迟无法完全覆盖搜索区域的现象,
比如随机游走算法,某些时候完成区域覆盖可能需要 2000 ticks 以上。为了减少这种超时覆盖情况,加速仿 真速度,则需要控制 ticks 上限,不能让仿真程序“无 休止”的运行下去。某次运行时间超过该上限值,则本 次仿真强制结束,所记录的 ticks 值采用均值过滤方式 进行过滤处理。
2.2.3 算法评价指标
算法以无人机群覆盖搜索完整个仿真区域的耗时为 评价指标,耗时越短算法相对越具有时间上的优势。即 当同样数量的无人机构成的无人机群,采用不同算法对 仿真区域进行覆盖搜索, 搜索完成时, NetLogo 中的 ticks 计时器数值越小越好。
3 仿真结果分析及对比
算法仿真过程中,我们增加了传统随机游走算法的 仿真,将随机游走覆盖搜索算法与回字形扩展覆盖搜索 算法进行了简单的对比。
3.1 无人机通信半径
在协同模式下无人机间的最佳通信距离会影响算法 的整体效果,本文需要对有效通信距离进行简单分析。
经过大量试验尝试发现,协同方式下,通信距离、 世界尺寸、无人机数量,都会影响算法效果。为了简化 算法对比,本文将世界尺寸、无人机数量固定,只关注 通信距离对算法的影响。试验发现,在协同模式下回字 形覆盖搜索算法中,算法的耗时随着无人机的有效通信 半径的增加,开始时会逐渐降低,当通信半径超过某个 阈值之后则会呈现小幅区间震荡。阈值半径值大概为世 界边长的 36% 左右,也即通信半径为 15 个 patch 长 度时是最佳通信半径。该通信半径既能保证算法运行结 果的理想度,实际当中也能最大程度地减少由于通信半 径增加功率过大带来的能量消耗。也即通信距离增加会 缩短区域覆盖耗时,但不能无限缩短,当距离大于某个 值后,再增大通信距离,不会继续缩短覆盖耗时。
3.2 随机游走覆盖搜索算法
随机游走覆盖算法无人机之间不共享搜索图信息, 即无人机之间是非协同的。如图 3 所示是随机游走法无 人机群的区域覆盖搜索的二维仿真图,图中显示的是大 部分区域已经被搜索完毕,只剩余少量区域待搜索。
图 3 中的线条为各无人机的搜索轨迹, 白色区域为 无人机已搜索区域,黑色区域为待搜索区域。从图 3 中 可以直观看出,随机游走算法每一步方向选择上均有一 定的偏角,一定程度上增加搜索的随机性,扩大了搜索 范围。随机游走搜索过程中存在一定的飞行线路重叠。 通过蒙特卡洛方法,完成所有区域搜索,随机游走算法
3.3 回字形扩展覆盖算法
回字形扩展算法分为协同和非协同两种模式。如 图 4、图 5 所示,分别是协同和非协同模式下的距离当 前无人机最近回字形扩展算法的仿真图。
试验结果显示回字形扩展覆盖搜索算法,协同模式 下完成整个区域覆盖搜索所需平均耗时为 74ticks,非 协同模式下平均耗时为 197.3ticks。非协同模式下区域 覆盖耗时较长,原因是因为搜索图信息未在无人机间进 行共享,提高了无人机对其他无人机已经搜索过的区域 进行重复搜索的概率,进而增加了覆盖搜索耗时。从图 4 和图 5 对比能看出, 明显图 5 非协同模式下无人机飞行 重叠区域较多。
3.4 算法对比
本节对随机游走覆盖搜索算法、协同和非协同两种 模式下的回字形扩展搜索算法完全覆盖区域平均耗时进 行对比如表 1 所示。
通过上表对比分析可知 ：
(1)对未知区域进行完全覆盖搜索耗时,回字形扩 展覆盖搜索算法在协同和非协同两种模式下较传统的随 机游走算法降低了 77.9% 和 41%,大大缩短了区域覆 盖搜索耗时 ;
(2)回字形扩展覆盖搜索算法协同模式较非协同模 式耗时要短,大概缩短了 62.5%。
回字形扩展覆盖搜索算法相比于随机游走算法大大 缩短了区域覆盖所需时间。协同模式下的回字形扩展覆 盖搜索算法属于分布式算法,无人机只需要利用局部共 享信息即可完成搜索路线的规划,较非协同模式算法耗 时短,搜索路线重叠率低,具备较强的自主性、在线实 时规划、抗毁性等特点,算法优势较为明显。
4 结语
本文针对未知环境的区域覆盖搜索问题设计了回字 形扩展区域覆盖搜索算法,按照无人机间是否共享信息 该算法分为协同和非协同两种方式。连同传统的随机游 走搜索算法,基于 NetLogo 多 Agent 仿真平台,通过 蒙特卡洛方法对这些算法进行了仿真对比。对比分析后 发现基于搜索图的协同方式下的回字形扩展算法表现最 优,该算法具有分布式、自主性、在线实时规划、抗毁 性等特点。下一步将在该算法基础上,考虑非规则区域 边界和算法移动点随机性选择方面继续深入研究。
参考文献
[1] 崔怀森,李向新,郭晓乐.现代化无人机技术在河湖划界方面 的应用[J].软件,2020.41(10):187-190.
[2] 韦定江,魏霄冉,蒋晓刚,等.基于5G通信网络条件下的无人 机海上搜救方案[J].软件,2021.42(06):145-150.
[3] FRANCO C D,BUTTAZZO G.Coverage Path Planning for UAVs Photogrammetry with Energy and Resolution Constraints[J].Journal of Intelligent & Robotic Systems, 2016.83(3/4):445-462.
[4] CABREIRA T M,FRANCO C D,FERREIRA P R,et al. Energy-aware Spiral Coverage Path Planning for UAV Photogrammetric Applications[J].IEEE Robotics and Automation Letters,2018.3(4):3662-3668.
[5] 肖玉婷,方勇纯,梁潇,等.基于分块优化思想的多无人机覆盖 路径规划[J].中国科学(技术科学),2020.50(4):439-452.
[6] YANG C M,DU L M,LI C.Methods and EfficiencyComparison of UAV Swarms Collaborative Search in Unknown Area[J].Aeronautical Science & Technology, 2019.30(10):56-63.
[7] REZAEE H,ABDOLLAHI F.Average Consensus Over High-order Multiagent Systems[J].IEEE Transactions on Automatic Control,2015.60(11):3047-3052.
[8] JOLLES J W,BOOGERT N J,SRIDHAR V H,et al. Consistent Individual Differences Drive Collective Behavior and Group Functioning of Schooling Fish[J].Current Biology, 2017.27(18):2862-2868.
[9] 李波,杨志鹏,贾卓然,等.一种无监督学习型神经网络的无人 机全区域侦察路径规划[J].西北工业大学学报,2021.39(1):77- 84.
[10] 任少睿,陆忠梅,石远明,等.一种基于信息素图的无人机高 效通信覆盖方法[J].航空学报,2022.43(2):332-346.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/54772.html
