帶定位誤差約束的多無(wú)人機(jī)快速協(xié)同航跡規(guī)劃

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

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

1 引言

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

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

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

2 問(wèn)題描述

2.1 打擊問(wèn)題

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

2.2 約束分析

以一架無(wú)人機(jī)為例，無(wú)人機(jī)的出發(fā)點(diǎn)為A點(diǎn)，目標(biāo)點(diǎn)為B點(diǎn)。其在飛行中受到約束如下：

1)無(wú)人機(jī)在飛行時(shí)存在定位誤差，包括垂直誤差和水平誤差。無(wú)人機(jī)每飛行1m，垂直誤差和水平誤差各增加δ個(gè)單位。為保證打擊的精準(zhǔn)性，要求無(wú)人機(jī)在到達(dá)目標(biāo)點(diǎn)B時(shí)垂直誤差和水平誤差均應(yīng)小于θ個(gè)單位。為簡(jiǎn)化問(wèn)題，假設(shè)當(dāng)垂直誤差和水平誤差均小于θ個(gè)單位時(shí)，無(wú)人機(jī)仍能夠按照規(guī)劃路徑飛行；

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

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

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

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

6)當(dāng)飛行器的垂直誤差不大于α1個(gè)單位，水平誤差不大于α2個(gè)單位時(shí)才能進(jìn)行垂直誤差校正；

7)當(dāng)飛行器的垂直誤差不大于β1個(gè)單位，水平誤差不大于β2個(gè)單位時(shí)才能進(jìn)行水平誤差校正；

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

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

3 模型建立

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

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

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

表1 符號(hào)說(shuō)明

3.2 規(guī)劃模型

3.2.1 符號(hào)說(shuō)明

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

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

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

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)參數(shù)

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

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

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

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

表4 實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果及分析

4.2.1 無(wú)人機(jī)初始位置的影響實(shí)驗(yàn)

設(shè)置3架無(wú)人機(jī)分別從點(diǎn)0，點(diǎn)2，點(diǎn)48出發(fā)，前往點(diǎn)326。無(wú)人機(jī)1的航跡為：0-184-163-114-8-309-305-123-45-160-92-93-61-292-326，航跡長(zhǎng)110140.79；無(wú)人機(jī)2的航跡為：2-40-290-209-8-309-121-123-45-160-191-92-93-61-292-326，航跡長(zhǎng)110126.97。無(wú)人機(jī)3的航跡為：48-56-58-8-309-305-123-45-160-191-92-93-61-292-326，航跡長(zhǎng)110127.25。航跡間最大差值為13.82。

圖2 三架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果(0、2、48出發(fā))

圖3 兩點(diǎn)之間航跡示意圖

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

圖4 中間航跡點(diǎn)切入弧與切出弧相接示意圖

對(duì)于每個(gè)中間航跡點(diǎn)都是兩個(gè)圓弧的交點(diǎn)，圖4顯示了半徑為200的輔助圓。

設(shè)置3架無(wú)人機(jī)分別從點(diǎn)23，點(diǎn)102，點(diǎn)152出發(fā)，前往點(diǎn)326。無(wú)人機(jī)1的航跡為：23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航跡長(zhǎng)140564.83。無(wú)人機(jī)2的航跡為：102-26-206-3-281-197-112-296-205-171-168-115-160-92-93-61-292-326，航跡長(zhǎng)140544.29。無(wú)人機(jī)3的航跡為：152-23-26-206-3-281-197-112-151-190-108-168-115-160-92-93-61-292-326，航跡長(zhǎng)140561.28。航跡間最大差值為20.54。

圖5 三架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果(23、102、152出發(fā))

設(shè)置3架無(wú)人機(jī)分別從點(diǎn)0，點(diǎn)1，點(diǎn)2出發(fā)，前往點(diǎn)326。無(wú)人機(jī)1的航跡為：0-163-114-8-309-305-123-45-160-92-93-61-292-326，航跡長(zhǎng)109405.51。無(wú)人機(jī)2的航跡為1-200-122-316-98-76-6-12-216-279-302-161-326，航跡長(zhǎng)109408.27。無(wú)人機(jī)3的航跡為2-56-290-158-8-309-305-123-231-160-92-93-61-292-326，航跡長(zhǎng)109389.22。航跡間最大差值為19.05，實(shí)際運(yùn)行時(shí)間91秒。

圖6 三架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果(0、1、2出發(fā))

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

4.2.2 無(wú)人機(jī)數(shù)量的影響實(shí)驗(yàn)

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

初始分別設(shè)置5架、7架、10架無(wú)人機(jī)，設(shè)置不同運(yùn)行時(shí)間，獲得幾次結(jié)果如表6所示。

表6 實(shí)驗(yàn)結(jié)果

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

5 總結(jié)展望

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

表7 五架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果

表8 七架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果

表9 十架無(wú)人機(jī)實(shí)驗(yàn)結(jié)果