單側區域分割的多無人機掃描線搜索方法研究

謝朋志　魏晨

摘 要：本文針對區域覆蓋任務需求對多無人機搜索問題展開研究。首先， 提出一種任意搜索區域的等面積單側區域分割方法（Unilateral Region Segmentation）。然后，每個搜索區域分派一架或一個編隊的無人機進行掃描線搜索，再基于人工勢場法來規避障礙物或者威脅從而獲得搜索路徑。最后，進行仿真分析，驗證了該算法在不同情況下的有效性、魯棒性以及適應性。該算法在面向任意搜索區域、考慮無人機機動性以及存在威脅等問題時具有明顯優勢。

關鍵詞： 多無人機;任意搜索區域;區域分割;掃描線搜索;人工勢場法;路徑規劃

中圖分類號： V279 文獻標識碼：A文章編號： 1673-5048（2020）03-0067-06

0 引言

多無人機搜索問題一直是近些年的熱點問題。國內外針對不同的任務需求展開了大量的研究，其中包括多無人機協同搜索以及區域覆蓋等方面的研究。

面向多無人機協同搜索問題，主要解決如何由多架無人機以最小的代價協同搜索發現特定任務區域內可能存在的多個目標，主要方法為控制理論融合智能計算方法。文獻[1]將最大可知度的控制算法與搜索不確定度圖結合，能夠有效實現多無人機之間的協同搜索，同時保證良好的時間優越性。文獻[2]將模型預測控制理論和遺傳算法相結合，建立了協同搜索的預測模型，并使用貝葉斯理論進行更新，有效降低了環境的不確定性。還有基于概率圖[3]、信息素圖[4]等智能計算方法的協同搜索算法。這類方法可以有效解決多無人機協同搜索優化問題中的NP-hard問題，有較好的偵察效果，但也普遍存在計算時間長、很難找到全局最優解以及難以覆蓋搜索區域等問題。

面向區域覆蓋的搜索算法雖然在協同性上不如前者，但在計算時間、任務分配難度和區域覆蓋率等方面卻有著明顯的優勢。

從國內外研究現狀來看，針對區域覆蓋搜索問題的研究大多采用分治策略的方法，即先進行區域分割（區域整理），然后采用掃描線[5]、螺旋線[6]等方式進行搜索。有學者將問題簡化為給定一個固定幾何區域內隨機分布的許多目標點，柵

格化離散目標區域以提取偵察航路點[7-9]，然后將該問題抽象為一個旅行商問題（Traveling Salesman Problem，TSP），可以有效提高區域覆蓋率，但這種區域劃分的方法沒有考慮區域幾何形狀對搜

索問題的影響，采用柵格化的方法沒有考慮無人機機動性的要求。彭輝等人[10]針對多無人機協同區域覆蓋搜索問題，將其分解為多無人機任務區域的分配以及分配后路徑規劃兩個子問題，基于分層模糊推理的方法求解無人機的性能評估指標，采用基于面積的區域分割方法對搜索任務區域進行分割分配。類似的還有于駟男等人[11]提出的多無人機協同搜索區域分割與覆蓋方法。但都沒有對無人機初始位置的選取給出合理的安排，沒有考慮存在威脅的情況。

目前多無人機的搜索問題的一個研究重點是如何有效提高搜索區域的覆蓋率，然而側重于多無人機協同搜索的方法大都存在計算時間長、覆蓋率低等問題;而覆蓋率比較高的掃描線方式的搜索算法也存在著沒有考慮搜索區域幾何形狀對搜索算法適應性的要求、對無人機機動性的要求、目標區域存在威脅的要求以及無人機初始位置的要求等問題。

1 問題描述

1.1 問題分析

基于上述多無人機搜索面向區域覆蓋方面的研究還存在一些需要解決的問題，因此從該研究出發，主要考慮搜索區域較大以及無人機從搜索區域外指定位置飛到搜索區域進行搜索的情況，進而研究對于搜索區域同一側（邊）作為初始位置的任意幾何區域的掃描線搜索方法，同時考慮無人機機動性對搜索路徑的影響以及存在障礙物或者威脅的情況。

本文主要研究任意多邊形的等面積單側區域分割方法，根據區域分割結果計算掃描線位置以及基于人工勢場法得到搜索路徑，實現對任務區域的搜索覆蓋。

1.2 問題建模

（1） 傳感器探測模型

基于區域覆蓋的需求對傳感器進行建模，采用下視的傳感器類型，不考慮無人機姿態的變化對傳感器視角的影響，高度H處的傳感器探測到的區域范圍是一個圓，其半徑為R=H·tanθ。如圖1所示。

（2） 無人機運動模型

對于一個由n架無人機組成的多無人機系統，用xi（t）， vi（t）， ui（t）分別表示無人機i的位置、速度和加速度，則無人機的運動方程可表示為

則無人機集群的動力學方程可表示為

X·=AX+BU（3）

根據運動方程，可將U設為無人機集群運動控制輸入。每個個體的速度以及加速度受到最大范圍的限制：

式中： Umax和Vmax分別為無人機可達到的最大加速度和最大速度。

個體控制量可分為兩個部分： 集群內部個體運動控制與避免環境威脅控制，即

ui（t）=uiα（t）+uiβ（t）（6）

式中： uiα（t）為集群內部個體運動控制量，主要基于避撞規則防止與其他無人機相撞，見式（7）;uiβ（t）為避免環境威脅控制量，計算思路見第5節。

uiα（t）=∑j∈Ri， j≠i1rij-1dr（xi-xj） （7）

式中： rij為無人機j到無人機i的距離; dr為無人機間的最大安全距離;xi和xj為無人機的位置向量。

2 單側區域分割的多無人機掃描線搜索算法

（1） 任意多邊形的等面積單側區域分割方法：首先采用格雷厄姆算法將任意多邊形區域拓展為凸多邊形區域，然后對凸多邊形的區域分割展開研究。同時對于一個較大的任務區域，采用多個方向分割的方式會使得同一位置起飛的無人機飛到各個初始位置再進行搜索的效率不高，因此研究對于多邊形同一側（邊）作為初始位置的區域分割方法。

（2） 根據區域分割結果計算掃描線位置： 多邊形區域分割之后，獲得了多個不同的小多邊形區域，以分割線的方向作為無人機初始運動方向，同時根據無人機搜索范圍計算得到每個小區域的掃描線的數量以及位置。

（3） 基于人工勢場法得到搜索路徑： 得到掃描線的數量以及位置之后，還需要規避障礙物以及威脅，因此考慮使用具有良好避撞效果以及可以得到平滑運動軌跡的人工勢場法來計算搜索路徑。

本文掃描線搜索研究內容及過程如圖2所示。

3 任意多邊形的等面積單側區域分割方法

3.1 區域預處理

為了解決基于區域覆蓋需求的搜索任務問題，提出一種新的多邊形區域分割方法——等面積單側區域分割算法（Unilateral Region Segmentation）。

首先采用格雷厄姆算法[12]將任意多邊形區域拓展為凸多邊形區域，如圖3所示，然后對凸多邊形的區域分割展開研究。

3.2 區域分割

設任一凸多邊形搜索任務區域為P，其頂點序列V（P）按照逆時針進行排列，共有N架無人機對任務區域進行搜索偵察。本文針對的是大型搜索任務區域，并沒有采用無人機的初始位置位于多邊形區域的多條邊（角）上，而是認為無人機群在飛往任務區時優先選擇飛往任務區域的一條邊上，然后展開搜索。因此，可將多邊形的一條邊作為無人機群開始搜索的起始位置，如圖4所示。這樣基于等面積的凸多邊形的單側區域分割方法計算分割線的過程如下：

Step 1： 取多邊形任務區域的一條邊作為起始邊，將這條邊等分為N份，以這條邊逆時針方向第一個頂點作為第1架無人機的起始位置，N-1個等分點作為剩下N-1架無人機的起始位置，該起始位置序列用S（N）表示，并且令V（1）=S（1）。

Step 2： 計算將凸多邊形區域N等分之后的面積，記為Aave。

Step 3： 令Nv=Size（V），Ns=Size（S），Vtemp=[V（Nv）， V（1）， S（2）]，計算其面積記為Atemp，如果Atemp=Aave，則執行Step 4;如果Atemp>Aave，則執行Step 5;如果Atemp

Step 4： 該條分割線起點為S（2），終點為V（Nv）。令V（1）=S（2），S（Ns）去掉第一個點，轉至Step 3計算下一條分割線。

Step 5： 在（V（Nv）， V（1））這條邊上找尋一點E，使得[V（1）， S（2）， E]的面積等于Aave，此時該條分割線起點為S（2），終點為E。令V（1）=S（2），并將E點放至V的序列最后，S（Ns）去掉第一個點，轉至Step 3計算下一條分割線。

Step 6： 在（V（Nv）， V（Nv-1））這條邊上找尋一點E，使得[V（Nv）， V（1）， S（2）， E]的面積等于Aave，如果這條邊上找不到這樣一個點，則在（V（Nv-1）， V（Nv-2））這條邊上找尋，以此類推直至找到E點，則該條分割線起點為S（2），終點為V（Nv）。同樣地，更新V序列，S（Ns）去掉第一個點，轉至Step 3計算下一條分割線。

直至計算完N-1條分割線的起點終點，結束計算。

4 掃描線位置的計算

在得到任意多邊形區域的分割結果之后，對每個分割后的區域進行掃描線的計算，得到該區域掃描線的數量以及每條掃描線的兩個端點，計算掃描線的過程如下：

設計算的區域為V，Nv=Size（V），即該區域頂點數。

Step 1： 取該區域的（V（1），V（Nv））這條邊作為基準線（起始方向），計算這條線的斜率、截距。

Step 2： 計算與基準線平行且過距離基準線最遠的頂點的直線的截距，并求出最大距離，進而根據搜索能力的要求（搜索范圍）求出該區域掃描線的數量。

Step 3： 計算每條與基準線平行的掃描線與區域V的兩個交點的位置： 遍歷該掃描線與V上所有邊所在直線的交點，并判斷交點是否屬于該邊，以此得到掃描線端點位置。

Step 4： 將得到的掃描線的端點按“Z”字掃描線進行排序。

5 基于人工勢場法對威脅進行規避

在搜索過程中會有障礙物、禁飛區、雷達等威脅的存在，本文采用人工勢場法[13]進行規避威脅得到掃描線的航跡。人工勢場法的原理[14]是在無人機周圍構建一種虛擬的勢場指引無人機的運動，運動環境中的威脅產生斥力場，目標點產生引力場，人工勢場由這兩種勢場疊加而成，對勢場中的無人機起到作用，飛行路徑由其受到的復合場函數梯度下降方向決定。

5.1 引力勢場

引力勢場主要與無人機和目標點間的距離有關，距離越大，無人機所受的勢能值就越大;距離越小，無人機所受的勢能值則越小，所以引力勢場的計算函數為

Uigra=η2r2ig（8）

式中： rig為無人機個體i到目標點g之間的距離;η為正比例增益系數。對應的引力可表示為

Figra=ηrig（9）

引力方向與xig相同，xig為無人機個體i指向目標點g的向量。

5.2 斥力勢場

決定障礙物斥力勢場的因素是無人機與威脅之間的距離。當無人機未進入障礙物的影響范圍時，其受到的勢能值為零;在無人機進入威脅的影響范圍后，兩者直接的距離越大，無人機受到的勢能值就越小，距離越小，無人機受到的勢能值就越大。斥力勢場的計算函數為

式中： k為正比例系數;rit為無人機個體i到威脅中心t之間的距離;R為威脅對無人機產生作用的最大距離（影響距離）。相應的斥力為斥力場的負梯度，即

Firep=k1rit-1R1r2igrit∈（0， R）

0rit≥R（11）

斥力方向與xti相同，xti為威脅中心t指向無人機個體i的向量。

5.3 合力勢場

根據人工勢場法原理，無人機受到以上引力勢場與斥力勢場所組成的復合場的作用，在無人機前往目標點的過程中很可能同時受到多個威脅的斥力場的作用，即無人機所受到的斥力場的作用是疊加的，則無人機所受的合力勢場的作用可表示為

Ui=Uigra+∑Uirep（12）

無人機所受的合力可表示為

Fi=Figra+∑Firep（13）

6 場景仿真與分析

本文基于一定的任務場景進行仿真，場景設定為： 在已知的一個任意多邊形的搜索任務區內，分派Nu個無人機節點對4個靜目標和2個動目標進行偵察搜索，無人機的傳感器類型為具有下視能力的截擊雷達，探測半徑為25～50 km。仿真測試過程如下。

6.1 單側區域分割方法

任意四邊形、五邊形、多邊形10架機區域分割結果如圖5所示;

任意五邊形1架、10架、20架機區域分割結果如圖6所示。

從圖中可以看出，該區域分割算法能夠實現任意不同凸多邊形、任意無人機數量的等面積單側區域分割。

6.2 掃描線位置的計算

不同多邊形8架機小搜索范圍的仿真對比如圖7所示;同一多邊形8架機不同搜索范圍的仿真對比如圖8所示;同一多邊形8架、16架機小搜索范圍的仿真對比如圖9所示。

從圖中可以看出，該方法能夠實現任意不同凸多邊形、任意無人機數量，以及不同搜索范圍需求的掃描線搜索，具有很好的適應性。

6.3 規避威脅后的無人機軌跡

此仿真場景下，設置2個禁飛區以及4個敵方雷達，無人機搜索過程中應避開這些威脅，仿真結果如下。

不同多邊形8架機小搜索范圍航跡對比如圖10所示;同一多邊形8架機不同搜索范圍航跡對比如圖11所示;

同一多邊形8架、16架機小搜索范圍航跡對比如圖12所示。

從圖中可以看出，本文提出的區域全覆蓋的掃描線搜索算法不僅能夠適應多樣的區域幾何形狀，而且對于不同無人機數量、不同搜索范圍的選擇均有良好的適應性;從搜索目標的能力來看，不論是靜目標還是動目標均具有極高的搜索能力。

6.4 與其他搜索方法的比較

最后，與目前應用比較廣泛的一種基于搜索圖采用滾動優化方式在線求解最優航跡的分布式多無人機協同搜索方法進行對比，該方法能夠有效實現多無人機之間的協同搜索，同時保證良好的時間優越性以及有效降低環境的不確定性等優勢，搜索航跡的對比如圖13所示。

主要采取以下統計指標來綜合衡量兩種不同搜索方法下的搜索效率：

（1） 平均區域覆蓋率： 該指標表示多次仿真條件下無人機在一定任務時間內搜索過的區域占總任務區域的平均面積比。

（2） 平均發現目標數量： 該指標表示多次仿真條件下無人機在足夠的任務時間內搜索到目標的平均數量。

在任意五邊形任務區域內，分派8架無人機對4個靜目標與2個動目標進行搜索，兩種搜索方法各進行10次仿真，其搜索指標對比結果如圖14與表1所示。

從圖14可以看出，到仿真結束時，本文提出的基于單側區域分割算法的多無人機掃描線搜索方法的平均區域覆蓋率為96.1%，而基于搜索圖的滾動時域優化方法的分布式多無人機協同搜索方法的平均區域覆蓋率僅為69.8%。

從表1可以看出，在動目標的搜索中，基于搜索圖的滾動時域優化方法略優于本文所提方法，但搜索效果差別不大;而對于靜目標的搜索，本文所提出的基于單側區域分割算法的多無人機掃描線搜索方法的搜索效果則明顯好于另一種搜索方法。仿真測試結果證明了本文所提方法的有效性。

7 結論

本文提出了一種任意搜索區域的等面積單側區域分割方法，并基于人工勢場法規避威脅得到掃描線搜索路徑，實現對任務區域的搜索覆蓋，最后結合掃描線搜索任務特點進行仿真分析。仿真分析結果表明所提方法可實現對待搜索區域的全面覆蓋，同時能夠在避免威脅的基礎上有效提高多無人機系統覆蓋偵察效率。

本文所提方法解決了搜索區域幾何形狀對搜索問題的限制問題;相比傳統掃描線搜索的方法，考慮了搜索區域中存在威脅的情況;與柵格化的掃描線方法相比更加符合無人機機動性的要求。但該方法是在考慮搜索區域較大以及無人機從搜索區域外指定位置飛到搜索區域進行搜索的情況下提出的，因此無人機的起始點限定在了區域的一側用來解決相應的搜索問題。未來可能會從多方向進行搜索的問題展開研究。

參考文獻：

[1] 張立鵬， 趙建輝， 肖永德. 基于最大可知度的無人機協同搜索控制方法[J]. 電光與控制， 2014， 21（11）： 33-40.

Zhang Lipeng， Zhao Jianhui， Xiao Yongde. A Control Method for the UAV Cooperative Searching Based on Uncertainty Value Reducing Maximization [J]. Electronics Optics and Control， 2014， 21（11）： 33-40. （in Chinese）

[2] 符小衛， 魏廣偉， 高曉光. 不確定環境下多無人機協同區域搜索算法[J]. 系統工程與電子技術， 2016， 38（4）： 821-827.

Fu Xiaowei，Wei Guangwei，Gao Xiaoguang. Cooperative Area Search Algorithm for Multi-UAVs in Uncertainty Environment[J]. Systems Engineering and Electronics， 2016， 38（4）： 821-827. （in Chinese）

[3] Lu Ping. Predictor-Corrector Entry Guidance for Low-Lifting Vehicles[J]. Journal of Guidance， Control， and Dynamics， 2008， 31（4）： 1067-1075.

[4] Joshi A， Sivan K， Amma S S. Predictor-Corrector Reentry Gui-dance Algorithm with Path Constraints for Atmospheric Entry Vehicles[J]. Journal of Guidance， Control， and Dynamics， 2007， 30（5）： 1307-1318.

[5] Altshuler Y， Yanovsky V， Wagner I A， et al. Efficient Cooperative Search of Smart Targets Using UAV Swarms[J]. Robotica， 2008， 26（4）： 551-557.

[6] Erignac C A. An Exhaustive Swarming Search Strategy Based on Distributed Pheromone Maps[C]∥ AIAA Infotech@Aerospace 2007 Conference and Exhibit，Rohnert Park，2007： 1130-1145.

[7] 趙晨皓， 劉永蘭， 趙杰. 一種基于PEGA 算法的UAV 區域覆蓋搜索路徑規劃方法[J]. 科技導報， 2014， 32（28/29）：85-90.

Zhao Chenhao， Liu Yonglan， Zhao Jie. Path Planning Method of UAV Area Coverage Searching Based on PEGA[J]. Science & Technology Review， 2014， 32（28/29）：85-90. （in Chinese）

[8] 趙晨皓， 李為民， 劉永蘭， 等. 多異構無人機覆蓋搜索任務區域分配方法研究[J]. 戰術導彈技術， 2014（6）： 32-37.

Zhao Chenhao， Li Weimin， Liu Yonglan， et al. Research on Mi-ssion Area Allocation Method for Multiple Heterogeneous UAVs Area Coverage Searching[J]. Tactical Missile Technology， 2014（6）： 32-37. （in Chinese）

[9] 吳青坡， 周紹磊， 閆實. 復雜區域多UAV覆蓋偵察方法研究[J]. 戰術導彈技術， 2016（1）： 50-55.

Wu Qingpo， Zhou Shaolei， Yan Shi. Multi-UAVs Cooperative Coverage Reconnaissance in Complex Area[J]. Tactical Missile Technology， 2016（1）： 50-55. （in Chinese）

[10] 彭輝， 沈林成， 霍霄華. 多UAV協同區域覆蓋搜索研究[J]. 系統仿真學報， 2007， 19（11）： 2472-2476.

Peng Hui， Shen Lincheng， Huo Xiaohua. Reasearch on Multiple UAV Cooperative Area Coverage Searching[J]. Journal of System Simulation， 2007， 19（11）： 2472-2476. （in Chinese）

[11] 于駟男， 周銳， 夏潔， 等. 多無人機協同搜索區域分割與覆蓋[J]. 北京航空航天大學學報， 2015， 41（1）： 167-173.

Yu Sinan， Zhou Rui， Xia Jie， 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）

[12] Graham R L. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set[J]. Information Processing Letters， 1972， 1（4）： 132-133.

[13] Khatib O. Real-Time Obstacle Avoidance for Manipulators and Mobile Robots[M]∥Cox I J，Wilfong G T. Autonomous Robot Vehicles. New York： Springer， 1986：396-404.

[14] Ge S S， Cui Y J. New Potential Functions for Mobile Robot Path Planning[J]. IEEE Transactions on Robotics and Automation， 2000， 16（5）：615-620.

Research on Scanning Line Search Method for Multi-UAV

Based on Unilateral Region Segmentation

Xie Pengzhi， Wei Chen*

（School of Automation Science and Electrical Engineering， Beihang University， Beijing 100083， China）

Abstract：Aiming at the requirement of area coverage task， the multi-UAV scanning line search task is researched. Firstly， an unilateral region segmentation for equal area （URSEA） method for arbitrary search region is proposed. Each search area is assigned one or a group of UAVs for scanning line search， and then obstacles or threats are evaded based on the artificial potential field method to obtain the search path. Finally， simulation analysis is carried out to verify the effectiveness， robustness and adaptability of the algorithm in different situations. The algorithm has obvious advantages when facing arbitrary search area， considering UAV maneuverability and threat.

Key words：multi-UAV;arbitrary search region;region segmentation;scanning line search;artificial potential field method;path planning

收稿日期：2019-07-17

基金項目： 國家自然科學基金項目（91648205）;航空科學基金項目（20185851022）

作者簡介： 謝朋志（1993-），男，吉林舒蘭人，碩士研究生，研究方向為無人機集群智能感知與搜索。

通訊作者：魏晨（1971- ），女，山東聊城人，博士，副教授，研究方向為非線性控制、模糊控制及時滯系統。

E-mail：weichen@buaa.edu.cn

引用格式： 謝朋志， 魏晨. 單側區域分割的多無人機掃描線搜索方法研究[ J].

航空兵器，2020， 27（ 3）： 67-72.

Xie Pengzhi， Wei Chen. Research on Scanning Line Search Method for Multi-UAV Based on Unilateral Region Segmentation [ J]. Aero Weaponry，2020， 27（ 3）： 67-72.（in Chinese）