﻿ 多无人机协同搜索区域划分与路径规划
 文章快速检索 高级检索

Multi-UAV cooperative search on region division and path planning
DAI Jian, XU Fei, CHEN Qifeng
School of Aeronautics and Astronautics, Central South University, Changsha 410083, China
Abstract: Aiming at the multi-UAV cooperative search, two sub-problems of UAV working region division and full-area coverage search path planning are discussed and analyzed. By adopting the parallel division method and the concave-convex decomposition method, the region division of convex polygons and non-convex polygons is carried out. Thus, the multi-UAV cooperative search problem is transformed into a single-UAV search problem on a sub-region. Based on this, the "Z"-type path coverage method and the Dubins turning path are used to implement the path planning on each small sub-region, establishing an overall invocation framework of regional division and path planning, which can quickly divide the target area and generate flight routes. Finally, the simulations of convex and non-convex polygons verify the validity of the proposed method in this study.
Keywords: unmanned aerial rehicle    cooperative search    region division    path planning    Dubins path

1 考虑无人机来向的搜索区域划分方法 1.1 凸区域划分方法

 图 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.2 非凸区域划分方法

1.1节中的方法可以很好地实现凸多边形的区域划分，但实际无人机搜索的环境多为非凸的，仅进行凸多边形的划分尤显不足，还需进行非凸多边形的划分。

 图 2 凹口处凸分解示意 Fig. 2 Convex decomposition at concave corner
 图 3 非凸多边形区域划分过程 Fig. 3 Division process of non-convex polygon area

2 覆盖搜索路径规划 2.1 无人机区域覆盖搜索方法

“Z”型路径是覆盖搜索最常用的路径之一，采用“Z”型路径来回扫描不仅能使其轨迹充满整个搜索区域，还能有效地避免或减少无人机运行轨迹的重复。无人机转弯时存在最小转弯半径的限制，需采用Dubins[15]路径辅助转弯。因无人机转弯时消耗的能量远多于无人机直飞时的能量消耗[16]。因此，实现最优路径需要找出目标区域的最大方向，即主轴方向[17]，使航路转弯的次数尽可能的少[18]。可以按照求惯性主轴的方法[17]，来得出区域的主轴方向，但其过程较复杂，取特殊情况，定义多边形的长边为其主轴所在的方向。图 4为“Z”型路径的2种覆盖方式对比图，长边为其主轴所在方向，其转弯次数明显少于以短边为主轴的转弯数。

 图 4 2种覆盖方式对比 Fig. 4 Comparison of two coverage methods

 图 5 d < 2Rmin时的几种Dubins转弯方式 Fig. 5 Several Dubins turning methods when d < 2Rmin

 $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）

 图 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.2 搜索路径模型

 ${{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）
2.3 路径规划基本步骤

 图 7 路径规划过程 Fig. 7 Process of path planning

UAV从起始点Ps出发，沿主轴(即多边形最长边)方向上行，到达多边形边界时采取左转弯掉头机动，沿主轴反方向返回，直到到达边界处再做右转弯掉头机动，沿主轴方向上行。如此循环往复，直到UAV到达或离开距离起始边最远的顶点Pf，路径规划完成。

 图 8 2个凸区间的路径转移 Fig. 8 Path transition between two convex regions
3 算法验证

 $\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架无人机从不同方向飞来的区域划分与路径规划结果 Fig. 9 9 Region division and path planning results of 3 UAVs flying from different directions

 $\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}}}$

 图 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
4 结论

 [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
http://dx.doi.org/10.7527/S1000-6893.2019.23770

0

#### 文章信息

DAI Jian, XU Fei, CHEN Qifeng

Multi-UAV cooperative search on region division and path planning

Acta Aeronautica et Astronautica Sinica, 2020, 41(S1): 723770.
http://dx.doi.org/10.7527/S1000-6893.2019.23770