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

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

1 引言

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

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

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

2 問題描述

2.1 打擊問題

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

2.2 約束分析

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

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

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

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

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

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

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

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

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

圖1 單架無人機飛行區(qū)域示意圖

3 模型建立

3.1 啟發(fā)式數(shù)據(jù)處理

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

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

表1 符號說明

3.2 規(guī)劃模型

3.2.1 符號說明

3.2.2 混合整數(shù)規(guī)劃模型

根據(jù)題目中的優(yōu)化目標和約束要求，建立如下航跡規(guī)劃的混合混合整數(shù)規(guī)劃模型：

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

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

綜合以上手段可以實現(xiàn)模型的快速求解，從而達到快速航跡規(guī)劃的目的。

4 實驗分析

4.1 實驗參數(shù)

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

表2 原始數(shù)據(jù)

表3 預處理后數(shù)據(jù)

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

表4 實驗參數(shù)

4.2 實驗結(jié)果及分析

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

設置3架無人機分別從點0，點2，點48出發(fā)，前往點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 三架無人機實驗結(jié)果(0、2、48出發(fā))

圖3 兩點之間航跡示意圖

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

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

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

設置3架無人機分別從點23，點102，點152出發(fā)，前往點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 三架無人機實驗結(jié)果(23、102、152出發(fā))

設置3架無人機分別從點0，點1，點2出發(fā)，前往點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 三架無人機實驗結(jié)果(0、1、2出發(fā))

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

4.2.2 無人機數(shù)量的影響實驗

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

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

表6 實驗結(jié)果

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

5 總結(jié)展望

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

表7 五架無人機實驗結(jié)果

表8 七架無人機實驗結(jié)果

表9 十架無人機實驗結(jié)果