多无人机(Unmanned Aerial Vehicle，UAV)广域协同搜索是无人机协同的重要任务之一，是指2架或2架以上无人机相互配合、协作执行搜索任务的方式[1-2]。根据无人机搜索任务的不同，多机协同的模式也各不相同，在对森林、水域、战场状况进行监测侦察时，则需要对目标区域进行协同搜索的全覆盖[3-4]。
多无人机协同搜索的本质也是一种路径规划问题，其重点在于数学建模及框架求解、环境表示和路径规划算法等[5]。而在路径规划的过程中，实现在搜索环境中平衡各无人机的搜索能力[6]，并利用合理算法对无人机的搜索区域与搜索路径进行划分和规划，以实现对目标区域的快速覆盖搜索，将大大降低搜索的时间成本[6-7]。
围绕快速、高效规划路径的问题，研究者们开展了大量的工作。Li等[8]根据组无人机的初始位置和耐久性划分搜索区域，并基于并行搜索策略的全局最优路径规划，用最少圈数的单个无人机找到整个区域的轨迹和持续时间；Chen等[9]研究了动态环境下多无人机协同区域侦察的问题，能够在保证实时性的前提下获得最优效率；Mansouri等[10]所提议方案的主要新颖性源于建立一个理论框架，该框架能够提供完成基础设施全覆盖的路径，无需进一步简化。
多机协同搜索的搜索区域划分方面，凸多边形易于实现凸分解和规划搜索路径；而对于非凸多边形，凹口的存在使得往复式的路径规划无法直接应用。Li等[11]通过调整凹口附近的路径方向来实现单机的全区域路径覆盖，但单机搜索效率低，连续的飞行轨迹不可避免地会产生不必要的转移路径。Vinh等[12]通过移除凹点将非凸多边形近似为凸多边形进行区域划分，但该方法仅适用于凹口较小或对飞行任务无额外影响的情况。Nielsen等[13]取用凹口处边的延长线来分解多边形实现区域划分，却不能契合无人机搜索能力所对应的面积需求。Hert和Lumelsky[14]的锚定区域划分方法能够较准确地划分出符合无人机搜索能力的子区域，但对非凸多边形划分的子区域仍是凹多边形，不利于规划无人机群搜索路径。能按各无人机能力均衡划分子区域、便于搜索路径规划且能考虑无人机来向的协同搜索区域划分方法还有待进一步研究。
本文对凸多边形区域按来向均衡划分的方法进行划分，以便于无人机不做大的机动直接进入搜索区域；对非凸多边形区域采用凹点处凸分解的方法进行划分，在满足面积均衡的同时能使分区便于路径规划。将多机协同搜索问题转化为子区域上的单机搜索问题，从而建立区域划分和路径规划的整体调用框架，能够对目标区域进行快速划分并生成飞行路线，满足多机协同搜索应用的要求。
1 考虑无人机来向的搜索区域划分方法 1.1 凸区域划分方法实际任务中无人机初始时通常不在目标区域的边界上，考虑无人机群从区域外某一方向飞来对目标区域进行覆盖搜索的情况，将该区域按无人机来向划分为数个子区域，使无人机可以直接进入分区进行覆盖搜索，这样一来无人机的航程和油耗都将有所节省。
如图 1所示，目标搜索区域可以简化为一个任意多边形P，按无人机来向将区域划分为n个等面积的分区(n为无人机数)，算法1是划分出一个子区域的基本步骤。首先，输入该凸多边形的顶点信息W(P)=wk (k=1, 2, …, m，其中m为顶点数)并按逆时针(CCW)顺序排序，沿无人机来向作一组平行线，斜率为K(UAV)=ki (i=1, 2, …, n-1)，从中取与多边形仅有一个交点(或与某条边重合)的2条平行线l1和l2作为扫描线的边界。l1和l2的距离是该方向上的最大宽度dmax，沿最大宽度方向从右到左可取n-1个位点S(P)=S1, S2, …, Sn－1将dmax做n等分，过位点可作分割线，Li=(Ls, Le) (i=1, 2, …, n-1)，Li与P交于Ls、Le。当Li右侧的多边形面积大于所需面积，即Area(PLir)>AreaRequired(S(PLir))时，Li向右移动，直到面积相等，即Area(PLir)=AreaRequired(S(PLir))，划分完成；当Li右侧的多边形面积小于所需面积，即Area(PLir) < AreaRequired(S(PLir))时，Li向左移动，直到面积相等，划分完成。依次类推直到Ln-1也完成，其中AreaRequired(S(PLir))=Area(P)/n。
|
| 图 1 考虑无人机群来向时的凸多边形区域划分 Fig. 1 Convex polygon division considering UAVs' arrival |
| 算法1 凸多边形划分算法 Algorithm 1 Procedure of dividing a convex polygon |
| Input 凸多边形P, W (P)=wk(k=1, 2, …, m), S (P)=Si(i=1, 2, …, n-1); Procedure 区域划分 1.逆时针排序W(P), AreaRequired(S (PLir))=Area(P)/n; l1, l2←扫描线边界, dmax←l1和l2间距离 2.初始化L1=(Ls, Le), 其中 Ls={(x, y)|y-S1y=k1(x-S1x), (wj, wj+1)}(j=1, 2, …, m); Le={(x, y)|y-S1y=k1(x-S1x), (wk, wk+1)}(k=1, 2, …, m, j≠k) 3.if Area(PL1r)>AreaRequired(S (PLir)) L1沿dmax向右移动, 直到Area(PL1r)=AreaRequired(S (PLir)) else if Area(PL1r) < AreaRequired(S (PLir)) L1 沿dmax向左移动, 直到Area(PL1r)= AreaRequired(S (PLir)) end end Output PL1r=P-PL1r; |
1.1节中的方法可以很好地实现凸多边形的区域划分，但实际无人机搜索的环境多为非凸的，仅进行凸多边形的划分尤显不足，还需进行非凸多边形的划分。
当无人机从某方向飞来时，若采用1.1节中所述方法，因为凹口的存在难免会将非凸多边形划分得支离破碎。而Hert和Lumelsky[14]提出的锚定区域划分方法虽然可以实现既定要求的区域面积划分，但是划分出的小区域有可能还是非凸多边形，这会给覆盖路径的规划带来极大的困难。因此，考虑在区域凹口处进行凸分解，无人机所对应的子区域表示为一个或几个凸多边形区域的组合。
如图 2所示，当边界1右侧的分区面积小于所需面积，即Area(CPL1r) < AreaRequired(CPLir)时，凹口处的分割线在凹口的边界延长线范围内扫描划分直到Area(CPL1r)=AreaRequired(CPLir)；若分割线1与边界2重合依然不满足所需面积，则将分割线平行于边界1或边界2向多边形左侧移动，Area(CP1－1)+Area(CP1－2)=AreaRequired(CP)时划分完成，此时分区CP由2个凸多边形CP1-1和CP1-2组成，{CP}←{CP1－1}+{CP1－2}。当边界1右侧的分区CP的面积大于所需面积，即Area(CPL1r)>AreaRequired(CPLir)时，分割线以凹点为轴，在CP1-1内逆时针扫描划分，直到获得所需面积。满足面积需求的区域输出为分区CP1，其余部分作为一个整体继续划分，直到划分出n-1个分区。图 3为非凸多边形区域划分的流程图。
|
| 图 2 凹口处凸分解示意 Fig. 2 Convex decomposition at concave corner |
|
| 图 3 非凸多边形区域划分过程 Fig. 3 Division process of non-convex polygon area |
凹口处的分区虽无法像凸多边形的子区域一样可使无人机按来向直接进入搜索，但也可以从路径规划的角度出发，根据已生成的分区路径，选取距离无人机最近的路径端点作为位点，即无人机路径起点，S(P)=S1, S2, …, Sn，以尽可能缩减无人机到达分区的路径长度。
2 覆盖搜索路径规划 2.1 无人机区域覆盖搜索方法“Z”型路径是覆盖搜索最常用的路径之一，采用“Z”型路径来回扫描不仅能使其轨迹充满整个搜索区域，还能有效地避免或减少无人机运行轨迹的重复。无人机转弯时存在最小转弯半径的限制，需采用Dubins[15]路径辅助转弯。因无人机转弯时消耗的能量远多于无人机直飞时的能量消耗[16]。因此，实现最优路径需要找出目标区域的最大方向，即主轴方向[17]，使航路转弯的次数尽可能的少[18]。可以按照求惯性主轴的方法[17]，来得出区域的主轴方向，但其过程较复杂，取特殊情况，定义多边形的长边为其主轴所在的方向。图 4为“Z”型路径的2种覆盖方式对比图，长边为其主轴所在方向，其转弯次数明显少于以短边为主轴的转弯数。
|
| 图 4 2种覆盖方式对比 Fig. 4 Comparison of two coverage methods |
无人机飞过所在区域上空时，2条中心线轨迹间会形成有一定宽度d的覆盖带[19]，当2条覆盖带中心线的间距大于无人机的最小转弯半径的2倍，即d>2Rmin时，无人机可通过圆弧转弯移至下一个覆盖带。但当d < 2Rmin时，需要无人机做适当机动来完成转移，图 5为几种典型的Dubins路径转弯方式。
|
| 图 5 d < 2Rmin时的几种Dubins转弯方式 Fig. 5 Several Dubins turning methods when d < 2Rmin |
几何分析可以轻易求出这4种路径方式的路径长度，如果单纯地从路径长度的角度选择的话，方式4最优。但方式2相较于方式4来说，少转一次弯，并且轨迹中有一段直线，这就使得方式2的机动难度大大降低，所以方式4与方式2相比，并不占有绝对优势，这需要结合实际情况进行综合考量。此处采用方式2的转移方式。
对方式2的Dubins路径进行求解，代入起始和终止位姿点的位置以及航向信息[20]，即可求得起始圆和终点圆的圆心，得到该圆弧路径。
| $ x_{{\rm{cs}}} = x _{\rm{s}} - \frac { 1 } { k _ { _{\rm{s}} } } \operatorname { cos } ( \phi _ { _{\rm{s}} } \pm \pi / 2 ) $ | （1） |
| $ y_{{\rm{cs}}} = y _{\rm{s}} - \frac { 1 } { k _ { _{\rm{s}} } } \operatorname { sin } ( \phi _ { _{\rm{s}} } \pm \pi / 2 ) $ | （2） |
| $ x_{{\rm{cf}}} = x _{\rm{f}} - \frac { 1 } { k _ { _{\rm{f}} } } \operatorname { cos } ( \phi _ { _{\rm{f}} } \pm \pi / 2 ) $ | （3） |
| $ y_{{\rm{cf}}} = {y_{\rm{f}}} - \frac { 1 } { k _ { _{\rm{f}} } } \operatorname { sin } ( \phi _ { _{\rm{f}} } \pm \pi / 2 ) $ | （4） |
式中:1/ks和1/kf分别为起始圆Cs和终点圆Cf的半径；ϕs和ϕf分别为起始点和终止点的倾斜角，为了方便计算与表达，在这里规定其取值范围为[0, 2π]。通过式(1)~式(4)，寻找起始圆Cs的圆心Os(xcs, ycs)，和终点圆Cf的圆心Of(xcf, ycf)。
图 6为d < 2Rmin时方式2的4种情况，其中r为无人机的转弯半径，a=d，取直线飞行方向为正方向来进行讨论，2位姿点间的距离正好满足:
|
| 图 6 d < 2Rmin时方式2的4种情况 Fig. 6 Four cases of mode 2 when d < 2Rmin |
| $ \left| {{x_{\rm{s}}} - {x_{\rm{f}}}} \right| = \sqrt {4{r^2} - {a^2}} $ | （5） |
一般情况下，2个位姿点的距离并不能恰好满足式(5)，但是可以通过移动起始点或终止点的位置来使得2个位姿点的位置满足式(5)[5]。
2.2 搜索路径模型在二维区域中用P(x, y, ψ, Δψ)来表示无人机在某一路径点的位姿信息，其中(x, y)表示无人机所在的位置，(ψ, Δψ)表示无人机的航向角和无人机飞向下一路径点所需要改变的航向角[21]。无人机经路径r(q)由起始点Ps飞往结束点Pf，可表示为
| $ {{P}_{\text{s}}}({{x}_{\text{s}}},{{y}_{\text{s}}},{{\psi }_{\text{s}}},\Delta {{\psi }_{\text{s}}})\xrightarrow{r(q)}{{P}_{\text{f}}}({{x}_{\text{f}}},{{y}_{\text{f}}},{{\psi }_{\text{f}}},\Delta {{\psi }_{\text{f}}}) $ | （6） |
图 7是对分区执行覆盖搜索任务时路径生成的基本步骤。首先，按逆时针顺序生成凸多边形的顶点列表，记为V(P)=vk (k=1, 2, …, m)。根据2.1节中所描述的“Z”型路径，确定凸多边形的主轴方向，即多边形的最长边，记为边l1，并从区域l1的左端点内角处选定一个搜索起点Ps(xs, ys, ψs, Δψs)。
|
| 图 7 路径规划过程 Fig. 7 Process of path planning |
UAV从起始点Ps出发，沿主轴(即多边形最长边)方向上行，到达多边形边界时采取左转弯掉头机动，沿主轴反方向返回，直到到达边界处再做右转弯掉头机动，沿主轴方向上行。如此循环往复，直到UAV到达或离开距离起始边最远的顶点Pf，路径规划完成。
对于非凸划分生成的2个子区域需要进行路径转移，如图 8所示，由于区域划分时分割线平行于凹角的延长边，所以能够保证2个区域的最大主轴方向相同，从而不必改变其路径的主方向。
|
| 图 8 2个凸区间的路径转移 Fig. 8 Path transition between two convex regions |
通常，中小型无人机的巡航速度一般在60~120 km/h[22]，即16.7~33.3 m/s，故假设取无人机的速度为v=20 m/s。滚转角不能取过大，为计算方便取滚转角γ=30°，运用牛顿第二定律可以得Rmin=70 m。假定无人机飞行高度为200 m，机载探测器的探测角为30°，可以得到覆盖带的宽度d约为100 m。
算例1 凸多边形搜索区域划分与路径规划
假设有3架完全相同的UAV覆盖搜索一个随机生成的凸六边形区域，该区域的顶点坐标为
| $ \mathit{\boldsymbol{V = }}{\left[ {\begin{array}{*{20}{c}} { - 2}&{ - 1}&0&5&3&{ - 1}\\ 0&4&6&{ - 1}&{ - 5}&{ - 5} \end{array}} \right]^{\rm{T}}} $ |
图 9为3架无人机从不同方向飞来时的区域划分与路径规划的结果。
|
| 图 9 3架无人机从不同方向飞来的区域划分与路径规划结果 Fig. 9 9 Region division and path planning results of 3 UAVs flying from different directions |
算例2 非凸多边形搜索区域划分与路径规划
同样，对于一个随机生成的非凸多边形区域，其顶点坐标为
| $ \mathit{\boldsymbol{V = }}{\left[ {\begin{array}{*{20}{c}} 0&3&7&8&{6.5}&5&{ - 4}&{ - 8}&{ - 5}\\ { - 1}&{ - 4}&{ - 4}&0&4&0&6&1&6 \end{array}} \right]^{\rm{T}}} $ |
当有3架无人机对该区域进行覆盖搜索时，其区域划分与路径规划结果如图 10所示。
|
| 图 10 3无人机非凸多边形区域划分与路径规划结果 Fig. 10 Non-convex polygon region division and path planning results of 3 UAVs |
5架无人机从东北方飞来时的区域划分和路径规划结果如图 11所示。
|
| 图 11 5无人机非凸多边形区域划分与路径规划结果 Fig. 11 Non-convex polygon region division and path planning results of 5 UAVs |
本文针对协同搜索任务无人机工作区间划分和全区域覆盖搜索路径规划问题，考虑无人机从某一方向飞来时的情况，采用分割线与无人机来向平行的均衡划分方法对凸多边形区域进行划分；采用凹点处凸分解的方法对非凸多边形区域进行划分。最后，采用“Z”型路径以及Dubins转弯路径规划搜索子区域覆盖搜索路径，从而建立了区域划分与路径规划的整体调用框架，能够快速划分并生成有效的无人机搜索区域及其搜索路径，且通过仿真验证了其有效性。
后续研究需要考虑搜索区域存在障碍物时的搜索区域划分和路径规划，以及其他情况下无人机初始位置不在搜索区域内部时如何进行最优搜索区域划分和路径规划。
| [1] |
黄长强, 翁兴伟, 王勇, 等. 多无人机协同作战技术[M]. 北京: 国防工业出版社, 2012: 1-7. HUANG C Q, WENG X W, WANG Y, et al. Cooperative combat technology for multi-UAVS[M]. Beijing: National Defense Industry Press, 2012: 1-7. (in Chinese) |
| [2] | ZHEN Z Y, ZHU P, XUE Y X, et al. Distributed intelligent self-organized mission planning of multi-UAV for dynamic targets cooperative search-attack[J]. Chinese Journal of Aeronautics, 2019, 32(12): 2706-2716. |
| Click to display the text | |
| [3] |
吴青坡, 周绍磊, 闫实. 复杂区域多UAV覆盖侦察方法研究[J]. 战术导弹技术, 2016(1): 50-55. WU Q P, ZHOU S L, YAN S. Multi-UAVs cooperative coverage reconnaissance in complex area[J]. Tactical Missile Technology, 2016(1): 50-55. (in Chinese) |
| Cited By in Cnki (11) | Click to display the text | |
| [4] | ZOTO J, MUSCI M A, KHALIQ A, et al. Automatic path planning for unmanned ground vehicle using UAV imagery[C]//201928th International Conference on Robotics in Alpe-Adria-Danube Region (RAAD). Berlin: Springer, 2020: 223-230. |
| [5] |
于驷男, 周锐, 夏洁, 等. 多无人机协同搜索区域分割与覆盖[J]. 北京航空航天大学学报, 2015, 41(1): 167-173. YU S N, ZHOU R, XIA J, et al. Decomposition and coverage of multi-UAV cooperative search area[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(1): 167-173. (in Chinese) |
| Cited By in Cnki (39) | Click to display the text | |
| [6] | BABEL L. Coordinated target assignment and UAV path planning with timing constraints[J]. Journal of Intelligent & Robotic Systems, 2019, 94(3-4): 857-869. |
| Click to display the text | |
| [7] | FOTIOS B, IVÁN M, ANÍBAL O. Coastal areas division and coverage with multiple UAVs for remote sensing[J]. Sensors, 2017, 17(4): 808-832. |
| Click to display the text | |
| [8] | LI J, LI X, YU L. Multi-UAV cooperative coverage path planning in plateau and mountain environment[C]//201833rd Youth Academic Annual Conference of Chinese Association of Automation. Piscataway: IEEE Press, 2018: 820-824. |
| [9] | CHEN J, ZHA W, PENG Z, et al. Cooperative area reconnaissance for multi-UAV in dynamic environment[C]//20139th Asian Control Conference (ASCC). Piscataway: IEEE Press, 2013. |
| [10] | MANSOURI S S, KANELLAKIS C, FRESK E, et al. Cooperative coverage path planning for visual inspection[J]. Control Engineering Practice, 2018, 74: 118-131. |
| Click to display the text | |
| [11] | LI Y, CHEN H, ER M J, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876-885. |
| Click to display the text | |
| [12] | VINH K, GEBREYOHANNES S, KARIMODDINI A. An area-decomposition based approach for cooperative tasking and coordination of UAVs in a search and coverage mission[C]//IEEE Aerospace Conference. Piscataway: IEEE Press, 2019. |
| [13] | NIELSEN L D, SUNG I, NIELSEN P. Convex decomposition for a coverage path planning for autonomous vehicles:Interior extension of edges[J]. Sensors, 2019, 19(19): 4165-4176. |
| Click to display the text | |
| [14] | HERT S, LUMELSKY V. Polygon area decomposition for multiple-robot workspace division[J]. International Journal of Computational Geometry & Applications, 1998, 8(4): 437-466. |
| Click to display the text | |
| [15] | DUBINS L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79(3): 497-516. |
| Click to display the text | |
| [16] |
郑宏捷.无人机区域侦察航路规划研究[D].长沙: 国防科技大学, 2011: 14-19. ZHENG H J. Investigation on the UAV path planning problem of area reconnaissance[D]. Changsha: National University of Defense Technology, 2011: 14-19(in Chinese). |
| [17] | HUANG Y, CAO Z, HALL E. Region filling operations for mobile robot using computer graphics[C]//1986 IEEE International Conference on Robotics & Automation. Piscataway: IEEE Press, 1986. |
| [18] |
陈海, 王新民, 焦裕松, 等. 无人机覆盖路径规划中转弯机动的运动学分析[J]. 飞行力学, 2010, 28(2): 31-34. CHEN H, WANG X M, JIAO Y S, et al. Kinematics analysis of UAV turning motion in coverage path planning[J]. Flight Dynamics, 2010, 28(2): 31-34. (in Chinese) |
| Cited By in Cnki (9) | Click to display the text | |
| [19] |
刘鑫, 杨霄鹏, 刘雨帆, 等. 基于GA-OCPA学习系统的无人机路径规划方法[J]. 航空学报, 2017, 38(11): 321275. LIU X, YANG X P, LIU Y F, et al. UAV path planning based on GA-OCPA learning system[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(11): 321275. (in Chinese) |
| Cited By in Cnki | Click to display the text | |
| [20] |
彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19(11): 2472-2476. PENG H, SHEN L C, HUO X H. Research on multiple UAV cooperative area coverage searching[J]. Journal of System Simulation, 2007, 19(11): 2472-2476. (in Chinese) |
| Cited By in Cnki (58) | Click to display the text | |
| [21] | LIU Y, ZHANG X J, ZHANG Y, et al. Collision free 4D path planning for multiple UAVs based on spatial refined voting mechanism and PSO approach[J]. Chinese Journal of Aeronautics, 2019, 32(6): 1504-1519. |
| Click to display the text | |
| [22] |
张佳龙, 闫建国, 张普, 等. 三架固定翼无人机协同编队飞行避障策略[J]. 国防科技大学学报, 2019(1): 123-129. ZHANG J L, YAN J G, ZHANG P, et al. Collision avoidance strategy of three fixed-wing unmanned aerial vehicles cooperative formation flight[J]. Journal of National University of Defense Technology, 2019(1): 123-129. (in Chinese) |
| Cited By in Cnki (3) | Click to display the text |