一种无人机覆盖路径规划问题的算法 An Algorithm for Coverage Path Planning with Unmanned Aerial Vehicles

doi:10.12677/AAM.2019.88170

Advances in Applied Mathematics
Vol. 08 No. 08 ( 2019 ), Article ID: 31805 , 6 pages
10.12677/AAM.2019.88170

An Algorithm for Coverage Path Planning with Unmanned Aerial Vehicles

Xun Xu^*, Yujie Guan, Yajuan Huang, Ye Wu

●How to Cite this Article

School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha Hunan

Received: Aug. 1^st, 2019; accepted: Aug. 15^th, 2019; published: Aug. 22^nd, 2019

ABSTRACT

The application of Unmanned Aerial Vehicles in road monitoring of disaster emergency rescue system which enables rescue organizations to obtain road network conditions in time provides more accurate ground information and improves rescue efficiency. Monitoring road by unmanned aerial vehicles needs to path planning according to the characteristics of remote sensing imaging and time is an important index of disaster emergency rescue system design. In order to speed up the solution of track planning, a set coverage model is established considering the characteristics of road monitoring in disaster emergency rescue system. A three-stage algorithm is proposed to decouple the problem into two subproblems. Finally, a concrete example is given to verify the feasibility of the algorithm.

Keywords:Road Monitoring, Path Planning, Integer Programming, Location Set Covering Problem, Travelling Salesman Problem

一种无人机覆盖路径规划问题的算法

徐迅^*，管玉洁，黄雅娟，吴烨

长沙理工大学数学与统计学院，湖南长沙

收稿日期：2019年8月1日；录用日期：2019年8月15日；发布日期：2019年8月22日

摘要

无人机应用于灾害应急救援系统的道路监控，使得救援组织能及时获得道路网络状况，提供更高精度的地面信息，提升救援效率。无人机监控道路需要根据遥感成像的特点规划航迹，而时间是灾害应急救援系统设计的重要指标。为了加快航迹规划的求解速度，考虑灾害应急救援系统的道路监控问题的特点，建立了集合覆盖模型。提出将该问题解耦成两个子问题的三阶段算法，根据约束条件推导出可行域，缩短了算法的搜索时间。最后通过一个具体算例验证了算法的可行性。

关键词 :道路监控，航迹规划，整数规划，位置集合覆盖问题，旅行商问题

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

我国地域广阔，地理条件复杂，自然灾害时有发生。自然灾害对国民经济和人民安全造成的影响日益严重，自然灾害不但破坏建筑，造成道路损毁，还带来通信的中断，这使得救援困难，医疗物资不能及时到位，从而导致不必要的伤亡 [1] 。而虽然自然灾害是无法避免的，但通过一个全面和高效率的灾害管理系统，可以大大减轻其影响：时间是灾害管理成功的最重要因素 [2] ，而无人机(Unmanned Aerial Vehicle, UAV)不受地形限制，道路限制，具有低成本、低损耗、可重复使用且风险小等诸多优势 [3] ，可以在第一时间将食品，饮用水，医疗药品等救援物资送达指定区域，并且可以搭载数码设备，实施对地观测，为救援人员提供道路受损信息。

无人机的航迹规划是指在适当的时间内找到满足约束条件的一条可行最优的路径。但是由于路径规划是一个NP-Hard问题，当问题规模过大时，算法很难在短时间内找到最优的路径，所以在求解大规模航迹规划时，通常采用搜索算法，启发式算法，神经网络等方法 [4] [5] [6] 求得“尽可能好”的解。文献 [7] 以最小化无人机巡视环路的飞行时间为路径规划的目标，讨论了具有遥感能力的无人机的路径规划。文献 [8] 将巡检的路径规划问题制定为扩展的旅行商问题(Travelling salesman problem, TSP)。文献 [9] 提出了几种在搜救系统中无人机离散路径规划的方法。文献 [10] 以最小化航线数量为目标提出了新的算法。文献 [11] 提出了基于旋转卡尺的算法解决起降点在路径中的覆盖路径规划问题。文献 [12] 分析了现有文献中关于覆盖路径规划问题，还介绍了通常用于评估覆盖任务成功与否的性能指标。

目前关于二，三维航迹规划研究大多是研究点到点的航迹规划，即研究出发点与目标点间的最优航迹。而当灾害发生时，使用无人机对目标道路网络进行遥感成像，收集道路受损信息要求的是以航迹上的每个点为圆心，拍摄半径为半径的圆的集合覆盖整个道路区域。

2. 问题描述及模型分析

自然灾害发生后，道路被损坏的同时，通信线路也常常被破坏。我们需要n架续航能力为LE(Long-Endurance)的无人机完成对某一道路网络的监控覆盖，为救援人员提供道路状况信息。记道路网

络为区域 $G_{R o a d} = {(x_{R o a d}, y_{R o a d}, z_{R o a d}) \in G_{R o a d}}$ ，无人机的理想可视半径为r₀ (不考虑遮挡的情况下，实际可

视范围与无人机和地面的相对高度差 $Δ h$ 成正比，这里设在理想相对高度差 $Δ h_{0}$ 的可视半径为理想可视半径r₀)，每t秒拍摄一张照片(视频也可看作是照片的集合，例如帧率为60 fps的视频可是视作每1/60秒拍摄一张照片)，航迹为由方程 $F_{i} (x, y, z) = 0, i = 1, 2, \dots n$ 确定的空间曲线F_i。则第i架无人机沿着曲线F_i的

监控区域 $G_{F_{i}, M o n i t o r}$ 可表示为

$G_{F_{i}, M o n i t o r} = \cup_{j = 1}^{\infty} {(x, y, z) | {(x - x_{i, 0})}^{2} + {(y - y_{i, 0})}^{2} \leq {(\frac{z_{i, 0} - z_{r o a d}}{Δ h_{0}} r_{0})}^{2}, (x_{i, j}, y_{i, j}, z_{i, j}) \in F_{i}}$ .

则总的监控区域 $G_{M o n i t o r} = \cup_{j = 1}^{n} G_{F_{i}, M o n i t o r}$ ，

综上所述，本文所研究的航迹规划问题可描述为：

从所有满足 $\cup_{i = 1}^{n} G_{F_{i}, M o n i t o r} \supseteq G_{R o a d}$ 的F曲线中找到n条最优的空间曲线F_i。

目前一般的三维航迹规划问题解决的是点到点的路径优化，其搜索空间为

，

其中 $x_{\min}, x_{\max}, y_{\min}, y_{\max}, z_{\min}, z_{\max}$ 分别表示待监控道路区域的经度，纬度和海拔的最小值和最大值，是

满足拍摄分辨率的最大相对高度。

然而由 $G_{R o a d} \subseteq \cup_{i = 1}^{n} G_{F_{i}, M o n i t o r} \subseteq \cup_{k = 1}^{\infty} F_{k} = G$ 知对于 $\forall (x_{R o a d}, y_{R o a d}, z_{R o a d}) \in G_{R o a d}$ ，

有 $(x_{R o a d}, y_{R o a d}, z_{R o a d}) \in G$ ，

即 $\exists (x_{i, j}, y_{i, j}, z_{i, j}) \in F_{i}, s . t . {(x_{R o a d} - x_{i, j})}^{2} + {(y_{R o a d} - y_{i, j})}^{2} \leq {(\frac{z_{i, j} - z_{R o a d}}{Δ h_{0}} r_{0})}^{2}$

$G^{C} = G_{g e n e r a l} - G = \underset{(x_{R o a d}, y_{R o a d}, z_{R o a d}) \notin G_{R o a d}}{\cup} {(x, y, z) | {(x - x_{R o a d})}^{2} + {(y - y_{R o a d})}^{2} \leq {(\frac{z - z_{R o a d}}{Δ h_{0}} r_{0})}^{2}} \neq \emptyset$

所以，本文提出的初始可行域G比一般的搜索空间G_general要小。

当地形起伏不大时，无人机的相对高度变化不大，可视半径的变化可忽略不计，可视半径可看作常数，本文将三维航迹规划问题转化为二维航迹规划问题以简化计算量，从而快速获得一个较好的解。

3. 近似算法研究

为解决基于无人机的道路监控的二维航迹规划问题，我们采用栅格法进行空间的划分。将空间离散化为m_grid行n_grid列的矩形单元后，道路监控的二维航迹规划问题即变为寻找一系列相邻的单元，使得以这些单元的中心为圆心，可视半径为圆的半径的实心圆覆盖道路所在的单元。传统的算法解决点到点之间的航迹规划使用的方法是采用网格划分规划空间后，构造以当前节点为中心的九宫图作为算法的数据结构，共有8个相邻节点，航迹由相邻网格节点连接形成，并连接起始节点和目标节点。此算法的时间

复杂度大于 $C_{m_{g r i d} + n_{g r i d}}^{m_{g r i d}}$ 。可见此方法的计算量十分巨大。因此我们提出以下三阶段算法：

第一阶段：首先求出 $c i r c l e_\min$ 。当问题规模较小时，以道路所在单元中心为圆心画圆确定G，将 G₁ = G 所在的单元视为位置集合覆盖问题(Location Set Covering Problem, LSCP)中的候选拍摄点，建立整数规划模型。使用分支定界法求解得到目标函数的最小值。当问题规模较大时，使用二分法确定覆盖整

个道路网络所需实心圆的最少数目 $c i r c l e_\min$ ，的初始搜索区间 $[c i r c l e_l e f t, c i r c l e_r i g h t]$ ，其中 $c i r c l e_l e f t = \frac{S_{r o a d}}{π r^{2}}$ ， $c i r c l e_r i g h t = \frac{L_{r o a d}}{2 r}$ ， $S_{r o a d}$ 是道路面积， $L_{r o a d}$ 是道路长度，r是无人机的可视半径。

第二阶段：记“每一个含有 $c i r c l e_\min$ 个单元的集合”为一个方案，若由 $c i r c l e_\min$ 个单元中心为圆心的实心圆集合能覆盖整个道路网络。显然当无人机的航迹经过方案中 $c i r c l e_\min$ 个单元的中心时，无人机能完成道路监控任务。定义不同单元间中心的距离为两个单元间的边的权重，记录下此方案的总权重。比较不同方案的总权重，使用启发式算法寻找总权重较小的方案或者遍历得到总权重最小的方案；

第三阶段最后将总权重较小的方案中的 $c i r c l e_\min$ 个单元中心坐标看作旅行商问题的城市坐标，求解该旅行商问题。三阶段算法的时间复杂度主要在第一阶段求解整数规划模型，确定s种有个候选拍摄点的方案，

算法步骤：

STEP1：对区域G_general使用栅格法进行空间的划分，以道路所在单元中心为圆心画圆确定G，将 $G_{1} = G$ 所在的单元视为LSCP问题中的候选拍摄点，建立整数规划模型。使用分支定界法求解，并确定 circle_min。

STEP2：检查STEP1中求出的 $c i r c l e_\min$ 个拍摄点，若存在两点之间的距离小于 $Δ s = v_{U A V} t$ ，( $v_{U A V}$ 为无人机的速度， $Δ s$ 为无人机拍摄两张照片所需的最小飞行间距，在一般情况下，如果 $L_{i}, L_{i + 1}$ 两点间的距离小于 $Δ s$ ，可以降低无人机的速度，使得无人机从 $L_{i}$ 飞到时，相机能够拍照，但是降低速度无疑会使完成任务的时间变长，而灾害救援系统有时间限制)，则从 $G_{1}$ 删去处于更“稠密”区域的那点。返回到STEP1重新计算。如果所有点的距离均不小于 $Δ s$ ，则计算当前方案的总权重，执行STEP3。

STEP3：使用启发式算法求解出满足预定精度的方案或使用遍历算法得到最优方案。

STEP4：求解出访问STEP3中求出的最优方案中 $c i r c l e_\min$ 个单元的先后顺序。

4. 算例研究

如图1所示，本文将空间划分为16 × 16个正方形单元，单元的边长记为一个单位长度，黄色单元为道路。无人机可视半径设置为3个单位长度，即 $r = 3$ 。第一阶段求解得到 $c i r c l e_\min = 4$ 。第二，三阶段使用遍历算法求解，结果如图2，黄色与白色区域为初始可行域G。红色空心圆所在的第87号，第105号，第151号和第155号单元是总权重最小的方案的四个单元。由151号单元到87号单元再到105号单元最后到155号单元即为最终航迹。值得注意的是，本文并未预设无人机的起飞点，但这并不影响算法的有效性，为了符合生活实际，只需要在第三阶段的算法中添加一个起飞点的坐标，即可得到实际问题的解决方案。

Figure 1. Rasterized road network

图1. 栅格化后的道路网络

Figure 2. The solution result of path

图2. 航迹的求解结果

5. 结束语

时间是灾害应急救援系统中的重要因素，受灾地区的救援物资运送受到道路的影响，使用无人机遥感成像可以快速提供道路受损状况，并弥补卫星遥感成像精度不足的问题。本文将灾害应急救援系统中无人机道路监控航迹规划问题解耦为LSCP问题和TSP问题，给出了覆盖整个道路网络所需实心圆的数

目的大致范围 $[c i r c l e_l e f t, c i r c l e_r i g h t]$ 与一种能够减少模型求解时间的三阶段算法。

基金项目

长沙理工大学大学生创新训练计划立项项目(无人机救灾响应系统开发)。

文章引用

徐迅,管玉洁,黄雅娟,吴烨. 一种无人机覆盖路径规划问题的算法
An Algorithm for Coverage Path Planning with Unmanned Aerial Vehicles[J]. 应用数学进展, 2019, 08(08): 1457-1462. https://doi.org/10.12677/AAM.2019.88170

参考文献

1. 夏威. 交通道路灾害监测与应急响应系统的研究[J]. 通讯世界, 2015(17): 245-247.

2. Luo, C., Miao, W., Ullah, H., et al. (2019) Unmanned Aerial Vehicles for Disaster Management. In: Durrani, T.S., Wang, W. and Forbes, S.M., Eds., Geological Disaster Monitoring Based on Sensor Networks, Springer, Berlin, 83-107. https://doi.org/10.1007/978-981-13-0992-2_7

3. 金伟, 葛宏立, 杜华强, 等. 无人机遥感发展与应用概况[J]. 遥感信息, 2009(1): 88-92.

4. 巴海涛. 无人机航迹规划研究[D]: [硕士学位论文]. 西安: 西北工业大学, 2006.

5. 郑昌文, 严平, 丁明跃, 等. 飞行器航迹规划研究现状与趋势[J]. 宇航学报, 2007(6): 1441-1446.

6. 胡中华. 基于智能优化算法的无人机航迹规划若干关键技术研究[D]: [博士学位论文]. 南京: 南京航空航天大学, 2011.

7. Jang, D.S., Chae, H.J. and Choi, H.L. (2017) Optimal Control-Based UAV Path Planning with Dynamical-ly-Constrained TSP with Neighborhoods. 17th International Conference on Control, Automation and Systems, Ramada Plaza, 18-21 October 2017, 373-378. https://doi.org/10.23919/ICCAS.2017.8204468

8. Jeong, S., Simeone, O. and Kang, J. (2017) Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning. IEEE Transactions on Vehicular Technology, 67, 2049-2063. https://doi.org/10.1109/TVT.2017.2706308

9. San Juan, V., Santos, M. and Andújar, J.M. (2018) Intelligent UAV Map Generation and Discrete Path Planning for Search and Rescue Operations. Complexity, 2018, Article ID: 6879419. https://doi.org/10.1155/2018/6879419

10. Torres, M., Pelta, D.A., Verdegay, J.L., et al. (2016) Cov-erage Path Planning with Unmanned Aerial Vehicles for 3D Terrain Reconstruction. Expert Systems with Applications, 55, 441-451. https://doi.org/10.1016/j.eswa.2016.02.007

11. Gomez, J.I.V., Melchor, M.M. and Lozada, J.C.H. (2017) Optimal Coverage Path Planning Based on the Rotating Calipers Algorithm. International Conference on Mechatronics, Electronics and Automotive Engineering, Cuernavaca, 21-24 November 2017, 140-144. https://doi.org/10.1109/ICMEAE.2017.11

12. Cabreira, T., Brisolara, L. and Ferreira, P.R. (2019) Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones, 3, 4. https://doi.org/10.3390/drones3010004

NOTES

^*第一作者。

期刊菜单