基于改進A*算法的無人機任務分配和航跡規(guī)劃優(yōu)化方法

鄭 鍇， 鄭獻民， 殷少鋒， 林宏旭， 孟慶豪

(中國人民解放軍32146部隊，河南 焦作 454000)

1 概述

任務分配和航跡規(guī)劃是無人機任務規(guī)劃的關鍵技術問題，國內外學者對無人機任務分配和航跡規(guī)劃開展了廣泛的研究，已取得了較大進展。無人機任務分配優(yōu)化算法主要包括數學規(guī)劃法、啟發(fā)式算法、智能優(yōu)化算法等；無人機航跡規(guī)劃優(yōu)化算法主要包括數學規(guī)劃法、基于圖形學的方法、啟發(fā)式搜索算法、智能優(yōu)化算法等[1-2]。

任務分配和航跡規(guī)劃并非簡單的連續(xù)過程，而是具有緊密的相互作用關系。在已有的研究工作中，往往將無人機的任務分配和航跡規(guī)劃作為兩個相對獨立的環(huán)節(jié)進行研究，無人機任務分配過程中通常應用直線歐氏距離近似表示航程，未充分考慮威脅區(qū)域等對航跡預估的影響，從而易造成任務分配不合理。在動態(tài)不確定、強對抗性的戰(zhàn)場環(huán)境下，無人機任務規(guī)劃面臨著復雜的環(huán)境約束條件，迫切要求在任務分配中參考航跡規(guī)劃的預估結果，在航跡規(guī)劃中應用任務分配的結果[3-6]。

本文提出了一種基于改進A*算法的無人機任務分配和航跡規(guī)劃優(yōu)化方法。該方法以無人機執(zhí)行多目標偵察任務為應用背景，基于改進A*算法預估航程代價，通過無人機區(qū)域設置、任務分配、航跡規(guī)劃等全局預先任務規(guī)劃階段，以及局部動態(tài)任務規(guī)劃階段，實現無人機多時序目標任務規(guī)劃。任務規(guī)劃的原理框圖如圖1所示。

圖1 任務規(guī)劃原理框圖

其主要流程如下。1) 區(qū)域設置。在地理信息系統(tǒng)(Geographic Information System,GIS)中，依次點擊無人機陣地坐標和任務坐標，確定任務規(guī)劃區(qū)域范圍，采用不同幾何形狀標記威脅區(qū)域。2) 任務分配。改進傳統(tǒng)A*算法，構建無人機、各任務點之間的A*預估航程矩陣；應用旅行商問題(Travelling Salesman Problem,TSP)模型和遺傳算法，求解各陣地內單無人機的時序任務分配。3) 航跡規(guī)劃。采用改進A*算法規(guī)劃并繪制航跡，基于三次B樣條曲線法進行航跡平滑。4) 局部動態(tài)任務規(guī)劃。在全局預先任務規(guī)劃的基礎上，依據威脅區(qū)域、任務目標的變化，確定局部動態(tài)規(guī)劃空間，執(zhí)行局部任務動態(tài)分配和局部航跡動態(tài)規(guī)劃。

2 規(guī)劃區(qū)域設置

典型應用場景為：無人機執(zhí)行多目標偵察任務，任務區(qū)域內有地形、探測和火力等多種飛行安全威脅，以無人機航程最短、消耗最小、安全性最好為優(yōu)化目的，每個目標至少被偵察一次，無人機航跡規(guī)避每個威脅區(qū)域，求解無人機的最優(yōu)任務分配和航跡規(guī)劃方案。

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

在地理信息系統(tǒng)中，點擊選定并標注無人機和多任務的位置，確定任務規(guī)劃的區(qū)域范圍，規(guī)劃區(qū)域見圖2。

圖2 規(guī)劃空間示意圖

設在無人機和任務位置點中，最大高斯坐標值分別為Xmax和Ymax，最小高斯坐標值分別為Xmin和Ymin，規(guī)劃空間的擴展距離值為L，則可確定矩形規(guī)劃區(qū)域的4個頂點分別為(Xmin-L,Ymin-L)，(Xmin-L,Ymax+L)，(Xmax+L,Ymax+L)和(Xmax+L,Ymin-L)。

將二維規(guī)劃空間離散柵格化，(Xmin-L,Ymin-L)為原點，設h為網格邊長，則規(guī)劃空間中任意點(x,y)的網格坐標(xg,yg)為

(1)

2.2 威脅設置

在地理和氣象條件惡劣、高強度對抗、空域資源緊張等特殊戰(zhàn)場環(huán)境下，無人機執(zhí)行任務將面臨地形、雷達探測、電子對抗、防空火力、禁飛區(qū)等飛行威脅區(qū)域。根據不同威脅模型的特點，分別通過手繪或標注等形式，用圓形、矩形、多邊形等不同形狀標記威脅區(qū)域。按式(1)計算威脅區(qū)域邊界的網格坐標(xgt,ygt)，構建威脅區(qū)域矩陣G[x][y]，令G[xgt][ygt]=1表示該網格為威脅網格，G[xgt][ygt]=0表示該網格不是威脅網格。

3 改進A*算法設計

A*算法是一種啟發(fā)式搜索算法，通過在柵格化空間不斷評估路徑函數值來啟發(fā)式搜索節(jié)點，構造最優(yōu)航跡[7-9]。A*算法全局性好、運行較快、易于工程實現，在航跡規(guī)劃領域獲得了廣泛的關注。結合具體應用背景，對傳統(tǒng)A*算法進行了改進設計，通過約束扇形搜索區(qū)域減小搜索計算代價，通過航跡節(jié)點調整去優(yōu)化鋸齒型航跡。

3.1 確定代價函數

A*算法的代價函數為

f(n)=g(n)+h(n)

(2)

式中：n為當前節(jié)點;f(n)為起始點經節(jié)點n到目標點的代價函數;g(n)為從起始點到節(jié)點n的實際代價;h(n)為節(jié)點n到目標節(jié)點的估計代價。

g(n)表示為

g(n)=ω1ln+ω2Jn+ω3zn

(3)

式中：ln為航程代價;Jn為威脅代價;zn為高度代價;ω1,ω2和ω3表示對應的代價權值。在戰(zhàn)場高對抗條件下，無人機安全飛行是首要指標，要求航跡能夠規(guī)避所有威脅區(qū)域，將威脅代價設為無窮大，令ω2=∞；無人機通常優(yōu)先采用固定高度巡航，為簡化航跡優(yōu)化問題、減少計算量，設定無人機以固定高度巡飛，將三維空間航跡搜索問題簡化為二維問題，令ω1=1，ω3=0。

h(n)可理解為啟發(fā)函數，引導節(jié)點(xn,yn)向目標點(xt,yt)的方向搜索擴展，可表示為

(4)

3.2 限定約束條件

考慮無人機最大航程、最小軌跡段長度、最大轉彎角等性能約束，為優(yōu)化搜索空間、提高搜索速度，在啟發(fā)式航跡搜索過程中，設定以下約束條件。

1) 最大航程。

無人機受數據鏈作用距離、飛行動力等因素影響，最大航程受限。單架無人機航跡搜索的總航程f應小于無人機的最大航程Lmax，即f

2) 最小軌跡段長度。

受機動能力約束，改變飛行方向前，需要沿原方向直飛一段距離，即最短直飛距離為lmin。在A*算法中，網格邊長h為搜索步長，搜索步長應大于最小航跡段長度，即h>lmin。

3) 最大轉彎角。

在規(guī)劃空間啟發(fā)性搜索下一節(jié)點時，限定在扇形約束區(qū)域內搜索，而不是遍歷每個相鄰節(jié)點。圖3為搜索區(qū)域示意圖，陰影區(qū)域表示扇形搜索區(qū)域，最大轉彎角θ對應于最小轉彎半徑Rmin，節(jié)點擴展角α在2θ范圍內，從而可減小搜索空間、加快搜索速度。

圖3 航跡節(jié)點的扇形搜索區(qū)域示意圖

3.3 航跡節(jié)點調整

在柵格化節(jié)點擴展過程中，節(jié)點擴展主要局限在柵格線的交叉點上，會導致部分航跡呈鋸齒狀。為了避免鋸齒形航跡，需要進行航跡節(jié)點調整，將部分鋸齒形折線航跡優(yōu)化為直線。圖4所示為節(jié)點調整示意圖，將虛線航跡優(yōu)化為實線航跡。

圖4 航跡節(jié)點調整示意圖

設初始航跡節(jié)點序列為vw1[r]，節(jié)點序列數量為r，則節(jié)點的調整過程為：1) 初始令j=r；2) 循環(huán)檢查(vw1[i],vw1[j])之間的連線是否通過威脅區(qū)，i∈{1,…,j-1}，若通過威脅區(qū)，令i=i+1,若不通過威脅區(qū)，令j=i，并將vw1[j]保存為調整后的航跡節(jié)點；3) 重復上述循環(huán)，直至j=1時停止循環(huán)，生成調整后的航跡序列vw2[l]，調整后的節(jié)點序列數量為l。

3.4 航跡搜索過程

在啟發(fā)式搜索時，建立Open和Close兩個表，Open表用于存儲已經計算但沒有擴展的節(jié)點，Close表用于存儲已經擴展的節(jié)點。數據存儲結構表示為{(xi,yi),fi,gi,hi,pi}，(xi,yi)為節(jié)點的網格坐標，fi,gi和hi為代價函數的變量值，pi代表當前節(jié)點的父節(jié)點。改進A*算法流程如圖5所示。

圖5 改進A*算法流程圖

算法流程如下。

1) 初始化。設置步長和障礙區(qū)域，初始化Open和Close表，起點放入Open表中作為當前節(jié)點。

2) 節(jié)點擴展與存儲。當前節(jié)點的相鄰節(jié)點，若滿足約束條件且不在當前Open和Close表中，則將該有效節(jié)點加入Open表；將Open表中代價最小的節(jié)點A移到Close表中；判斷節(jié)點A是否為終點，若是終點則退出節(jié)點搜索，若不是終點則繼續(xù)節(jié)點擴展。從Close表中提取初始航跡節(jié)點序列vw1[r]，將終點的代價函數值作為預估航程。

3) 航跡節(jié)點調整。初始設vw1[r]中的初始航跡起點為調整起點，初始航跡終點作為調整中繼點；從調整起點開始，依次判斷vw1[r]中各航跡點與調整中繼點的連線是否經過障礙區(qū)；若調整起點與調整中繼點的連線通過障礙，則將當前調整起點的下一點更新為調整起點，繼續(xù)判斷是否通過障礙；若調整起點與調整中繼點的連線不通過障礙，將當前調整中繼點保存為航跡調整后的一個航程點，并將當前調整起點更新為調整中繼點，繼續(xù)循環(huán)判斷；直至當前調整中繼點為起點，停止循環(huán)，綜合各個調整中繼點構建出調整后的航跡序列vw2[l]。

4 任務分配

TSP問題是經典的路徑優(yōu)化問題，傳統(tǒng)的TSP模型求解時，通常將各點之間距離簡化為直線歐氏距離[10]。在復雜高對抗的戰(zhàn)場環(huán)境下，目標點間距離若不考慮規(guī)避威脅區(qū)域，將存在較大的誤差，TSP求解將難以獲取合理的結果。因此，改進TSP求解方法，任意兩點的距離采用A*算法預估距離。

考慮規(guī)避威脅區(qū)域，采用A*算法估算出無人機起點、多個任務目標點之間的距離，構建出A*距離矩陣pw[k][k]，k為無人機的任務數量。圖6所示為時序任務分配編碼示意圖，起點和終點為無人機陣地，1,2,…,k代表目標序號。

圖6 時序任務分配編碼示意圖

目標函數R表示為

(5)

式中：hi j為無人機從目標i到目標j的A*距離;ci j∈{0,1},為決策變量。

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

5 航跡規(guī)劃

5.1 航跡尋優(yōu)

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

無人機起點、時序序列u[c]中的各任務點、無人機回收點構成航跡點序列，從起點開始，依次將航跡序列中的兩個連續(xù)時序節(jié)點作為A*搜索的起止點，獲得各連續(xù)節(jié)點之間的初始航跡序列v1[r]及調整后航跡序列v2[l]。任意兩個時序連續(xù)節(jié)點間的v2[l]，組合在一起構成無人機的總航跡v3[q]，總航跡點數量為q。

將無人機的航跡點v3[q]進行地理坐標轉換，繪制在地理信息系統(tǒng)上，可得到無人機航跡圖。

5.2 航跡平滑

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

航跡尋優(yōu)獲得的航跡控制點為Pi(i=0,1,…,n)，采用三次B樣條曲線進行平滑處理，每段曲線由連續(xù)相鄰的4個航跡控制點確定。改進A*算法的航跡點往往易于稀疏化，使航跡平滑曲線更接近初始航跡折線，可考慮在v3[q]的各個航跡點附近增加控制點，比如航跡點v3[i]與節(jié)點v1[j]相對應，可在v3[i]點后增加控制點v1[j+1]，再執(zhí)行曲線平滑操作。

n次B樣條曲線可表示為

(6)

式中：Pi為序列航跡點；基函數Bi,n(t)為

(7)

當n=3時，三次B樣條曲線表示為

t∈[0,1]。

(8)

6 局部動態(tài)任務規(guī)劃

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

1) 局部區(qū)域設置。根據威脅區(qū)域分布、目標變化情況，在GIS中點擊選定局部規(guī)劃的起點、多個目標點、終止點的位置，標繪威脅區(qū)域，確定局部區(qū)域范圍。起點和終止點通常在初始全局航跡上，選在更新后威脅區(qū)域的邊界附近，中間點為無人機必須經過的一些目標點，包括預先已知目標點和動態(tài)變化的目標點。

2) 局部任務動態(tài)分配。依據改進A*算法，構建局部規(guī)劃起點、多個目標點、終止點之間的A*預估航程矩陣；基于旅行商問題模型和遺傳算法，求解各點的時序任務分配。

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

7 實驗驗證

針對無人機任務規(guī)劃的應用需求，應用Visual Studio 2015與QT5.8開發(fā)環(huán)境和C++語言，開發(fā)了無人機任務規(guī)劃軟件，包括無人機管理和監(jiān)測、地理信息系統(tǒng)、任務分配、航跡規(guī)劃、數據上報等功能模塊，地理信息系統(tǒng)模塊基于OSG/OSGEarth開源庫二次開發(fā)。任務規(guī)劃軟件界面主要包括菜單欄、GIS顯示區(qū)域、狀態(tài)區(qū)域和任務規(guī)劃子界面等。

圖7(a)所示為確定無人機和7個目標的位置、標繪威脅區(qū)域后，點擊任務分配按鍵，根據考慮障礙區(qū)域的預估A*距離，求出了時序任務分配結果，并在子窗口右下方顯示出分配結果；點擊航跡搜索按鍵，給出了A*搜索的初始航跡，可以看出航跡能夠規(guī)避障礙，但是由于航跡搜索局限在柵格交叉點而導致部分航跡呈鋸齒狀。圖7(b)所示為點擊航跡調整后進行航跡節(jié)點調整，將部分鋸齒形折線航跡優(yōu)化為直線。圖7(c)所示為點擊航跡平滑按鍵后得出航跡曲線。測試結果表明，多個目標時序分配合理，無人機航跡規(guī)避了障礙區(qū)域，通過航跡調整和航跡平滑避免了航跡折線現象。測試過程無明顯時延，全局任務規(guī)劃結果合理。

圖7 全局任務規(guī)劃測試結果

圖8(a)所示為分別在局部區(qū)域標志出局部起點、2個中間點、局部終點，標繪更新后的威脅區(qū)域，點擊任務分配按鍵，根據預估A*距離，求出了時序任務分配結果，并在子窗口右下方顯示出分配結果。圖8(b)所示為點擊航跡搜索、航跡調整、航跡平滑后，規(guī)劃出局部動態(tài)航跡曲線。測試結果表明，局部動態(tài)任務規(guī)劃的目標時序分配合理，航跡規(guī)避了障礙區(qū)域，動態(tài)任務規(guī)劃結果合理。

圖8 局部動態(tài)任務規(guī)劃測試結果

8 結論

基于改進A*算法的無人機任務分配和航跡規(guī)劃優(yōu)化方法，主要包括規(guī)劃區(qū)域設置、任務分配、航跡規(guī)劃和動態(tài)任務規(guī)劃等步驟。在地理信息系統(tǒng)中，點擊選定無人機和各任務點的位置，標繪威脅區(qū)域，確定規(guī)劃區(qū)域；結合應用背景改進A*算法，通過航跡調整優(yōu)化航跡；應用預估A*航程矩陣，基于TSP模型和遺傳算法求解任務時序分配結果；應用改進A*算法和B樣條曲線法規(guī)劃并繪制出無人機航跡；根據威脅區(qū)域和目標的變化進行局部區(qū)域動態(tài)規(guī)劃，合理規(guī)劃出局部航跡。實驗證明該方法可靠性好、易于工程實現。