基于A*定長搜索算法的多無人機協同航跡規劃

肖自兵, 袁冬莉, 屈耀紅

(西北工業大學 自動化學院, 陜西 西安 710129)

基于A*定長搜索算法的多無人機協同航跡規劃

肖自兵, 袁冬莉, 屈耀紅

(西北工業大學 自動化學院, 陜西 西安 710129)

基于多無人機同時作業情況下的航跡規劃問題,提出了一種A*定長航跡搜索算法。該算法通過選擇代價值最接近給定值的節點作為最佳節點,得到定長規劃航跡,接著進一步通過限定最佳節點的選擇范圍,改善了航跡的可飛性。仿真結果表明,利用該算法規劃的定長航跡長度誤差可以控制在1.4%以內,協同航跡長度誤差可以控制在0.8%以內,能夠滿足多無人機同時到達的一般要求。

無人機; A*算法; 協同航跡規劃; 航跡代價

引言

多無人機協同作業在軍事領域有著重要的意義,近年來成為國內外研究的熱點。多無人機的協同航跡規劃是一個復雜的問題,包含了無人機物理會合約束、作業環境約束和其他操作要求約束[1]。

選擇算法是協同航跡規劃的重要一環,適宜的航跡搜索算法在沒有人工干預的條件下,能夠使無人機有效地規避障礙[2]。常用的航跡搜索算法有Dijkstra算法、Bellman Ford算法、Floyd-Warshall算法和A*算法等[3]。A*算法通過構造啟發函數提高了搜索效率,成為靜態路網中求解最短路徑(或航跡)的有效方法[4]。然而A*算法多應用于單機航跡規劃,不能用于多機協同航跡規劃。文獻[5-7]對A*算法進行了改進,這些改進措施雖然優化了規劃結果或提高了搜索效率,卻仍然局限于單機航跡規劃應用,不能實現多機協同航跡規劃。

本文提出了一種A*定長航跡搜索算法。用該算法可以實現定長航跡規劃,進而實現多無人機的協同航跡規劃。

1 協同航跡規劃問題

1.1 問題描述

假設N架無人機在時刻t0分別處于不同位置S1,S2,…,SN,要求在同一時刻t1到達N個不同目標點D1,D2,…,DN,實施打擊且代價最小。飛經區域存在雷達和導彈陣地威脅,設各無人機勻速飛行且航速相同。

1.2 協同航跡規劃原理

多無人機協同航跡規劃總體結構[8]如圖1所示。

圖1 多無人機協同航跡規劃總體結構圖

整個工作過程大致是:協同管理層根據戰場環境、無人機速度的變化范圍以及路徑規劃層傳來的路徑長度,確定出編隊的協同時間t,并把t和各無人機的相應路徑編號送到路徑規劃器;路徑規劃器把協同管理層確定的t和相應的路徑航路點序列送到軌跡控制層;軌跡控制層根據航路點序列確定可飛軌跡以及相應的控制向量,并把求得的可飛航跡的高度、速度和航向送到無人機自動駕駛伺服系統去執行,操縱無人機按規劃出來的航跡飛行。

一類協同航跡規劃問題為多機同時到達問題。為了使各無人機能夠同時到達目標,通常采用兩種方式:一種是通過調節無人機的飛行速度使航程較大的無人機采取較大的速度,而航程較小的無人機采取較小的速度;另一種是對航路進行修正,通過增加較短航路的長度使每架無人機的航程大致相等。

1.3 航跡代價

當飛行區域存在地面雷達或地空導彈威脅時,一種代價計算方法[9]為:

J=kJt+(1-k)Jf

(1)

式中,J為航跡總代價;k為威脅權重系數,由規劃者根據實際情況給出;Jt為雷達或導彈威脅代價;Jf為燃油代價。

為使問題簡化,本文只考慮航程代價(與燃油代價成正比),而使無人機完全繞開地面雷達和地空導彈的威脅,即威脅代價為0(對應上式中k=0)。

2 A*算法原理

A*算法是一種經典的啟發式搜索算法,其代價函數為:

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

(2)

式中,f(n)為節點n從初始點到目標點的估計代價,稱為代價函數;g(n)為在狀態空間中從初始節點到n節點的實際代價(即已走路徑代價);h(n)為從n到目標節點最佳路徑的估計代價,稱為啟發函數。

3 航跡規劃

3.1 A*定長搜索算法與定長航跡規劃

A*算法的搜索策略是:選取Open表中f值(代價)最小的節點作為最佳節點加以擴展,得到代價最小的航跡。如果重新定義最佳節點,應能規劃出不同的航跡。

修改A*算法如下:選取Open表中f值(航程)最接近于給定長度f0的節點作為最佳節點加以擴展。如此當能規劃出長度為f0的定長航跡,從而為多無人機協同航跡規劃奠定了基礎。改進后的A*算法由于采用了定長搜索策略,稱其為A*定長搜索算法,將分別在下面介紹的兩種情形下應用。

情形1:設無人機飛經區域100 km×100 km范圍內共40個威脅點(雷達陣地和導彈陣地),且設任意兩個威脅點的間距大于無人機安全距離的兩倍,無人機沿這些威脅點生成的Voronoi圖邊線飛行。

情形2:在400 km×400 km的區域內分布著6個威脅區域(雷達陣地和導彈陣地),地圖比例尺取為1∶10。地圖柵格劃分及節點擴展方式如下:用間距為10 km的水平線和豎直線將該大小為400 km×400 km的正方形柵格化,使得每個網格均為10 km×10 km的正方形,所有網格的頂點均作為可擴展的節點。除邊界上的點外,每個節點都按8個方向進行擴展以到達相鄰的8個節點,節點擴展方式如圖2所示。

圖2 節點擴展示意圖

設情形1下無人機的起始位置S的坐標為(10,10) km,起始時刻t0為8∶00,所要到達的目標點D的坐標為(40,85) km,要求的到達時刻t1為8∶15,且設無人機的航速為v=200 m/s。

設情形2下無人機的起始位置S的坐標為(10, 30) km,起始時刻t0為8∶00,所要到達的目標點D的坐標為(360,300) km,要求的到達時刻t1為8∶50,且設無人機的航速為v=200 m/s。

情形1中因為采用的是Voronoi圖,最佳節點只能是Voronoi節點,而無人機的起始點和目標點不一定與Voronoi節點重合。為此,直線連接起點S(xS,yS)和最近的Voronoi節點A(xA,yA)并計算長度:

(3)

直線連接終點D(xD,yD)和最近的Voronoi節點B(xB,yB)并計算長度:

(4)

則中間應規劃航跡長度為dc=f0-c1-c2,接下來只要進行起始點為A、目標點為B、給定長為dc的定長航跡規劃就可以了。

情形2中為使航跡在長度上更精確,采用圖2所示的節點擴展方式,這就決定了航跡上可能出現的角度分別為45°,90°,135°,180°,而45°和90°的角將影響航跡的可飛性。以往處理的辦法是對所生成的航跡進行平滑處理,這就將航跡規劃工作人為地分為了兩個部分,且平滑工作較為繁雜。這里通過對算法進行進一步的改進來改善航跡的可飛性。

航跡上出現直角甚至銳角的原因是最佳節點的選擇范圍過大,為此,對算法進行進一步改進:從最新添加進Open表的節點(也即上一循環中既不屬于Open表也不屬于Closed表的擴展節點)中選擇最佳節點,這從根本上杜絕了銳角的產生,且能降低直角發生率,具體分析如下。

圖3為航跡角度控制示意圖。圖中,符號“○”表示節點。

圖3 航跡角度控制示意圖

搜索過程如下:

(1)選擇A點作為最佳節點,擴展A點,產生后繼節點D,B,E,將D,B,E點加入Open表。

(2)從最新添加進Open表的節點D,B,E中選擇最佳節點。假設為B,擴展B點,產生后繼節點F,C,G,H,I,E,A,D,將F,C,G,H,I添加進Open表(E,A,D已在Open表,不需再添加)。

(3)從最新添加進Open表的節點F,C,G,H,I中選擇最佳節點。如果選F,則∠ABF=90°;如果選C,則∠ABC=135°;如果選G,則∠ABG=180°;如果選H,則∠ABH=135°;如果選I,則∠ABI=90°。由于避免了選擇E和D作為最佳節點,當前航跡不會出現銳角(45°)。假設最佳節點選為C,擴展C點,產生后繼節點J,K,L,G,H,B,D,F,將J,K,L添加進Open表(G,H,B,D,F已在Open表,不需再添加)。

(4)從最新添加進Open表的節點J,K,L中選擇最佳節點。如果選J,則∠BCJ=135°;如果選K,則∠BCK=180°;如果選L,則∠BCL=135°。由于避免了選擇H和D作為最佳節點,當前航跡不會出現銳角(45°),又由于避免了選擇G和F作為最佳節點,當前航跡不會出現直角。

上述分析表明:針對算法的改進措施可以有效地改善航跡的可飛性。但這樣會導致一個問題:由于最佳節點的選取范圍縮小了,導致不一定能搜索到目標節點,可能會與之“擦肩而過”,以致造成程序“死循環”。為避免這種情況的發生,需要修改程序終止的條件,將“搜索到的最佳節點為目標節點”這一條件改為“搜索到的最佳節點與目標節點較為接近”。

情形1中不能通過這樣進一步的算法改進來改善航跡可飛性,其原因是Voronoi圖中每個節點只有3個擴展方向,下一個最佳節點只能從這3個點中選取,如果再縮小選擇范圍,就可能導致找不到最佳節點而使搜索無法繼續。

3.2 多機協同航跡規劃

在用改進的A*算法實現定長航跡規劃后,可進一步實現多無人機協同航跡規劃。以3架無人機為例,其策略為:根據起始點、目標點以及途中要規避的威脅,3架無人機先各自進行最短航跡規劃,然后從中選取長度最大的一條作為參照,以其長度作為給定值,對其他兩架無人機進行定長航跡規劃。這樣就實現了3機同時出發、同時到達且用時最短的協同航跡規劃。

設在上述情形1下,第1架無人機的起始點S1坐標為(10, 10) km,目標點D1坐標為(70, 70) km;第2架無人機的起始點S2坐標為(5, 40) km,目標點D2坐標為(70, 95) km;第3架無人機的起始點S3坐標為(30, 10) km,目標點D3坐標為(90, 70) km。

設在上述情形2下,第1架無人機的起始點S1坐標為(10, 10) km,目標點D1坐標為(270, 270) km;第2架無人機的起始點S2坐標為(10, 110) km,目標點D2坐標為(290, 360) km;第3架無人機的起始點S3坐標為(70, 10) km,目標點D3坐標為(340, 280) km。

4 仿真結果及分析

在MATLAB環境下,進行上述單機定長航跡規劃和3機協同航跡規劃數字仿真。

啟發函數取為當前節點到目標節點直線距離的1.4倍。1.4為啟發系數,決定了啟發函數h(n)的大小。

計算可得情形1下無人機應飛航跡的給定長度為f0=v(t1-t0)=180 km,情形2下無人機應飛航跡的給定長度為f0=v(t1-t0)=600 km。

圖4為第一次改進的A*算法在情形1下的定長航跡規劃結果,航跡長度為179.309 6 km,與理論應飛航程180 km非常接近,相對誤差為0.383 6%。

圖4 情形1下定長規劃結果

圖5為第一次改進的A*算法在情形2下的定長航跡規劃結果,航跡長度為592.132 km,與理論應飛航程600 km較為接近,相對誤差為1.311 3%。但同時看到圖中航跡出現了較多的直角,有些地方甚至出現了銳角,這使得航跡的可飛性受到很大影響。

圖5 情形2下定長規劃結果

圖6為進一步改進的A*算法在情形2下的定長航跡規劃結果,航跡長度為599.411 km,與理論應飛航程600 km非常接近,相對誤差為0.098 2%。相對于圖5而言,盡管圖6中航跡仍然包含少許直角,其可飛性還是得到了很大改善,基本滿足飛行要求。

圖6 改善可飛性的定長航跡

圖7為在情形1下3機協同航跡規劃的仿真結果,3條航跡(從上到下)的長度分別為97.506 4,98.235 9,97.591 3 km,較為接近(相對于中間的參考航跡,上面航跡的誤差為0.742 6%,下面航跡的誤差為0.656 2%),滿足3機同時出發、同時到達的協同航跡規劃要求。

圖7 情形1下的協同航跡

圖8為在情形2下3機協同航跡規劃的結果,3條航跡(從上到下)的長度分別為403.553,405.269,405.269 km,較為接近(相對于下面的參考航跡,上面航跡的誤差為0.423 4%,中間航跡的誤差為0),滿足3機同時出發、同時到達的協同航跡規劃要求。

圖8 情形2下的協同航跡

5 結束語

本文通過對A*算法進行改進,提出了一種A*定長航跡搜索算法,用該算法規劃出了定長航跡,并以此為基礎實現了多機協同航跡規劃,仿真結果證明了算法的有效性。本文研究的多機協同航跡規劃問題為靜態路網中的各無人機同時到達問題,對于其他協同航跡規劃問題,如動態規劃情形,還有待今后進一步探討。所做工作對今后無人機航跡規劃有一定的借鑒意義。

[1] Shanmugavel M,Tsourdos A,White B,et al.Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs[J].Control Engineering Practice,2010,18(9):1084-1092.

[2] Oliver M,Natalie F,Christian A,et al.Adaptive path planning for VTOL-UAVs[J].IEEE Aerospace and Electronic Systems Magazine,2009,24(7):36-41.

[3] Sathyaraj B M,Jain L C,Finn A,et al.Multiple UAVs path planning algorithms:a comparative study[J].Fuzzy Optimization and Decision Making,2008,7(3):257-267.

[4] Seo W J,Ok S H,Ahn J H,et al.An efficient hardware architecture of the A-star algorithm for the shortest path search engine[C]//2009 Fifth International Joint Conference on INC,IMS and IDC.Piscataway:IEEE Computer Society,2009:1499-1502.

[5] Li Ji,Sun Xiuxia.Route planning’s method for unmanned aerial vehicles based on improved A-star algorithm [J].Binggong Xuebao,2008,29(7):788-792.

[6] 孟中杰,黃攀峰,閆杰.基于改進稀疏A*算法的高超聲速飛行器航跡規劃技術[J].西北工業大學學報,2010,28(2):182-186.

[7] Dai Zhiquan,Guan Yong,Guan Ran.Dynamic adjustment A*rounting algorithm[C]//CICC-ITOE 2010 International Conference on Innovative Computing and Communication and 2010 Asia-Pacific Conference on Information Technology and Ocean Engineering. Piscataway:IEEE Computer Society,2010:316-318.

[8] 高曉光,符小衛,宋紹梅. 多UCAV航跡規劃研究[J].系統工程理論與實踐,2004,24(5):140-143.

[9] Meng Bobo,Gao Xiaoguang,Wang Yunhui.Multi-mission path re-planning for multiple unmanned aerial vehicles based on unexpected events[C]//2009 International Conference on Intelligent Human-Machine Systems and Cybernetics.Piscataway:IEEE Computer Society,2009:423-426.

Multi-UAVscooperativepathplanningbasedonA*fixedlengthsearchalgorithm

XIAO Zi-bing, YUAN Dong-li, QU Yao-hong

(College of Automation, NWPU, Xi’an 710129, China)

An improved A*algorithm for fixed length path searching was proposed based on the path planning problems of multiple unmanned aerial vehicles(UAVs) operating simultaneously. A path with fixed length was obtained by choosing nodes with costs closest to given value as best nodes in the algorithm. Then, the path was smoothed by limiting the range of the best nodes choosing from in the algorithm. Simulation results show that length error of the fixed length path obtained from the algorithm can be controlled within 1.4%, and length error of collaborative paths is less than 0.8%. It basically meets the requirements of multi-UAVs arriving at the same time.

unmanned aerial vehicle(UAV); A*algorithm; cooperative path planning; path costs

2011-04-18;

2011-09-04

國家自然科學基金資助(60974146)

肖自兵(1984-)，男，四川簡陽人，碩士，主要研究方向為現代控制理論及應用;

袁冬莉(1966-)，女，陜西乾縣人，副教授，博士，研究方向為先進控制理論及應用、導航制導與控制、計算機控制與智能控制、飛行控制與仿真等。

V279; V249.122

A

1002-0853(2012)01-0092-05

(編輯：姚妙慧)