一種改進的多無人機覆蓋航跡規劃方法

張小孟，胡永江，李文廣，張世華，龐強偉

(陸軍工程大學石家莊校區 無人機工程系，石家莊 050003)

無人機以其造價低、體積小、零傷亡等優勢被應用于現代戰爭的各個方面，如偵察監視[1]、通信中繼[2]、精確打擊[3]等，具有巨大的發展潛力和應用前景。在無人機作戰運用中，多無人機區域覆蓋偵察任務[4]主要是指在任務區域面積較大，區域內目標屬性未知，又需要得到完整任務區域信息的背景下，對任務區域進行全覆蓋偵察。在執行任務前首先要為各任務機規劃飛行航跡，即多無人機區域覆蓋航跡規劃問題，規劃的要求是根據任務區域大小、形狀、無人機數量以及載荷性能，結合相應的航跡規劃算法，規劃得到各個任務機的飛行路徑，使無人機可完全偵察覆蓋任務區域，且滿足飛行路徑代價最小的指標要求。

現階段國內外對于多無人機區域覆蓋航跡規劃問題的解決方法一般分為兩步[5,10]：第1步根據無人機的數量和無人機的偵察能力等要素，對任務區域進行分解，得到等無人機數量的子區域。第2步在各個子區域內，規劃相應任務機的飛行航跡。對任務區域的分解，文獻[6]提出了一種基于任務性能和子區域寬度的任務區域分解算法，將凹多邊形分解為多凸多邊形，解決凹多邊形的區域覆蓋偵察問題。文獻[7]提出一種區域分解方法，實現了三角形任務區域的快速分解，僅討論了三角形任務區域的分解方法。文獻[8]提出了一種以無人機飛行時間最短為目標的區域分解和分配算法，保證了整體偵察時間最短。但該方法僅適用于矩形任務區域，算法普適性弱。文獻[9-10]根據無人機初始位置和各任務機的搜索面積要求對任務區域進行分解，但是分解算法比較復雜，分解效率低。

上述方法可以在某些方向上解決多無人機區域覆蓋偵察航跡規劃問題，但仍存在以下不足：① 分解時只是針對特定區域形狀如矩形或者三角形，普適性比較差;② 分解方法比較復雜，分解效率低。

針對上述問題，本文提出了一種改進的多無人機覆蓋航跡規劃方法，可用于解決多無人機偵察凸多邊形(凹多邊形可以首先分解為多個凸多邊形)區域內覆蓋航跡規劃問題，且該方法相對于現有的基于凸多邊形分解的多無人機覆蓋航跡規劃方法具有代價低、效率高的特點。

1 任務模型

多無人機區域覆蓋航跡規劃問題可以描述為：給定任意有界封閉區域S和N架同構或異構無人機UAVn(n=1,2,…,N)。要求無人機攜帶偵察載荷，從地面站位置起飛，對封閉區域S進行覆蓋偵察，后返回起飛點。要求設計一種航跡規劃方法，可為各任務機規劃相應的偵察航跡，實現N架無人機滿足整體路徑代價最小的情況下，對區域S完全覆蓋偵察。

為了簡化問題模型，作出以下合理假設：N架無人機為同構無人機且攜帶相同的偵察載荷。無人機在執行任務時，載荷鏡頭保持垂直向下。所有無人機從相同的地面站起飛，回到地面站。偵察覆蓋區域是凸多邊形任務區域(三角形、矩形均屬于凸多邊形)。

針對載荷鏡頭保持垂直向下的偵察模式，建立相應的載荷模型，如圖1所示。無人機沿X方向飛行，H為無人機的飛行高度，O為載荷中心在地面上的垂直投影，矩形區域ABCD為無人機的探測區域，其中運動方向上的探測步長L，探測寬度W。

圖1 載荷探測模型示意圖

約束條件為：

1) 單架無人機無人機執行任務的能力約束，無人機攜帶能源有限，因此具有航程限制，在其載荷和飛行高度確定的情況下，無人機執行掃描任務具有最大限制:

cn

(1)

其中C表示無人機偵察覆蓋的最大能力。

2) 無人機最小轉彎半徑約束，無人機在飛行速度一定的情況下在空中轉彎時受離心力作用，具有最小轉彎半徑約束：

rn≥Rmin

(2)

其中Rmin為無人機的最小轉彎半徑。

無人機覆蓋偵察的目的是對任務區域進行完全覆蓋偵察，使的所有執行偵察任務的無人機飛行路徑代價和最小，其目標函數為

minf=min(L)=min(L1+L2+L3)

(3)

其中，L為所有無人機總的路徑長度；L1為轉彎過程的路徑長度和；L2為任務區域掃描線的長度和；L3為無人機從地面站到任務區域以及完成任務后返回地面站的距離和。

2 區域分解方法

文獻[7-8]中，均提出了相應的區域分解方法，但都只是針對某種特定形狀的任務區域(如三角形、矩形)進行分解，不適用于其他形狀的任務區域。文獻[11]從能量、飛行路程和時間的角度分析了無人機轉彎過程的低效性，因此在進行無人機覆蓋航跡規劃時，應當盡量規劃較少的轉彎次數，用來降低偵察時間和路程代價，提高偵察效率。為減少所有區域內部任務機的轉彎次數，本文提出了一種分解方法，可有效解決各類凸多邊形任務區域的分解問題(三角形、矩形均屬于凸多邊形)，依據凸多邊形寬度和最小的方向確定區域分解方向，根據區域的大小以及各任務機執行任務的能力確定子區域數量，來實現目標區域的分解，如圖2所示，一個凸多邊形任務區域沿寬度方向分解為n個子區域。

圖2 凸多邊形區域分解示意圖

2.1 區域分解方向

文獻[11]給出了凸多邊形跨度和寬度的定義：在平面上兩條相距足夠遠的平行線向凸多邊的中心靠攏，兩條平行線均與凸多邊形相交即停止移動，此時兩條平行線之間的距離即為凸多邊形的跨度Ds。所有跨度中的最小值即為凸多邊形的寬度d。如圖3所示，凸多邊形兩邊的平行線稱為凸多邊形的支撐平行線，且凸多邊形的寬度只可能出現在“點邊式”跨度中。

圖3 凸多邊形的跨度和寬度

命題：對一凸多邊形，任意分解成多個子凸多邊形后，各個子凸多邊形的寬度和不小于原凸多邊形寬度。

首先考慮將任意凸多邊形分解為兩個凸多邊形的情況。假設原凸多邊形為P，寬度為d，兩個子凸多邊形分別為P1、P2，對應的寬度為d1、d2。

根據確定子凸多邊形寬度所對應的凸多邊形頂點和邊與分割線的關系，有以下幾種情況：

情況1：至少有一個子凸多邊形寬度所對應的頂點和邊都不在分割線上；

情況2：兩個子凸多邊形寬度所對應的頂點或邊在分割線上，又可細分為以下3種情形：

Case1：兩個子凸多邊形寬度所對應的邊都在分割線上；

Case2：一個子凸多邊形寬度所對應的邊在分割線上，另一個子凸多邊形寬度所對應的頂點是分割線與原凸多邊形的交點；

Case3：兩個子凸多邊形寬度對應的頂點都是分割線與原凸多邊形的交點，但兩個子凸多邊形寬度對應的頂點有可能是同一頂點，也有可能不相同。

對情況1證明如下：

如圖4所示，假設子凸多邊形P1寬度所對應的頂點和邊都不在分割線上，又P1的寬度是其本身的最小跨度，而切割線并沒有使P1產生更小跨度，所以新凸多邊形P1的寬度為原凸多邊形P的寬度，即：d1=d，又d2>0，則d1+d2>d。

圖4 情況1

對情況2證明如下：

對Case1有如下形式：作平行于分割線的原凸多邊形P的兩條支撐平行線，如圖5，則兩個子凸多邊形P1、P2的寬度之和d1+d2為原凸多邊形P的兩個支撐平行線的距離即原凸多邊形的一個跨度，根據跨度的定義可得d1+d2≥d。

圖5 情況2(Case1)

對Case2有如下形式:假設子凸多邊形P1的寬度所對應的邊在分割線上，子凸多邊形P2寬度所對應的頂點是分割線與原凸多邊形的交點。

如圖6：過子凸多邊形P2寬度所對應的頂點作P2寬度所對應的邊的平行線以及與其平行的原凸多邊形P的兩條支撐平行線，假設子凸多邊形P2的寬度所對應的頂點到另一條支撐平行線的距離為d3，則d2+d3為兩個支撐平行線的距離即原凸多邊形P的一個跨度，按寬度的定義得d2+d3≥d，按平行線平移d3至d3′ 位置，可得在以d3′ 為直角邊直角三角形中，斜邊為d1的一部分，即d1>d3′=d3。又因為d2+d3≥d，則d1+d2≥d。

圖6 情況2(Case2)

對Case3有如下形式：

當兩個子凸多邊形寬度所對應的頂點不是同一個點。如圖7：分別作與兩個子凸多邊形寬度所對應的邊平行的原凸多邊形P的兩組支撐平行線，再過兩個子凸多邊形各自寬度所對應的頂點作其本身寬度所對應的邊的平行線，假設與子凸多邊形P1寬度所對應的邊平行的原凸多邊形的一組支撐平行線的距離小于另一組，則同情況2(Case2)：d1+d3為原凸多邊形的一個跨度，d1+d3≥d，平行線內同時平移d1至d1′，d3至d3′位置。可得在以d3′為直角邊的直角三角形中，斜邊為d2′的一部分，則d2′=d2>d3′ =d3。又因為d1+d3≥d，則d1+d2≥d。

圖7 情況2(Case3)假設1

當兩個子凸多邊形寬度所對應的頂點是同一個點。

如圖8：分別向兩邊延長兩個子凸多邊形寬度所對應的邊，再向兩邊延長兩個子凸多邊形的寬度所對應頂點所在的原凸多邊形的邊，三條延長線相交為一個三角形，稱為原凸多邊形的外切三角形，可以得出原凸多邊形的寬度d必然小于或等于其外切三角形在凸多邊形定義下的寬度，因為三角形最長邊上的高是其最小跨度，設為H，則H≥d；將問題轉化為：三角形邊上的任意一點到另外兩個邊上的距離之和d1+d2大于三角形最長邊上的高H，即d1+d2≥H。

圖8 情況2(Case3)假設2

根據點是否在三角形最長邊上分為兩種情況：點在最長邊上如圖9：設AB=c，BC=a，AC=b，BD=e,AD=x；由三角形性質可知b≥c,b≥a;由凸多邊形寬度的定義可知在三角形CBD中寬度的在CB上則a為三角形CBD的最長邊，即：a>b-x,a>e;同理在三角形ABD中有：c>x,c>e;d1=x*sin(A),d2=(b-x)*sin(C),H=a*sin(C);

(4)

當a≥c時：

(5)

當a

(6)

則得證。

圖9 情況2(Case3)假設2(1)

點不在最長邊上

如圖10：設AB=c，BC=a，AC=b，BD=e,AD=x，∠ACB記為∠C； 由三角形性質可知c≥a,c>b; 由凸多邊形寬度的定義可知在三角形CBD中寬度的在CB上則a為三角形CBD的最長邊，即:a>b-x,a>e; 同理在三角形ABD中有：c>x,c>e;d1=x*sin(A),d2=(b-x)*sin(C),H=a*sin(C);

(7)

又c≥a,則：

(8)

即：

(9)

得證。

圖10 情況2(Case3)假設2(2)

則可得當頂點在同一個點上時d1+d2≥H≥d，得證。

綜上，將凸多邊形分解為兩個子凸多邊形后，子凸多邊形的寬度之和不小于原凸多邊形的寬度，即d1+d2≥d。

同理，將子凸多邊形繼續分解為n個子凸多邊形，由數學歸納法很容易得出d≤d1+d2≤d1+d2+d3≤…≤d1+d2+…+dn。

證畢。

由此可以得出：沿著垂直凸多邊形寬度方向分解得到的各個子凸多邊形寬度和的最小值等于原凸多邊形的寬度，則說明凸多邊形區域的最優分解方式是沿著凸多邊形寬度的垂直方向進行分解。

2.2 區域分解數量

在無人機航程及載荷性能一定的條件下，其所能偵察覆蓋的面積也是一定的，所以各子區域的面積也應該符合無人機所能偵察覆蓋的能力范圍。而無人機可偵察覆蓋的能力是根據無人機自身的性能、飛行速度、高度以及載荷的參數決定。用C表示無人機偵察覆蓋的能力。用p表示額外損耗率，即在規劃任務時需留有一定裕度用以應付突發情況和任務機往返。用S表示任務區域的總面積。

則子區域數量為

(10)

確定了子區域的數量，則在垂直區域寬度方向將任務區域按照面積等分原則，分成n份即可。

3 航跡規劃方法

3.1 偵察掃描方式

“Z”字形模式[12]如圖11所示，是一種簡潔實用的覆蓋方式，也是國內外研究無人機覆蓋偵察最主要的方式之一，其優點是無人機在覆蓋偵察過程中對任務區域可以完全覆蓋偵察且重復率小。

圖11 Z字形掃描模式

當無人機以不同飛行方向偵察同一任務區域時，其路徑代價也不同，如圖12所示。文獻[11]證明了沿著垂直于寬度方向偵察，無人機的轉彎次數較小，飛行路程短，偵察效率高。

圖12 飛行方向對航跡的影響示意圖

3.2 η形轉彎方法

文獻[13]針對任務機的最小轉彎半徑Rmin以及和任務載荷有關的航帶間距和旁向重疊率的關系，提出了η形轉彎方法，并證明了η形轉彎方法相對其他轉彎方法的優越性。轉彎方式如圖13所示。

圖13 η形轉彎方法示意圖

4 方法步驟

一種改進的多無人機覆蓋航跡規劃方法步驟如圖14所示：

圖14 航跡規劃方法步驟框圖

步驟1確定分解方向。根據任務區域的坐標，計算凸多邊形所有的跨度，其中跨度最小的方向作為凸多邊形寬度的方向，凸多邊形的分解方向便是寬度的垂直方向。

步驟2求解子區域數量。根據任務區域的面積和無人機執行任務的能力及其額外損耗率，求解無人機數量即區域分解數量。

步驟3按照由步驟1、步驟2求解的區域分解方向和分解數量進行任務區域分解。

步驟4規劃各任務航跡。根據起始位置坐標和無人機最小轉彎半徑，無人機高度以及載荷參數，按照“Z”字形覆蓋方式進行各區域內部航跡規劃。

5 仿真實驗

5.1 實驗設置

實驗平臺為Inter Core i5-7300HQ CPU,8GB,64位Win10操作系統惠普筆記本。編程工具為Matlab R2017b(64位)。

仿真實驗的參數來源于XR-4型無人機，主要參數如表1所示。

表1 仿真參數設置

凸多邊形任務區域頂點坐標分別是(2 800,200)，(4 200,600),(5 800,4 000),(4 800,5 800),(4 200,5 600),(1 000,3 400)。地面站坐標為(1 000,1 000)，以上坐標的單位均是m。

5.2 仿真結果及分析

圖15和圖17分別為分4個子區域和3個子區域時用本文提出的最小寬度和分解法所得的多無人機覆蓋掃描航跡，圖16和圖18分別為分4個子區域和3個子區域時用文獻[8]所提出的凸多邊形分解法所得的多無人機覆蓋掃描航跡。其路徑代價如表2所示。

圖15 分4個子區域時最小寬度和分解方法

圖16 分4個子區域時凸多邊形分解法

圖17 分3個子區域時最小寬度和分解方法

圖18 分3個子區域時凸多邊形分解法

表2 兩種區域分解方法的航跡路徑代價

結果分析如下：

1) 數據L1為兩種分解法轉彎過程的飛行路徑代價，可以看出由于分解方式的不同轉彎過程的路徑代價差距非常大，所提最小寬度和分解法的轉彎過程路徑代價和原有的凸多邊形分解法轉彎過程路徑代價差距非常大，可以說明最小寬度和分解法的優越性。

2) 數據L2可以看出掃描線路徑代價基本相同，進一步驗證了對于覆蓋掃描方式來說，對掃描效率影響的主要因素不是直線掃描部分，而是轉彎部分。

3) 數據L為兩種分解法的總路徑代價，可以看出最小寬度和分解法比凸多邊形分解法路徑代價減少了5.14%和3.72%，表明最小寬度和分解法可以有效降低路徑代價，對任務完成有利。

4) 數據n為轉彎次數，可以看出最小寬度和分解法轉彎次數明顯少于原有的凸多邊形分解法，有效提高了無人機的偵察效率。

5) 從仿真損耗時間t可以看出，最小寬度和分解法的仿真損耗時間遠遠少于與原有的凸多邊形分解法的損耗時間，提高了航跡規劃效率。

6 結論

1) 通過證明凸多邊形任意分解成多個子凸多邊形后，各個子凸多邊形的寬度和不小于原凸多邊形寬度，得出沿寬度方向分解時，子區域寬度和最小。

2) 使用所提分解方法根據無人機的能力和任務區域的大小來確定分區的個數，使無人機在任務區域內掃描的總轉彎次數最少，相對于現有的分解方法路徑代價小，算法效率高。

3) 在各個區域內部使用“Z”字形掃描方式，根據最小轉彎半徑結合η形轉彎方法，使子區域內部偵察掃描效率更高。

4) 在今后的研究中可進一步討論異構無人機根據能力大小分區的區域配置以及多無人機覆蓋偵察多區域的任務分配以及路徑規劃。