固定翼無(wú)人機(jī)巡邏覆蓋協(xié)同路徑規(guī)劃方法

尹洪玉，吳宇，*，梁天驕

1.重慶大學(xué) 航空航天學(xué)院，重慶 400044

2.航空工業(yè)成都飛機(jī)設(shè)計(jì)研究所，成都 610091

隨著無(wú)人機(jī)（Unmanned Aerial Vehicle，UAV）技術(shù)的日益成熟，其可靠性、方便性和實(shí)用性大大增強(qiáng)，而且伴隨著低空空域的逐漸開放，無(wú)人機(jī)能夠扮演的角色也越來(lái)越多，越來(lái)越重要。無(wú)人機(jī)能夠完成的任務(wù)也逐漸多元化，其已經(jīng)被廣泛應(yīng)用在多個(gè)領(lǐng)域之中，包括貨物遞送［1］，地表觀測(cè)［2］，追蹤監(jiān)視［3］，軍事國(guó)防［4］等重要產(chǎn)業(yè)或前沿領(lǐng)域。無(wú)人機(jī)在完成以上任務(wù)時(shí)，都需要按照一定的路徑飛行，涉及到路徑規(guī)劃問(wèn)題。根據(jù)規(guī)劃條件和目的的不同，無(wú)人機(jī)的路徑規(guī)劃問(wèn)題可以分為兩類：實(shí)現(xiàn)起點(diǎn)到終點(diǎn)的路徑規(guī)劃［5］和實(shí)現(xiàn)區(qū)域覆蓋的路徑規(guī)劃［6］。

起點(diǎn)到終點(diǎn)的路徑規(guī)劃多應(yīng)用在無(wú)人機(jī)送貨，無(wú)人機(jī)近地打擊和民航飛行器的航路修改［7］等方面，這些問(wèn)題中無(wú)人機(jī)都有確定的起點(diǎn)和終點(diǎn)，只需要考慮兩點(diǎn)之間的障礙物，采用一定的方法生成路徑，其技術(shù)相對(duì)比較成熟。

區(qū)別于上述由起點(diǎn)到終點(diǎn)的路徑規(guī)劃方式，以區(qū)域偵察覆蓋為目的的路徑規(guī)劃需要考慮更多的約束和處理全局性的信息。區(qū)域覆蓋問(wèn)題可以利用往復(fù)折返路徑和盤旋路徑求解。如文獻(xiàn)［8］中介紹了一種追求單次完全覆蓋的無(wú)人機(jī)路徑規(guī)劃方法，極大提高了不規(guī)則區(qū)域的覆蓋率，這種覆蓋模式會(huì)放棄偵察成本較高的區(qū)域，權(quán)衡飛行成本和覆蓋率以判斷路徑的優(yōu)劣。多架無(wú)人機(jī)應(yīng)用這種路徑規(guī)劃方式進(jìn)行排隊(duì)式巡邏，可以實(shí)現(xiàn)區(qū)域持續(xù)監(jiān)控。但這種覆蓋方式?jīng)]有區(qū)分區(qū)域重要性無(wú)法實(shí)現(xiàn)重點(diǎn)區(qū)域重點(diǎn)偵察，且具有極強(qiáng)的規(guī)律性，在軍事應(yīng)用中會(huì)被敵人輕易針對(duì)。因此需要開發(fā)一種持續(xù)性的偵察策略，以視野內(nèi)地點(diǎn)的訪問(wèn)時(shí)間間隔來(lái)判斷決策優(yōu)劣，保證任務(wù)空間中所有地點(diǎn)都在持續(xù)的偵察之中。

以往對(duì)于無(wú)人機(jī)覆蓋路徑規(guī)劃的研究基本都將任務(wù)環(huán)境看作是二維平面。對(duì)于規(guī)則多邊形的二維平面來(lái)說(shuō)，無(wú)人機(jī)通過(guò)Z 字形往復(fù)或者螺旋模式［9］飛行即可實(shí)現(xiàn)對(duì)于目標(biāo)區(qū)域的覆蓋。這種往復(fù)的覆蓋模式，任務(wù)區(qū)域越大，則其在成本方面的表現(xiàn)就越良好［10］。對(duì)于不規(guī)則的多邊形區(qū)域，以往的研究往往更加傾向于將不規(guī)則的多邊形通過(guò)分解和整合，再利用無(wú)人機(jī)進(jìn)行分區(qū)域的往復(fù)覆蓋，如文獻(xiàn)［11］介紹的局部路徑規(guī)劃算法。這種基于二維平面環(huán)境的路徑規(guī)劃，因?yàn)闆](méi)有考慮到禁飛區(qū)或者障礙物遮擋等問(wèn)題，所以僅對(duì)于海面，平原等無(wú)起伏障礙物的環(huán)境具有適用性。然而無(wú)人機(jī)更多的是應(yīng)用在三維環(huán)境當(dāng)中。為了更加貼近現(xiàn)實(shí)應(yīng)用，近年來(lái)對(duì)于無(wú)人機(jī)覆蓋路徑規(guī)劃的研究開始考慮禁飛區(qū)和空間障礙物的影響，將原來(lái)在二維空間中的覆蓋任務(wù)擴(kuò)展到了三維空間中［12］。

相較于二維空間，三維空間中的路徑規(guī)劃更加復(fù)雜，需要考慮更多的約束，如環(huán)境障礙物，視線障礙物等。目前，多種先進(jìn)的信息交互設(shè)備也應(yīng)用到空間覆蓋當(dāng)中，三維空間中的無(wú)人機(jī)技術(shù)已經(jīng)逐漸成熟。文獻(xiàn)［13］中論述了一種利用能量轉(zhuǎn)換最大化無(wú)人機(jī)效率的三維空間路徑規(guī)劃，但是其覆蓋形式仍然是點(diǎn)對(duì)面的覆蓋，沒(méi)有考慮地形起伏的影響。當(dāng)前無(wú)人機(jī)三維覆蓋問(wèn)題的研究，大多是針對(duì)待檢外形周邊多個(gè)確定的監(jiān)測(cè)點(diǎn)的連接優(yōu)化［14］，這類問(wèn)題多轉(zhuǎn)化為旅行商問(wèn)題進(jìn)行分析求解［15］。文獻(xiàn)［16］直接提出了一種旅行商-覆蓋路徑規(guī)劃模型。區(qū)別于以往連接監(jiān)測(cè)點(diǎn)的覆蓋方式，文獻(xiàn)［17］中實(shí)現(xiàn)了一種小尺度環(huán)境中旋翼機(jī)三維覆蓋方法，但不適用于固定翼無(wú)人機(jī)的大面積偵察搜索。

從以上分析中可以看出，當(dāng)前對(duì)于無(wú)人機(jī)覆蓋路徑規(guī)劃的研究仍然存在著諸多問(wèn)題。首先在完全覆蓋工作模式下，沒(méi)有對(duì)每個(gè)區(qū)域的重要程度進(jìn)行區(qū)分。在實(shí)際應(yīng)用中，某些長(zhǎng)期未被訪問(wèn)的區(qū)域或者出現(xiàn)緊急情況需要進(jìn)行重點(diǎn)關(guān)注。其次在三維地形環(huán)境下，由于地形遮擋和設(shè)置禁飛區(qū)等原因，可能無(wú)法實(shí)現(xiàn)對(duì)整個(gè)區(qū)域的完全覆蓋［18］。在研究多機(jī)協(xié)同覆蓋問(wèn)題時(shí)，多是將對(duì)無(wú)人機(jī)進(jìn)行任務(wù)劃分，每架無(wú)人機(jī)負(fù)責(zé)各自子區(qū)域的覆蓋［19］。在這種工作模式中，無(wú)人機(jī)之間的協(xié)同程度不高。

本文針對(duì)以上問(wèn)題，根據(jù)區(qū)域被訪問(wèn)間隔對(duì)各區(qū)域進(jìn)行了分類，以區(qū)分其重要程度，如圖1 所示。并以縮短區(qū)域相鄰兩次被訪問(wèn)時(shí)間間隔為目標(biāo)，針對(duì)普通區(qū)域設(shè)計(jì)了固定翼無(wú)人機(jī)巡邏覆蓋路徑規(guī)劃算法和協(xié)同機(jī)制，同時(shí)為下一步備選點(diǎn)視野范圍內(nèi)的超時(shí)區(qū)域設(shè)計(jì)加權(quán)處理方式，以提高無(wú)人機(jī)對(duì)該區(qū)域的關(guān)注度?？紤]出現(xiàn)緊急情況的區(qū)域和下一步備選點(diǎn)視野范圍外的超時(shí)區(qū)域2 種特殊情況，設(shè)計(jì)了針對(duì)性的穿插覆蓋算法。

圖1 地面區(qū)域分類Fig.1 Classification of regions on ground

1 路徑規(guī)劃模型

1.1 持續(xù)監(jiān)視任務(wù)路徑規(guī)劃空間模型

在設(shè)計(jì)算法之前需要對(duì)任務(wù)的地面空間和飛行空間進(jìn)行網(wǎng)格劃分，首先在對(duì)需要偵察的地面進(jìn)行網(wǎng)格化時(shí)，考慮到地形的高低起伏和對(duì)地形細(xì)節(jié)的描述，網(wǎng)格尺寸不宜太大。其次，搭載偵察設(shè)備的固定翼無(wú)人機(jī)巡航高度較高，視野范圍較大，無(wú)人機(jī)需要計(jì)算偵察覆蓋范圍并更新地面網(wǎng)格的狀態(tài)和訪問(wèn)信息，以此作為無(wú)人機(jī)做出決策的參考數(shù)據(jù)，這就要求地面網(wǎng)格的劃分要更加的精密，所以地面網(wǎng)格往往小于空中網(wǎng)格的尺寸。同時(shí)，每個(gè)地面網(wǎng)格按照該網(wǎng)格內(nèi)地形的最高高度定義該網(wǎng)格的高度，就可以得到地形的近似模擬。

類似地，將無(wú)人機(jī)飛行空間劃分為若干大小相同的空間網(wǎng)格，無(wú)人機(jī)將經(jīng)過(guò)空間網(wǎng)格的體心，并在其周圍26 個(gè)方格中選擇滿足約束條件且覆蓋任務(wù)指標(biāo)最優(yōu)的網(wǎng)格體心作為下一目標(biāo)點(diǎn)［20］。所有的空間網(wǎng)格根據(jù)與障礙物的距離關(guān)系分為3 種狀態(tài)，如圖2 所示。

圖2 空間網(wǎng)格狀態(tài)信息Fig.2 State information of space grids

圖2 中，球形區(qū)域是障礙物或禁飛區(qū)，其所占網(wǎng)格狀態(tài)為“-1”表示無(wú)人機(jī)不能通行；“1”狀態(tài)網(wǎng)格遠(yuǎn)離禁飛區(qū)和障礙物表示可以通行；“0”狀態(tài)網(wǎng)格表示在障礙物或禁飛區(qū)附近，可以作為路徑點(diǎn)經(jīng)過(guò)，但是不能作為路徑的起點(diǎn)或者終點(diǎn)，從而避免無(wú)人機(jī)沖撞禁飛區(qū)。

在研究無(wú)人機(jī)的路徑規(guī)劃時(shí)，單個(gè)無(wú)人機(jī)可以看作一個(gè)質(zhì)點(diǎn)，在各網(wǎng)格的體心之間移動(dòng)。固定翼無(wú)人機(jī)在運(yùn)動(dòng)中，豎直方向的運(yùn)動(dòng)尺寸要遠(yuǎn)遠(yuǎn)小于水平方向的運(yùn)動(dòng)尺寸，所以兩水平邊長(zhǎng)相等且大于豎直邊長(zhǎng)的非正六面體網(wǎng)格更加適合固定翼無(wú)人機(jī)的運(yùn)動(dòng)形式。

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

在這種非正六面體的飛行網(wǎng)格中，固定翼無(wú)人機(jī)的飛行路徑存在4 種形式，如圖3 所示。

圖3 無(wú)人機(jī)在網(wǎng)格中的多種運(yùn)動(dòng)形式Fig.3 Multiple forms of movement of UAVs in gridded space

圖3 為本文劃分的非正六面體，這導(dǎo)致每次規(guī)劃可選擇多種不同長(zhǎng)度的路徑，使得無(wú)人機(jī)飛過(guò)的距離有所不同。因此，為保證多無(wú)人機(jī)之間的協(xié)調(diào)性，無(wú)人機(jī)就需要進(jìn)行變速飛行。在這種工作模式中，每架無(wú)人機(jī)無(wú)論選擇哪一種路徑，都需要保證到達(dá)下一個(gè)路徑點(diǎn)的時(shí)間是相同的，以消除個(gè)體之間的時(shí)間差異性，初步達(dá)到協(xié)同的目的。此時(shí)可以通過(guò)式（1）和式（2）表達(dá)無(wú)人機(jī)的位置變化：

式中：xi，yi，zi，t為某時(shí)刻第i架無(wú)人機(jī)所處的四維位置信息；Nd為任務(wù)中無(wú)人機(jī)的數(shù)量；a，b，h分別為所劃分網(wǎng)格的3 個(gè)方向的邊長(zhǎng)（a=b）；nt是t時(shí)刻無(wú)人機(jī)控制向量，nx，ny，nz的值可以從D=｛-1，0，1｝中選擇，控制向量要保證滿足固定翼無(wú)人機(jī)轉(zhuǎn)角約束，且3 個(gè)值不能同時(shí)為0。

1.3 無(wú)人機(jī)的視野覆蓋模型

無(wú)人機(jī)在偵查過(guò)程中需要采集地面的環(huán)境信息和狀態(tài)信息，環(huán)境信息作為任務(wù)需求，狀態(tài)信息作為無(wú)人機(jī)做出路徑規(guī)劃的參考。為模擬無(wú)人機(jī)對(duì)于地面信息的采集，需要建立無(wú)人機(jī)的視野覆蓋模型。本文中的固定翼無(wú)人機(jī)偵察模型與傳統(tǒng)旋翼機(jī)偵察模型存在一定區(qū)別，旋翼機(jī)的偵察設(shè)備一般固定在機(jī)體下方，如文獻(xiàn)［21］中的旋翼機(jī)搭載的偵察設(shè)備能對(duì)機(jī)身正下方的椎體區(qū)域進(jìn)行投影覆蓋。

本文中固定翼無(wú)人機(jī)的偵察設(shè)備安裝在機(jī)身下方，視線在無(wú)人機(jī)對(duì)稱平面內(nèi)并與固定翼無(wú)人機(jī)機(jī)身軸線成一定的角度，如圖4 所示。攝像頭可覆蓋范圍受視野角度，固定角度，飛行俯仰角3 個(gè)因素限制。同時(shí)任務(wù)中對(duì)攝像頭的分辨率可能存在一定要求，所以攝像頭的視線距離也受到一定的限制?？紤]以上因素建立無(wú)人機(jī)的拍攝視野模型。

圖4 固定翼無(wú)人機(jī)的視野模型Fig.4 Sight model of fixed-wing UAV

偵察設(shè)備的視野約束包括：左極限角度θle，右極限角度θri，前極限角度θf(wàn)r，后極限角度θba，拍攝分辨率（即視線距離）R。根據(jù)無(wú)人機(jī)偵察設(shè)備的安裝固定角度和視野角度，無(wú)人機(jī)能夠偵察的角度范圍可以表示為

式中：θf(wàn)ront、θback分別 表示前后視線與 地面夾角的余角；θleft、θright分別表示左右視線與地面夾角的余角；θpit為無(wú)人機(jī)的俯仰角度。在實(shí)際的無(wú)人機(jī)巡航過(guò)程中，可能存在爬升或者俯沖運(yùn)動(dòng)，所以無(wú)人機(jī)的視野模型還要綜合考慮其俯仰角與視野的關(guān)系，才能得到準(zhǔn)確的偵察視野。無(wú)人機(jī)視野模型根據(jù)航向角度和俯仰角度的不同一共有24 種情況，在這24 種情況中，可以分為對(duì)角線航向和非對(duì)角線航向兩類，如圖5 所示。

圖5 兩類無(wú)人機(jī)偵察覆蓋范圍Fig.5 Coverage area of two types of reconnaissance flight

根據(jù)二維航向與水平方向的夾角θhead可以得到包括視野范圍的方形區(qū)域。對(duì)方形區(qū)域內(nèi)的網(wǎng)格進(jìn)行逐一的檢查，如果3 個(gè)條件都能滿足，那么記該網(wǎng)格在該時(shí)間能被偵察到：①網(wǎng)格4 個(gè)頂點(diǎn)都在灰色區(qū)域內(nèi)；②網(wǎng)格4 個(gè)頂點(diǎn)都在視野距離極限R以內(nèi)；③網(wǎng)格4 個(gè)頂點(diǎn)與無(wú)人機(jī)偵察設(shè)備之間沒(méi)有障礙物遮擋。

假設(shè)整個(gè)偵察區(qū)域是邊長(zhǎng)分別為L(zhǎng)x，Ly的矩形，則圖5 中方形區(qū)域的范圍如表1 所示。

表1 方形區(qū)域邊界Table 1 Boundary of square area

θx是無(wú)人機(jī)右視野極限在地面的投影與OX軸正方向的夾角；（x0，y0，z0）為無(wú)人機(jī)當(dāng)前位置。為了利用向量夾角檢查地面某個(gè)點(diǎn)是否在視野范圍內(nèi)，建立點(diǎn)相對(duì)無(wú)人機(jī)位置的向量P，其表達(dá)式如式（4）所示：

式 中：（xp，yp，zp）為待檢查點(diǎn)坐標(biāo)。向量P存在2 個(gè)分量：無(wú)人機(jī)縱刨面上的投影Ph，地面上的投影為Pg。只有2 個(gè)分量滿足式（5）與式（6），才能被判斷為在視野范圍內(nèi)。

其中：h是固定向量，h=［0 0 -1］T；g是無(wú)人機(jī)水平面內(nèi)的航向向量；ωmin，ωmax分別是飛機(jī)縱刨面內(nèi)最小和最大視線偏移角度。各角度和向量關(guān)系如圖6 所示。

圖6 計(jì)算無(wú)人機(jī)視野的角度和向量關(guān)系Fig.6 Angle and vector quantity in calculation of UAV sight

2 無(wú)人機(jī)巡邏覆蓋協(xié)同路徑規(guī)劃方法

2.1 地形網(wǎng)格狀態(tài)表示及路徑點(diǎn)選取策略

區(qū)別于以往的區(qū)域完全覆蓋任務(wù)［22］，區(qū)域監(jiān)視任務(wù)的目的是盡可能多的覆蓋地面區(qū)域并且要著重關(guān)注長(zhǎng)時(shí)間未偵察過(guò)的網(wǎng)格。所以僅僅利用0、1 兩個(gè)狀態(tài)來(lái)表達(dá)網(wǎng)格是否被訪問(wèn)過(guò)是不夠的［23］，在此對(duì)地面網(wǎng)格引入一個(gè)狀態(tài)變量，該變量的值只和無(wú)人機(jī)對(duì)該點(diǎn)偵查的時(shí)間間隔有關(guān)，計(jì)算方式如式（7）所示：

式中：svk(s)為對(duì)地面第k個(gè)網(wǎng)格引入的第s步路徑規(guī)劃后的狀態(tài)變量；tv為網(wǎng)格上次被偵查的時(shí)間點(diǎn)；tc（s）為第s步路徑規(guī)劃的時(shí)間。如果該網(wǎng)格還沒(méi)有被偵察過(guò)，那么tv的值為0，與此同時(shí)該點(diǎn)的svk(s)值為1。

式（7）所表達(dá)的是任務(wù)空間某一網(wǎng)格的狀態(tài)變量，無(wú)人機(jī)每次能夠采集大量的網(wǎng)格信息，所以持續(xù)監(jiān)視任務(wù)的監(jiān)視指標(biāo)可以表示為式（8）：

式中：g（s）是第s步無(wú)人機(jī)能夠偵察覆蓋的網(wǎng)格總數(shù)；J（s）是第s步無(wú)人機(jī)的監(jiān)視指標(biāo)。該式同時(shí)考慮了所有能被覆蓋的網(wǎng)格和被訪問(wèn)的時(shí)間間隔，每一步路徑規(guī)劃的目標(biāo)為最大化J（s）的值。

2.2 長(zhǎng)期未被訪問(wèn)地點(diǎn)的處理策略

如式（8）所示，無(wú)人機(jī)路徑規(guī)劃時(shí)將會(huì)選擇具有最大J（s）指標(biāo)的備選路徑點(diǎn)，因此無(wú)人機(jī)更傾向于在一個(gè)特定的高度飛行，這個(gè)高度上無(wú)人機(jī)能夠覆蓋的地面網(wǎng)格面積最大，由此獲得更大的J（s）值的可能性就會(huì)更高。但是在特殊情況下需要修改J（s）的值以使無(wú)人機(jī)能夠適應(yīng)特殊環(huán)境變化。

當(dāng)某一網(wǎng)格長(zhǎng)時(shí)間（超過(guò)閾值ΔTv）沒(méi)有被訪問(wèn)時(shí)（即tc（s）-tv＞ΔTv），為了使得無(wú)人機(jī)能夠特別注意該網(wǎng)格，J（s）可以表示如式（9）：

根據(jù)式（9），一旦某個(gè)備選網(wǎng)格的可覆蓋面積中存在超過(guò)閾值時(shí)間未訪問(wèn)的區(qū)域，該備選網(wǎng)格會(huì)根據(jù)覆蓋面積對(duì)J（s）進(jìn)行加權(quán)處理，使得無(wú)人機(jī)有更大的概率選擇該備選網(wǎng)格。

2.3 多無(wú)人機(jī)協(xié)同機(jī)制

本文中無(wú)人機(jī)的協(xié)同是全區(qū)域、全過(guò)程進(jìn)行的，實(shí)現(xiàn)了覆蓋效率最大化和無(wú)人機(jī)防撞。所有無(wú)人機(jī)共用同一個(gè)記錄區(qū)域訪問(wèn)信息的矩陣，且都具有采集和更新矩陣數(shù)據(jù)的權(quán)限。為避免發(fā)生多架無(wú)人機(jī)同時(shí)被同一偵察價(jià)值較高的區(qū)域吸引，引入依次規(guī)劃的規(guī)則，一架無(wú)人機(jī)完成規(guī)劃后，立即更新區(qū)域訪問(wèn)信息，給下一架無(wú)人機(jī)作為規(guī)劃參考，實(shí)現(xiàn)多架無(wú)人機(jī)之間的信息分享和協(xié)同偵察。

但是距離較近的無(wú)人機(jī)偵察區(qū)域可能會(huì)產(chǎn)生重疊，當(dāng)兩架或多架無(wú)人機(jī)的第一備選路徑點(diǎn)覆蓋區(qū)域出現(xiàn)重復(fù)時(shí)，當(dāng)前路徑可能為非最優(yōu)路徑。為了解決非最優(yōu)問(wèn)題，并確定無(wú)人機(jī)規(guī)劃的次序，本文參考了文獻(xiàn)［24］中解決多架無(wú)人機(jī)之間飛行沖突的方法，即利用模擬退火算法來(lái)確定無(wú)人機(jī)的次序。

本文采用的是基于運(yùn)動(dòng)方程的局部防撞方法。無(wú)人機(jī)之間的碰撞有2 種情況，分別是節(jié)點(diǎn)處碰撞與路徑交叉碰撞，其形式如圖7 所示。

圖7 2 種碰撞形式Fig.7 Two types of collisions

第1 種碰撞發(fā)生在路徑點(diǎn)處，由于2 架無(wú)人機(jī)在同一時(shí)間選擇了相同的路徑點(diǎn)而產(chǎn)生了碰撞，其特點(diǎn)可以表達(dá)為式（10）：

式中：（xi（t+1），yi（t+1），zi（t+1））為第i架無(wú)人機(jī)在t+1 時(shí)刻的位置信息。

第2 種碰撞發(fā)生在非路徑點(diǎn)，由于2 條路徑產(chǎn)生了交叉，導(dǎo)致碰撞。無(wú)人機(jī)為了達(dá)到協(xié)同效果，執(zhí)行可變速飛行，導(dǎo)致無(wú)人機(jī)執(zhí)行路徑的速率是相等的，一旦2 架無(wú)人機(jī)路徑產(chǎn)生交叉，那么其碰撞就必然會(huì)發(fā)生。其碰撞特點(diǎn)可以由式（11）描述：

每架無(wú)人機(jī)規(guī)劃路徑時(shí)都要避免經(jīng)過(guò)上述運(yùn)動(dòng)方程中涉及到的路徑點(diǎn)，以消除無(wú)人機(jī)之間碰撞的可能。無(wú)人機(jī)在保持協(xié)同偵察和協(xié)同防撞的同時(shí)利用上述的選取策略進(jìn)行路徑規(guī)劃，具體流程如圖8 所示。

圖8 巡邏覆蓋協(xié)同路徑規(guī)劃流程圖Fig.8 Flow chart of patrolling and collaborative coverage path planning algorithm

3 緊急任務(wù)下無(wú)人機(jī)覆蓋路徑規(guī)劃方法

本文考慮在持續(xù)覆蓋任務(wù)中加入一種緊急任務(wù)，其背景是多架無(wú)人機(jī)在執(zhí)行持續(xù)監(jiān)視任務(wù)的某一時(shí)刻，接收到指令中心下達(dá)的針對(duì)視野外超時(shí)區(qū)域或緊急任務(wù)區(qū)域執(zhí)行一次完全覆蓋。選擇距離最近的無(wú)人機(jī)，提高該無(wú)人機(jī)的路徑規(guī)劃優(yōu)先權(quán)。被選中的無(wú)人機(jī)在接近目標(biāo)區(qū)域的同時(shí)，利用設(shè)置動(dòng)態(tài)目標(biāo)點(diǎn)的策略保證持續(xù)監(jiān)視任務(wù)的效率，在抵達(dá)任務(wù)區(qū)域后執(zhí)行覆蓋偵察。在此同時(shí)，其余無(wú)人機(jī)繼續(xù)執(zhí)行原持續(xù)監(jiān)視任務(wù)。

3.1 緊急任務(wù)抵近路徑規(guī)劃和動(dòng)態(tài)目標(biāo)點(diǎn)的設(shè)置

緊急任務(wù)的路徑規(guī)劃分為2 部分：抵達(dá)任務(wù)區(qū)域路徑規(guī)劃和對(duì)區(qū)域進(jìn)行偵察的路徑規(guī)劃。在第1 部分抵達(dá)任務(wù)區(qū)域的過(guò)程中，執(zhí)行緊急任務(wù)無(wú)人機(jī)需要在距離成本允許的情況下，兼顧持續(xù)監(jiān)視任務(wù)。為保證此無(wú)人機(jī)能夠及時(shí)到達(dá)指定區(qū)域開始緊急任務(wù)，為第1 部分設(shè)置距離閾值Lmax，如式（12）所示：

式中：（xc，yc，zc）是緊急任務(wù)區(qū)域形心坐標(biāo)。

被選中的無(wú)人機(jī)每步都要計(jì)算待更新節(jié)點(diǎn)到達(dá)距離其最近的任務(wù)空間節(jié)點(diǎn)的距離，從中選擇滿足式（13）約束的節(jié)點(diǎn)作為待更新節(jié)點(diǎn)。

式中：Lpre是由起點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)的路程；Li是當(dāng)前節(jié)點(diǎn)到達(dá)第i個(gè)待更新節(jié)點(diǎn)的路程；是第i個(gè)待更新節(jié)點(diǎn)到距離其最近的動(dòng)態(tài)終點(diǎn)的路程；n是當(dāng)前待更新節(jié)點(diǎn)的個(gè)數(shù)。3 個(gè)路程相加就是由起點(diǎn)到達(dá)終點(diǎn)的一個(gè)可行路徑的總路程，其小于路程閾值Lmax。

每個(gè)路徑點(diǎn)所對(duì)應(yīng)任務(wù)空間中最近的節(jié)點(diǎn)就是動(dòng)態(tài)目標(biāo)點(diǎn)，如圖9 所示。

圖9 動(dòng)態(tài)目標(biāo)點(diǎn)方法Fig.9 Schematic diagram of dynamic target

圖9 中矩形區(qū)域表示任務(wù)空間，陰影網(wǎng)格是無(wú)人機(jī)每一步飛行所對(duì)應(yīng)的動(dòng)態(tài)目標(biāo)點(diǎn)。每一步路徑規(guī)劃都要更新一次目標(biāo)點(diǎn)坐標(biāo)值（xtar，ytar，ztar）。一旦檢測(cè)到下一步路徑規(guī)劃不能滿足最大距離成本約束或?qū)ぢ肥r(shí)，無(wú)人機(jī)以現(xiàn)在所在節(jié)點(diǎn)為起點(diǎn)，當(dāng)前動(dòng)態(tài)目標(biāo)點(diǎn)為終點(diǎn)，執(zhí)行通過(guò)改進(jìn)A*算法生成的路徑，到達(dá)任務(wù)空間，開始緊急任務(wù)的第2 部分。

在上述緊急任務(wù)的第1 部分中A*算法有2 個(gè)功能：一是檢查從備用路徑點(diǎn)到相應(yīng)的目標(biāo)點(diǎn)的最短路徑是否滿足距離約束，二是當(dāng)所有備用路徑點(diǎn)都不能滿足約束的時(shí)候生成當(dāng)前位置到當(dāng)前目標(biāo)點(diǎn)的最短路徑。

通過(guò)這種路徑規(guī)劃，能夠保證無(wú)人機(jī)覆蓋面積最大的同時(shí)能到達(dá)任務(wù)空間，開始執(zhí)行緊急監(jiān)視任務(wù)。第1 部分抵達(dá)任務(wù)空間的終點(diǎn)（xtar，ytar，ztar）是第2 部分偵察覆蓋的起點(diǎn)。

3.2 基于轉(zhuǎn)角約束的A*算法

A*算法是智能體進(jìn)行軌跡規(guī)劃的一種可靠的啟發(fā)式算法，而在傳統(tǒng)的A*算法中沒(méi)有對(duì)智能體轉(zhuǎn)角約束的考慮。固定翼無(wú)人機(jī)不能進(jìn)行大角度轉(zhuǎn)彎，必須設(shè)計(jì)一種改進(jìn)的A*算法，以適用固定翼無(wú)人機(jī)的飛行方式。

本文兩點(diǎn)之間的路徑規(guī)劃，起點(diǎn)之前可能存在父代方向約束，終點(diǎn)之后也可能存在子代方向約束。為滿足固定翼無(wú)人機(jī)的機(jī)動(dòng)約束，本文中設(shè)計(jì)了一種基于轉(zhuǎn)角約束的A*算法，圖10 給出改進(jìn)A*算法的流程圖。

圖10 具有方向約束的A*算法流程圖Fig.10 Flow chart of optimized A* with directional constraints

與傳統(tǒng)A*算法相比，基于轉(zhuǎn)角約束的A*算中估計(jì)函數(shù)f（n），啟發(fā)函數(shù)h（n）計(jì)算方法不變，但每個(gè)空間網(wǎng)格具有來(lái)自26 個(gè)待擴(kuò)展節(jié)點(diǎn)的代價(jià)函數(shù)gi（n）。改進(jìn)的思路是根據(jù)約束條件對(duì)待擴(kuò)展的節(jié)點(diǎn)進(jìn)行進(jìn)一步的篩選，篩選條件為：①非“-1”狀態(tài)，非“close”狀態(tài)；②滿足轉(zhuǎn)角約束；③從該網(wǎng)格出發(fā)，無(wú)人機(jī)可繼續(xù)飛行一定步數(shù)（不會(huì)出現(xiàn)在某一步無(wú)可選網(wǎng)格的情況）；④如果與終點(diǎn)相鄰，必須滿足接入終點(diǎn)的方向約束。

經(jīng)過(guò)這樣的改進(jìn)能夠使得生成的路徑滿足所有約束條件。算法中加入能夠繼續(xù)更新若干步的條件，目的是給算法留出足夠的轉(zhuǎn)彎空間，防止轉(zhuǎn)彎約束太強(qiáng)導(dǎo)致的算法尋路失敗。其實(shí)質(zhì)為轉(zhuǎn)彎空間加入探索過(guò)程，其避障原理如圖11所示。

圖11 轉(zhuǎn)彎避障原理Fig.11 Principle of obstacle avoidance

圖11 中展示了一種無(wú)人機(jī)駛離障礙物的過(guò)程。當(dāng)無(wú)人機(jī)到達(dá)如圖11（a）位置時(shí)，存在3 個(gè)備用路徑點(diǎn)。圖11（b）展示了無(wú)人機(jī)如果繼續(xù)直行，那么只能向前再探索1 步就會(huì)沖入禁飛區(qū)，所以直行路徑點(diǎn)不可行。圖11（c）展示了無(wú)人機(jī)如果選擇一個(gè)路徑點(diǎn)轉(zhuǎn)向，存在至少一條路徑能繼續(xù)前進(jìn)若干步，此備用路徑點(diǎn)可行。在圖11（d）中無(wú)人機(jī)選擇了圖11（c）分析的路徑點(diǎn)，此時(shí)無(wú)人機(jī)有3 個(gè)備選路徑點(diǎn)，但是只有一個(gè)路徑點(diǎn)能夠繼續(xù)前進(jìn)若干步，無(wú)人機(jī)只能選擇該路徑點(diǎn)駛離。

3.3 緊急監(jiān)視任務(wù)區(qū)域覆蓋路徑規(guī)劃

由于固定翼無(wú)人機(jī)的視野范圍不再是正圓錐且無(wú)法實(shí)現(xiàn)原地轉(zhuǎn)向，使得現(xiàn)有的方法在三維地形環(huán)境中不再適用。本文采用逆向思維，首先確定待飛網(wǎng)格，因?yàn)榭紤]到飛行方向與地形遮擋因素，每段路徑并不能保證完成相應(yīng)覆蓋，隨后再通過(guò)多輪的穿梭飛行，不斷減少待飛網(wǎng)格的數(shù)量，最終實(shí)現(xiàn)對(duì)局部區(qū)域的完全覆蓋。

任務(wù)區(qū)域上空存在一個(gè)由多個(gè)錐體構(gòu)成的空域，每個(gè)錐體代表了每個(gè)地面網(wǎng)格所對(duì)應(yīng)的可能偵察到該網(wǎng)格的空間（是否能偵察到網(wǎng)格與無(wú)人機(jī)的飛行方向有關(guān)）。但是由于地面網(wǎng)格劃分的尺寸遠(yuǎn)遠(yuǎn)小于空中網(wǎng)格尺寸，如此劃分椎體空間會(huì)存在大量的重復(fù)交疊的錐體。所以應(yīng)先將任務(wù)網(wǎng)格放大再確定椎體空間，如圖12 所示。

圖12 緊急任務(wù)區(qū)域和任務(wù)空間Fig.12 Grids of emergency area and cone in task space

圖12 中將地面網(wǎng)格簡(jiǎn)化為與空中網(wǎng)格大小對(duì)應(yīng)的網(wǎng)格，以統(tǒng)一空間尺寸，減少計(jì)算量。無(wú)人機(jī)執(zhí)行緊急任務(wù)的過(guò)程就可視為抵達(dá)椎體空間并在椎體空間中偵察覆蓋的過(guò)程。8 個(gè)頂點(diǎn)都在椎體空間內(nèi)的空中網(wǎng)格定義為待飛網(wǎng)格。覆蓋分為2輪，第1 輪覆蓋目的是穿越所有椎體，盡量覆蓋緊急區(qū)域所有網(wǎng)格。在第1 輪覆蓋完成后，移除已被覆蓋網(wǎng)格所對(duì)應(yīng)的椎體，然后是以完成任務(wù)為目標(biāo)的第2輪覆蓋，分別如圖13與圖14所示。

圖13 第1 輪覆蓋Fig.13 The first time scout

圖14 第2 輪覆蓋Fig.14 The second time scout

如圖13 所示，在第1 輪覆蓋中，無(wú)人機(jī)的路徑規(guī)劃以當(dāng)前位置為起點(diǎn)，以還沒(méi)有訪問(wèn)過(guò)的最近椎體空間中距離最近的待飛網(wǎng)格為終點(diǎn)，往復(fù)進(jìn)行，直到所有的錐體都被訪問(wèn)過(guò)一次，移除已被覆蓋網(wǎng)格所對(duì)應(yīng)的錐體。路徑規(guī)劃中需要利用改進(jìn)的A*算法，生成一段帶有起點(diǎn)方向約束的路徑。任務(wù)前期網(wǎng)格比較密集，所以不對(duì)終點(diǎn)方向進(jìn)行約束，如果約束終點(diǎn)方向會(huì)存在過(guò)多無(wú)用盤旋。第1 輪覆蓋中，不能保證所有椎體都被移除，僅為第2 輪覆蓋做準(zhǔn)備。

如圖14 所示，第2 種覆蓋過(guò)程開始前要重新選擇到達(dá)最近椎體空間成本最小的無(wú)人機(jī)作為任務(wù)機(jī)。任務(wù)機(jī)在進(jìn)入椎體空間時(shí)，終點(diǎn)后子代方向要盡量指向椎體中軸線。在這種約束了終點(diǎn)方向的情況下，無(wú)人機(jī)的視野足夠覆蓋椎體頂點(diǎn)所在的網(wǎng)格。第2 輪覆蓋不對(duì)椎體空間的覆蓋次數(shù)做約束，錐體對(duì)應(yīng)任務(wù)空間被覆蓋完成，則刪除該錐體，直到所有任務(wù)完成。第2 種覆蓋中A*算法會(huì)對(duì)終點(diǎn)方向進(jìn)行約束，提高無(wú)人機(jī)覆蓋地面網(wǎng)格概率。

4 仿真算例

為驗(yàn)證建立模型的合理性和所提出巡邏覆蓋協(xié)同路徑規(guī)劃算法的有效性，進(jìn)行了多組仿真實(shí)驗(yàn)。第1 組仿真算例中，采用了巡邏覆蓋協(xié)同路徑規(guī)劃算法規(guī)劃無(wú)人機(jī)持續(xù)覆蓋路徑，驗(yàn)證了算法有效性，分析了禁飛區(qū)對(duì)算法的影響。第2 組仿真中，應(yīng)用不同數(shù)量的無(wú)人機(jī)執(zhí)行持續(xù)監(jiān)視任務(wù)，計(jì)算特定空間最優(yōu)無(wú)人機(jī)架數(shù)。第3 組仿真中應(yīng)用了緊急任務(wù)覆蓋算法和改進(jìn)的A*算法規(guī)劃了緊急任務(wù)軌跡，驗(yàn)證了算法有效性，對(duì)比了動(dòng)態(tài)目標(biāo)和靜態(tài)目標(biāo)方法的效率。

仿真算例的空間和模型參數(shù)的設(shè)定如表2所示。

表2 模型參數(shù)Table 2 Parameters of model

4.1 持續(xù)覆蓋任務(wù)協(xié)同路徑規(guī)劃結(jié)果

針對(duì)持續(xù)監(jiān)視任務(wù)進(jìn)行了2 次仿真。第1 次仿真應(yīng)用5 架無(wú)人機(jī)對(duì)空間進(jìn)行重點(diǎn)覆蓋。為探索禁飛區(qū)對(duì)覆蓋結(jié)果的影響，第2 次仿真在原有空間的不同高度層中加入一定數(shù)量的禁飛區(qū)。

2 架無(wú)人機(jī)距離太近會(huì)對(duì)其決策產(chǎn)生影響，所以為了消除無(wú)人機(jī)之間的初始干涉，無(wú)人機(jī)的隨機(jī)初始位置之間應(yīng)保持一定距離。為對(duì)比2 次仿真的結(jié)果，無(wú)人機(jī)均從相同的初始位置出發(fā)，如表3 所示。

表3 無(wú)人機(jī)初始位置Table 3 Initial coordinates of UAVs

第1 次仿真中5 架無(wú)人機(jī)在沒(méi)有禁飛區(qū)的空間執(zhí)行持續(xù)偵察覆蓋任務(wù)的軌跡如圖15 所示。

圖15 無(wú)禁飛區(qū)環(huán)境多無(wú)人機(jī)路徑Fig.15 UAVs paths in clear space

從圖15 可以看出，5 架無(wú)人機(jī)的軌跡分布均勻，沒(méi)有出現(xiàn)軌跡空白區(qū)，且無(wú)人機(jī)集中于3.0～3.8 km 的高度層中飛行。圖16 展示了地面網(wǎng)格被覆蓋情況。

圖16 無(wú)禁飛區(qū)環(huán)境多無(wú)人機(jī)覆蓋次數(shù)Fig.16 Coverages of UAVs in clear space

圖16 中顏色越深表示該網(wǎng)格被覆蓋的次數(shù)越多。可見在沒(méi)有禁飛區(qū)的環(huán)境中總體上各網(wǎng)格被覆蓋的次數(shù)相差不大，山丘和山頂被覆蓋的次數(shù)高于溝壑和山谷，海拔高的地區(qū)被覆蓋的次數(shù)高于海拔低的地區(qū)，邊界區(qū)域被覆蓋次數(shù)要少于中心區(qū)域。出現(xiàn)以上現(xiàn)象的原因可總結(jié)為2 點(diǎn)：首先由于考慮了山頂對(duì)于周圍區(qū)域的遮擋作用，導(dǎo)致了每次偵察中總有一些海拔低的地區(qū)被遮擋；其次為了防止無(wú)人機(jī)飛出邊界，在邊界處增加了約束，所以邊界附近的覆蓋次數(shù)較少。

第2 次仿真在不同高度隨機(jī)生成禁飛區(qū)，并在與第1 次仿真相同的初始位置釋放無(wú)人機(jī)，觀察其飛行軌跡和覆蓋情況，如圖17 和圖18所示。

圖17 禁飛區(qū)環(huán)境中多無(wú)人機(jī)飛行軌跡Fig.17 UAVs path in space with no-fly zones

圖18 禁飛區(qū)環(huán)境中多無(wú)人機(jī)覆蓋次數(shù)Fig.18 Coverage of UAVs in space with no-fly zones

在空間中不同高度加入禁飛區(qū)后，無(wú)人機(jī)軌跡中出現(xiàn)了空白區(qū)域，相對(duì)應(yīng)的地面出現(xiàn)了覆蓋盲區(qū)。無(wú)人機(jī)為了躲避禁飛區(qū)執(zhí)行了規(guī)避動(dòng)作，沒(méi)有嘗試去覆蓋禁飛區(qū)附近的網(wǎng)格，而是選擇了更加安全的路徑。

2 次仿真中，無(wú)人機(jī)在任務(wù)開始后都迅速向著同一高度層集中，隨后的所有路徑都集中在這個(gè)高度層內(nèi)。在初始階段，無(wú)人機(jī)為了獲得更大的視野范圍而上升高度，但是由于無(wú)人機(jī)的可視距離有一定的限制，使得無(wú)人機(jī)不能無(wú)限制上升，最終會(huì)停留在某個(gè)高度層。無(wú)人機(jī)集中的高度層是由其搭載偵察設(shè)備的視野參數(shù)和地面障礙物的高度決定的。

第2 次仿真隨機(jī)加入的禁飛區(qū)中，只有一個(gè)對(duì)航路產(chǎn)生了影響，該禁飛區(qū)所在的高度層正好影響了無(wú)人機(jī)所集中的高度層。無(wú)人機(jī)在遭遇禁飛區(qū)時(shí)沒(méi)有選擇降低高度或者是上升高度進(jìn)行規(guī)避，也說(shuō)明了3.0～3.8 km 高度層對(duì)于持續(xù)監(jiān)視任務(wù)來(lái)說(shuō)飛行價(jià)值要遠(yuǎn)遠(yuǎn)高于上下高度層。

為驗(yàn)證禁飛區(qū)對(duì)于巡邏覆蓋協(xié)同路徑規(guī)劃算法路徑規(guī)劃的影響，采集第2 次仿真1 500 步路徑規(guī)劃后地面表示網(wǎng)格被覆蓋狀態(tài)的sv參數(shù)值和平均sv參數(shù)值進(jìn)行對(duì)比，如圖19 所示。

圖19 網(wǎng)格sv參數(shù)和平sv參數(shù)Fig.19 Parameters sv of grids and average parameters sv

深色的條柱代表每個(gè)地面網(wǎng)格此時(shí)的sv參數(shù)值，高度越高，說(shuō)明該網(wǎng)格的sv參數(shù)值越大。淺色平面是整個(gè)區(qū)域的平均sv參數(shù)值。邊界和禁飛區(qū)附近以外區(qū)域的sv值都在空間平均sv值上下。為了避免無(wú)人機(jī)沖出任務(wù)區(qū)域，在邊界處設(shè)立了警戒范圍，無(wú)人機(jī)會(huì)被禁止在邊界附近飛行，這就導(dǎo)致邊界處sv值較大。圖中明顯可見，影響航路的禁飛區(qū)下方的網(wǎng)格sv值存在較大起伏，禁飛區(qū)的存在對(duì)于無(wú)人機(jī)路徑規(guī)劃的影響非常大。

為進(jìn)一步驗(yàn)證存在禁飛區(qū)情況下算法的有效性，整個(gè)區(qū)域平均sv值隨規(guī)劃步數(shù)變化曲線如圖20 所示。

圖20 2 種環(huán)境下sv參數(shù)優(yōu)化曲線Fig.20 Curves of optimized parameters sv in two spaces

由圖20 可知，2 種情況的網(wǎng)格平均sv 值都在極短的時(shí)間內(nèi)驟減，說(shuō)明算法對(duì)sv值具有良好的優(yōu)化行為。在有禁飛區(qū)的情況下，無(wú)人機(jī)對(duì)于指標(biāo)的優(yōu)化具有更大的波動(dòng)，但是波動(dòng)在合理的范圍內(nèi)，不會(huì)對(duì)整體算法優(yōu)化趨勢(shì)產(chǎn)生影響。可以看到隨著路徑規(guī)劃的進(jìn)行，2 條曲線的波動(dòng)都逐漸趨于穩(wěn)定，并且在800 步路徑規(guī)劃之后曲線的下降趨勢(shì)變緩，說(shuō)明此時(shí)整個(gè)區(qū)域都已在無(wú)人機(jī)的持續(xù)監(jiān)視之中。進(jìn)一步分析兩條曲線，發(fā)現(xiàn)無(wú)禁飛區(qū)時(shí)，算法對(duì)空域的覆蓋優(yōu)化程度要優(yōu)于存在禁飛區(qū)的情況，但是差別不明顯。說(shuō)明禁飛區(qū)不會(huì)對(duì)算法有效性產(chǎn)生影響。禁飛區(qū)下方無(wú)人機(jī)由于安全性考慮而長(zhǎng)時(shí)間放棄覆蓋的網(wǎng)格，可以采取緊急任務(wù)指令來(lái)完成覆蓋。

4.2 無(wú)人機(jī)數(shù)量對(duì)于任務(wù)結(jié)果的影響

為確定該任務(wù)空間中任務(wù)無(wú)人機(jī)的最優(yōu)數(shù)量，分別利用3～10 架無(wú)人機(jī)進(jìn)行多次仿真實(shí)驗(yàn)，分別得到多次實(shí)驗(yàn)的sv平均值隨迭代次數(shù)的變化曲線。仿真中發(fā)現(xiàn)無(wú)人機(jī)的初始位置會(huì)對(duì)任務(wù)初期的整體效率產(chǎn)生影響，為了減小初始位置帶來(lái)的影響，在使用不同數(shù)量無(wú)人機(jī)進(jìn)行仿真時(shí)，保證初始位置之間具有足夠的距離，仿真結(jié)果如圖21 所示。

圖21 不同數(shù)量無(wú)人機(jī)的優(yōu)化曲線Fig.21 Curves of optimized parameters for different number of UAVs

圖21 中，無(wú)人機(jī)的數(shù)量由3 架增加到8 架，每增加1 架，地面網(wǎng)格的平均sv狀態(tài)值都有明顯的下降，收斂速度都有明顯的加快。當(dāng)無(wú)人機(jī)數(shù)量由8 架增加到10 架時(shí)，平均sv值優(yōu)化曲線的差別不再明顯，且曲線的收斂趨勢(shì)大致相同?？芍捎诳臻g大小有限，執(zhí)行任務(wù)無(wú)人機(jī)的數(shù)量并不是越多越好，當(dāng)無(wú)人機(jī)達(dá)到一定密度后，繼續(xù)增加無(wú)人機(jī)的數(shù)量不僅不會(huì)使效率明顯提高反而可能會(huì)造成資源的浪費(fèi)。在本算例中，最佳的無(wú)人機(jī)數(shù)量為8 架，過(guò)多的無(wú)人機(jī)會(huì)對(duì)剛覆蓋過(guò)的區(qū)域進(jìn)行重復(fù)覆蓋由此造成重復(fù)工作。所以無(wú)人機(jī)的數(shù)量可以根據(jù)具體偵察間隔和成本要求來(lái)設(shè)定。

4.3 緊急偵察任務(wù)路徑規(guī)劃仿真

無(wú)人機(jī)正常執(zhí)行持續(xù)覆蓋任務(wù)時(shí)，在某個(gè)時(shí)間點(diǎn)設(shè)置需要進(jìn)行緊急覆蓋的區(qū)域，此場(chǎng)景下，各架無(wú)人機(jī)的飛行航路如圖22 所示。

圖22 緊急任務(wù)場(chǎng)景Fig.22 Situation of emergency task

圖22 中，距離任務(wù)區(qū)域最近的5 號(hào)無(wú)人機(jī)被選中執(zhí)行第一輪覆蓋，其路徑由黑色實(shí)線表示，其余無(wú)人機(jī)繼續(xù)執(zhí)行持續(xù)監(jiān)視任務(wù)，其路徑由虛線表示。下面將5 號(hào)無(wú)人機(jī)的飛行軌跡單獨(dú)展示，如圖23 所示。

圖23 緊急任務(wù)無(wú)人機(jī)軌跡Fig.23 UAV path of emergency task

執(zhí)行緊急偵察任務(wù)的5 號(hào)無(wú)人機(jī)為了最大化持續(xù)監(jiān)視任務(wù)效率不會(huì)第一時(shí)間以任務(wù)區(qū)為目標(biāo)飛行，而是當(dāng)距離成本即將超過(guò)極限時(shí)，開始專注朝緊急任務(wù)區(qū)域飛行，在抵達(dá)任務(wù)區(qū)域后，執(zhí)行第1 輪覆蓋，再被選為第2 輪覆蓋任務(wù)機(jī)，完成緊急覆蓋任務(wù)。仿真中發(fā)現(xiàn)，2 輪覆蓋均選擇了同一架無(wú)人機(jī)。分析影響無(wú)人機(jī)決策的網(wǎng)格訪問(wèn)信息，首先發(fā)現(xiàn)第1 輪任務(wù)機(jī)執(zhí)行第1 輪覆蓋的同時(shí)更新了地面訪問(wèn)時(shí)間，降低了該區(qū)域?qū)ζ溆酂o(wú)人機(jī)的“吸引力”，其余無(wú)人機(jī)沒(méi)有理由接近此區(qū)域。同時(shí)任務(wù)空間無(wú)人機(jī)最佳數(shù)量為8 架，空間飽和數(shù)量為10 架（繼續(xù)增加無(wú)人機(jī)數(shù)量，對(duì)偵察效率的提高作用很?。?，仿真中無(wú)人機(jī)數(shù)量為5 架，所以無(wú)人機(jī)間距足夠大。考慮到無(wú)人機(jī)執(zhí)行完第1 輪任務(wù)需要轉(zhuǎn)彎或掉頭執(zhí)行第2輪任務(wù)，但是其成本仍小于派遣其他無(wú)人機(jī)。

圖23 中黑色軌跡是無(wú)人機(jī)接受緊急任務(wù)之前的飛行軌跡，第2 段軌跡表示無(wú)人機(jī)接近緊急任務(wù)區(qū)域的過(guò)程，第3 段軌跡表示無(wú)人機(jī)的盤旋偵察過(guò)程?？梢? 號(hào)無(wú)人機(jī)在接收緊急任務(wù)時(shí)，即第2 段軌跡的開端，并沒(méi)有第一時(shí)間趕往緊急區(qū)域，而是在接近的同時(shí)保證持續(xù)監(jiān)視任務(wù)的效率。當(dāng)5 號(hào)無(wú)人機(jī)檢測(cè)到距離成本即將超過(guò)閾值時(shí)，則以最快的速度抵達(dá)任務(wù)區(qū)域上空開始執(zhí)行緊急任務(wù)。

區(qū)別于以往的全過(guò)程靜態(tài)目標(biāo)點(diǎn)策略，5 號(hào)無(wú)人機(jī)接近段軌跡分為2 個(gè)過(guò)程：一是保證持續(xù)監(jiān)視任務(wù)效率，執(zhí)行動(dòng)態(tài)目標(biāo)點(diǎn)策略；二是為了滿足任務(wù)的時(shí)間約束直接抵達(dá)任務(wù)區(qū)域，執(zhí)行靜態(tài)目標(biāo)點(diǎn)策略。為了驗(yàn)證動(dòng)態(tài)目標(biāo)點(diǎn)策略的可行性和適用性，對(duì)全過(guò)程采用靜態(tài)目標(biāo)點(diǎn)和本文中設(shè)置動(dòng)態(tài)目標(biāo)點(diǎn)的策略進(jìn)行對(duì)比。

執(zhí)行緊急任務(wù)的無(wú)人機(jī)分別采用以上2 種策略飛行，對(duì)表示網(wǎng)格被覆蓋狀態(tài)的參數(shù)sv進(jìn)行采集，并對(duì)比其優(yōu)化效率。2 次對(duì)比實(shí)驗(yàn)中，無(wú)人機(jī)均在第200 步規(guī)劃時(shí)開始執(zhí)行緊急任務(wù)。靜態(tài)目標(biāo)點(diǎn)仿真在第220 步完成緊急任務(wù)，動(dòng)態(tài)目標(biāo)點(diǎn)仿真在第229 步完成緊急任務(wù)，完成緊急任務(wù)后，無(wú)人機(jī)繼續(xù)執(zhí)行持續(xù)監(jiān)視任務(wù)。sv參數(shù)的優(yōu)化效果和路徑規(guī)劃步數(shù)的關(guān)系如圖24 所示。

圖24 動(dòng)態(tài)目標(biāo)點(diǎn)和靜態(tài)目標(biāo)點(diǎn)效率對(duì)比Fig.24 Efficiency comparison of dynamic target and statical target

圖24 中曲線展示了接受緊急任務(wù)（第200 步）后，2 種策略的平均sv參數(shù)變化對(duì)比，由于緊急任務(wù)在第235 步執(zhí)行完畢，故只關(guān)注第200～235 步平均sv參數(shù)的變化，其中直線表示實(shí)驗(yàn)從緊急任務(wù)開始到第235 步規(guī)劃的整體優(yōu)化效率的對(duì)比。從圖21 可見無(wú)人機(jī)接受任務(wù)后，無(wú)論采用何種策略，全區(qū)域的平均sv參數(shù)值有明顯的升高趨勢(shì)，但是對(duì)于靜態(tài)目標(biāo)點(diǎn)來(lái)說(shuō)，其sv參數(shù)值升高的更加明顯，因此，采用動(dòng)態(tài)目標(biāo)點(diǎn)策略時(shí)，無(wú)人機(jī)執(zhí)行覆蓋任務(wù)的效率明顯高于靜態(tài)目標(biāo)點(diǎn)模式。本算例中，空間較小且空間網(wǎng)格劃分稀疏，導(dǎo)致接受任務(wù)的無(wú)人機(jī)距離任務(wù)區(qū)域較近，不需要飛行太遠(yuǎn)的距離便能抵達(dá)緊急區(qū)域，所以sv參數(shù)變化也不大。當(dāng)無(wú)人機(jī)多次執(zhí)行緊急任務(wù)后，兩曲線差別會(huì)更加明顯。仿真實(shí)驗(yàn)說(shuō)明動(dòng)態(tài)目標(biāo)點(diǎn)的方法適用于緊急任務(wù)的路徑規(guī)劃，并且要優(yōu)于靜態(tài)目標(biāo)點(diǎn)的規(guī)劃方式。

5 結(jié)論

本文研究了固定翼無(wú)人機(jī)巡邏覆蓋協(xié)同路徑規(guī)劃方法。以網(wǎng)格化空間為背景建立無(wú)人機(jī)飛行和偵察模型?？紤]障礙物的遮擋，攝像頭的安裝角度和拍攝角度建立無(wú)人機(jī)的偵察覆蓋模型。設(shè)計(jì)了多無(wú)人機(jī)協(xié)同偵察和防碰撞模型。引入了網(wǎng)格狀態(tài)值的概念，用以描述各網(wǎng)格被覆蓋的時(shí)間信息，并以此信息為基礎(chǔ)，建立了覆蓋指標(biāo)。另外，針對(duì)超過(guò)一定時(shí)間未被訪問(wèn)的特殊方格，對(duì)覆蓋指標(biāo)進(jìn)行了修正，使得特殊網(wǎng)格能有更大概率在近期被訪問(wèn)。當(dāng)某一區(qū)域發(fā)生緊急情況時(shí)，利用設(shè)置動(dòng)態(tài)目標(biāo)點(diǎn)的策略，使得無(wú)人機(jī)在滿足距離成本限制的同時(shí)也順便執(zhí)行持續(xù)覆蓋任務(wù)。并在可能覆蓋緊急區(qū)域的倒三角錐型上空進(jìn)行兩輪飛行，實(shí)現(xiàn)對(duì)緊急區(qū)域的完全覆蓋。

在仿真中，通過(guò)設(shè)置執(zhí)行持續(xù)監(jiān)視任務(wù)和處理應(yīng)急情況的場(chǎng)景，驗(yàn)證了巡邏覆蓋協(xié)同路徑規(guī)劃算法的有效性，以及算法在不同空間環(huán)境中良好的適用性。本文提出的新的緊急任務(wù)路徑規(guī)劃方法，能夠解決禁飛區(qū)帶來(lái)的丟失視野問(wèn)題，并在緊急任務(wù)規(guī)劃中應(yīng)用動(dòng)態(tài)目標(biāo)點(diǎn)策略，實(shí)現(xiàn)保證持續(xù)監(jiān)視任務(wù)效率的同時(shí)，完成緊急覆蓋任務(wù)。同時(shí)，持續(xù)監(jiān)視任務(wù)能夠應(yīng)用于各種實(shí)際環(huán)境中。將來(lái)可以繼續(xù)深入研究巡邏覆蓋協(xié)同路徑規(guī)劃算法，發(fā)展算法的使用范圍來(lái)解決各種類似的問(wèn)題。