无人机巡航问题的一点尝试

问题：

2017年8月8日，四川阿坝州九寨沟县发生7.0级地震，造成了不可挽回的人员伤亡和重大的财产损失。由于预测地震比较困难，及时高效的灾后救援是减少地震损失的重要措施。无人机作为一种新型运载工具，能够在救援行动中发挥重要作用。震区的高程数据，共有2913列，2775行。第一行第一列表示(0,0)点处的海拔高度值(单位：米)，相邻单元格之间的距离为38.2米，即第m行第n列单元格中的数据代表坐标(38.2(m-1), 38.2(n-1))处的高度值。震区存在7个重点区域。

无人机都假设平均飞行速度60千米/小时，最大续航时间为8小时，飞行时的转弯半径不小于100米，最大爬升(俯冲)角度为±15°，与其它障碍物(含地面)的安全飞行距离不小于50米，最大飞行高度为海拔5000米。所有无人机均按规划好的航路自主飞行，无须人工控制，完成任务后自动返回原基地。

  使用无人机携带视频采集装置巡查7个重点区域中心方圆10公里以内的灾情。假设无人机飞行高度恒为4200米，将在地面某点看无人机的仰角大于60°且视线不被山体阻隔视为该点被巡查。若所有无人机均从基地H(110,0)(单位：千米)处派出，且完成任务后再回到H，希望在4小时之内使区域S内海拔3000米以下的地方尽可能多地被巡查到，最少需要多少架无人机？覆盖率是多少？每架无人机的飞行路线应如何设计？在论文中画出相应的飞行路线图及巡查到的区域（不同的无人机的飞行路线图用不同的颜色表示）。

（本题地图数据见Excel表格）

  解答：

 0 基本符号说明

 1   问题分析

本题目从总体来说是对高程数据所代表地图的区间完全遍历问题，题目通过限定无人机的属性、设定探查范围等衍生出问题。

数据的合并处理。题目给出的数据集巨大，为了抽象化问题，对数据进行适当的处理是必要的。在高程数据集中相邻单元格之间的距离为38.2米，且有2775行、2913列，而无人机在空中某一位置所能探查的区域远大于此，因此考虑对高程数据集中的数据进行适当的合并。

数据在图中的表示。通过等高线图可以更好的理解数据集的特征，如图1所示为高程数据集地图的登高线表示:其中颜色越深的区域海拔高度越低，颜色越浅的区域海拔高度越高。由图1可知，数据集右侧地势较低，数据集左侧地势较高。此外，将震区7个重点区域方圆十公里内区域在登高线图中表示如图2所示，从图中可知，震区重点区域多位于海拔较低的右上方，此地区海拔在区间[1000，3000]的范围内。

图1 数据集等高线图

图2 震区重点区域图

4.1问题一分析

问题需对7个重点区域中心方圆10公里进行巡查，且无人机的飞行高度恒为4200米，所以首先需要分析7个重点区域的地形，并根据内部地形设计无人机在区域内部的飞行轨迹，在此基础上，再对无人机在区域间的飞行顺序进行设计，使得4小时内区域S内海拔3000米以下巡查覆盖率大，无人机的数量少。对于区域内部，分成两种情况进行讨论：第一种情况是区域内部不存在海拔高于4150米的山峰，在该种情况下，采用牛耕往复法对区域进行巡航；第二种情况是区域内部存在海拔高于4150米的山峰，需将无人机改变航向绕过障碍物。

 1   问题一模型建立与求解

1.1 无人机巡航最小半径的确定

当地面某点看无人机的仰角大于60°且视线不被山体阻隔视为该点被巡查，则无人机在空中巡视时，其对应的巡视区域为一个角为120°且边长无限的圆锥，如图5.1所示。无人机飞行海拔高度 ，需要巡视区域的最高海拔高度 ，考虑极限情况，当无人机巡视区域的海拔均为h时，无人机巡视面积取得最小值。

图5.1 无人机巡视视野图

由题目可知， H_1=4200m， h_1=3000m，由勾股定理可知，无人机在空中某点时巡查区域半径r_1的最小值如式(1)所示:

　　r_1=(H_1-h_1)/√(3 )=400√3 m                             公式(1)

　　则无人机在空中某点时巡查区域直径d_1的最小值如式(2)所示：

　　d_1=2r_1=800√3 m                               公式(2)

1.2 高程数据集的合并数据处理

　　无人机在空中某点巡查的半径远大于高程数据集的间隔距离，则当无人机从数据集中某点dot正上方飞过时，无人机不仅探查了当前点，也探查了以dot为圆心，以r_1为半径的圆C_1的范围内的高程数据点。由此，我们可以将C_1范围内的点合并为dot，只要无人飞过dot，那么C_1范围内的高程数据就都被无人机探查过了。进一步考虑，无人机在空中不断移动位置，如图5.2所示，若无人机依次飞过A、B、C、D，那么无人机的探查范围为黄色区域，相较于矩形区域近损失了开始点与结尾点附近的区域，可以忽略不计，则可以将以dot为中心点，直径为〖2r〗_1的正方形区域内的数据合并。

图5.2 无人机探查范围示意图

由式(1)可知，d_1=800√3 m，高程数据集中相邻单元格之间的距离D=38.2m，则被合并正方形的一条边上有M个点，计算结果向下取整，则有公式(3)：

　　M=d_1/D≈36                                                             公式(3)

　　则合并后两个相邻单元格之间的距离D_1如公式(4)所示：

　　D_1=38.2*M=1375.2m                               公式(4)

　　由题意可知，beforeCol=2913,高程数据集合并后的列数afterCol其结果向上取整，如式(5)所示：

　　           afterCol=beforeCol/M≈81                                  公式(5)

　　由题意可知，beforeRow=2775,高程数据集合并后的行数beforeRow其结果向上取整，如式(6)所示：

　　           afterRow=beforeRow/M≈79                                公式(6)

其中，被合并正方形中数据表示为：

           CubeSet = [ N10,N11,N12……N1M,

                   N20,N21,N22……N2M,

                        ……

                      NM0,NM1,NM2……NMM  ]                               公式(7)

　　由公式(4)可知合并后点dot的数值dotValue设置为CubeSet的平均值：

dotValue=∑_(i=1)^M?∑_(j=1)^M?N_ij                          公式(8)

高程数据集合并之后有79行，81列。第一行第一列表示(0,0)点处的海拔高度值(单位：米)，相邻单元格之间的距离为38.2米，即第m行第n列单元格中的数据代表坐标(38.2(m-1), 38.2(n-1))处的高度值。

　　对7个震源点进行坐标变换，结果如表1所示，以A为例，其X坐标表示

表1 震源坐标变换结果

    对起飞点P(110，0）进行坐标变换后，得到P(81,0)。

使用以上方法对数据集进行合并，使用合并后的数据集作图，绘制出7个震区重点区域及数据集中大于H_1的数据，该图中蓝色区域即为题中要求无人机需要巡查的全部范围，黑色区域为数据集中大于H_1的数据，如图5.3所示。

图5.3 无人机巡航区域示意图

1.3 震区重点区域内部巡航方式

由上文可知，震区重点区域是半径为10km的圆。则在合并后的数据集中，无人机巡航震区重点区域就是遍历以震源为圆心，以10km为半径的圆中所包含的数据点，如图5.4所示。对于单个连续区域的完全遍历问题有两种解决方式：(1)牛耕往复法,即从震区圆形区域上一点出发，沿直径方向折返遍历，如图5.5中黄色线所示；(2)内外螺旋法，即从震区圆形区域上一点出发，绕圆心向内遍历。其中，使用牛耕往复法巡逻一个震区重点区所走过的路程小于内外螺旋法，所以这里我们采用牛耕往复法巡航震区重点区域内部。

图5.4 震区重点区域数据点图                 图5.5 牛耕往复法遍历震区重点区域

1.4 震区重点区域外部巡航方式

无人机在巡查完毕一个震区圆形区域后，如果还有充足的时间，那么可以飞向下一个震区圆形区域。同时需要注意，由于我们在震区重点区域内部巡航使用牛耕往复法，该遍历方法需要水平或垂直的遍历震区圆形区域才能够保证算法效率。因此在外部巡航时，无人机总是从震区圆形区域与坐标线相切的点进出震区圆形区域，如图5.6中红色点所示，该红色点称为外部巡航进出点。并且无人机的外部巡航进点与出点欧式距离为 。

图5.6外部巡航方式进出震区重点区域的位置

若无人机飞离当前震区圆形区域且时间充足，则下一个震区圆形区域的选择使用贪心法求解，求解步骤为：

    Step0：创建包含7个震区重点区域的数据集S

Step1：求取起飞地点与S中数据的4个外部巡航进出点的欧式距离，取与起飞点距离最短的数据data，并从S移除数据data

Step2：求取data与S中数据的4个外部巡航进入点的欧式距离，取与起飞点距离最短的数据更新为data，并从S移除数据data。若此时S不为空，重复Step2。

算法执行后的结果如表2所示，表中入点，出点的坐标为合并数据后该点在高程数据集中的位置表示。在图中表示为图5.7，沿红色箭头方向即为巡航完毕当前震区圆形区域且有时间富裕的无人机的去向。即若F震区的无人机遍历本震区后有充足时间，那么飞往G；若G震区的无人机遍历本震区后有充足时间，那么飞往D；若D震区的无人机遍历本震区后有充足时间，那么飞往E；若E震区的无人机遍历本震区后有充足时间，那么飞往A；若A震区的无人机遍历本震区后有充足时间，那么飞往C；若C震区的无人机遍历本震区后有充足时间，那么飞往B；

表2 震区重点区域巡航出入点

图5.7 贪心法选择飞往下一个震区圆形区域

1.5 结果

根据5.3及5.4的内容可画出无人机机群在七个震区圆形区域整体的轨迹图，如图5.8所示。无人机机群在不受山体阻隔时的整体航行路线是:在震区圆形区域内采用牛耕往复法巡逻，在震区圆形区域间采用贪心法选择下一个区域。由于题目希望在4小时内对震区3000m以下区域进行巡逻，则每架无人机只有4小时时间飞达震区巡视并返回，那么无人机的有效巡视路径长度如公式（9）所示，其中v是无人机的飞行速度，v=60km/h，X为飞机巡航的震区的中心位置，||X-P||   为震区X到起飞点P的欧式距离，D_1为合并后两个单元格之间的长度。

         Sp=v*4-D_1* ||X-P||                                                             公式(9)

巡航每个震区圆形区域所要走过的路径长度S可近似表示为公式（10）：

          S=〖（M-1）〗^2   *D_1                                          公式(10)

图 5.8 无人机机群巡航轨迹图

则无人机组的飞行轨迹可以视为：起飞点到震区，震区巡视，震区返航三个部分，其中震区巡视路段的轨迹构成图5.8中形状，起飞点到震区，震区返航两部分的路径长度可以近似表示为起飞点到震区中心的位移，使用迭代算法计算每架飞机的路径，计算可得所需最少无人机数为14架，每架飞机的飞行路径如图5.9所示,具体见附录：

  图5.9 无人机飞行路线图

由于山体阻隔，部分震区重点区域未能覆盖，由图1可知，覆盖率 如公式(11)所示，其中S为一个震区重点区域的面积：

           P_S=(7S-1/2S-1/2S)/7S≈0.867=86.7%                     公式(11)