一种面向地震场景的无人机协同搜索路径规划算法

沈秀娟,曹媛丽,卫 连,胡 蝶

(1.曲靖师范学院 数学与统计学院，云南 曲靖 655011；2.曲靖市第二小学，云南 曲靖 655000)

0 引 言

地震作为一种突发性、规模性的自然灾害,对人类的生产生活造成严重威胁.如果发生在人口密集的区域,往往会造成巨大的人员伤亡和经济损失.面对震后的危险性及不确定性,紧靠传统的人工救援方法无法快速有效且安全地解决救援问题.随着科学技术的进步,无人机的研发日趋成熟.面对震后场景,采用群体无人机协同搜索救援,可以提高救援效率[1].震后情况复杂,如何科学合理地利用无人机辅助救援行动,制定最佳的无人机协同搜索路径规划方案显得尤为重要[2].

由于无人机用途广泛且投入成本低,对于无人机的应用研究已成为国内外学者研究的热点话题之一.在国外方面,Jotrao 等人提出混合整数规划(MIP)方法和模拟退火启发式算法来研究在指定的燃料限制内无人机怎样设计飞行路径可获取更多的信息[3].Wang等人基于非支配排序遗传算法,提出了一种大规模约束的无人机路径规划智能算法[4].Lu等人利用蒙特卡洛树搜索和粒子群算法提出了一种充分利用智能离散和连续搜索算法的星载分布式轨迹规划统一框架,并将其运用到多无人机协同航迹规划和避障中进行仿真实验[5].Luo等人针对复杂环境下多无人机协同目标搜索问题提出了一种闭环路径规划方法[6].国内学者也积极进行了探索和研究:骆文冠等人考虑路径长度、风险成本、高度成本和平滑程度四个指标,建立应急无人机路径规划模型,提出一种基于强化学习的布谷鸟搜索算法对模型求解[7].杨春宁等人基于Voronoi图构型的多无人机区域覆盖模型和概率地图信息更新融合的协同搜索策略对未知区域无人机协同搜索方法及效率进行分析[8].刘培宾、盛怀洁以“全时域视场覆盖”为指标,结合一致性算法解决反辐射无人机协同搜索问题[9].王洪民等人针对多无人机协同搜索追踪区域内多运动目标问题,考虑无人机的传感器与避撞等约束和目标随机运动等特征,提出以垂线搜索为基础的多无人机协同搜索追踪策略[10].上述研究对多无人机协同控制方案和航行路线进行规划和设计时大都采用聚类、遗传算法、粒子群算法、神经网络算法等,在操作过程中不易理解,且这些算法在实践过程中或多或少都存在一些不足,不能广泛应用到现实生活中.

为了增强无人机协同搜索路径规划算法的实用性,文章考虑采用操作简单且易理解的深度优先搜索算法,并用生成树子树的方式对路径进行存储.然而,传统的深度优先搜索算法[11]是从一个节点沿着一条路径一直搜索下去,进行深度优先遍历,每个节点只能被访问一次.虽然该方法可以穷尽所有的节点,但它在路径搜索中费时费力,不够高效.同样,传统的生成树算法[12]可以系统地访问到图中所有顶点,但生成树的不唯一性,也增加了搜索的难度.本文在综合考虑各种利弊之后,提出了一种基于深度优先搜索和生成树算法的改进的路径规划策略,对多无人机协同的航行轨迹进行设计.该策略在深度优先遍历过程中嵌入目标函数和代价函数并对生成树进行减枝优化,同时对生成树子树所存储的路径以一定的权重计算目标搜索概率,用搜索概率的大小对子树进行编号排序,使得路径搜索算法在满足约束条件的情况下更加精准高效.该方法为今后无人机在抗震救灾过程中的协同搜索航行方案提供了一种新的思路.

1 问题提出

地震作为三大自然灾害之一,会对人类社会生活造成极大影响,比如人员伤亡和经济损失.地震后,对受伤、被困人员的搜救是一种高难度、高风险的行为,且不能完全保证实施搜救人员的生命安全.如果不能在一定时间内找到受伤严重的待救人员,可能会错过最佳医治时间,致使其残疾或伤亡.传统的震后救援方案是由施救人员和搜救犬根据先前经验结合当地地形、人口分布进行施救,针对性不强,搜救效率低.近年来,无人机在震后救灾时的应用使得施救效率提高和人员伤亡率降低,然而搜救团队的无人机数量是有限的.因此,需要对无人机协同搜索方案进行设计.

经过调查知道某地的搜救团队拥有2架侦察型无人机,该无人机搭载合成孔径雷达、航拍CCD相机等设备且具有航程远、留空时间长、环境适应性强等特点,可在断电、断网等极端灾害条件下,对目标区域进行成像,完成多谱段灾害现场探查.其性能如表1所示.

表1 无人机性能参数

本文收集该地以及其周围市、县所有的镇(乡)、村(社区)的地理位置坐标和相应人口数据进行实验模拟.图1是根据所收集数据绘制的人口居住分布图,图中的黑色五角星表示市或县,红色三角形表示镇(乡),蓝色圆圈表示村(社区).

图1 观测震区的人口居住分布图

由于同一观测震区的人口分布和震后受损程度不一样,为了更好地进行观测,本文根据损失最小和获救人数最多原则,决定以人口数量分布为主要参考因素,以村(社区)为基本单位对震区进行划分.图2是进行划分后的人口分布热力图,图中蓝色圆圈表示居住人口在0～1 000以内的村落、绿色圆圈表示居住人口在1 000～2 000以内的村落,红色圆圈表示居住人口在2 000～3 000以内的村落,黑色圆圈表示居住人口在3 000以上的村落.

图2 观测震区人口分布热力图

不同颜色的圆圈决定了观测顺序和观测次数的不同.黑色圆圈的分布地为重点观测区域,红色圆圈为次重点观测区域,绿色圆圈为一般重点观测区域,蓝色圆圈为一般观测区域.观察图2可知,观测震区的右下方人口分布非常密集,观测震区的中上方和左下方有较多人口分布.由于震后救灾时间紧张,而重点观测区域分布不集中,同时有无人区的存在,我们需要考虑怎样设计无人机的飞行路线使得无人机在最短时间内巡视重点观测区域时兼顾其他观测区域,返回更多的灾情信息.

2 建立模型

2.1 模型假设

(1)假设无人机从机场起飞前已充分考虑震区的特殊地形地势并设计出合理的飞行高度,起飞后都是按该高度以匀速对震区进行巡航.

(2)假设无人机在飞行的过程中工作状态保持稳定,不受地震后磁场、重力和天气异常等情况影响.

(3)假设重伤及被困人员在地震后处于不动或小范围移动状态,其移动范围可以忽略不计.

2.2 模型建立

震后的黄金救援时间为72小时,在此时间段内待救人员的存活率极高.从发生地震、相关部门收到地震救援信息、救援团队赶往救灾地点、救援方案的设计到救援行动的开展均需花费一定的时间.因此,为了留出更多的救援时间,无人机巡航返回观测震区情况的时间需要尽可能地缩短.综合考虑各种因素后,认为无人机的巡航时间应设定为1小时.

在充分考虑无人机的数量、性能参数等约束条件下,以救灾型无人机的起飞点为圆心,以最大探测距离8千米为半径绘制出无人机的探测范围(如图3中的圆1).为了对观测震区进行科学合理的巡查和航行轨迹设计的便利,以起始圆为基准,用一系列平行且相切的圆对观测震区进行全覆盖,这些平行且相切的圆称为“轨迹圆”.图3是轨迹圆对观测震区的覆盖情况图.

由图3可知,覆盖观测震区需要32个互不重叠的轨迹圆.按照从上到下、从左到右的顺序,依次将32个轨迹圆的圆心坐标记为Mi(xi,yi),i=1,2,…,32.根据轨迹圆的命名规则,将其中的第i个轨迹圆称为圆Mi,其圆心坐标如表2所示.

表2 轨迹圆Mi的圆心坐标

所建立的模型假设无人机的飞行轨迹是沿着相邻(相切)的轨迹圆的圆心直线飞行.无人机的巡航速度是130千米/小时,两个相切的轨迹圆的圆心Mi(xi,yi)和Mj(xi,yi)之间的距离是16千米,因此,搜寻时间内无人机大概可以飞过8个相邻的圆,加上起飞时机场位置所在的圆,将这9个圆循序依次排列起来,并将其称为该飞机的飞行路线.例如:第一架无人机U1从机场M1起飞,沿着相邻的圆,依次飞过M1、M2、M3、M6、M7、M12、M18、M24、M25,则记G1(M1、M2、M3、M6、M7、M12、M18、M24、M25)为U1的一条飞行路线.

按照模型假设,T=0时刻无人机从机场出发,此后每10秒成像一次.则在1小时内,每架无人机共成像360次(T=0秒时成像第1次,T=3600秒时成像第361次).

通常,无人机离目标越近,拍摄次数越多,发现目标的概率越大.定义qu,i,j,k,其中u=1,2表示无人机架次,i=1,…,100表示某位置的横坐标,j=1,…,100表示某位置的纵坐标,k=1,…,361表示成像的次数.例如q1,75,60,77表示第一架无人机第77次成像时发现位置为(75,60)处的目标的概率.影像中发现目标的概率为:

(1)

其中d是无人机与目标位置的距离,α是机载雷达的检测指数.

根据分析,每架无人机在给定的1小时内,都可以成像361次,则2架无人机的所有成像结果能够发现某个位置(xi,yj)上的目标的概率为:

(2)

把绘制的观测震区人口分布热力图(图2)看成一个100×100的热力矩阵,每个村落的人口数看成热力值.以热力值为指标对每个1×1的区域进行赋值,根据所赋数值的大小决定观测的优先级别.根据先前经验和现实综合研判,目标出现在某个位置(xi,yj)的概率为:

(3)

其中hij表示位置(xi,yj)的热力值.

结合式(2)和式(3),可以得到某条搜索路线的方案能够找到目标的概率为:

(4)

式(1)、(2)、(3)、(4)就是所研究问题的数学模型.其中式(4)是目标函数,不同的搜索路线影响式(2)的取值.根据目标函数,可以更好地设计无人机的飞行路线,进而达到提高抗震救灾效率的目的.

3 搜索策略

在求解无人机飞行路线的目标搜索概率之前需要找出无人机所有可行的飞行路径.观测震区已经用“轨迹圆”覆盖,无人机按照轨迹圆的圆心连线进行搜索飞行,相邻圆心之间的连线实质上构成了一幅带权值的无向图.为了使找到的无人机的飞行路径更加准确,在进行路径搜索之前先根据轨迹圆覆盖图的信息建立邻接矩阵作为辅助工具.邻接矩阵的建立过程如下所示:

假设F表示某个无向图,根据F的各个顶点之间是否可以直接连接,构造一个矩阵,1表示可以直接连接,0表示不能直接连接,其严格的数学定义如下:

以图4为例,进一步说明邻接矩阵的构造过程:

图4 无向图的邻接矩阵构建示例图

在邻接矩阵的基础上,如果不对无人机求解飞行路径的条件进行约束,那么路径的数量将会难以估量,导致模型求解难度提升.

为了找出适合的路径搜索算法,决定开展实验模拟.经过对多种已知路径算法进行尝试,发现其结果都很难达到预期要求.借鉴相关文献[11,12],利用深度优先搜索算法和生成树算法的特点,对其进行改进,得到了一种新的路径算法.

算法分为两步,第一步用于求解所有满足约束条件的通路,第二步用于求出最优的路径组合.使用者可根据自己的需求决定是否进行第二步算法.第一步,对深度优先搜索的每一个路径点选择都根据人口热力值的分布情况赋予不同权值,然后根据邻接矩阵、目标函数和所设置的步数条件判断从上一个路径点到下一个路径点是否可以通行,确认可通行后,有序保存该路径节点.为了保证所得路径各不相同,算法通过代价函数在每一次循环迭代中都对邻接矩阵实时更新.最后把每一条筛选出来的路径都以生成树子树的形式进行存储,形成满足约束条件的所有通路.第二步,根据第一步所得的所有满足约束条件的通路,算法可以任意指定由多少条路径进行组合,最终根据使用者设置的所需组合数留下权重最大即搜索概率较大的组合.留下的路径组合即为满足条件的最优路径组合.第一、二步算法流程图见图5、图6.算法的具体步骤如下:

图5 第一步算法流程图

图6 第二步算法流程图

Step1:输入起点和步数;

Step2:将图转换为邻接矩阵形式表示,并用二维数组存储;

Step3:从起点开始,从邻接矩阵遍历与起点相邻的所有通路节点,并存储编号;

Step4:遍历上一步的节点,找出与该节点相邻的所有通路节点,并判断是否有路径中已存储的节点,如果有则丢弃,否则存储该节点编号;

Step5:判断是否达到指定步数,如果达到,转到Step6,否则将转到Step4;

Step6:输出所有满足指定步数的路径.

Step1:输入满足约束条件的所有通路;

Step2:设定路径数n和路径组合数N;

Step3:计算每条通路的权重;

Step4:根据路径数n进行路径组合,并计算每个路径组合的权重;

Step5:对路径组合按权重从大到小进行排序;

Step6:输出前N个路径组合及其权重.

4 模型求解

无人机续航时间为10小时,可保证1小时内搜索任务结束后顺利返航,无需考虑中途返场补能情况.已知无人机在1小时内可飞行130千米(即大概8个轨迹圆),决定以此为约束条件.

根据观测震区轨迹圆覆盖图(图3)建立邻接矩阵,在邻接矩阵基础上,采用第一步算法对所有满足约束条件的飞行路径进行编程求解,实现了从给定顶点出发在指定步数约束下找到所有通路.根据程序运行结果得知符合无人机通行规则的路线一共有638条.

已知有两架无人机可供我们使用,采用第二步算法对无人机可能的飞行路线组合进行编程求解.根据程序运行结果得知两架无人机可能的飞行路线组合共有:638×638个.为了设计出符合预期效果的无人机巡航方案,表3列出了目标搜索概率较大的前十种路径组合,发现最大搜索概率为0.73,搜索概率最大的路径组合的飞行路线如图7所示.

图7 无人机最优飞行路径组合图

从计算结果看,路径搜索算法列出所有满足约束条件的搜索路径中,发现目标概率较高的路线主要覆盖人口密集的居民区,与实际相符.在考虑无人机的数量和各种约束条件下,无人机根据路径搜索算法所得到的最优路径组合即搜索目标概率最大的飞行路径,可以在给定时间内最大限度地获取灾情现场信息使救援行动的开展更加科学高效.

5 结 语

地震后,救援时间每拖延一分,被困人员面临的生命威胁便加重一分.救灾型无人机在震后救援中的应用使得施救团队充分了解灾情现场信息,能够制定出合理的救援方案,提高救援效率.但是怎样使用无人机能够更好地在复杂情况下实施救援,需要制定一个科学可行的方案.多无人机协同搜索路径规划方案的设计往往受无人机性能、既定飞行时间、搜索目标等因素的影响.针对多无人机协同搜索最优路径组合的求解,本文把深度优先搜索算法和生成树算法结合起来并对其进行改进,得到了一种新的路径搜索算法.算法首先对深度优先搜索的每一个节点都根据给定的数据赋予一定的权值;然后按指定步数、代价函数和目标函数进行路径节点的选择,得出所有符合要求的合理路径;最后根据指定路径组合数和无人机的架数输出权重最大即搜索概率最大的路径组合.通过仿真模拟实验,验证了算法的可行性与合理性,为以后救灾过程中多无人机协同搜索路径规划问题提供了新的思路.