裂縫區域優化隨機擴展航路規劃方法

何仁珂, 魏瑞軒, 張啟瑞, 許卓凡, 周凱

(空軍工程大學 航空航天工程學院, 陜西 西安 710038)

裂縫區域優化隨機擴展航路規劃方法

何仁珂, 魏瑞軒, 張啟瑞, 許卓凡, 周凱

(空軍工程大學 航空航天工程學院, 陜西 西安 710038)

摘要:針對密集障礙代價空間中存在的局部裂縫區域,基于采樣的路徑規劃方法隨機生成的節點無法進行有效擴展,形成可行路徑的概率極低的問題,采用電勢原理建立環境威脅模型,提出局部區域啟發模式轉換機制及節點一步檢測方法。采用路徑代價改進Transition-based RRT算法的節點選擇機制,實現節點擴展的雙啟發。仿真結果表明,該算法能夠有效地解決上述問題,其算法性能和路徑生成優于同類算法。

關鍵詞:航路規劃; 快速擴展隨機樹; 裂縫問題

0引言

航路規劃是保證移動機器人及無人飛行器等各類智能體安全飛行和執行任務的基礎環節。隨著這一領域研究的不斷深入,對于航路規劃問題的求解由簡單約束條件向復雜約束條件延伸,由二維空間向高維空間拓展。這一趨勢對傳統航路規劃方法提出了巨大的挑戰,特別在解決密集障礙空間航路規劃問題上,傳統航路規劃算法如拓撲圖[1]、人工勢場法[2]、柵格法[3]、智能優化算法[4-5]等在算法適用性和計算效率方面有諸多限制。以快速擴展隨機樹[6](Rapidly exploring Random Tree,RRT)算法為代表的基于采樣的路徑規劃方法,在處理二維、多維空間的復雜約束規劃問題方面有著廣泛的應用[7];但由于該算法是建立在隨機采樣的基礎上的,因此路徑生成帶有很大的隨機性。為了更好地處理節點選擇問題,更為復雜的代價地圖被應用于解決路徑優化問題[8-11]。Karaman等[12]證明了RRT算法得到最優解的概率為零。近年來,研究人員又提出了許多改進算法用于求解最優或漸近最優路徑。Li等[13]利用A*算法的啟發函數改進了RRT算法,但無法避免局部最小問題。Lee等[14]從控制節點原始生成的角度減小了算法的計算代價。文獻[15-16]提出將改進的RRT方法應用于二維空間的動態環境。Leonard等[17]提出Transition-based RRT(T-RRT)算法,利用隨機優化的方法引導節點向低代價空間擴展,其性能明顯優于一般啟發的RRT算法。隨機生成的節點,無法保證有效擴展到高代價區域中存在的局部低代價裂縫區域,而在實際任務中,這一區域是縮短航路、執行縱深突防打擊任務的重要“安全走廊”,有著極為重要的戰場價值。Berenson等[18]提出Gradien T-RRT算法,采用局部梯度下降法引導節點穿越裂逢區域;但是梯度下降方向是單一的,在代價空間中解決該類問題時,結果并非均優于T-RRT算法。

本文運用電學中關于空間電場和電勢分布原理構建了飛行威脅場,構成代價空間,提出了局部區域啟發模式轉換機制和一步檢測方法。在局部區域擴展受限的情況下,采用A*算法啟發引導節點對T-RRT算法在全局和局部進行雙啟發,實現路徑節點在局部裂縫區域的有效擴展。

1基于電勢原理構建飛行威脅場

傳統的建模方法通常是以威脅或障礙的邊界確定威脅半徑,建立圓形或球形的威脅模型。由于威脅的影響與相對距離有密切聯系,因此這種方法無法有效地描述與距離有關的威脅程度。本文利用電學中有關電荷激發形成電場原理[19]建立以威脅點、目標點為元素的威脅場,通過電勢公式對電場強度和距離的關系表達,較好地表征了飛機逼近威脅的緊迫度,以此構建代價空間。

假設有n個點電荷q1,q2,…,qn,根據電勢場疊加原理,在點P處激發形成的電勢為:

(1)

式中：ri為P點與qi的距離。

電場強度為:

(2)

設qoi為第i個威脅,威脅均為正電荷,目標點qt為負電荷。引入目標點后,電勢場變化為:

(3)

式中：rt為目標點與飛行器的距離。電場強度的大小取決取決于激發電場的電荷,與電場中的受力電荷無關。設飛行器為受力試探電荷,不影響電勢分布,以此建立完整的代價空間。

2T-RRT算法

首先定義標準RRT變量。對于空間C,存在若干障礙區域。設Cfree為一非障礙的自由狀態空間,Cfree∈C;Tk為一個具有K個節點的擴展樹,x為Tk的節點,且Tk∈Cfree;qinit為起點,qgoal為終點;令qrand為非障礙區空間的一個隨機采樣點,即qrand∈Cfree;qnear為樹中找到距離qrand最近的節點。設p,q∈Cfree,令d(p,q)為狀態點的距離,則d(qnear,qrand)≤d(q,qrand)。在qrand與qnear兩點直線間取qnew,qnew∈Cfree,并滿足d(qnear,qnew)=ρ,其中ρ>0,為樹生長的最小單位長度,稱為步長。

T-RRT算法能較好地解決在多維代價空間尋找合適低代價路徑的問題。其主要思想是利用RRT算法向全局擴展的優勢,結合Monte Carlo優化和模擬退火的方法判斷是否接受新的節點,形成類似于隨機優化方法的轉換檢測(Transition Tests)的判斷機制,在代價空間中運用最小機械功的思想計算出代價最小的路徑。當新節點為低代價點,則加入擴展樹中;若為高代價點,則根據Metropolis準則函數判斷是否能加入,取決于函數中溫度T的值:

(4)

T的取值隨擴展失敗的次數nfailmax而調整,拒絕次數越多,則溫度值越高,接受的概率越小,排斥高代價點,較好地處理了路徑節點尋優與擴展的關系。

3優化隨機擴展算法

基于采樣方式的T-RRT算法在選擇路徑節點上有很大隨機性。雖然該算法從機械功的角度對所有節點選擇進行概率檢驗,確保篩選出低代價節點;但對于在高代價區域中存在的局部低代價空間無法進行有效的節點搜索,樹擴展的概率極低。從根本上來講,基于采樣的方法的隨機性在該問題上存在固有缺陷,因此,本文提出利用A*算法在低代價點上的搜索優勢來改進T-RRT算法在裂縫問題上的不足。A*算法并不依賴于基于采樣的方法獲得節點,節點生成不受裂縫區域限制。值得注意的是,對于復雜密集阻礙區域,尤其是局部低代價區域,如何有效地解決有啟發與局部最小的矛盾是關鍵問題。這就需要合理地將Metropolis準則函數與A*算法啟發函數結合起來,從而在有效引導節點穿越裂縫區域的同時,保證避免局部最小問題。

首先進行威脅環境建模,將威脅設為正電荷,目標點設為負電荷,飛行器為正的點電荷,構建空間C。擴展樹Tk進行隨機節點qrand的生成,然后進行碰撞檢測,當節點出現在高電勢區時,判定該節點位于威脅區域。當qrand?Cfree時,計數器加1,否則進入轉換檢測,根據相鄰節點的電勢差選擇符合條件的qnear節點;當d(qnear,qrand)≤d(q,qrand)時,以步長ρ取qnew。檢測條件為:

(5)

式中:cparent為擴展出qnew的父節點的代價;(cparent-cnew)/dij為代價斜率。當cnew代價低于cparent時接受該節點,否則當rand(0,1)

當計數器達到門限值nfail>nfailmax時停止計數,進入局部啟發模式。以相同步長ρ計算當前節點qparent與周圍8個節點的相對代價值。估價函數為:

(6)

(7)

式中:g(n)為路徑長度;h(n)為當前節點qparent與目標節點qgoal的歐氏距離;(xi,yi)為周圍節點。

接下來進行節點擴展測試。如果h(qparent,qgoal)135°,以此為條件篩選節點。

4仿真試驗及結果分析

建立局部復雜密集障礙區域飛行威脅場,將本文算法與RRT, T-RRT, Gradien T-RRT進行對比分析,以檢驗算法在復雜密集障礙環境以及裂縫區域的性能。仿真試驗環境:軟件Matlab 7.0;計算機配置:Windows XP操作系統、CPU為Inter Core i3、主頻3.3 GHz。仿真條件:設定11處威脅點,威脅強度由電量大小確定,電量為+1 C和+2 C,目標點電量為-10 C;飛行器為元電荷,電量為+1 C。飛行威脅場大小為50 km×50 km,設K為1,ρ=1,ε0=1/(4π),α≥135°。試驗結果如圖1所示。

圖1　各種算法路徑規劃結果Fig.1　Planning results of various algorithms

由圖1可以看出,對于密集障礙區域,各算法均能找到從起點到目標點的路徑。RRT算法的隨機擴展具有未知搜索優勢,幾乎遍布全局;但并不能很好地擴展到裂縫區域,路徑隨機性強,沒有考慮運動約束條件。T-RRT算法能根據代價大小在全局中選擇合適的擴展節點,從而路徑擴展有很好的指向性,當在威脅區域擴展失敗時可退出重點選取節點,很好地避開威脅所在的高代價區域。Gradien T-RRT算法在密集障礙區域進行了有效地擴展試探,路徑在梯度引導下有良好的方向性;但由于梯度方向的限制,在靠近威脅時梯度易受威脅勢能的影響,沒有成功通過裂縫區域。本文算法能很好地穿越裂縫區域,且路徑擴展有很好的方向性,局部啟發能有效引導節點通過密集障礙區域。

為了更加清晰地反映上述算法在計算時間和路徑代價上的優劣,本文設置最大擴展失敗次數nfailmax為10～80次,每一層級在相同的條件下進行10次試驗,結果如圖2所示。由于RRT算法不具有此項性能,故不進行比較。

圖2　各種算法的計算時間和路徑代價Fig.2　Computing time and path cost of various algorithms

由圖2可以看出,在相同條件下,T-RRT算法的計算時間和路徑代價最大,且計算時間隨nfailmax的增加逐漸變大,而對其他兩種算法的影響不大。這是由于在密集障礙區域,T-RRT算法選擇低代價節點的難度增大,擴展溫度不斷升高,隨著nfailmax的增加,在同一節點擴展次數增加,計算時間隨之提高;路徑代價下降是因為nfailmax增加,能夠保證選擇合適節點的概率增大,生成的路徑代價降低。Gradien T-RRT和本文算法由于在節點擴展失敗后進行了不同模式的節點增長機制,從而在根本上改變了隨機擴展的節點生成方式,因此計算時間和路徑代價受nfailmax影響較小。對于密集障礙區域生成的路徑，本文算法在計算時間和代價方面優于其他兩種方法。

5結束語

本文針對基于采樣的路徑規劃方法在密集障礙區域裂縫問題上的不足,在建立新型威脅模型的基礎上,提出用A*算法改進T-RRT算法,從而有效地解決了算法在高代價局部區域節點擴展困難的問題,較好地實現了復雜密集障礙“雙啟發式”引導。與傳統威脅模型相比,該威脅模型能有效表征威脅與相對距離的關系,更具有應用價值。本文的不足在于“一步檢測”時需進行兩次節點篩選,在數據規模較大時影響計算速度。下一步將對路徑規劃實時性和計算效率方面進行改進。

參考文獻：

[1]Israel L,Flores G,Salazar S,et al.Dubins path generation for a fixed wing UAV[C]//International Conference on Unmanned Aircraft Systems (ICUAS).Orlando:IEEE,2014:339-346.

[2]Tingbin C,Qisong Z.Robot motion planning based on improved artificial potential field[C]//2013 3rd International Conference on Computer Science and Network Technology (ICCSNT).Dalian:IEEE,2013:1208-1211.

[3]Robert J S,Peggy G I S,Clickstein,et al.Robust algorithm for algorithm for real-time route planning[J].IEEE Transaction on Aerospace and Electronic System,2000,36(3):869-878.

[4]Tuncer A,Yildirim M.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computer Electrical Engineering,2012,38(6):1564-1572.

[5]Chaari I,Koubaa A,Bennaceur H,et al.SmartPATH:a hybrid ACO-GA algorithm for robot path planning[C]//2012 IEEE Congress on Evolutionary Computation (CEC).Brisbane:IEEE,2012:1-8.

[6]Lavalle S M,Kuffner J J.Randomized kinodynamic planning[J].International Journal of Robotics Research,2001,20(3):378-400.

[7]Erion P,Kostas E B,Brjan Y C,et al.Samplng-based roadmap of trees for parallel motion planning[J].IEEE Transactions on Robotics,2005,21(4):597-608.

[8]Urmson C,Simmons R.Approaches for heuristically biasing RRT growth[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robotics and Systems (Volume:2).Las Vegas:IEEE,2003:1178-1183.

[9]Lee J,Pippin C,Balch T.Cost based planning with RRT in outdoor environment[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Nice:IEEE,2008:684-689.

[10]Ettlin A,Bleuler H.Rough-terrain robot motion planning based on obstacleness[C]//9th International Conference on Control,Automation,Robotics and Vision.Singapore:IEEE,2006:1-6.

[11]Xu Y,Choi J,Oh S.Mobile sensor network navigation using Gaussian processes with truncated observations[J].IEEE Transactions on Robotics,2011,27(6):1118-1131.

[12]Karaman S,Frazzoli E.Sampling-based algorithms for optimal motion planning[J].International Journal of Robotics Research,2011,30(7):846-894.

[13]Li J,Liu S,Zhang B.RRT-A*motion planning algorithm for non-holonomic mobile robot[C]//2014 Proceedings of the SICE Annual Conference.Sapporo:IEEE,2014:1833-1838.

[14]Lee D,Shim D H.Spline-RRT*based optimal path planning of terrain following flights for fixed-wing UAVs[C]//2014 11th International Conference on Ubiquitous Robots and Ambient Intelligence (URAI 2014) Hilton.Kuala Lumpur:IEEE,2014:257-261.

[15]Svenstrup M,Bak T,Andersen H J.Trajectory planning for robots in dynamic human environments [C]//2010 IEEE/RSJ International Conference on Intelligent Robots and Systems.Taipei:IEEE,2010:4293-4298.

[16]Jaillet L,Hoffman J,Berg J,et al.EG-RRT:environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles [C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.San Francisco:IEEE,2011:2646-2652.

[17]Leonard J,Juan C,Thierry S. Sampling-based path planning on configuration-space costmaps[J].IEEE Transaction on Robotics,2010,26(4):635-646.

[18]Berenson D,Simeon T,Srinivasa S S.Addressing cost-space chasms in manipulation planning[C]//2011 International Conference on Robotics and Automation.Shanghai:IEEE,2011:4561-4568.

[19]馬文蔚.物理學[M].第5版.北京:高等教育出版社,2006:149-186.

(編輯：李怡)

Addressing chasm in optimization rapidly exploring path planning

HE Ren-ke, WEI Rui-xuan, ZHANG Qi-rui, XU Zhuo-fan, ZHOU Kai

(Aeronautics and Astronautics Engineering College, AFEU, Xi’an 710038, China)

Abstract:Narrow low-cost regions called chasm exits in dense obstacle cost space; it is difficult for sampling-based methods to extend nodes in this area. This paper built model based on electric potential, proposed local heuristic mechanism and step detection method, improved Transition-based RRT algorithm by path cost function. The results show that the proposed method could effectively solve the problem mentioned above, its algorithm performance and path generation method are better than others.

Key words:path planning; rapidly exploring random tree; chasm problem

收稿日期:2015-09-07;

修訂日期:2015-11-28; 網絡出版時間:2016-02-29 16:37

基金項目:國家自然科學基金資助(61573373)；航空科學基金資助(20135896027)

作者簡介:何仁珂(1993-)，男，河南信陽人，碩士研究生，主要研究方向為無人機自主控制。

中圖分類號：V249.1

文獻標識碼：A

文章編號：1002-0853(2016)03-0026-04