單側(cè)區(qū)域分割的多無(wú)人機(jī)掃描線(xiàn)搜索方法研究

謝朋志　魏晨

摘 要：本文針對(duì)區(qū)域覆蓋任務(wù)需求對(duì)多無(wú)人機(jī)搜索問(wèn)題展開(kāi)研究。首先， 提出一種任意搜索區(qū)域的等面積單側(cè)區(qū)域分割方法（Unilateral Region Segmentation）。然后，每個(gè)搜索區(qū)域分派一架或一個(gè)編隊(duì)的無(wú)人機(jī)進(jìn)行掃描線(xiàn)搜索，再基于人工勢(shì)場(chǎng)法來(lái)規(guī)避障礙物或者威脅從而獲得搜索路徑。最后，進(jìn)行仿真分析，驗(yàn)證了該算法在不同情況下的有效性、魯棒性以及適應(yīng)性。該算法在面向任意搜索區(qū)域、考慮無(wú)人機(jī)機(jī)動(dòng)性以及存在威脅等問(wèn)題時(shí)具有明顯優(yōu)勢(shì)。

關(guān)鍵詞： 多無(wú)人機(jī);任意搜索區(qū)域;區(qū)域分割;掃描線(xiàn)搜索;人工勢(shì)場(chǎng)法;路徑規(guī)劃

中圖分類(lèi)號(hào)： V279 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)： 1673-5048（2020）03-0067-06

0 引言

多無(wú)人機(jī)搜索問(wèn)題一直是近些年的熱點(diǎn)問(wèn)題。國(guó)內(nèi)外針對(duì)不同的任務(wù)需求展開(kāi)了大量的研究，其中包括多無(wú)人機(jī)協(xié)同搜索以及區(qū)域覆蓋等方面的研究。

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

面向區(qū)域覆蓋的搜索算法雖然在協(xié)同性上不如前者，但在計(jì)算時(shí)間、任務(wù)分配難度和區(qū)域覆蓋率等方面卻有著明顯的優(yōu)勢(shì)。

從國(guó)內(nèi)外研究現(xiàn)狀來(lái)看，針對(duì)區(qū)域覆蓋搜索問(wèn)題的研究大多采用分治策略的方法，即先進(jìn)行區(qū)域分割（區(qū)域整理），然后采用掃描線(xiàn)[5]、螺旋線(xiàn)[6]等方式進(jìn)行搜索。有學(xué)者將問(wèn)題簡(jiǎn)化為給定一個(gè)固定幾何區(qū)域內(nèi)隨機(jī)分布的許多目標(biāo)點(diǎn)，柵

格化離散目標(biāo)區(qū)域以提取偵察航路點(diǎn)[7-9]，然后將該問(wèn)題抽象為一個(gè)旅行商問(wèn)題（Traveling Salesman Problem，TSP），可以有效提高區(qū)域覆蓋率，但這種區(qū)域劃分的方法沒(méi)有考慮區(qū)域幾何形狀對(duì)搜

索問(wèn)題的影響，采用柵格化的方法沒(méi)有考慮無(wú)人機(jī)機(jī)動(dòng)性的要求。彭輝等人[10]針對(duì)多無(wú)人機(jī)協(xié)同區(qū)域覆蓋搜索問(wèn)題，將其分解為多無(wú)人機(jī)任務(wù)區(qū)域的分配以及分配后路徑規(guī)劃兩個(gè)子問(wèn)題，基于分層模糊推理的方法求解無(wú)人機(jī)的性能評(píng)估指標(biāo)，采用基于面積的區(qū)域分割方法對(duì)搜索任務(wù)區(qū)域進(jìn)行分割分配。類(lèi)似的還有于駟男等人[11]提出的多無(wú)人機(jī)協(xié)同搜索區(qū)域分割與覆蓋方法。但都沒(méi)有對(duì)無(wú)人機(jī)初始位置的選取給出合理的安排，沒(méi)有考慮存在威脅的情況。

目前多無(wú)人機(jī)的搜索問(wèn)題的一個(gè)研究重點(diǎn)是如何有效提高搜索區(qū)域的覆蓋率，然而側(cè)重于多無(wú)人機(jī)協(xié)同搜索的方法大都存在計(jì)算時(shí)間長(zhǎng)、覆蓋率低等問(wèn)題;而覆蓋率比較高的掃描線(xiàn)方式的搜索算法也存在著沒(méi)有考慮搜索區(qū)域幾何形狀對(duì)搜索算法適應(yīng)性的要求、對(duì)無(wú)人機(jī)機(jī)動(dòng)性的要求、目標(biāo)區(qū)域存在威脅的要求以及無(wú)人機(jī)初始位置的要求等問(wèn)題。

1 問(wèn)題描述

1.1 問(wèn)題分析

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

本文主要研究任意多邊形的等面積單側(cè)區(qū)域分割方法，根據(jù)區(qū)域分割結(jié)果計(jì)算掃描線(xiàn)位置以及基于人工勢(shì)場(chǎng)法得到搜索路徑，實(shí)現(xiàn)對(duì)任務(wù)區(qū)域的搜索覆蓋。

1.2 問(wèn)題建模

（1） 傳感器探測(cè)模型

基于區(qū)域覆蓋的需求對(duì)傳感器進(jìn)行建模，采用下視的傳感器類(lèi)型，不考慮無(wú)人機(jī)姿態(tài)的變化對(duì)傳感器視角的影響，高度H處的傳感器探測(cè)到的區(qū)域范圍是一個(gè)圓，其半徑為R=H·tanθ。如圖1所示。

（2） 無(wú)人機(jī)運(yùn)動(dòng)模型

對(duì)于一個(gè)由n架無(wú)人機(jī)組成的多無(wú)人機(jī)系統(tǒng)，用xi（t）， vi（t）， ui（t）分別表示無(wú)人機(jī)i的位置、速度和加速度，則無(wú)人機(jī)的運(yùn)動(dòng)方程可表示為

則無(wú)人機(jī)集群的動(dòng)力學(xué)方程可表示為

X·=AX+BU（3）

根據(jù)運(yùn)動(dòng)方程，可將U設(shè)為無(wú)人機(jī)集群運(yùn)動(dòng)控制輸入。每個(gè)個(gè)體的速度以及加速度受到最大范圍的限制：

式中： Umax和Vmax分別為無(wú)人機(jī)可達(dá)到的最大加速度和最大速度。

個(gè)體控制量可分為兩個(gè)部分： 集群內(nèi)部個(gè)體運(yùn)動(dòng)控制與避免環(huán)境威脅控制，即

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

式中： uiα（t）為集群內(nèi)部個(gè)體運(yùn)動(dòng)控制量，主要基于避撞規(guī)則防止與其他無(wú)人機(jī)相撞，見(jiàn)式（7）;uiβ（t）為避免環(huán)境威脅控制量，計(jì)算思路見(jiàn)第5節(jié)。

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

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

2 單側(cè)區(qū)域分割的多無(wú)人機(jī)掃描線(xiàn)搜索算法

（1） 任意多邊形的等面積單側(cè)區(qū)域分割方法：首先采用格雷厄姆算法將任意多邊形區(qū)域拓展為凸多邊形區(qū)域，然后對(duì)凸多邊形的區(qū)域分割展開(kāi)研究。同時(shí)對(duì)于一個(gè)較大的任務(wù)區(qū)域，采用多個(gè)方向分割的方式會(huì)使得同一位置起飛的無(wú)人機(jī)飛到各個(gè)初始位置再進(jìn)行搜索的效率不高，因此研究對(duì)于多邊形同一側(cè)（邊）作為初始位置的區(qū)域分割方法。

（2） 根據(jù)區(qū)域分割結(jié)果計(jì)算掃描線(xiàn)位置： 多邊形區(qū)域分割之后，獲得了多個(gè)不同的小多邊形區(qū)域，以分割線(xiàn)的方向作為無(wú)人機(jī)初始運(yùn)動(dòng)方向，同時(shí)根據(jù)無(wú)人機(jī)搜索范圍計(jì)算得到每個(gè)小區(qū)域的掃描線(xiàn)的數(shù)量以及位置。

（3） 基于人工勢(shì)場(chǎng)法得到搜索路徑： 得到掃描線(xiàn)的數(shù)量以及位置之后，還需要規(guī)避障礙物以及威脅，因此考慮使用具有良好避撞效果以及可以得到平滑運(yùn)動(dòng)軌跡的人工勢(shì)場(chǎng)法來(lái)計(jì)算搜索路徑。

本文掃描線(xiàn)搜索研究?jī)?nèi)容及過(guò)程如圖2所示。

3 任意多邊形的等面積單側(cè)區(qū)域分割方法

3.1 區(qū)域預(yù)處理

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

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

3.2 區(qū)域分割

設(shè)任一凸多邊形搜索任務(wù)區(qū)域?yàn)镻，其頂點(diǎn)序列V（P）按照逆時(shí)針進(jìn)行排列，共有N架無(wú)人機(jī)對(duì)任務(wù)區(qū)域進(jìn)行搜索偵察。本文針對(duì)的是大型搜索任務(wù)區(qū)域，并沒(méi)有采用無(wú)人機(jī)的初始位置位于多邊形區(qū)域的多條邊（角）上，而是認(rèn)為無(wú)人機(jī)群在飛往任務(wù)區(qū)時(shí)優(yōu)先選擇飛往任務(wù)區(qū)域的一條邊上，然后展開(kāi)搜索。因此，可將多邊形的一條邊作為無(wú)人機(jī)群開(kāi)始搜索的起始位置，如圖4所示。這樣基于等面積的凸多邊形的單側(cè)區(qū)域分割方法計(jì)算分割線(xiàn)的過(guò)程如下：

Step 1： 取多邊形任務(wù)區(qū)域的一條邊作為起始邊，將這條邊等分為N份，以這條邊逆時(shí)針?lè)较虻谝粋€(gè)頂點(diǎn)作為第1架無(wú)人機(jī)的起始位置，N-1個(gè)等分點(diǎn)作為剩下N-1架無(wú)人機(jī)的起始位置，該起始位置序列用S（N）表示，并且令V（1）=S（1）。

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

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

Step 4： 該條分割線(xiàn)起點(diǎn)為S（2），終點(diǎn)為V（Nv）。令V（1）=S（2），S（Ns）去掉第一個(gè)點(diǎn)，轉(zhuǎn)至Step 3計(jì)算下一條分割線(xiàn)。

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

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

直至計(jì)算完N-1條分割線(xiàn)的起點(diǎn)終點(diǎn)，結(jié)束計(jì)算。

4 掃描線(xiàn)位置的計(jì)算

在得到任意多邊形區(qū)域的分割結(jié)果之后，對(duì)每個(gè)分割后的區(qū)域進(jìn)行掃描線(xiàn)的計(jì)算，得到該區(qū)域掃描線(xiàn)的數(shù)量以及每條掃描線(xiàn)的兩個(gè)端點(diǎn)，計(jì)算掃描線(xiàn)的過(guò)程如下：

設(shè)計(jì)算的區(qū)域?yàn)閂，Nv=Size（V），即該區(qū)域頂點(diǎn)數(shù)。

Step 1： 取該區(qū)域的（V（1），V（Nv））這條邊作為基準(zhǔn)線(xiàn)（起始方向），計(jì)算這條線(xiàn)的斜率、截距。

Step 2： 計(jì)算與基準(zhǔn)線(xiàn)平行且過(guò)距離基準(zhǔn)線(xiàn)最遠(yuǎn)的頂點(diǎn)的直線(xiàn)的截距，并求出最大距離，進(jìn)而根據(jù)搜索能力的要求（搜索范圍）求出該區(qū)域掃描線(xiàn)的數(shù)量。

Step 3： 計(jì)算每條與基準(zhǔn)線(xiàn)平行的掃描線(xiàn)與區(qū)域V的兩個(gè)交點(diǎn)的位置： 遍歷該掃描線(xiàn)與V上所有邊所在直線(xiàn)的交點(diǎn)，并判斷交點(diǎn)是否屬于該邊，以此得到掃描線(xiàn)端點(diǎn)位置。

Step 4： 將得到的掃描線(xiàn)的端點(diǎn)按“Z”字掃描線(xiàn)進(jìn)行排序。

5 基于人工勢(shì)場(chǎng)法對(duì)威脅進(jìn)行規(guī)避

在搜索過(guò)程中會(huì)有障礙物、禁飛區(qū)、雷達(dá)等威脅的存在，本文采用人工勢(shì)場(chǎng)法[13]進(jìn)行規(guī)避威脅得到掃描線(xiàn)的航跡。人工勢(shì)場(chǎng)法的原理[14]是在無(wú)人機(jī)周?chē)鷺?gòu)建一種虛擬的勢(shì)場(chǎng)指引無(wú)人機(jī)的運(yùn)動(dòng)，運(yùn)動(dòng)環(huán)境中的威脅產(chǎn)生斥力場(chǎng)，目標(biāo)點(diǎn)產(chǎn)生引力場(chǎng)，人工勢(shì)場(chǎng)由這兩種勢(shì)場(chǎng)疊加而成，對(duì)勢(shì)場(chǎng)中的無(wú)人機(jī)起到作用，飛行路徑由其受到的復(fù)合場(chǎng)函數(shù)梯度下降方向決定。

5.1 引力勢(shì)場(chǎng)

引力勢(shì)場(chǎng)主要與無(wú)人機(jī)和目標(biāo)點(diǎn)間的距離有關(guān)，距離越大，無(wú)人機(jī)所受的勢(shì)能值就越大;距離越小，無(wú)人機(jī)所受的勢(shì)能值則越小，所以引力勢(shì)場(chǎng)的計(jì)算函數(shù)為

Uigra=η2r2ig（8）

式中： rig為無(wú)人機(jī)個(gè)體i到目標(biāo)點(diǎn)g之間的距離;η為正比例增益系數(shù)。對(duì)應(yīng)的引力可表示為

Figra=ηrig（9）

引力方向與xig相同，xig為無(wú)人機(jī)個(gè)體i指向目標(biāo)點(diǎn)g的向量。

5.2 斥力勢(shì)場(chǎng)

決定障礙物斥力勢(shì)場(chǎng)的因素是無(wú)人機(jī)與威脅之間的距離。當(dāng)無(wú)人機(jī)未進(jìn)入障礙物的影響范圍時(shí)，其受到的勢(shì)能值為零;在無(wú)人機(jī)進(jìn)入威脅的影響范圍后，兩者直接的距離越大，無(wú)人機(jī)受到的勢(shì)能值就越小，距離越小，無(wú)人機(jī)受到的勢(shì)能值就越大。斥力勢(shì)場(chǎng)的計(jì)算函數(shù)為

式中： k為正比例系數(shù);rit為無(wú)人機(jī)個(gè)體i到威脅中心t之間的距離;R為威脅對(duì)無(wú)人機(jī)產(chǎn)生作用的最大距離（影響距離）。相應(yīng)的斥力為斥力場(chǎng)的負(fù)梯度，即

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

0rit≥R（11）

斥力方向與xti相同，xti為威脅中心t指向無(wú)人機(jī)個(gè)體i的向量。

5.3 合力勢(shì)場(chǎng)

根據(jù)人工勢(shì)場(chǎng)法原理，無(wú)人機(jī)受到以上引力勢(shì)場(chǎng)與斥力勢(shì)場(chǎng)所組成的復(fù)合場(chǎng)的作用，在無(wú)人機(jī)前往目標(biāo)點(diǎn)的過(guò)程中很可能同時(shí)受到多個(gè)威脅的斥力場(chǎng)的作用，即無(wú)人機(jī)所受到的斥力場(chǎng)的作用是疊加的，則無(wú)人機(jī)所受的合力勢(shì)場(chǎng)的作用可表示為

Ui=Uigra+∑Uirep（12）

無(wú)人機(jī)所受的合力可表示為

Fi=Figra+∑Firep（13）

6 場(chǎng)景仿真與分析

本文基于一定的任務(wù)場(chǎng)景進(jìn)行仿真，場(chǎng)景設(shè)定為： 在已知的一個(gè)任意多邊形的搜索任務(wù)區(qū)內(nèi)，分派Nu個(gè)無(wú)人機(jī)節(jié)點(diǎn)對(duì)4個(gè)靜目標(biāo)和2個(gè)動(dòng)目標(biāo)進(jìn)行偵察搜索，無(wú)人機(jī)的傳感器類(lèi)型為具有下視能力的截?fù)衾走_(dá)，探測(cè)半徑為25～50 km。仿真測(cè)試過(guò)程如下。

6.1 單側(cè)區(qū)域分割方法

任意四邊形、五邊形、多邊形10架機(jī)區(qū)域分割結(jié)果如圖5所示;

任意五邊形1架、10架、20架機(jī)區(qū)域分割結(jié)果如圖6所示。

從圖中可以看出，該區(qū)域分割算法能夠?qū)崿F(xiàn)任意不同凸多邊形、任意無(wú)人機(jī)數(shù)量的等面積單側(cè)區(qū)域分割。

6.2 掃描線(xiàn)位置的計(jì)算

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

從圖中可以看出，該方法能夠?qū)崿F(xiàn)任意不同凸多邊形、任意無(wú)人機(jī)數(shù)量，以及不同搜索范圍需求的掃描線(xiàn)搜索，具有很好的適應(yīng)性。

6.3 規(guī)避威脅后的無(wú)人機(jī)軌跡

此仿真場(chǎng)景下，設(shè)置2個(gè)禁飛區(qū)以及4個(gè)敵方雷達(dá)，無(wú)人機(jī)搜索過(guò)程中應(yīng)避開(kāi)這些威脅，仿真結(jié)果如下。

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

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

從圖中可以看出，本文提出的區(qū)域全覆蓋的掃描線(xiàn)搜索算法不僅能夠適應(yīng)多樣的區(qū)域幾何形狀，而且對(duì)于不同無(wú)人機(jī)數(shù)量、不同搜索范圍的選擇均有良好的適應(yīng)性;從搜索目標(biāo)的能力來(lái)看，不論是靜目標(biāo)還是動(dòng)目標(biāo)均具有極高的搜索能力。

6.4 與其他搜索方法的比較

最后，與目前應(yīng)用比較廣泛的一種基于搜索圖采用滾動(dòng)優(yōu)化方式在線(xiàn)求解最優(yōu)航跡的分布式多無(wú)人機(jī)協(xié)同搜索方法進(jìn)行對(duì)比，該方法能夠有效實(shí)現(xiàn)多無(wú)人機(jī)之間的協(xié)同搜索，同時(shí)保證良好的時(shí)間優(yōu)越性以及有效降低環(huán)境的不確定性等優(yōu)勢(shì)，搜索航跡的對(duì)比如圖13所示。

主要采取以下統(tǒng)計(jì)指標(biāo)來(lái)綜合衡量?jī)煞N不同搜索方法下的搜索效率：

（1） 平均區(qū)域覆蓋率： 該指標(biāo)表示多次仿真條件下無(wú)人機(jī)在一定任務(wù)時(shí)間內(nèi)搜索過(guò)的區(qū)域占總?cè)蝿?wù)區(qū)域的平均面積比。

（2） 平均發(fā)現(xiàn)目標(biāo)數(shù)量： 該指標(biāo)表示多次仿真條件下無(wú)人機(jī)在足夠的任務(wù)時(shí)間內(nèi)搜索到目標(biāo)的平均數(shù)量。

在任意五邊形任務(wù)區(qū)域內(nèi)，分派8架無(wú)人機(jī)對(duì)4個(gè)靜目標(biāo)與2個(gè)動(dòng)目標(biāo)進(jìn)行搜索，兩種搜索方法各進(jìn)行10次仿真，其搜索指標(biāo)對(duì)比結(jié)果如圖14與表1所示。

從圖14可以看出，到仿真結(jié)束時(shí)，本文提出的基于單側(cè)區(qū)域分割算法的多無(wú)人機(jī)掃描線(xiàn)搜索方法的平均區(qū)域覆蓋率為96.1%，而基于搜索圖的滾動(dòng)時(shí)域優(yōu)化方法的分布式多無(wú)人機(jī)協(xié)同搜索方法的平均區(qū)域覆蓋率僅為69.8%。

從表1可以看出，在動(dòng)目標(biāo)的搜索中，基于搜索圖的滾動(dòng)時(shí)域優(yōu)化方法略?xún)?yōu)于本文所提方法，但搜索效果差別不大;而對(duì)于靜目標(biāo)的搜索，本文所提出的基于單側(cè)區(qū)域分割算法的多無(wú)人機(jī)掃描線(xiàn)搜索方法的搜索效果則明顯好于另一種搜索方法。仿真測(cè)試結(jié)果證明了本文所提方法的有效性。

7 結(jié)論

本文提出了一種任意搜索區(qū)域的等面積單側(cè)區(qū)域分割方法，并基于人工勢(shì)場(chǎng)法規(guī)避威脅得到掃描線(xiàn)搜索路徑，實(shí)現(xiàn)對(duì)任務(wù)區(qū)域的搜索覆蓋，最后結(jié)合掃描線(xiàn)搜索任務(wù)特點(diǎn)進(jìn)行仿真分析。仿真分析結(jié)果表明所提方法可實(shí)現(xiàn)對(duì)待搜索區(qū)域的全面覆蓋，同時(shí)能夠在避免威脅的基礎(chǔ)上有效提高多無(wú)人機(jī)系統(tǒng)覆蓋偵察效率。

本文所提方法解決了搜索區(qū)域幾何形狀對(duì)搜索問(wèn)題的限制問(wèn)題;相比傳統(tǒng)掃描線(xiàn)搜索的方法，考慮了搜索區(qū)域中存在威脅的情況;與柵格化的掃描線(xiàn)方法相比更加符合無(wú)人機(jī)機(jī)動(dòng)性的要求。但該方法是在考慮搜索區(qū)域較大以及無(wú)人機(jī)從搜索區(qū)域外指定位置飛到搜索區(qū)域進(jìn)行搜索的情況下提出的，因此無(wú)人機(jī)的起始點(diǎn)限定在了區(qū)域的一側(cè)用來(lái)解決相應(yīng)的搜索問(wèn)題。未來(lái)可能會(huì)從多方向進(jìn)行搜索的問(wèn)題展開(kāi)研究。

參考文獻(xiàn)：

[1] 張立鵬， 趙建輝， 肖永德. 基于最大可知度的無(wú)人機(jī)協(xié)同搜索控制方法[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] 符小衛(wèi)， 魏廣偉， 高曉光. 不確定環(huán)境下多無(wú)人機(jī)協(xié)同區(qū)域搜索算法[J]. 系統(tǒng)工程與電子技術(shù)， 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 區(qū)域覆蓋搜索路徑規(guī)劃方法[J]. 科技導(dǎo)報(bào)， 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] 趙晨皓， 李為民， 劉永蘭， 等. 多異構(gòu)無(wú)人機(jī)覆蓋搜索任務(wù)區(qū)域分配方法研究[J]. 戰(zhàn)術(shù)導(dǎo)彈技術(shù)， 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] 吳青坡， 周紹磊， 閆實(shí). 復(fù)雜區(qū)域多UAV覆蓋偵察方法研究[J]. 戰(zhàn)術(shù)導(dǎo)彈技術(shù)， 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協(xié)同區(qū)域覆蓋搜索研究[J]. 系統(tǒng)仿真學(xué)報(bào)， 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] 于駟男， 周銳， 夏潔， 等. 多無(wú)人機(jī)協(xié)同搜索區(qū)域分割與覆蓋[J]. 北京航空航天大學(xué)學(xué)報(bào)， 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

基金項(xiàng)目： 國(guó)家自然科學(xué)基金項(xiàng)目（91648205）;航空科學(xué)基金項(xiàng)目（20185851022）

作者簡(jiǎn)介： 謝朋志（1993-），男，吉林舒蘭人，碩士研究生，研究方向?yàn)闊o(wú)人機(jī)集群智能感知與搜索。

通訊作者：魏晨（1971- ），女，山東聊城人，博士，副教授，研究方向?yàn)榉蔷€(xiàn)性控制、模糊控制及時(shí)滯系統(tǒng)。

E-mail：weichen@buaa.edu.cn

引用格式： 謝朋志， 魏晨. 單側(cè)區(qū)域分割的多無(wú)人機(jī)掃描線(xiàn)搜索方法研究[ 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）