基于改進(jìn)A＊算法的多基地多無人機(jī)分階段任務(wù)規(guī)劃方法

鄭 鍇，尹 棟，殷少鋒，鄭獻(xiàn)民，林宏旭

（1. 32146部隊(duì)，焦作 454000；2. 國防科技大學(xué) 智能科學(xué)學(xué)院，長沙 410000）

隨著戰(zhàn)爭形態(tài)和作戰(zhàn)樣式的轉(zhuǎn)變，無人機(jī)偵察保障要求越來越高，由重要時(shí)節(jié)和重點(diǎn)方向偵察轉(zhuǎn)變成全時(shí)、全域和多任務(wù)偵察[1-3]。單一無人機(jī)平臺受作用半徑、續(xù)航時(shí)間、實(shí)用升限和任務(wù)載荷等性能局限，往往難以滿足實(shí)際應(yīng)用需求，多無人機(jī)協(xié)同運(yùn)用將是未來戰(zhàn)場的重要作戰(zhàn)樣式。多無人機(jī)任務(wù)規(guī)劃成為國內(nèi)外廣泛關(guān)注的課題[4-6]。

任務(wù)分配和航跡規(guī)劃是多無人機(jī)任務(wù)規(guī)劃的關(guān)鍵問題。多無人機(jī)任務(wù)規(guī)劃研究，通常將任務(wù)規(guī)劃問題分解成子問題，首先基于近似代價(jià)進(jìn)行層次化的任務(wù)分配，而后基于分配方案規(guī)劃航跡[7-11]。文獻(xiàn)[7]針對單基地多無人機(jī)協(xié)同搜索多目標(biāo)問題，提出分步組合優(yōu)化方法，應(yīng)用聚類方法將MTSP（Multiple Travelling salesman problem）問題分解為多個旅行商（Travelling Salesman Problem, TSP）問題，應(yīng)用遺傳算法求解TSP問題，該方法具有較好的計(jì)算優(yōu)勢；文獻(xiàn)[8]針對多無人機(jī)任務(wù)分配問題，將任務(wù)分配分解為任務(wù)分簇、任務(wù)簇分配和簇內(nèi)分配三個階段，層次化分配方法具有較好的實(shí)時(shí)性；文獻(xiàn)[9]針對有人/無人任務(wù)聯(lián)盟形成問題，采用任務(wù)聚類-平臺分配的分階段策略，分別采用貪心聚類策略和人工蜂群算法求解，仿真驗(yàn)證了該方法的有效性；文獻(xiàn)[10]針對多目標(biāo)群多無人機(jī)協(xié)同任務(wù)規(guī)劃，提出“雙重優(yōu)化”思想，首先運(yùn)用貪心算法對各目標(biāo)群群內(nèi)的目標(biāo)進(jìn)行航路規(guī)劃，而后運(yùn)用遺傳算法對各目標(biāo)間的目標(biāo)進(jìn)行任務(wù)規(guī)劃。文獻(xiàn)[11]應(yīng)用分層優(yōu)化法解決多協(xié)作無人機(jī)任務(wù)規(guī)劃問題，融合Dubins和B樣條曲線規(guī)劃多無人機(jī)執(zhí)行多任務(wù)航線，估算可能的任務(wù)指派產(chǎn)生的消耗，進(jìn)行任務(wù)分配求解，進(jìn)而應(yīng)用高斯偽譜法規(guī)劃無人機(jī)飛行航跡。

在當(dāng)前任務(wù)規(guī)劃方法的研究中，通常簡化了任務(wù)分配和航跡規(guī)劃的耦合關(guān)系，采用直線或簡單曲線航跡估計(jì)任務(wù)分配中的代價(jià)指標(biāo)，未考慮環(huán)境威脅規(guī)避和飛行性能等對航跡影響因素，造成任務(wù)分配與實(shí)際情況存在沖突，任務(wù)規(guī)劃往往不是最優(yōu)或次優(yōu)解。

本文針對多無人機(jī)疏散配置在多個基地、協(xié)同執(zhí)行多目標(biāo)偵察的任務(wù)規(guī)劃應(yīng)用需求，綜合考慮任務(wù)分配和航跡規(guī)劃的航程代價(jià)耦合關(guān)系，基于改進(jìn)A*算法預(yù)估航程代價(jià)矩陣，提出了一種基于改進(jìn)A*算法的多基地多無人機(jī)分階段任務(wù)規(guī)劃方法。該方法系統(tǒng)地給出了一種多基地多無人機(jī)多階段、層次化的任務(wù)規(guī)劃處理流程，包括區(qū)域設(shè)置、航程估算、多基地多無人機(jī)任務(wù)分配、基地內(nèi)單無人機(jī)時(shí)序分配、航跡搜索、航跡平滑、局部動態(tài)規(guī)劃等多個階段。該方法改進(jìn)了A*算法用于預(yù)估航程代價(jià)和航跡搜索，改進(jìn)了K-means算法用于任務(wù)聚類分配，將問題化繁為簡。

1 原理架構(gòu)

基于改進(jìn)A*算法的多基地多無人機(jī)分階段任務(wù)規(guī)劃方法的原理架構(gòu)，如圖1所示。具體表述為：①區(qū)域設(shè)置。在地理信息系統(tǒng)（Geographic Information System, GIS）中，依次點(diǎn)擊確定各基地坐標(biāo)和任務(wù)坐標(biāo)，確定任務(wù)規(guī)劃區(qū)域范圍，采用不同幾何形狀標(biāo)記威脅區(qū)域。②任務(wù)分配。航程估算階段，改進(jìn)A*算法，構(gòu)建各基地、各任務(wù)點(diǎn)之間的A*預(yù)估航程矩陣，從而避免直接應(yīng)用直線歐式距離導(dǎo)致的任務(wù)分配誤差。多基地多無人機(jī)任務(wù)分配階段，當(dāng)任務(wù)數(shù)量多、區(qū)域集中分布時(shí)，基于改進(jìn)K-means算法，實(shí)現(xiàn)目標(biāo)區(qū)域聚類、各基地聚類目標(biāo)分配、基地內(nèi)無人機(jī)任務(wù)分配等；當(dāng)任務(wù)數(shù)量少、疏散分布時(shí)，采用深度遍歷方法實(shí)現(xiàn)精確任務(wù)分配。基地內(nèi)單無人機(jī)時(shí)序任務(wù)分配階段，基于TSP模型進(jìn)行求解；③航跡規(guī)劃。采用改進(jìn)A*算法搜索并繪制航跡，基于三次B樣條曲線進(jìn)行航跡平滑。④動態(tài)任務(wù)規(guī)劃。依據(jù)威脅區(qū)域和任務(wù)目標(biāo)的變化，確定需要執(zhí)行動態(tài)規(guī)劃的無人機(jī)及其局部規(guī)劃空間，并針對部分無人機(jī)和局部區(qū)域進(jìn)行動態(tài)任務(wù)分配和航跡規(guī)劃。

圖1 多基地多無人機(jī)任務(wù)規(guī)劃的原理框圖Fig.1 Mission assignment framework of multi-UAVs deployed in different bases

2 區(qū)域設(shè)置

2.1 區(qū)域規(guī)劃

在地理信息系統(tǒng)中，點(diǎn)擊選定并標(biāo)注多基地、多任務(wù)的位置，按點(diǎn)擊次序?yàn)槊總€基地和任務(wù)編號，確定任務(wù)規(guī)劃的區(qū)域范圍。規(guī)劃區(qū)域如圖2所示，設(shè)各基地和任務(wù)的最大位置高斯坐標(biāo)值分別為Xmax、Ymax，最小位置高斯坐標(biāo)值分別Xmin、Ymin，規(guī)劃空間的擴(kuò)展距離值為H。將規(guī)劃空間離散柵格化，（Xmin-H,Ymin-H)為原點(diǎn)，設(shè)h為網(wǎng)格邊長，則規(guī)劃空間中任意點(diǎn)（x,y）的網(wǎng)格坐標(biāo)（xg, yg）為：

圖2 規(guī)劃空間示意圖Fig.2 Schematic diagram of plan area

2.2 威脅設(shè)置

基于基礎(chǔ)地理信息和戰(zhàn)場態(tài)勢信息，在GIS中標(biāo)繪出地形障礙、雷達(dá)探測、電子對抗、防空火力、禁飛區(qū)等飛行威脅區(qū)域。根據(jù)不同威脅模型的特點(diǎn)，在GIS系統(tǒng)中通過手繪或標(biāo)注等形式，標(biāo)記出圓形、矩形、多邊形等任意不同形狀的威脅區(qū)域，并按式(1)計(jì)算威脅區(qū)域邊界的網(wǎng)格坐標(biāo)。

3 任務(wù)分配

3.1 改進(jìn)A*算法設(shè)計(jì)

A*算法全局性好、運(yùn)行較快、易于工程實(shí)現(xiàn)，在航跡規(guī)劃領(lǐng)域獲得了廣泛關(guān)注[12-15]。在任務(wù)分配過程中，在考慮距離代價(jià)時(shí)通常用直線歐式距離近似表示航程，沒有考慮威脅區(qū)域等約束條件對航程的影響，易于造成任務(wù)規(guī)劃不合理，因此可通過A*算法預(yù)估各基地與各個任務(wù)點(diǎn)、各個任務(wù)點(diǎn)之間的距離，將A*預(yù)估距離作為任務(wù)分配的航程代價(jià)。此外，在航跡規(guī)劃過程中，A*算法用于實(shí)現(xiàn)各基地、各任務(wù)點(diǎn)間的航跡搜索。

A*算法的代價(jià)函數(shù)表示為：

式中，n為當(dāng)前節(jié)點(diǎn)，f(n)為起始點(diǎn)經(jīng)節(jié)點(diǎn)n到目標(biāo)點(diǎn)的代價(jià)函數(shù)，g(n)為從起始點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h(n)為節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價(jià)。

代價(jià)函數(shù)g(n)可表示為：

式中，ln為航程代價(jià)，Jn為威脅代價(jià)，zn為高度代價(jià)，ω1、ω2和ω3分別表示航跡代價(jià)權(quán)值。為確保無人機(jī)航跡能夠規(guī)避所有威脅區(qū)域，將威脅代價(jià)設(shè)為無窮大，令ω2=∞；無人機(jī)通常優(yōu)先采用固定高度巡航，為簡化航跡優(yōu)化問題、減少計(jì)算量，設(shè)無人機(jī)以固定高度巡飛，將三維空間航跡搜索問題簡化為二維問題，令ω1=1，ω3=0。

啟發(fā)函數(shù)h(n)，引導(dǎo)節(jié)點(diǎn)(xn,yn)向目標(biāo)點(diǎn)(xt,yt)的方向搜索擴(kuò)展，可表示為：

傳統(tǒng)A*算法在柵格節(jié)點(diǎn)擴(kuò)展過程中，節(jié)點(diǎn)擴(kuò)展主要局限在柵格線的交叉點(diǎn)上，可能會導(dǎo)致部分航跡呈鋸齒狀。為了避免鋸齒型航跡，改進(jìn)A*算法，進(jìn)行航跡節(jié)點(diǎn)再調(diào)整，優(yōu)化部分鋸齒型航跡。

圖3所示為節(jié)點(diǎn)再調(diào)整示意圖，將虛線航跡優(yōu)化為實(shí)線航跡。設(shè)無人機(jī)w初始航跡節(jié)點(diǎn)序列vw1[r]，節(jié)點(diǎn)序列數(shù)量為r，則節(jié)點(diǎn)再調(diào)整過程為：a. 初始令j=r；b. 循環(huán)檢查（vw1[i],vw1[j]）之間的連線是否通過威脅區(qū)，i?[1…j-1]；若通過威脅區(qū)，令i=i+1；若不通過威脅區(qū)，令j=i，并將vw1[j]保存為再調(diào)整后的航跡節(jié)點(diǎn)；c. 重復(fù)上述循環(huán)，直至j=1，停止循環(huán)，生成再調(diào)整后的航跡序列vw2[l]，調(diào)整后的節(jié)點(diǎn)序列數(shù)量為l。

圖3 航跡節(jié)點(diǎn)調(diào)整示意圖Fig.3 Schematic diagram of path optimization

圖4所示為改進(jìn)A*算法的主要處理流程。在啟發(fā)式搜索時(shí)，建立OPEN和CLOSE兩個表，OPEN表用于存儲已經(jīng)計(jì)算但沒有擴(kuò)展的節(jié)點(diǎn)，CLOSE表用于存儲已經(jīng)擴(kuò)展的節(jié)點(diǎn)。數(shù)據(jù)存儲結(jié)構(gòu)表示為{（x i,y i）,f i,g i,hi,pi}，其中，(xi,yi)為節(jié)點(diǎn)的網(wǎng)格坐標(biāo)，fi、gi、hi分別為代價(jià)函數(shù)的變量值，pi代表當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。具體表述為：

圖4 改進(jìn)A*算法流程圖Fig.4 The framework of improved A* algorithm

步驟1 初始化。初始化OPEN和CLOSE表，將起點(diǎn)放入OPEN表中作為當(dāng)前節(jié)點(diǎn)。

步驟2 節(jié)點(diǎn)擴(kuò)展與存儲。當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，若滿足約束條件且不在當(dāng)前OPEN和CLOSE表中，則將該有效節(jié)點(diǎn)加入OPEN表；將OPEN表中代價(jià)最小的節(jié)點(diǎn)A移到CLOSE表；判斷節(jié)點(diǎn)A是否為終點(diǎn)，若是終點(diǎn)則退出節(jié)點(diǎn)搜索，若不是終點(diǎn)則繼續(xù)節(jié)點(diǎn)擴(kuò)展。從CLOSE表中提取航跡節(jié)點(diǎn)序列vw1[r]，將終點(diǎn)的代價(jià)函數(shù)值作為預(yù)估A*航程。

步驟3 航跡節(jié)點(diǎn)調(diào)整。設(shè)vw1[r]中的航跡起點(diǎn)為調(diào)整起點(diǎn)，初始航跡終點(diǎn)作為調(diào)整中繼點(diǎn)；從調(diào)整起點(diǎn)開始，依次判斷vw1[r]中各航跡點(diǎn)與調(diào)整中繼點(diǎn)的連線是否經(jīng)過威脅區(qū)域；若調(diào)整起點(diǎn)與調(diào)整中繼點(diǎn)連線通過威脅區(qū)域，則將當(dāng)前調(diào)整起點(diǎn)的下一點(diǎn)更新為調(diào)整起點(diǎn)，并繼續(xù)判斷是否通過威脅區(qū)域；若調(diào)整起點(diǎn)與調(diào)整中繼點(diǎn)連線不通過威脅區(qū)域，將當(dāng)前調(diào)整中繼點(diǎn)保存為航跡調(diào)整后的一個航程點(diǎn)，并將當(dāng)前調(diào)整起點(diǎn)更新為調(diào)整中繼點(diǎn)，繼續(xù)循環(huán)判斷；直至當(dāng)前調(diào)整中繼點(diǎn)為起點(diǎn)，停止循環(huán)，則各個調(diào)整中繼點(diǎn)構(gòu)建出調(diào)整后的航跡序列vw2[l]。

通過改進(jìn)A*算法，分別以各基地和任務(wù)點(diǎn)為起止點(diǎn)，啟發(fā)式搜索航跡，并估算各基地與各個任務(wù)點(diǎn)、各個任務(wù)點(diǎn)之間的A*預(yù)估航程距離。

3.2 多基地多無人機(jī)任務(wù)分配

設(shè)基地序列為P={P1,P2,P3…Pn}，基地?cái)?shù)量為n；任務(wù)目標(biāo)序列為T={T1,T2,T3…Tm}，任務(wù)數(shù)量為m；構(gòu)建距離矩陣d[n][m]，用于表示每個基地距離每一目標(biāo)的A*距離；構(gòu)建距離矩陣表示為q[m][m]，用于表示任兩個目標(biāo)之間的A*距離；各基地?zé)o人機(jī)數(shù)量序列為U={U1,U2,U3…Un}，用于表示各個基地配置的無人機(jī)數(shù)量。

圖5所示為多基地?zé)o人機(jī)任務(wù)分配編碼示意圖，確保每項(xiàng)任務(wù)均有無人機(jī)負(fù)責(zé)執(zhí)行。

圖5 多基地多無人機(jī)任務(wù)分配編碼示意圖Fig.5 Schematic diagram of mission assignment coding

根據(jù)任務(wù)數(shù)量和分布情況，多無人機(jī)任務(wù)分配可以區(qū)分兩種情況求解：①任務(wù)數(shù)量多、區(qū)域集中分布時(shí)，采用基于目標(biāo)聚類的求解方法。該方法包括目標(biāo)區(qū)域聚類、聚類目標(biāo)分配、基地內(nèi)無人機(jī)任務(wù)分配等多個處理環(huán)節(jié)，可將較大規(guī)模的目標(biāo)分配問題化繁為簡、時(shí)效性和可擴(kuò)展性好；②任務(wù)數(shù)量少、疏散分布時(shí)，采用基于深度遍歷的求解方法。該方法適用于計(jì)算規(guī)模小、目標(biāo)聚類初始參數(shù)難以確定等情況，簡化了求解過程，直接采用深度遍歷方法進(jìn)行精確任務(wù)分配。

3.2.1 基于目標(biāo)聚類的求解方法

基于目標(biāo)聚類的求解方法包括三個處理環(huán)節(jié)：目標(biāo)區(qū)域聚類、聚類目標(biāo)分配、基地內(nèi)無人機(jī)任務(wù)分配等。目標(biāo)區(qū)域聚類，是實(shí)現(xiàn)目標(biāo)按地理分布集聚特性進(jìn)行區(qū)域聚類；聚類目標(biāo)分配，是實(shí)現(xiàn)將各個聚類目標(biāo)區(qū)域分配給距離最近的無人機(jī)基地；基地內(nèi)無人機(jī)任務(wù)分配，是實(shí)現(xiàn)無人機(jī)基地內(nèi)多架無人機(jī)的目標(biāo)分配。

K-means聚類算法是一種迭代求解的聚類分析方法，其原理簡單、收斂速度快、實(shí)用性好[16,17]。采用各目標(biāo)間距離作為相似性評價(jià)指標(biāo)，通過多輪循環(huán)迭代，最終確定K個緊湊且相對獨(dú)立的目標(biāo)聚類。需要注意的是，由于無人機(jī)基地的異構(gòu)性，各無人機(jī)基地配備的無人機(jī)數(shù)量和型號不同，因此聚類目標(biāo)不應(yīng)超出其距離最近基地的任務(wù)能力值，需要關(guān)注各基地的總?cè)蝿?wù)航程這一約束條件。

結(jié)合具體應(yīng)用背景，在初始聚類中心選取、添加任務(wù)總航程約束、確定聚類目標(biāo)對應(yīng)的基地等方面，對傳統(tǒng)K-means算法進(jìn)行改進(jìn)。改進(jìn)K-means聚類算法的處理流程，如圖6所示為：

圖6 改進(jìn)K-means聚類算法的流程圖Fig.6 The framework of improved K-means algorithm

步驟1 目標(biāo)聚類初始化。選取K個位置分散的目標(biāo)點(diǎn)為初始聚類中心。傳統(tǒng)的隨機(jī)選取初始聚類中心的方法，容易導(dǎo)致聚類效果不佳，因此根據(jù)GIS系統(tǒng)上各位置點(diǎn)的分布，手動點(diǎn)擊選擇K個相對離散、可能接近目標(biāo)區(qū)域中心的位置點(diǎn)，作為初始聚類中心點(diǎn)；

步驟2 確定無人機(jī)基地與目標(biāo)聚類的對應(yīng)關(guān)系。將無人機(jī)基地分配給距離最近的聚類中心點(diǎn)；

步驟3 循環(huán)目標(biāo)聚類。循環(huán)計(jì)算各目標(biāo)點(diǎn)到各個聚類中心的距離，將每個目標(biāo)劃入其距離最近的目標(biāo)區(qū)域類中。為避免聚類區(qū)域的目標(biāo)數(shù)量超出距離最近基地的任務(wù)能力，基于航程代價(jià)進(jìn)行判斷。若隨機(jī)選取一個聚類目標(biāo)序列，其與對應(yīng)基地之間總航程超過基地內(nèi)所有無人機(jī)最大航程，則從該目標(biāo)類中選擇距離鄰近目標(biāo)聚類中心最近的一個目標(biāo)，將該目標(biāo)加入鄰近目標(biāo)聚類中；

步驟4 更新目標(biāo)聚類中心點(diǎn)。根據(jù)所有數(shù)據(jù)點(diǎn)的平均距離值計(jì)算區(qū)域質(zhì)心位置，將聚類中心調(diào)整至各區(qū)域類的中心目標(biāo)點(diǎn)；

步驟5 重復(fù)步驟2、3和4，直至聚類中心不再變化或達(dá)到最大的迭代次數(shù)。

通過改進(jìn)后的K-means目標(biāo)聚類方法，實(shí)現(xiàn)目標(biāo)區(qū)域聚類和聚類目標(biāo)分配等兩種功能，將目標(biāo)按地理分布分成任務(wù)區(qū)域、并將任務(wù)區(qū)域分配給距離最近的無人機(jī)基地。

單個基地內(nèi)的無人機(jī)任務(wù)分配，若單架無人機(jī)能夠完成任務(wù)，則優(yōu)先使用單無人機(jī)執(zhí)行；若單架次無人機(jī)無法完成所有任務(wù)，則結(jié)合執(zhí)行任務(wù)的總航程和單機(jī)的最大航程，估算出所需的無人機(jī)數(shù)量，進(jìn)而采用K-means聚類方法進(jìn)行基地內(nèi)的多無人機(jī)任務(wù)分配。最終為每架無人機(jī)分配任務(wù)，第w架無人機(jī)對應(yīng)的任務(wù)分組為hw[k]。

3.2.2 基于深度遍歷的求解方法

任務(wù)數(shù)量少、疏散分布時(shí)，通常計(jì)算規(guī)模較小，可簡化求解環(huán)節(jié)，直接采用深度遍歷方法進(jìn)行精確任務(wù)分配。為每個基地分配距離最近的目標(biāo)，目標(biāo)函數(shù)Z表示為：

其中，dij為無人機(jī)i到目標(biāo)j的A*距離。

約束條件為：①最大航程約束。單個基地的無人機(jī)執(zhí)行多任務(wù)的總航程不能超出其最大航程Lmax。②任務(wù)約束。每個基地一架無人機(jī)參與任務(wù)，每個目標(biāo)至少有一架無人機(jī)去執(zhí)行任務(wù)。

深度遍歷精確求解的流程表述為：

步驟1 按照目標(biāo)序列T的編號，從第一個目標(biāo)開始依次循環(huán)；對比目標(biāo)與每個無人機(jī)基地的距離，選擇出距離當(dāng)前目標(biāo)最近的無人機(jī)基地；依次循環(huán)比較，最終確定與目標(biāo)序列T對應(yīng)的無人機(jī)基地序列，設(shè)為H={H1,H2,H3…Hm}。

步驟2 結(jié)合序列T和H的對應(yīng)關(guān)系，為每架無人機(jī)分配任務(wù)，獲得第w架無人機(jī)對應(yīng)的任務(wù)分組為hw[k]。

3.3 基地內(nèi)單無人機(jī)時(shí)序任務(wù)分配

在多基地?zé)o人機(jī)任務(wù)分配方案中，若單個無人機(jī)分配了多項(xiàng)任務(wù)，則需進(jìn)行單無人機(jī)多任務(wù)時(shí)序分配。單無人機(jī)時(shí)序任務(wù)分配，采用了TSP旅行商模型。傳統(tǒng)的TSP模型求解時(shí)，在計(jì)算各路徑點(diǎn)之間的距離時(shí)，通常是將各點(diǎn)之間距離簡化為直線歐式距離[18,19]。在復(fù)雜高對抗的戰(zhàn)場環(huán)境下，目標(biāo)點(diǎn)間距離若不考慮規(guī)避威脅區(qū)域，將存在較大的誤差，TSP求解將難以獲取合理的結(jié)果。因此，改進(jìn)傳統(tǒng)TSP求解方法，任意兩點(diǎn)的距離采用A*算法預(yù)估距離。

充分考慮規(guī)避威脅區(qū)域，采用A*算法估算出無人機(jī)起飛點(diǎn)、多個任務(wù)目標(biāo)點(diǎn)之間的距離。對于第w架無人機(jī)，其對應(yīng)的任務(wù)分組為hw[k]，構(gòu)建出A*距離矩陣表示為pw[k][k]，k為第w架無人機(jī)的對應(yīng)任務(wù)數(shù)。

目標(biāo)函數(shù)R表示為：

其中，hij為無人機(jī)從目標(biāo)i到目標(biāo)j的A*距離，cij?{0,1}為決策變量。

若時(shí)序任務(wù)分配規(guī)模較小，優(yōu)先采用遍歷法，循環(huán)比較任何一種可能方案，準(zhǔn)確獲得最優(yōu)解。若時(shí)序任務(wù)分配規(guī)模較大，精確算法求解計(jì)算量過大，采用遺傳算法求解[20]。

4 航跡規(guī)劃

4.1 航跡尋優(yōu)

基于多無人機(jī)任務(wù)分配和單機(jī)時(shí)序任務(wù)分配的分配方案，依據(jù)每架無人機(jī)的任務(wù)序列分別進(jìn)行航跡規(guī)劃，應(yīng)用改進(jìn)A*算法進(jìn)行航跡尋優(yōu)。A*算法按照3.1執(zhí)行。

以第w架無人機(jī)為例，無人機(jī)w的起點(diǎn)、時(shí)序序列uw[k]中的各任務(wù)點(diǎn)、無人機(jī)w的回收點(diǎn)構(gòu)成航跡點(diǎn)序列，從起點(diǎn)開始，依次將航跡序列中的兩個連續(xù)時(shí)序節(jié)點(diǎn)作為A*搜索的起止點(diǎn)，獲得各連續(xù)節(jié)點(diǎn)之間的初始航跡序列vw1[r]、及調(diào)整后航跡序列vw2[l]。任意兩個時(shí)序連續(xù)節(jié)點(diǎn)間的vw2[l]，組合在一起最終構(gòu)成第w架無人機(jī)的總航跡vw3[q]，總航跡點(diǎn)數(shù)量為q。

將無人機(jī)的航跡點(diǎn)vw3[q]，進(jìn)行地理坐標(biāo)轉(zhuǎn)換，繪制在地理信息系統(tǒng)上，可得到無人機(jī)航跡圖。依次繪制每架無人機(jī)的航跡點(diǎn)，得到多基地多無人機(jī)的航跡規(guī)劃圖。

4.2 航跡平滑

航跡尋優(yōu)繪制的航跡為折線圖，不符合實(shí)際航跡，需要進(jìn)行航跡平滑處理，得出滿足飛行約束的航跡曲線。三次B樣條曲線具有局部性、凸包性和C2連續(xù)性等特點(diǎn)，平滑效果好[21]。

基于A*算法航跡尋優(yōu)獲得的航跡控制點(diǎn)為Pi(i=0,1 …n)，采用三次B樣條曲線進(jìn)行平滑處理，每段曲線由連續(xù)相鄰4個航跡控制點(diǎn)確定。三次B樣條曲線可表示為：

5 局部動態(tài)任務(wù)規(guī)劃

在復(fù)雜多變的戰(zhàn)場環(huán)境中，往往存在突發(fā)威脅、目標(biāo)變化等情況，全局規(guī)劃航跡將不能滿足任務(wù)的動態(tài)需求。根據(jù)戰(zhàn)場態(tài)勢變化，在預(yù)先全局規(guī)劃的基礎(chǔ)上，僅進(jìn)行局部動態(tài)規(guī)劃，從而可縮小規(guī)劃空間、減少規(guī)劃時(shí)間。具體表述如下：

①局部區(qū)域設(shè)置。根據(jù)威脅區(qū)域和目標(biāo)變化情況，在GIS中點(diǎn)擊選定局部規(guī)劃的起點(diǎn)、多個目標(biāo)點(diǎn)、終止點(diǎn)的位置，標(biāo)繪局部威脅區(qū)域，確定局部規(guī)劃空間。初始點(diǎn)和終止點(diǎn)通常選在威脅區(qū)域邊界附近的預(yù)先規(guī)劃航跡上，中間點(diǎn)為無人機(jī)必須經(jīng)過的一些目標(biāo)點(diǎn)，包括預(yù)先已知目標(biāo)點(diǎn)和動態(tài)變化的目標(biāo)點(diǎn)。

②局部任務(wù)動態(tài)分配。依據(jù)改進(jìn)A*算法，構(gòu)建局部規(guī)劃起點(diǎn)、多個目標(biāo)點(diǎn)、終止點(diǎn)之間的A*預(yù)估航程矩陣；基于旅行商模型和遺傳算法，求解各點(diǎn)的時(shí)序任務(wù)分配。

③局部航跡動態(tài)規(guī)劃。采用改進(jìn)A*算法規(guī)劃并繪制航跡，基于三次B樣條曲線法進(jìn)行航跡平滑，規(guī)劃出局部起點(diǎn)、各中間點(diǎn)、終止點(diǎn)之間的航跡。

6 實(shí)驗(yàn)驗(yàn)證

針對多無人機(jī)任務(wù)規(guī)劃的應(yīng)用需求，采用Visual Studio 2015與QT5.8開發(fā)環(huán)境、以及C++編程語言，基于本文提出的任務(wù)規(guī)劃方法，開發(fā)了多無人機(jī)任務(wù)規(guī)劃軟件。圖7所示為任務(wù)規(guī)劃軟件的主界面，軟件界面主要包括菜單欄、GIS顯示區(qū)域、狀態(tài)顯示區(qū)域、任務(wù)規(guī)劃子界面等，任務(wù)規(guī)劃子界面包括基本設(shè)置（網(wǎng)格設(shè)置、標(biāo)繪設(shè)置、分配設(shè)置等）、任務(wù)規(guī)劃按鍵（位置選取、區(qū)域設(shè)定、威脅標(biāo)繪等）、以及任務(wù)顯示區(qū)域。

任務(wù)規(guī)劃測試的主要操作流程為：輸入或選取各初始設(shè)置參數(shù)；依次點(diǎn)擊無人機(jī)選取、目標(biāo)選取、區(qū)域設(shè)定、威脅標(biāo)繪、威脅確定等按鍵，并相應(yīng)在GIS區(qū)域點(diǎn)擊確定各位置點(diǎn)、繪制威脅區(qū)域，實(shí)現(xiàn)規(guī)劃區(qū)域設(shè)置；點(diǎn)擊航程估算、聚類選取、目標(biāo)聚類、任務(wù)分配等按鍵，實(shí)現(xiàn)任務(wù)分配，分配結(jié)果以圖示形式在任務(wù)顯示區(qū)域顯示；點(diǎn)擊航跡搜索、航跡調(diào)整和航跡平滑等按鍵，航跡規(guī)劃結(jié)果在GIS界面中繪制并顯示。

測試1 基于改進(jìn)K-means聚類求解的分階段任務(wù)規(guī)劃流程測試。按照任務(wù)規(guī)劃處理流程，逐步驟進(jìn)行分析驗(yàn)證，多基地多無人機(jī)任務(wù)分配階段采用K-means聚類的方法求解。

（1）參數(shù)設(shè)置

規(guī)劃區(qū)域內(nèi)包括3個無人機(jī)基地和18個目標(biāo)，規(guī)劃空間約80 km×70 km，網(wǎng)格邊長h為1 km，擴(kuò)展距離H為20 km，無人機(jī)最大航程200 km。

（2）測試結(jié)果分析

圖7(a)所示為，分別在GIS中點(diǎn)擊確定了無人機(jī)基地和目標(biāo)的位置，目標(biāo)分布呈現(xiàn)區(qū)域集中的分布態(tài)勢，以手繪形式標(biāo)記出任意形狀的多個威脅區(qū)域，點(diǎn)擊“航程估算”預(yù)估出各個位置點(diǎn)之間A*航程，點(diǎn)擊“聚類選取”確定了3個目標(biāo)初始聚類中心，GIS區(qū)域的實(shí)心圓點(diǎn)表示初始聚類中心；圖7(b)所示為，點(diǎn)擊“目標(biāo)聚類”實(shí)現(xiàn)目標(biāo)區(qū)域聚簇，GIS區(qū)域的實(shí)心圓點(diǎn)分別為初始聚類中心及K-means聚類后的中心，點(diǎn)擊“任務(wù)分配”，將3個聚類目標(biāo)群分配至3個無人機(jī)基地，分配結(jié)果顯示在任務(wù)顯示區(qū)域；圖7(c)所示為，點(diǎn)擊“航跡搜索”后，在GIS區(qū)域繪制出各無人機(jī)與其時(shí)序任務(wù)之間的A*搜索航跡，可以看出航跡能夠規(guī)避障礙，但由于A*搜索局限在柵格交叉點(diǎn)而導(dǎo)致部分航跡呈鋸齒狀；圖7(d)所示為，點(diǎn)擊“航跡調(diào)整”后，繪制出調(diào)整優(yōu)化后的航跡，將部分A*搜索鋸齒型折線航跡段優(yōu)化為直線；圖7(e)所示為，點(diǎn)擊“航跡平滑”后，在GIS區(qū)域繪制出B樣條平滑航跡；圖7(f)所示為，分別在局部區(qū)域標(biāo)志出局部起點(diǎn)、2個中間點(diǎn)、局部終點(diǎn)，標(biāo)繪更新后的威脅區(qū)域，在動態(tài)規(guī)劃子界面，點(diǎn)擊“任務(wù)分配”，求出時(shí)序任務(wù)分配結(jié)果；點(diǎn)擊“航跡搜索、航跡調(diào)整、航跡平滑”后，規(guī)劃出局部動態(tài)航跡曲線。

圖7 基于K-means聚類求解的任務(wù)規(guī)劃測試Fig.7 Mission plan test with K-means algorithm

測試結(jié)果表明，目標(biāo)聚簇分配和目標(biāo)時(shí)序分配合理，航跡規(guī)避了障礙區(qū)域，通過航跡調(diào)整和航跡平滑優(yōu)化了復(fù)雜威脅條件下無人機(jī)航跡，動態(tài)任務(wù)規(guī)劃結(jié)果合理，測試過程計(jì)算無明顯時(shí)延。

測試2 基于深度遍歷求解的分階段任務(wù)規(guī)劃流程測試。按照任務(wù)規(guī)劃處理流程，逐步驟進(jìn)行分析驗(yàn)證，多無人機(jī)任務(wù)分配階段采用深度遍歷方法求解。

（1）參數(shù)設(shè)置

規(guī)劃區(qū)域內(nèi)包括5個無人機(jī)基地和7個目標(biāo)，規(guī)劃空間約80 km×70 km，網(wǎng)格邊長h為1 km，擴(kuò)展距離H為20 km，無人機(jī)最大航程200 km。

（2）測試結(jié)果分析

圖8(a)所示為，分別在GIS中點(diǎn)擊確定了無人機(jī)基地和目標(biāo)位置，目標(biāo)數(shù)量較少、呈疏散分布態(tài)勢，以手繪形式標(biāo)記出任意形狀的多個威脅區(qū)域，點(diǎn)擊“航程估算”預(yù)估出各個位置點(diǎn)之間A*航程，點(diǎn)擊“任務(wù)分配”為每個目標(biāo)分配無人機(jī)，2個無人機(jī)基地參與執(zhí)行任務(wù)，分配結(jié)果顯示在任務(wù)顯示區(qū)域；圖8(b)所示為，點(diǎn)擊“航跡搜索”，在GIS區(qū)域繪制出各無人機(jī)與其時(shí)序任務(wù)之間的A*搜索航跡；圖8(c)所示為，點(diǎn)擊“航跡調(diào)整”，將部分A*搜索鋸齒型折線航跡段進(jìn)行優(yōu)化；圖8(d)所示為，點(diǎn)擊“航跡平滑”后，在GIS區(qū)域繪制出B樣條平滑航跡。圖8(e)所示為，分別標(biāo)記2組局部起點(diǎn)、中間點(diǎn)、局部終點(diǎn)，標(biāo)繪更新威脅區(qū)域，點(diǎn)擊“任務(wù)分配”，求出任務(wù)分配結(jié)果；點(diǎn)擊“航跡搜索、航跡調(diào)整、航跡平滑”，規(guī)劃出2組局部動態(tài)航跡曲線。

圖8 基于深度遍歷求解的任務(wù)規(guī)劃測試Fig.8 Mission plan with depth first search algorithm

測試表明，疏散分布的目標(biāo)合理分配至各無人機(jī)基地，各無人機(jī)航跡有效規(guī)避了威脅區(qū)，通過航跡調(diào)整和航跡平滑優(yōu)化了復(fù)雜威脅條件下的無人機(jī)航跡。動態(tài)任務(wù)規(guī)劃結(jié)果合理，測試過程無明顯時(shí)延。

測試3 傳統(tǒng)A*算法和改進(jìn)A*算法的比較分析。結(jié)合測試1中的圖7(c)和7(d)進(jìn)行比較分析，圖7(c)所示為按照傳統(tǒng)A*算法繪制的航跡，圖7(d)所示為按照本文改進(jìn)A*算法繪制的航跡。表1所示為改進(jìn)A*算法的比較分析表，給出了傳統(tǒng)A*和改進(jìn)A*算法的航跡參數(shù)表。

表1 改進(jìn)A*算法的比較分析Tab.1 Comparison of improved A＊ algorithm

通過比較表明，改進(jìn)A*算法有效濾除了冗余航跡節(jié)點(diǎn)，抑制了鋸齒形搜索航跡，縮短了無人機(jī)航程，航程縮短了4%以上。進(jìn)而易于通過航跡平滑獲取優(yōu)化航跡。

測試4 應(yīng)用改進(jìn)A*預(yù)估距離與歐式預(yù)估距離的任務(wù)規(guī)劃比較分析。圖9所示為應(yīng)用歐式預(yù)估距離的任務(wù)規(guī)劃測試結(jié)果，在任務(wù)分配過程中的航程代價(jià)均應(yīng)用歐式直線距離。圖10所示為本文所提出方法的測試結(jié)果，在任務(wù)分配過程中的航程代價(jià)均應(yīng)用改進(jìn)A*預(yù)估距離。多基地多無人機(jī)任務(wù)分配階段采用改進(jìn)K-means聚類的方法求解。表2所示為應(yīng)用改進(jìn)A*預(yù)估距離的任務(wù)規(guī)劃比較分析表，給出了兩種方法的測試結(jié)果。

圖9 應(yīng)用歐式預(yù)估距離的任務(wù)規(guī)劃測試Fig.9 Mission plan with Euclidean estimated route

圖10 應(yīng)用改進(jìn)A*預(yù)估距離的任務(wù)規(guī)劃測試Fig.10 Mission plan with improved A* estimated route

表2 應(yīng)用改進(jìn)A*預(yù)估距離的任務(wù)規(guī)劃比較分析Tab.2 Comparison of mission plan with improved A＊route

通過比較表明，應(yīng)用改進(jìn)A*預(yù)估距離時(shí)，在目標(biāo)區(qū)域聚類、聚類目標(biāo)分配階段中，均能夠顧及威脅障礙區(qū)對于預(yù)估距離的影響，而直線歐式預(yù)估距離無法考慮障礙區(qū)影響，應(yīng)用改進(jìn)A*預(yù)估距離的任務(wù)規(guī)劃具有更短的航程。航程縮短了12%。

7 結(jié) 論

本文系統(tǒng)地給出了一種多基地?zé)o人機(jī)多階段、層次化的任務(wù)規(guī)劃處理流程，開發(fā)了多無人機(jī)任務(wù)規(guī)劃軟件，驗(yàn)證了所提出方法的有效性。主要結(jié)論如下：（1）改進(jìn)了傳統(tǒng)A*算法，通過航跡調(diào)整，剔除冗余節(jié)點(diǎn)，將節(jié)點(diǎn)柵格擴(kuò)展的鋸齒型折線優(yōu)化為直線航跡；（2）考慮任務(wù)分配和航跡規(guī)劃的航程耦合關(guān)系，在多階段任務(wù)分配中，應(yīng)用改進(jìn)A*算法預(yù)估航程矩陣，生成滿足威脅規(guī)避和飛行性能約束的任務(wù)分配方案；

（3）在初始聚類中心選取、添加任務(wù)總航程約束、確定聚類目標(biāo)對應(yīng)的基地等方面，改進(jìn)傳統(tǒng)的K-means算法，實(shí)現(xiàn)了目標(biāo)區(qū)域聚類和聚類目標(biāo)分配等功能。

本文方法主要適用于靜態(tài)確定威脅環(huán)境，對于動態(tài)不確定環(huán)境適應(yīng)性不強(qiáng)。下一步，需要結(jié)合動態(tài)不確定的戰(zhàn)場威脅、任務(wù)變更、飛機(jī)損毀等對抗性行動展開研究，精確評估威脅模型和威脅度，針對多種不確定要素進(jìn)行綜合任務(wù)規(guī)劃，提高對抗性環(huán)境下任務(wù)規(guī)劃方法的實(shí)用性。