帶定位誤差約束的多無人機快速協同航跡規劃

顧 偉，吳 靖，李 晟，趙嘯宇

(1. 中國人民解放軍第31113部隊，江蘇 南京210018；2. 軍事科學院國防科技創新研究院，北京 100091)

1 引言

近年來，無人機由于具有環境要求低、操作簡單不易出錯、靈活可靠成本低等特點，在各領域都獲得了廣泛應用[1]。但隨著任務環境越來越復雜、任務要求越來越高，單個無人機的有限容量已經不能夠滿足日益復雜的任務需求，利用多無人機協同執行任務成為了重要發展趨勢。特別是在軍事應用中，利用多架無人機協同執行偵察、定位、打擊等任務，可以有效提高任務完成質效，確保戰場優勢[2，3]。

文獻[4]研究了多無人機協同覆蓋航跡規劃問題，利用幾何方法進行了求解。文獻[5]研究了在多無人機的任務執行能力、能源資源和所受威脅等約束下的多無人機協同任務規劃問題，采用改進的遺傳算法進行求解。文獻[6]以無人機的飛行總航程、攻擊目標收益、完成任務時間和執行任務時的威脅代價為子目標函數，然后將多目標規劃問題轉化為單目標規劃，運用改進的遺傳算法進行求解。文獻[7]利用幾何運動模型研究了多無人機對組網雷達的協同干擾問題。文獻[8]引入位置、速度和航向作為協同變量，設計了具有線性混合器的編隊保持控制器，實現了編隊隊形的精確保持。文獻[9]利用多無人機與目標之間的距離，實現了目標位置估算。

學者們針對不同的應用場景進行了研究，考慮了很多不同的約束條件，包括無人機的轉彎半徑約束、障礙物約束等，但是對實際廣泛存在的定位誤差約束的研究比較少。在戰場環境中，定位誤差的存在將極大影響任務完成質量，甚至會直接導致任務失敗。本文重點研究在定位存在誤差情況下的多無人機協同航跡規劃問題。

2 問題描述

2.1 打擊問題

對敵方某一軍事目標進行打擊摧毀，要求位于目標附近的幾架無人機快速實施打擊任務。為保證打擊效果及避免提前暴露，需要所有無人機同時(在較小時間差內)到達目標位置并執行打擊。已知，受限于系統結構限制，無人機的定位系統無法對自身進行精準定位，并且誤差將累積。而當定位誤差積累到一定程度，將偏離預定航線，導致任務失敗。因此，無人機在飛行過程中需要對定位誤差進行校正。

2.2 約束分析

以一架無人機為例，無人機的出發點為A點，目標點為B點。其在飛行中受到約束如下：

1)無人機在飛行時存在定位誤差，包括垂直誤差和水平誤差。無人機每飛行1m，垂直誤差和水平誤差各增加δ個單位。為保證打擊的精準性，要求無人機在到達目標點B時垂直誤差和水平誤差均應小于θ個單位。為簡化問題，假設當垂直誤差和水平誤差均小于θ個單位時，無人機仍能夠按照規劃路徑飛行；

2)無人機在飛行過程中需要對定位誤差進行校正。飛行區域中存在一些已知校正點(如圖1，綠的點為水平誤差校正點，藍色的點為垂直誤差校正點)，當無人機到達校正點即能夠根據該位置的誤差校正類型進行誤差校正。若垂直誤差、水平誤差都能得到及時校正，則飛行器可以按照預定航線飛行，通過若干個校正點進行誤差校正后最終到達目的地；

3)在出發地A點，飛行器的垂直和水平誤差均為0；

4)飛行器在垂直誤差校正點進行垂直誤差校正后，其垂直誤差將變為0，水平誤差保持不變；

5)飛行器在水平誤差校正點進行水平誤差校正后，其水平誤差將變為0，垂直誤差保持不變；

6)當飛行器的垂直誤差不大于α1個單位，水平誤差不大于α2個單位時才能進行垂直誤差校正；

7)當飛行器的垂直誤差不大于β1個單位，水平誤差不大于β2個單位時才能進行水平誤差校正；

8)無人機的最小轉彎半徑為200m。

圖1 單架無人機飛行區域示意圖

3 模型建立

3.1 啟發式數據處理

由于必須經過校正點，因此這是一個離散空間搜索問題。首先計算任意兩點間的距離，由于無人機存在轉彎半徑約束，無法瞬間改變速度方向，因此計算任意兩點間的最短距離時必須同時考慮無人機的速度方向。為了便于模型建立和計算，引入啟發式，無人機在各點的方向均指向目標點。

在二維平面上，Dubins[10]幾何地給出了固定初始和最終位置及速度方向的光滑最短路徑。針對問題中帶曲率的三維最短路徑，SikhaHota[11]給出了在給定初始和最終構型參數的情況下，若兩點間距足夠遠(距離大于四倍曲率半徑)，在給定曲率約束下，計算三維空間中的最優路徑的方法。運用該方法對離散點數據進行預處理。

表1 符號說明

3.2 規劃模型

3.2.1 符號說明

3.2.2 混合整數規劃模型

根據題目中的優化目標和約束要求，建立如下航跡規劃的混合混合整數規劃模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

M(1-xkij)+Δxkj≥δdij+Δxki·li，?k，i，j

(8)

M(1-xkij)+Δykj≥δdij+Δyki·(1-li)，?k，i，j

(9)

Δxki≤α2，i∈V，?k

(10)

Δyki≤α1，i∈V，?k

(11)

Δxki≤β2，i∈L，?k

(12)

Δyki≤β1，i∈L，?k

(13)

Δxkn≤θ，i∈L，?k

(14)

Δykn≤θ，i∈L，?k

(15)

(16)

penalty≥0

(17)

其中，式(1)表示最小化所有無人機航跡長度之和。式(2)和(3)表示每個點最多只能經過一次，點本身不存在邊，即無人機不能在一個點上繞圈。約束(4)要求除出發點和終點外，航跡要實現節點的流平衡，即進入該節點的次數等于出于該節點的次數。約束(5)、(6)和(7)要求無人機必須從出發點出發，最終在終點停止，并且不能從終點飛往其它節點。約束(8)和(9)為無人機誤差傳遞約束，無人機在一個節點的水平和垂直誤差等于前一個節點校正后誤差加上從前一節點到本節點的飛行距離造成的誤差之和，當上一個節點為水平誤差校正點時，校正后水平誤差變為0，垂直誤差不變。當上一個節點為垂直誤差校正點時，校正后垂直誤差變為0，水平誤差不變。約束(10)至(15)要求飛行器在垂直誤差校正點、水平誤差校正點和終點要小于允許的垂直誤差和水平誤差最大值。約束(16)表示所有無人機軌跡長度要盡可能平均，即與平均值的差的絕對值之和不能超過參數γ。式(17)中penalty是為了便于模型求解引入的懲罰因子。在目標函數(1)中，只有當懲罰因子penalty為零時才能取到最優值。

直觀的目標應該是幾條航跡中的最大值最小，而本模型是幾條航跡之和最小。一方面是因為這樣便于模型求解，航跡最大值最小是一個非線性問題，不符合快速航跡規劃的要求。另一方面，約束是航跡差較小，極端情況航跡差為零時，航跡和最小和航跡最大值最小是等價的，因此當航跡差較小時，兩者差別在可接受范圍之內。同理，在航跡差約束的表達上，理論上是最長航跡減最短航跡的差小于一個參數，而本模型實際采用了與平均值差的絕對值之和小于一個參數。采用以上兩個替換實現了在建模時提高模型的可解性。利用懲罰因子penalty，將約束放到目標函數中進行考慮實現了在模型求解時提高模型的可解性。

綜合以上手段可以實現模型的快速求解，從而達到快速航跡規劃的目的。

4 實驗分析

4.1 實驗參數

校正點位置數據采用2019年中國研究生數學建模競賽F題(單無人機航跡規劃)附件二。原始數據如表2，基于三維Dubins曲線數據預處理(假定每個點的方向均指向目標點)后收據如表3所示。

表2 原始數據

表3 預處理后數據

實驗采用JAVA語言調用CPLEX的API進行航跡規劃混合整數規劃模型求解。在配置為CORE i7 8550U，主頻2.0GHZ，8GB內存的電腦上，運行時間均為300s。其它實驗參數如表4所示。

表4 實驗參數

4.2 實驗結果及分析

4.2.1 無人機初始位置的影響實驗

設置3架無人機分別從點0，點2，點48出發，前往點326。無人機1的航跡為：0-184-163-114-8-309-305-123-45-160-92-93-61-292-326，航跡長110140.79；無人機2的航跡為：2-40-290-209-8-309-121-123-45-160-191-92-93-61-292-326，航跡長110126.97。無人機3的航跡為：48-56-58-8-309-305-123-45-160-191-92-93-61-292-326，航跡長110127.25。航跡間最大差值為13.82。

圖2 三架無人機實驗結果(0、2、48出發)

圖3 兩點之間航跡示意圖

圖2的結果圖由于比例原因(轉彎半徑相對地圖空間太小)，看不到無人機轉彎，隨機找兩個點，中間航跡如圖3所示。任意兩點之間的航跡均由切出弧、弧切線和切入弧構成。

圖4 中間航跡點切入弧與切出弧相接示意圖

對于每個中間航跡點都是兩個圓弧的交點，圖4顯示了半徑為200的輔助圓。

設置3架無人機分別從點23，點102，點152出發，前往點326。無人機1的航跡為：23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航跡長140564.83。無人機2的航跡為：102-26-206-3-281-197-112-296-205-171-168-115-160-92-93-61-292-326，航跡長140544.29。無人機3的航跡為：152-23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航跡長140561.28。航跡間最大差值為20.54。

圖5 三架無人機實驗結果(23、102、152出發)

設置3架無人機分別從點0，點1，點2出發，前往點326。無人機1的航跡為：0-163-114-8-309-305-123-45-160-92-93-61-292-326，航跡長109405.51。無人機2的航跡為1-200-122-316-98-76-6-12-216-279-302-161-326，航跡長109408.27。無人機3的航跡為2-56-290-158-8-309-305-123-231-160-92-93-61-292-326，航跡長109389.22。航跡間最大差值為19.05，實際運行時間91秒。

圖6 三架無人機實驗結果(0、1、2出發)

上述3個實驗表明：1)無人機初始位置會影響航跡的長度；2)本模型可以在較短時間內為任意起點的三架無人機規劃出滿足約束條件的協同航跡。

4.2.2 無人機數量的影響實驗

在三架無人機的航跡規劃實驗中，前兩個運行300秒獲得了可行解(懲罰因子penalty為0的解)，第三個實際運行91秒，得到了最優解。初始位置會對求解速度有影響，但是并不是問題規模的決定因素。從理論上可以分析出，問題規模(搜索空間)將隨無人機的增加而大大增長。下面對無人機的數量對模型實際求解時間進行分析，以驗證理論上的結論。對于航跡差參數γ，取每架無人機航跡長度到平均值的差值為10。

初始分別設置5架、7架、10架無人機，設置不同運行時間，獲得幾次結果如表6所示。

表6 實驗結果

五架無人機在運行300秒時無法獲得可行解，運行500秒才能獲得可行解，說明問題規模確實會隨著無人機數量的增加而增加。五架無人機運行500秒獲得可行解，七架無人機運行1000秒獲得可行解，十架運行2000秒才能獲得可行解，說明問題規模的增長并不是呈線性的。當然，可行解并不是唯一確定的，選取的運行時間也都是間隔很大的離散點，并不能算是嚴格證明，但是也足夠表明問題規模隨無人機的數量增加而大大增加。

5 總結展望

本文模型可用于解決多無人機在多約束條件下的時序到達問題。存在的不足是，首先在數據預處理時，引入三維Dubins曲線，精確解得因轉彎造成的航跡變化。但是三維Dubins曲線的入射速度方向與出射速度方向應該均為決策變量，為簡化計算量，提升求解效率，本文假設了速度方向均朝向終點方向，在以后的研究中可以進一步考慮無人機速度方向的影響。其次，本文采用了數學規劃方法，數學規劃方法始終存在著無法解決大規模問題的局限性。總體而言，本章提出的多無人機在多約束條件下的協同航跡快速生成模型可以用于較少無人機協同打擊時飛行的合理安全以及任務執行的高效穩定。

表7 五架無人機實驗結果

表8 七架無人機實驗結果

表9 十架無人機實驗結果