基于最小圆覆盖法的无人机救灾航巡策略研究

Drone Patrol Strategy Based on Minimum Circle Coverage Method

摘要: 本文针对灾难应急响应系统问题，以波多黎各城市2017年发生的严重飓风灾难为例，在满足无人机种类组合最佳、系统响应时间最短、无人机运输救生包最大量的前提下，建立了动态多目标规划模型，得到最优无人机舰队配置。基于最小圆覆盖法，将波多黎各区域离散化，确定三个货物集装箱的最佳安置位置，即无人机舰队从三个集装箱位置出发运输货物以及巡航的路径最短。我们将波多黎各地图主要道路化曲为直，得到波多黎各主要路迹的线路图，基于欧拉回路和Dijkstra算法，得到最优无人机巡航路线，其侦察范围覆盖率达90%以上，遍历路径距离最短。

Abstract: For the disaster emergency response system problem, we take the severe hurricane disaster in the city of Puerto Rico in 2017 as an example, under the premise of satisfying the best combination of drone types, the shortest system response time, and the maximum amount of drone transport life-saving packages, the dynamic multi-objective programming model is used to obtain the optimal drone fleet configuration. Based on the minimum circle coverage method, the Puerto Rico region is discretized to determine the optimal placement position of the three cargo containers, that is, the drone fleet transports goods from three container locations and the cruising path is the shortest. We have transformed the main roads of Puerto Rico into straight lines, and obtained the route map of the main roads in Puerto Rico. Based on the Euler loop and the Dijkstra algorithm, we obtained the optimal UAV cruise route with a coverage range of over 90% and the traversing path distance is the shortest.

1. 引言

飓风的风暴潮和海浪作用对建筑、房屋和道路会造成极大的破坏，尤其是靠近海岸的地区，飓风造成大部分输电线路和蜂窝通信网络被严重损坏，导致大部分区域断电数月。另外，洪水的泛滥会使公路和道路阻塞损坏，许多地区会被孤立，无法正常得到医疗救生。以2017年史上最严重的飓风为例，飓风袭击了美国领土波多黎各使该岛人员伤亡惨重，现为提高救灾响应能力，试图设计可移动式灾难响应系统，通过无人机来完成医疗供应交付和高分辨率的视频侦察。计划给出多个无人机类型、不同医疗套餐等设备，现需根据波多黎各2017年的具体情况来设计一个灾难响应系统。应急系统是以无人机为主要配置来进行医疗供应交付和高分辨率的视频侦察，需得到灾难响应系统的最优的选址以及无人机最优航巡策略。因此，我们将从以下几方面进行考虑，以最优化理论为基础，研究多无人机协同巡查、救援以及侦察问题。建立动态多目标规划模型，考虑在无人机数量最少、无人机种类组合最佳、系统响应时间最短、巡航覆盖率最大等目标的前提下，得到最优无人机舰队配置。选择最优无人机舰队，得到无人机的最优巡航最优方案；从而进一步得到将整个应急响应系统运输到波多黎各的方案。

2. 动态多目标规划模型

在有目标和无目标下的搜救航迹规划需要细致划分，不同环境模型和约束要区别对待，系统将根据救灾实际情况，构建以下航迹规划目标 [1] ，在对任务目标的基础上对航线进行重要性排序，再进行航迹规划的策略进行规划，并规划处大致的救灾航迹。航迹规划目标主要有以下几个，一、在无人机数量最少，二、无人机种类组合最佳，三、系统响应时间最短，四、巡航覆盖率最大的前提下，得到最优无人机舰队配置。

2.1. 动态多目标规划模型–区域划分

满足医疗套餐和无人机配置要求的前提下，三个货物集装箱到各自区域最远点的距离最小，即货运无人机和巡航无人机从此集装箱到目的地的总距离最小。在有目标和无目标下的搜救航迹规划需要细致划分，不同环境模型和约束要区别对待，系统将根据救灾实际情况，构建航迹规划目标，在对任务目标的基础上对航线进行重要性排序，再进行航迹规划的策略进行规划，并规划出大致的救灾航迹。

2.2. 约束条件

1) 周期短

多机协同搜救的无人机分为两部分，第一部分为送货的无人机，使得全部满足需求且最后一架无人机到达交付位置的时间最短，第二部分为只执行侦察的无人机，在最短的时间之内侦察到受灾地区和交通公路网的损坏情况，即完成搜救任务的时间最短，两部分均完成为一个周期。

$\min T$

2) 无人机数量少

在节约成本的前提下，对进行救灾的无人机数量进行确定，救援机数量应尽量合理。

$\min N_H$

3) 运输医疗包总量多

由于所需医疗保运输总量有一个上限，所以在满足需求的情况下，提供尽可能多的医疗包。

$\max N_{Package}$

4) 时间短

在灾情发生之后，医疗中心的受灾人员将持续激增一段时间，救援物资的紧缺要求第一时间送达所需医疗包。

$\min t$

综上所述，结合规划目标和约束条件，可建立航迹规划的数学模型如下式所示：

$G=\{\begin{array}{l}\min :t,T,N_H\\ \max :P_f,N_{Package}\end{array}$ $\text{s}\text{.t}\text{.}\{\begin{array}{l}T\le T_{\min }\\ t\le t_{\max }\\ 1\le N_H\le N_{H_{\min }}\\ P_{\min }\le P_f\le 1\\ N_{Packag{e}_{\min }}\le N_{Package}\le N_H\cdot N_{PP}\end{array}$

2.3. 实例分析

就目前的应用情况来看，无人机主要应用于两种场景，情况一：侦察目标个数和位置都已知；情况二：目标个数及位置均未知，受灾情况不明。在不同的搜救任务情况下，对上述四个航迹规划目标1)、2)、3)、4)的重要性程度进行排序，如表1所示。

Table 1. Planning goal importance ranking table

表1. 规划目标重要性排序表

在实际案例中，在航空侦察目标不定及交付位置已知的大面积区域覆盖侦察情境下，搜索150组数据 [2] 模拟了波多黎各的三维地势图，见图1，发现其平均海拔为900km，于是无人机飞行高度的假设合理，模拟无人机飞行侦察方式 [3] 见图2，此时扫描半径为 $S=\text{π}{\left(h\tan \alpha \right)}^2$ 。

符合情况一的任务要求，以最短时间送达救灾医疗用品为目标确定了三个集装箱的第一次放置的位置，我们采取的策略方式是先进行区域划分再指派；区域划分时，我们考虑主要城市居住人口密集、交通运输路线复杂度，于是选择了阿瓜迪亚、卡瓜斯、乌马考等19个城市和5个交付位置作为主要侦察位置，基于任务均衡率为最大为目的求解。

Figure 1. Simulates the three-dimensional map of Puerto Rico

图1. 模拟波多黎各的三维地势图

Figure 2. Simulated drone reconnaissance map

图2. 无人机模拟侦察图

2.4. 求解方法

先根据灾区的分布特点将灾区大体划分在三个区域之内，并使三架侦察机分别对这三个区域进行侦察，求取各自的最短时间。然后对任务不均衡区域之中的点做适当调整，划分子区域，要达到比较均衡，应使每架飞机的巡航时间基本相同，由于侦察点的分布较均匀，可以将侦察目标的地理位置图分成面积基本相同的三部分。如过点 $\left(-66.52,17.9\right)$ 以斜率 $k_1=-2.8$ 作一条斜线，过点 $\left(-66.27,17.9\right)$ 以斜率 $k_2=6.7$ 作一条斜线，把基地所在的地区划分成左，中，右三部分。

对每个子图分别运用禁忌搜索算法求得其最短侦察路线，和最短侦察路径 ${\phi }_i$ ，和最短侦察时间 $t\left({\phi }_i\right)\left(i=1,2,3\right)$ 。

均衡任务，定义均衡率Equilibrium task, define equalization rate

$\eta =\frac{\min \left\{t\left({\phi }_1\right),t\left({\phi }_2\right),t\left({\phi }_3\right)\right\}}{\max \left\{t\left({\phi }_1\right),t\left({\phi }_2\right),t\left({\phi }_3\right)\right\}}\times 100\%$

若 $\eta$ 接近于1，则上面划分的任务就可以接受。否则的话，根据大小用局部搜索算法，调整 $k_1,k_2$ 的斜率，从而调整各分区内点的个数，直至任务达到均衡。最后计算结果如下：

两直线的斜率分别为： $k_1=-2.5,k_2=4.8$ ，均衡率 $\eta =\frac{169.3}{195}\times 100\%\approx 86.82\%$ 。

A，B，C三个区域分别代表左，中，右三部分，如下图3所示：

Figure 3. Division of the area

图3. 区域划分图

3. 基于最小圆覆盖法的集装箱定位

基于前面区域划分进行多目标规划，将波多黎各区域离散化后 [4] ，要确定货物集装箱的最佳安置位置，即使无人机舰队从三个集装箱位置出发运输货物以及巡航的路径最短。则此问题转化为已知平面上有限个点，求一个半径最小的圆能够覆盖平面上所有的有限个点，即最小圆覆盖问题 [5] 。

3.1. 算法介绍

给定有限点集S，包含所有点S的最小圆B满足： $B=B\left(c,r\right):=\left\{x:\Vert x-c\Vert \le r\right\}$ 。

1) 输入n个数据点，在点集n中任取3点A，B，C；

2) 作一个包含三点的最小圆C1；

3) 在点集中找出距离C1最远的点D，若点D在圆C1的圆内或圆周上，则该圆即为所求的最小圆，算法结束，否则继续下一步；

4) 在A，B，C，D中选3个点，求解使包含这四个点的圆最小，所选取的三点成为新的A，B，C三点，返回执行第二步。具体算法操作步骤见图4。

Figure 4. Block diagram of the minimum circle coverage algorithm

图4. 最小圆覆盖法算法流程图

3.2. 实例分析

将地球看作规则球体进行计算，地球的平均半径作为其半径R，设地球上某点的经度为A，纬度为B，则这点的空间坐标是 $x=\cos B\ast \cos A,y=\cos B\ast \sin A,z=\sin B$ 。设地球上两点的空间坐标分别为 $\left(x_1,y_1,z_1\right),\left(x_2,y_2,z_2\right)$ ，则它们的夹角为 $C=\text{arcos}\left(x_1\ast x_2+y_1\ast y_2+z_1\ast z_2\right)$ ，则两地距离 $d=\frac{C}{180\ast \text{π}\ast R}$ ，其中R为地球平均半径6371 km。

这样，我们将波多黎各划分成的三个区域分别记为A，B，C，每个区域的主要城市分别记为 $A_i,B_j,C_k$ ， $i,j,k=1,2,3,\cdots$ ，根据各点的经纬度数据，最终编程得到三个区域各点之间的距离。

3.3. 结果求解

根据以上计算得到的各区域各点间的距离，选取最短路径，根据最小圆覆盖原理，编程得到三个货物集装箱的最佳安置位置，见图5。

Figure 5. Minimum circle coverage graph

图5. 最小圆覆盖图

在区域A集装箱1应安置在马里考(Maricao)，与此区域的最远距离为39.94 km；在区域B集装箱2应安置在巴兰基塔斯(Barranqultas)，与此区域的最远距离为27.67 km；在区域C集装箱3应安置在拉斯彼德拉斯(Las Piedras)，与此区域的最远距离为31.96 km。具体位置分布见图6。

Figure 6. The location of cargo container placement

图6. 货物集装箱安置位置图

4. 基于欧拉回路和Dijkstra算法的最佳巡航路线

为使无人机舰队进行高分辨率的视频侦察来评估主要公路和道路，根据所给波多黎各的地图，采用化曲为直的思想，将原地图进行简化，得到波多黎各主要路迹的线路图。无人机舰队巡航的最佳线路，即满足无人机架数最少、巡航覆盖率最大、遍历路径最短的巡航路径。这样，我们将求巡航最佳飞行计划问题转化为：从某个点出发，经过每条边至少一次，然后回到原点，求可达到要求最短的总路径。

4.1. 算法介绍

欧拉回路：如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。如果一个回路是欧拉路径，则称为欧拉回路。本题中，我们在将地图简化后得到的路径分布图的基础上增加一些边，使得这个图是欧拉回路，即每个点的度都是偶数。由于点很少，我们可以用状态压缩，相应位置1表示这个点度数是偶数，0表示这个点的度数是奇数。对于一个状态，加一条边则两个点奇偶性变了，相应位置取反，到达下一给状态。最终求dis[11111]时的边的总长度，从而得到最短的飞行距离；

Dijkstra算法：利用不断松弛得到最小的加边状况，并记录下算法中所添加的边。将初始边和添加的边建图，遍历一遍欧拉回路，得到飞机的最短巡视路线。具体如下：

设 $G=\left(V,E\right)$ 是一个带权有向图，顶点集合记为V，已求出最短路径的顶点集合用S表示，其余未确定最短路径的顶点集合用U表示

1) 初始时，S只包含源点，即 $S=\left\{v\right\}$ ，v的距离为0。U包含除v外的其他顶点，即：U = {其余顶点}，若v与U中顶点u有边，则 $\langle u,v\rangle$ 正常有权值，若u不是v的出边邻接点，则 $\langle u,v\rangle$ 权值为∞。

2) 从U中选取一个距离v最小的顶点k，把k，加入S中(该选定的距离就是v到k的最短路径长度)。

3) 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

4) 重复步骤2)和3)直到所有顶点都包含在S中。

4.2. 结果求解

1) 飞行路径以及最短距离

采用以上欧拉回路思想和Dijkstra算法，将求波多黎各无人机最佳飞行计划问题巧妙的转化为了由边缩点的求最短路径问题，编程得到最短路径遍历回路，即确定了无人机巡航最优路线，见图7。

Figure 7. Drone empowerment flight route diagram

图7. 无人机赋权飞行线路图

结合已得到的各区域各点间的距离，从而得到无人机遍历路径的最短距离：

区域A的无人机飞行最短距离：316.8 km；

区域B的无人机飞行最短距离：235.752 km；

区域C的无人机飞行最短距离：215.004 km。

2) 无人机舰队视频侦察覆盖率

我们定义无人机舰队视频侦察覆盖率为遍历过的路径距离总和与所有路径距离总和之比，并记覆盖率为 $\lambda$ ，记遍历过得路径距离总和为m，记所有路径距离总和为n，则：

$\lambda =\frac{m}{n}$ ， $m=564.1371$ ， $n=625.2681$ ，

则： $\lambda =\frac{m}{n}=\frac{564.1371}{625.2681}\approx 90.22\%$ ，即无人机舰队视频侦察覆盖率为90.22%。

综上所述，我们制定的无人机飞行计划，使无人机视频侦察效率大大提高到90.22%，并且最大可能节约无人机资源，使巡航线路最短。