基于SAS算法的三維多UAV協(xié)同航跡規(guī)劃方法

王奎民

(中國(guó)人民解放軍海軍 駐錦州地區(qū)軍事代表室，遼寧 錦州121000)

隨著無(wú)人飛行器技術(shù)逐漸成熟，新型無(wú)人飛行器可完成更多的復(fù)雜任務(wù)，而這些復(fù)雜任務(wù)是人工駕駛飛機(jī)所無(wú)法實(shí)現(xiàn)的。同時(shí)由于無(wú)人飛行器造價(jià)低、隱身性能好、無(wú)人員傷亡等優(yōu)點(diǎn)，無(wú)人飛行器代替人工駕駛飛行器已成為未來(lái)發(fā)展的趨勢(shì)，無(wú)人飛行器航跡規(guī)劃作為其關(guān)鍵技術(shù)之一已逐漸成為研究熱點(diǎn)。

目前無(wú)人飛行器航跡規(guī)劃的研究重點(diǎn)側(cè)重于單個(gè)UAV的航跡規(guī)劃［1］，對(duì)于多UAV協(xié)同航跡規(guī)劃的研究也多簡(jiǎn)化在二維環(huán)境空間中。具體算法主要有人工勢(shì)場(chǎng)法、隨機(jī)路線圖法、進(jìn)化算法和多目標(biāo)PSO算法［2－5］等。本文針對(duì)三維多UAV協(xié)同航跡規(guī)劃問(wèn)題，提出一種啟發(fā)式SAS算法進(jìn)行求解，并仿真驗(yàn)證了算法的正確性與可靠性。

1 多UAV協(xié)同航跡規(guī)劃描述

1.1 SAS算法擴(kuò)展方式

用SAS算法進(jìn)行路徑規(guī)劃是從起始點(diǎn)開始擴(kuò)展直到目標(biāo)點(diǎn)生成一條路徑。在其擴(kuò)展過(guò)程中共有封閉節(jié)點(diǎn)、開放節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)3類擴(kuò)展點(diǎn)。封閉節(jié)點(diǎn)為擴(kuò)展過(guò)程中已經(jīng)選擇的節(jié)點(diǎn)，在擴(kuò)展過(guò)程中放入Closed表中;開放節(jié)點(diǎn)為擴(kuò)展過(guò)程中已經(jīng)出現(xiàn)但尚未選擇的節(jié)點(diǎn)，在擴(kuò)展過(guò)程中放入Open表中;當(dāng)前節(jié)點(diǎn)為擴(kuò)展過(guò)程中正在擴(kuò)展的節(jié)點(diǎn)。

SAS算法擴(kuò)展方式如圖1所示，A為起始點(diǎn)，MB為目標(biāo)點(diǎn)，擴(kuò)展的步長(zhǎng)為最小航跡段，航跡段數(shù)為擴(kuò)展到當(dāng)前節(jié)點(diǎn)所需擴(kuò)展的步長(zhǎng)個(gè)數(shù)，已擴(kuò)展航程為從起始位置到當(dāng)前節(jié)點(diǎn)的真實(shí)距離，記為L(zhǎng)G，預(yù)估到達(dá)航程為從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的直線距離，記為L(zhǎng)H。初始航向?yàn)閺钠鹗键c(diǎn)到目標(biāo)點(diǎn)的連線方向。A點(diǎn)為當(dāng)前節(jié)點(diǎn)，從A點(diǎn)開始擴(kuò)展得到B，C，D 3個(gè)擴(kuò)展點(diǎn)，將這3點(diǎn)放入Open表中，計(jì)算B，C，D各點(diǎn)的代價(jià)，假設(shè)B點(diǎn)代價(jià)最小，將B點(diǎn)從OPEN表中刪除，放入Closed表中。將B點(diǎn)作為當(dāng)前節(jié)點(diǎn)，重復(fù)以上操作直到目標(biāo)點(diǎn)。在三維中與在二維中擴(kuò)展的方式相同。

圖1 SAS算法擴(kuò)展方式

1.2 約束函數(shù)

多UAV航跡規(guī)劃存在著單UAV約束和多UAV約束，具體描述如下:

(1)最小航跡段長(zhǎng)度。即UAV開始改變飛行姿態(tài)前必須保持直飛的最短距離。在SAS算法中擴(kuò)展一步的步長(zhǎng)為最小航跡段長(zhǎng)度。

(2)最大拐彎角。其限制了生成的航跡只能在小于或等于預(yù)先確定的最大拐彎角范圍內(nèi)轉(zhuǎn)彎。在SAS算法中擴(kuò)展點(diǎn)與當(dāng)前節(jié)點(diǎn)的直線與當(dāng)前節(jié)點(diǎn)的航向的水平夾角均小于最大拐彎角。

(3)最大爬升/俯沖角。該約束由UAV自身機(jī)動(dòng)性能決定，其限制了生成航跡在高度方向上爬升/俯沖的最大角。在SAS算法中擴(kuò)展點(diǎn)與當(dāng)前節(jié)點(diǎn)的直線與當(dāng)前節(jié)點(diǎn)的航向垂直夾角小于最大爬升/俯沖角。

(4)最大航跡長(zhǎng)度。限制了航跡的長(zhǎng)度必須小于或等于一個(gè)預(yù)先設(shè)定的最大距離，在SAS算法中其表達(dá)式如下

其中，LH為預(yù)估到達(dá)航程;LG為以擴(kuò)展航程;dmax為最大航跡長(zhǎng)度。

(5)最低/高飛行高度。其限制了UAV飛行的最低/高飛行高度，在SAS算法中其表達(dá)式如下

其中，h為當(dāng)前節(jié)點(diǎn)所在高度;hmin和hmax分別表示最高和最低飛行高度。

(6)最小安全距離。限制了UAV之間必須保持的最小距離，當(dāng)UAV間小于最小安全距離時(shí)認(rèn)為UAV間發(fā)生了碰撞。在SAS算法中其表達(dá)式如下

其中，jl為當(dāng)前節(jié)點(diǎn)與其他航跡的距離;danq為最小安全距離。

(7)避開威脅區(qū)。限制了UAV在規(guī)劃過(guò)程中必須避開威脅區(qū)，由于在SAS算法中，設(shè)定的威脅區(qū)為火炮球型模型，其表達(dá)式如下

其中，d為當(dāng)前節(jié)點(diǎn)到威脅區(qū)中心的距離;R為威脅區(qū)的半徑。

約束(1)～(3)在SAS算法擴(kuò)展中實(shí)現(xiàn)，約束(4)～(7)在SAS算法的評(píng)價(jià)函數(shù)中進(jìn)行評(píng)價(jià)。

1.3 評(píng)價(jià)函數(shù)

多航跡規(guī)劃中每條航跡代價(jià)函數(shù)為

其中，α、λ1～λ4為常值;C1～C4的值根據(jù)上文所示計(jì)算;L(xj)為協(xié)同航程。其計(jì)算方式如下文所述。

協(xié)同航程為每個(gè)UAV規(guī)劃出的航跡最理想的航程值。在文中協(xié)同航程使用二維航跡距離法計(jì)算。計(jì)算各起始點(diǎn)與目標(biāo)點(diǎn)之間二維航跡規(guī)劃后的航跡距離，如圖2所示的航跡距離L1、L2、L3、L4。選定航跡距離長(zhǎng)的作為參考航跡，協(xié)同航程的計(jì)算公式如下

圖2 協(xié)同航程計(jì)算

L(xj)的表達(dá)式如下

其中，LG為此條航跡已經(jīng)擴(kuò)展的航程;LH為此條航跡預(yù)估的到達(dá)對(duì)應(yīng)攻擊目標(biāo)的航程;LX為協(xié)同航程。

2 基于SAS的多UAV協(xié)同航跡規(guī)劃算法

多UAV協(xié)同航跡規(guī)劃的目的是在保證每架UAV最大生存概率的前提下，為每架UAV生成一條航跡，保證UAV同時(shí)到達(dá)作戰(zhàn)區(qū)域，以最佳的作戰(zhàn)效果完成預(yù)期的作戰(zhàn)任務(wù)。SAS算法的執(zhí)行步驟描述如下:

(1)將多個(gè)起始點(diǎn)放入各自的Closed表中，將起始點(diǎn)作為個(gè)自航跡的當(dāng)前節(jié)點(diǎn)，按順序找到航跡段數(shù)最小的作為待擴(kuò)展當(dāng)前節(jié)點(diǎn)，并對(duì)其進(jìn)行擴(kuò)展。

(2)將擴(kuò)展節(jié)點(diǎn)放入Open表中，檢測(cè)當(dāng)前擴(kuò)展航跡的當(dāng)前航跡段是否與其他航跡發(fā)生碰撞。

(3)若未發(fā)生碰撞，轉(zhuǎn)第(7)步，否則轉(zhuǎn)至第(4)步。

(4)比較當(dāng)前擴(kuò)展航跡的當(dāng)前航跡段標(biāo)號(hào)No.{當(dāng)前航跡段}和與其發(fā)生碰撞航跡的當(dāng)前航跡段標(biāo)號(hào)No.{碰撞航跡}。

(5)如果No.{當(dāng)前航跡段}=No.{碰撞航跡}，淘汰當(dāng)前擴(kuò)展航跡的當(dāng)前擴(kuò)展節(jié)點(diǎn)。轉(zhuǎn)至第(7)步。

(6)如果No.{當(dāng)前航跡段}≠No.{碰撞航跡}，保存擴(kuò)展節(jié)點(diǎn)，將擴(kuò)展節(jié)點(diǎn)放入Closed表中。

(7)按順序找到航跡段數(shù)最小的作為待擴(kuò)展當(dāng)前節(jié)點(diǎn)，并對(duì)其進(jìn)行擴(kuò)展。

(8)如果規(guī)劃成功則轉(zhuǎn)第(9)步，否則轉(zhuǎn)第(2)步。

(9)輸出規(guī)劃結(jié)果。

3 仿真結(jié)果分析

仿真環(huán)境為根據(jù)真實(shí)地形生成的200×200像素大小的數(shù)字地形圖像，如圖3所示。設(shè)定各無(wú)人機(jī)均具有相同速度，最小航跡段為10 km，作戰(zhàn)半徑650 km，最大拐彎角為π/6，最大爬升/俯沖角為π/4，最小安全距離為1 km。作戰(zhàn)要求:我方無(wú)人機(jī)同時(shí)到達(dá)不同的敵方目標(biāo)進(jìn)行打擊，無(wú)人機(jī)不能穿越敵方威脅區(qū)，且無(wú)人機(jī)之間距離必須小于最短安全距離。

圖3 數(shù)字高程地圖俯視圖

3.1 3起始點(diǎn)3目標(biāo)點(diǎn)協(xié)同航跡規(guī)劃

實(shí)驗(yàn)中，共有3架無(wú)人機(jī)，分別從不同的起始點(diǎn)出發(fā)飛往不同的目標(biāo)點(diǎn)，圖4顯示了3起始點(diǎn)飛往3目標(biāo)點(diǎn)多航跡規(guī)劃完成情況。戰(zhàn)場(chǎng)中包含4個(gè)威脅區(qū)，以及山峰等多個(gè)禁飛區(qū)。具體數(shù)據(jù)如下:起始點(diǎn)數(shù)據(jù)如表1，目標(biāo)點(diǎn)數(shù)據(jù)如表2，任務(wù)分配表如表3。

表1 起始點(diǎn)數(shù)據(jù)

表2 目標(biāo)點(diǎn)數(shù)據(jù)

表3 任務(wù)分配表

表4給出了本組實(shí)驗(yàn)的航跡規(guī)劃情況，從中可以看到3個(gè)任務(wù)的航跡距離差值分別為1.1 km、1.3 km、0.25 km，由于無(wú)人機(jī)飛行速度快，1 km的距離幾乎可以忽略不計(jì)。從規(guī)劃速度上講，3條航跡的規(guī)劃僅耗時(shí)23.7 s。

表4 3起始點(diǎn)3目標(biāo)點(diǎn)協(xié)同航跡規(guī)劃實(shí)驗(yàn)結(jié)果

圖4 3起始點(diǎn)飛往3目標(biāo)點(diǎn)航跡俯視圖

3.2 5起始點(diǎn)5目標(biāo)點(diǎn)協(xié)同航跡規(guī)劃

本實(shí)驗(yàn)的目的是驗(yàn)證航跡規(guī)劃數(shù)目增加時(shí)算法的收斂性能。圖5顯示了5起始點(diǎn)飛往5目標(biāo)點(diǎn)多航跡規(guī)劃完成情況。表5給出了本組實(shí)驗(yàn)航跡規(guī)劃情況，從中可以看到5個(gè)任務(wù)的航跡距離差值在十幾到幾十之間。5條航跡也僅耗時(shí)57.1 s，比三條航跡的規(guī)劃耗時(shí)23.7 s多33.4 s。

表5 5起始點(diǎn)5目標(biāo)點(diǎn)協(xié)同航跡規(guī)劃實(shí)驗(yàn)結(jié)果

圖5 5起始點(diǎn)飛往5目標(biāo)點(diǎn)航跡俯視圖

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

本文在保證可靠性的基礎(chǔ)上使用SAS算法解決了多UAV協(xié)同航跡規(guī)劃問(wèn)題，仿真結(jié)果證明使用SAS算法能夠較快地規(guī)劃出協(xié)同航跡，規(guī)劃出的航跡距離相差較小滿足了協(xié)同性能的要求。

［1］AKYILDIZ I F，MELODIA T，KAUSHIK R.A survey on wireless multimedia sensor networks［J］.Computer Networks，2007，51(4):921－960.

［2］LI C H，LEE C K.Minimum cross entropy thresholding［J］.Pattern Recognition，1993，26(4):617－625.

［3］KHATIB O.Real time obstacle avoidance for manipulators and mobile robots［J］.International Journal of Robotics Research，1986，5(1):90－99.

［4］ 葉文，范洪達(dá)，朱愛紅.無(wú)人飛行器任務(wù)規(guī)劃［M］.北京:國(guó)防工業(yè)出版社，2011.

［5］ 朱紅果，鄭昌文.一種基于PSO的多UAV協(xié)同航跡規(guī)劃方法［J］.計(jì)算機(jī)工程與科學(xué)，2010，32(10):142－144.

［6］ 丁明躍，鄭昌文，周成平，等.無(wú)人飛行器航跡規(guī)劃［M］.北京:電子工業(yè)出版社，2008.