多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃

夏令儒，孫首群

(上海理工大學(xué) 機(jī)械工程學(xué)院，上海 200082)

多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃

夏令儒，孫首群

(上海理工大學(xué) 機(jī)械工程學(xué)院，上海 200082)

為解決多無(wú)人機(jī)協(xié)同規(guī)劃軍事目標(biāo)打擊的問(wèn)題，基于多旅行商(TSP)數(shù)字規(guī)劃理論進(jìn)行路徑和時(shí)間的優(yōu)化。文中建立了多旅行商(TSP)數(shù)字規(guī)劃模型，并根據(jù)任務(wù)性能和區(qū)域劃分理論，利用退火算法求解出該模型的最優(yōu)解。使用A*路徑規(guī)劃算法，通過(guò)編程仿真規(guī)劃出了無(wú)人機(jī)的時(shí)間最優(yōu)路徑。結(jié)果表明，該方法較好地解決了當(dāng)前無(wú)人機(jī)協(xié)同作戰(zhàn)的目標(biāo)分配問(wèn)題，大幅提高了無(wú)人機(jī)協(xié)同作戰(zhàn)的能力。

多無(wú)人機(jī)；模擬退火算法；A*算法；最優(yōu)路徑規(guī)劃；協(xié)同作戰(zhàn)

無(wú)人機(jī)是一種具備自主飛行和獨(dú)立執(zhí)行任務(wù)能力的新型作戰(zhàn)平臺(tái)，不僅能夠執(zhí)行軍事偵察、監(jiān)視、搜索以及目標(biāo)指向等非攻擊性任務(wù)，而且還能夠執(zhí)行對(duì)地攻擊和目標(biāo)轟炸等作戰(zhàn)任務(wù)[1]。而實(shí)現(xiàn)無(wú)人機(jī)協(xié)同作戰(zhàn)的自主控制，需要首先解決目標(biāo)威脅實(shí)時(shí)評(píng)估、任務(wù)目標(biāo)分配和攻擊排序，針對(duì)不同問(wèn)題提出的多任務(wù)需求, 確定出各無(wú)人機(jī)的任務(wù)順序, 包括執(zhí)行任務(wù)的方式、執(zhí)行任務(wù)的類型以及不同任務(wù)的執(zhí)行順序和時(shí)間等, 以確保多無(wú)人機(jī)在多任務(wù)執(zhí)行過(guò)程中的協(xié)同性。用最優(yōu)化的方法研究高效率協(xié)同多任務(wù)分配方法是提升無(wú)人機(jī)未來(lái)戰(zhàn)場(chǎng)適應(yīng)能力和作戰(zhàn)效能的重要途徑, 具有較大的理論和合效應(yīng)及系統(tǒng)動(dòng)力學(xué)。

實(shí)際意義。目前，常用的目標(biāo)分配方法有：自主優(yōu)先權(quán)的分配和協(xié)同優(yōu)先權(quán)的分配[2-5]，這些目標(biāo)分配方法考慮的對(duì)象都是空中目標(biāo)。在目標(biāo)分配時(shí)，在考慮敵機(jī)對(duì)我方無(wú)人機(jī)威脅的同時(shí)，增加了地面目標(biāo)的威脅，進(jìn)行無(wú)人機(jī)協(xié)同作戰(zhàn)的目標(biāo)分配。

基于多邊形區(qū)域分割的基本思想，將多UAV 協(xié)同作戰(zhàn)分解為區(qū)域問(wèn)題，然后分別優(yōu)化求解。在滿足約束條件下，達(dá)到區(qū)域與整體的最優(yōu)解，根據(jù)無(wú)人機(jī)性能評(píng)估結(jié)果，最后通過(guò)仿真實(shí)驗(yàn)顯示了所給方法的有效性。

1 無(wú)人機(jī)群協(xié)同作戰(zhàn)模型建立

問(wèn)題描述

假定現(xiàn)有P01、P02、P03、P04、P05、P06、P07具有FY-1、FY-2、兩種不同配置無(wú)人機(jī)的基地，要對(duì)10個(gè)目標(biāo)基地共68個(gè)目標(biāo)進(jìn)行偵察和軍事打擊，尋找出最優(yōu)的解決方法。

約束條件

(1)FY-1型無(wú)人機(jī)主要擔(dān)任目標(biāo)偵察和目標(biāo)指示，巡航飛行速度為200 km/h，最長(zhǎng)巡航時(shí)間為10 h，巡航飛行高度為1 500 m；

(2)FY-1型無(wú)人機(jī)每次只能攜帶S-1、S-2其中一種裝備；

(3)S-1、S-2兩種不同載荷對(duì)于每個(gè)目標(biāo)群各自至少偵察一次；

(4)FY-2型無(wú)人機(jī)主要擔(dān)任通信中繼，巡航飛行速度為300 km/h，最長(zhǎng)巡航時(shí)間為8 h，巡航飛行高度為5 000 m；

(5)無(wú)人機(jī)的最小轉(zhuǎn)彎半徑為70 m；

(6)同一基地的兩架無(wú)人機(jī)起飛時(shí)間間隔和降落回收的時(shí)間間隔不低于3 min；

從連接度看：連接度為與某一空間直接相連的空間數(shù)目，連接度高的空間能方便到達(dá)多個(gè)相鄰空間。軸線分析地圖表明，余蔭山房中部的“烷紅跨綠橋”區(qū)域空間連接度較高，穿過(guò)性交通較大，與“深柳堂”前庭、旱庭、“臨池別館”前廊等空間直接相通，使用者可以很方便地在園中的不同區(qū)域穿行[13]。相反，余蔭山房西部與南部區(qū)域空間的連接度較低，使用者行至這一區(qū)域沒(méi)有太多的選擇，只能按照設(shè)計(jì)好的路線游覽。對(duì)于連接度只有1的“深柳堂”東側(cè)廂房來(lái)說(shuō)，穿過(guò)性交通較少只與一個(gè)空間直接相連，較為僻靜。

(7)無(wú)人機(jī)執(zhí)行完任務(wù)后需返回原基地；

(8)每個(gè)目標(biāo)群均配屬雷達(dá)，且對(duì)FY型無(wú)人機(jī)的有效探測(cè)距離為70 km。

1.1 協(xié)同作戰(zhàn)路線優(yōu)化模型

基于偵察任務(wù)與路線長(zhǎng)度之間的近似線性關(guān)系[6-7], 偵察路線優(yōu)化模型通常以偵察總時(shí)間最短作為優(yōu)化目標(biāo)。通過(guò)分析偵察系統(tǒng)的特點(diǎn), 可將偵察路線優(yōu)化模型描述為基地為單位的各個(gè)雷達(dá)監(jiān)測(cè)內(nèi)部的目標(biāo)點(diǎn)設(shè)計(jì)最短耗時(shí)的偵查路線，一方面起到降維的目的，另一方面估計(jì)出在每個(gè)基地的最短逗留時(shí)間。第二步是把以基地為單位的偵察時(shí)間串聯(lián)起來(lái)，建立規(guī)劃模型來(lái)計(jì)算要遍歷這些基地總的偵察時(shí)間，估算出需要派出幾架無(wú)人機(jī)出動(dòng)偵查。思路流程如圖1所示。

圖1 思路流程圖

1.2 無(wú)人機(jī)的任務(wù)分配

模擬退火算法[8]是所謂3大非經(jīng)典算法之一，它脫胎于自然界的物理過(guò)程，與優(yōu)化問(wèn)題相結(jié)合。其思想源于固體的退火過(guò)程，即將固體加熱至足夠高的溫度，再緩慢冷卻。為尋找出最優(yōu)解，把多無(wú)人機(jī)的協(xié)同任務(wù)數(shù)據(jù)用在退火程序中。

對(duì)任意基地內(nèi)部，可以建立經(jīng)典TSP規(guī)劃模型[9]來(lái)求解最短時(shí)間的滯留路徑。為簡(jiǎn)化計(jì)算，可以先不考慮無(wú)人機(jī)轉(zhuǎn)彎半徑70 m的限制。根據(jù)題設(shè)條件，假設(shè)無(wú)人機(jī)的任務(wù)分配原理如圖2所示。

圖2 無(wú)人機(jī)的任務(wù)分配原理

1.3 數(shù)學(xué)模型的建立

為了更加精確的解決無(wú)人機(jī)群協(xié)同作戰(zhàn)問(wèn)題，需要建立理論數(shù)學(xué)模型如下

Tmin=Ts1+Ts2

(1)

(2)

Ts2=(i=0,1,2,…,10)

(3)

(4)

(5)

其中，Ts1為s1和s2在雷達(dá)區(qū)分別的滯留時(shí)間；Tmin為s1和s2的最小滯留時(shí)間之和；Vk為s1和s2的平穩(wěn)運(yùn)行的速度(k=0,k=1)；r為雷達(dá)的輻射范圍；Ts1Ai為s1在Ai號(hào)基地的滯留時(shí)間；sj為出目標(biāo)群時(shí)的距離。

基于10個(gè)基地的建模并且運(yùn)用Matlab運(yùn)行處每個(gè)目標(biāo)群最優(yōu)路徑所需的最短時(shí)間如表1所示 。

表1 每個(gè)目標(biāo)群中最優(yōu)路徑及時(shí)間

2 A*路徑規(guī)劃算法及仿真

2.1 A*算法的選擇

A*算法是一種經(jīng)典的啟發(fā)式搜索算法，一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問(wèn)題的有效算法[11-12]。算法的創(chuàng)新之處在于探索下一個(gè)結(jié)點(diǎn)時(shí)引入了已知的路網(wǎng)信息 ，特別是目標(biāo)點(diǎn)信息，增加當(dāng)前結(jié)點(diǎn)有效評(píng)估，即增加約束條件，作為評(píng)價(jià)該結(jié)點(diǎn)處于最優(yōu)路線上可能性的量度，因此首先搜索可能性較大的結(jié)點(diǎn)，從而減少探索結(jié)點(diǎn)個(gè)數(shù)，提高算法效率。

設(shè)O點(diǎn)為搜索過(guò)程中的某個(gè)節(jié)點(diǎn)， 它可以有 8 個(gè)擴(kuò)展方向。首先建立二維平面的無(wú)人機(jī)運(yùn)動(dòng)，如下

(6)

(7)

式中，x和y為無(wú)人機(jī)在二維平面內(nèi)的慣性坐標(biāo)；v為無(wú)人機(jī)速度；θ為偏航角。

假設(shè)有n架無(wú)人機(jī)，定義第i架無(wú)人機(jī)的代價(jià)函數(shù)為

f(i)=g(i)+h(i),i=1,2,…,n

(8)

(9)

(10)

其中，(xi,yi)為第i架無(wú)人機(jī)的位置坐標(biāo)；(xi1,yi1)是為i架無(wú)人機(jī)的待飛點(diǎn)；(xt,yt)為目標(biāo)點(diǎn)坐標(biāo)。由此設(shè)定為目標(biāo)函數(shù)，編寫成為Matlab程序。

2.2 約束條件

假設(shè)各無(wú)人機(jī)類型相同，時(shí)間步長(zhǎng)為T,飛行速度為200 m/h, A*算法步長(zhǎng)為 時(shí)，可以得到各無(wú)人機(jī)在A*算法不同步長(zhǎng)下到達(dá)目標(biāo)的時(shí)間集St1，St2，St3，…，求取它們的交集?=St1∩Si2∩Si3∩……。從?中選取最小的時(shí)間作為多無(wú)人機(jī)最優(yōu)協(xié)同飛行時(shí)間t，使各無(wú)人機(jī)按照在t約束下的時(shí)間飛行，且各無(wú)人機(jī)同時(shí)到達(dá)目標(biāo)點(diǎn)。即在最優(yōu)協(xié)同時(shí)間t之后，X1=X2,Y1=Y2。

在無(wú)人機(jī)協(xié)同飛行過(guò)程中，當(dāng)兩架無(wú)人機(jī)之間的距離大于或等于無(wú)人機(jī)最大通信距離dmax時(shí)，啟動(dòng)通信距離限制約束。兩架無(wú)人機(jī)在遵循小轉(zhuǎn)彎半徑約束的前提下，向減小兩機(jī)距離的方向各運(yùn)動(dòng)一個(gè)步長(zhǎng)。取各無(wú)人機(jī)當(dāng)前位置為A*算法新的起始節(jié)點(diǎn)，重新規(guī)劃協(xié)同航路。如果兩架無(wú)人機(jī)在相互接近時(shí)又遇到威脅區(qū)域，此時(shí)為了保證無(wú)人機(jī)的安全，無(wú)人機(jī)應(yīng)首先繞開(kāi)威脅區(qū)域，然后再相接近，使相互間距離保持在通信距離范圍內(nèi)，具體流程如圖3所示。

圖3 A *算法流程圖

2.3 仿真結(jié)果分析

區(qū)域A下FY-1型無(wú)人機(jī)的起始位置基地P01坐標(biāo)為(368，319)，起始時(shí)刻t0為8:00，所要到達(dá)的目標(biāo)基地的坐標(biāo)為A010(264，715),且無(wú)人機(jī)的航速為v=200 m/s。

區(qū)域B下FY-2型無(wú)人機(jī)的起始位置基地的坐標(biāo)為P07(360，110)，起始時(shí)刻t0為8:00，所要到達(dá)的目標(biāo)基地A0501的坐標(biāo)為(120，400)，且FY-2型無(wú)人機(jī)的航速為v=300 m/s。

將相鄰兩個(gè)點(diǎn)的位置相連，求出其距離，公式如下

(11)

(12)

則中間應(yīng)規(guī)劃航跡長(zhǎng)度為dc=f0-c1-c2，接下來(lái)只要進(jìn)行起始點(diǎn)為P01、目標(biāo)點(diǎn)為A0101、 給定長(zhǎng)為dc的定長(zhǎng)航跡規(guī)劃，多機(jī)協(xié)同航跡規(guī)劃，在用A*算法實(shí)現(xiàn)定長(zhǎng)航跡規(guī)劃后，可進(jìn)一步實(shí)現(xiàn)多人機(jī)協(xié)同航跡規(guī)劃[14-15]。以 3 架無(wú)人機(jī)為例，其策略為：根據(jù)起始點(diǎn)、目標(biāo)點(diǎn)以及途中要規(guī)避的威脅，3 架無(wú)人機(jī)先各自進(jìn)行最短航跡規(guī)劃，然后從中選取長(zhǎng)度最大的一條作為參照，以其長(zhǎng)度作為給定值，對(duì)其他兩架無(wú)人機(jī)進(jìn)行定長(zhǎng)航跡規(guī)劃。這樣就實(shí)現(xiàn)了3機(jī)同時(shí)出發(fā)、同時(shí)到達(dá)且用時(shí)最短的協(xié)同航跡規(guī)劃。

設(shè)在上述情形 1 下，第 1 架無(wú)人機(jī)的起始點(diǎn)P01坐標(biāo)為(264，715)，目標(biāo)基地坐標(biāo)為(368，319)，第 2 架無(wú)人機(jī)的起始點(diǎn)P02坐標(biāo)為(264，44)，目標(biāo)基地坐標(biāo)為A0501(120，400)，第 3 架無(wú)人機(jī)的起始點(diǎn)P03坐標(biāo)為(392,220)，目標(biāo)點(diǎn)A0701坐標(biāo)為(10,451) 。設(shè)在上述情形2下，第 1 架無(wú)人機(jī)的起始點(diǎn)P05坐標(biāo)為(392，275) ，目標(biāo)點(diǎn)A0301坐標(biāo)為(168，538)，第 2 架無(wú)人機(jī)的起始點(diǎn)P06坐標(biāo)為(296，242)，目標(biāo)點(diǎn)A0201坐標(biāo)為(225，605)，第3架無(wú)人機(jī)的起始點(diǎn)P07坐標(biāo)為(256,121)，目標(biāo)點(diǎn)A0801坐標(biāo)為(162，660)。

在Matlab環(huán)境下，進(jìn)行上述單機(jī)定長(zhǎng)航跡規(guī)劃和3機(jī)協(xié)同航跡規(guī)劃數(shù)字仿真。啟發(fā)函數(shù)[16]取為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)直線距離的1.4 倍。1.4 為啟發(fā)系數(shù)， 決定了啟發(fā)函數(shù)h(i)的大小。計(jì)算可得情形1下無(wú)人機(jī)應(yīng)飛航跡的給定長(zhǎng)度為f0=v(t1-t0)=470 km，情形 2 下無(wú)人機(jī)應(yīng)飛航跡的給定長(zhǎng)度為f0=v(t1-t0)=456 km，與問(wèn)題飛航程470 km 非常接近，相對(duì)誤差為 0. 383 6%。通過(guò)以上流程的建模和計(jì)算，代入N=3得到三架無(wú)人通訊機(jī)可以由最優(yōu)路徑進(jìn)行保持通訊和偵查，由仿真結(jié)果圖可以看出，本文設(shè)計(jì)的通信約束下的航路規(guī)劃算法是合理和有效的。圖4顯示出FY-1型無(wú)人偵察機(jī)裝載載荷在A01目標(biāo)群中各目標(biāo)間進(jìn)行偵察的順序及航線，10個(gè)目標(biāo)群中整體路徑規(guī)劃如圖5和路線分配圖6所示。

圖4 無(wú)人機(jī)在A01中偵察的順序及航線

圖5 整體路線規(guī)劃

圖6 整體路線分配圖

3 結(jié)束語(yǔ)

(1)結(jié)合多目標(biāo)、多無(wú)人機(jī)和多種作戰(zhàn)任務(wù)的協(xié)同分配需求建立了數(shù)字規(guī)劃模型，重點(diǎn)考慮了同一作戰(zhàn)任務(wù)需要多架次無(wú)人機(jī)共同完成的情況，并結(jié)合協(xié)同任務(wù)的約束條件和協(xié)同任務(wù)的特點(diǎn)，構(gòu)造了基于遺傳算法的協(xié)同任務(wù)分配求解算法；(2)提出了改進(jìn)的多無(wú)人機(jī)協(xié)同作戰(zhàn)優(yōu)化模型, 利用遺傳算法得到偵察、打擊目標(biāo)與時(shí)間總和最短的優(yōu)化路線改進(jìn)模型,并解決多無(wú)人機(jī)多任務(wù)的優(yōu)化問(wèn)題；(3)將提出的路線優(yōu)化問(wèn)題的解決方案應(yīng)用于實(shí)例, 運(yùn)算結(jié)果證明該方法是適用和可行的。

[1] 楊俊超,史越,馬海明.種人一自動(dòng)系統(tǒng)協(xié)作的無(wú)人機(jī)航跡規(guī)劃方法[J].計(jì)算機(jī)測(cè)量與控制,2015,23(9):25-31.

[2] 柏建普,吳強(qiáng).蟻群混合遺傳算法的研究及應(yīng)用[J].電子科技,2011,24(4):20-23.

[3] 劉躍峰,張安.有人機(jī)/無(wú)人機(jī)編隊(duì)協(xié)同任務(wù)分配方法[J].系統(tǒng)工程與電子技術(shù),2010,32(3):584-588.

[4] 彭輝,沈林成,朱華勇.基于分布式模型預(yù)測(cè)控制的多UAV 協(xié)同區(qū)域搜索[J]. 航空學(xué)報(bào),2010(3):594-600.

[5] Chen L D,Toru S.Data mining methods，applications and tools[J].Information System Management,2000,17(1):65-70.

[6] Szczerba R J.Robust algorithm for algorithm for real time route planning[J].IEEE Transaction on Aerospace and Electronic System,2000,36(3):869-878.

[7] 孟中杰,黃攀峰,閆杰.基于改進(jìn)稀疏 A * 算法的高超聲速飛行器航跡規(guī)劃技術(shù)[J].西北工業(yè)大學(xué)學(xué)報(bào),2010,28(2):182-186.

[8] 王豐雪,陳家琪.一種結(jié)合模擬退火和貪心策略的社團(tuán)識(shí)別算法[J].電子科技,2016,29(2):8-10.

[9] 高海昌,馮博琴,朱利.智能優(yōu)化算法求解 TSP 問(wèn)題[J].控制與決策,2006,21(3):241-247.

[10] Brown D T.Routing unmanned aerial vehicles while considering general restricted operating zones[D].Ohio: Air Force Institute of Technology,2001.

[11] 郭文強(qiáng),高曉光,任佳,等.基于圖模型自主優(yōu)化的多無(wú)人機(jī)多目標(biāo)攻擊[J].系統(tǒng)工程與電子技術(shù),2010,32(3): 574-578.

[12] 高暉,陳欣,夏云程.無(wú)人機(jī)航路規(guī)劃研究[J].南京航空航天大學(xué)學(xué)報(bào),2001,33(2):135-138.

[13] 郭齊勝,郅志剛,楊瑞平,等.裝備效能評(píng)估概論[M].北京:國(guó)防工業(yè)出版社,2013.

[14] 浦鵬,張金春,孫璽菁.多機(jī)協(xié)同多目標(biāo)分配戰(zhàn)術(shù)決策研究[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù),2007,28(2):57-61.

[15] 榮少巍.基于改進(jìn)A* 算法的水下航行器自主搜索航跡規(guī)劃[J].電子科技,2015,28(4):17-19．

[16] 陳建榮,郭齊勝.無(wú)人機(jī)系統(tǒng)的系統(tǒng)效能評(píng)估[J].指揮控制與仿真,2008,33(5):45-48.

Planning Route for UAV Cooperative Combat

XIA Lingru，SUN Shouqun

(School of Mechanical Engineering，Shanghai University for Science and Technology，Shanghai 200000, China)

In order to solve the problem of multiple unmanned aerial vehicle cooperative planning military target attack, based on the theory of multiple traveling salesman (TSP) digital planning, path and the time of optimization. Multiple traveling salesman (TSP) was established by the digital planning model, and according to the theory of division and task performance, the annealing algorithm is used to derive the model of the optimal solution; Finally using the A * path planning algorithm, through the programming simulation time optimal path planning out of the unmanned aerial vehicle . Results show that the method solve the target assignment problem of unmanned aerial vehicle cooperative engagement, greatly improve the ability of the unmanned aerial vehicle cooperative engagement.

unmanned aerial vehicle;simulated annealing algorithm;A * algorithm;the optimal path planning;operation

2017- 03- 08

國(guó)家科技支撐計(jì)劃項(xiàng)目(2015BAK16B04)

夏令儒(1990-)，男，碩士研究生。研究方向：大型油氣管道泄露搶險(xiǎn)密封技術(shù)。孫首群(1964-)，男，博士，副教授。研究方向：機(jī)電系統(tǒng)電熱耦合效應(yīng)及系統(tǒng)動(dòng)力學(xué)。

TN256

A

1007-7820(2018)01-004-05