基于仿人發(fā)育的混合空域智能無人機防碰撞策略研究

雷鵬飛，魏賢智，張啟瑞，齊 鐸，張志浩

(1.空軍工程大學 空管領(lǐng)航學院，西安 710051；2.空軍工程大學 航空工程學院，西安 710051；3.中國人民解放軍 93525部隊，西藏 日喀則 857060)

0 引言

隨著國家低空開放政策的實施以及無人機技術(shù)的飛速發(fā)展[1]，越來越多的中小型無人機將會穿梭在城市上空，進行搜索救援、航空拍攝、氣象觀測以及貨物運送等活動。為了保證飛行安全，各國將無人機限制在特定空域內(nèi)進行飛行，使無人機與有人機進行隔離飛行。但隨著航空技術(shù)與航空事業(yè)的發(fā)展，在有限的空域資源內(nèi)往往存在有人機、無人機以及靜態(tài)障礙共存的混合空域。在混合空域中，一方面，需要無人機能在城市密集障礙環(huán)境中對靜態(tài)的樓宇障礙進行有效地自主防碰撞，保證其飛行安全；另一方面，在混合空域中由于動態(tài)障礙密集的加大，需要無人機能夠?qū)討B(tài)障礙進行快速反應(yīng)，具備在密集動態(tài)障礙中快速防碰撞的能力[2]。

目前針對無人機自主防碰撞已經(jīng)有了許多研究。傳統(tǒng)的無人機自主防碰撞路徑規(guī)劃算法主要包括：可視圖法、Dijkstra算法、A*算法、RRT算法等?？梢晥D法由Lozano-Perez和Wesley于1979年提出[3]，其將障礙物視為多邊形，機器人視為一個點，將起點、障礙物各頂點、終點的所有連線進行組合連接，構(gòu)建可視圖的關(guān)鍵在于障礙物各頂點之間可見性的判斷，要求所連接線段不能穿過多邊形內(nèi)部，而后通過線段所賦權(quán)值的大小選取最優(yōu)路徑。Dijkstra算法[4]是一種經(jīng)典的廣度優(yōu)先的狀態(tài)空間搜索算法，其通過計算起點到環(huán)境模型中任意一點的最短距離從而得到全局最優(yōu)路徑。A*算法在廣度優(yōu)先的基礎(chǔ)上增加了一個代價函數(shù) ，既考慮了當前節(jié)點與起點的距離代價，同時也考慮了當前節(jié)點與終點的距離代價，通過調(diào)節(jié)的大小來調(diào)整算法的精度與速度。RRT算法[4]是一種簡單有效的隨機算法，通過從根節(jié)點隨機向外擴散，生成隨機擴展樹，當葉子節(jié)點包含目標點時，即可獲得一條路徑。RRT算法雖然具有搜索效率快，能夠用于高維空間的優(yōu)點，但是其隨機擴展的方式，使得結(jié)果可能并不是最優(yōu)的，并且RRT算法并不適用于狹長的搜索環(huán)境。

由于約束條件的增加以及環(huán)境模型復雜度的上升，傳統(tǒng)的路徑規(guī)劃算法在進行路徑規(guī)劃時，存在適應(yīng)性差、難以求解的問題。為更好地解決路徑規(guī)劃問題，智能優(yōu)化算法應(yīng)運而生[5]。

智能優(yōu)化算法主要包括遺傳算法、蟻群算法、粒子群算法以及飛蛾撲火算法等。遺傳算法(GA)是借鑒達爾文進化論、孟德爾遺傳機制提出的一種啟發(fā)式搜索算法。其本質(zhì)上是一種并行、全局搜索算法。文獻[6]提出了一種雙循環(huán)遺傳算法(DCGA，double-cycling genetic algorithm)，在實驗考慮環(huán)境模型及運動約束的情況下，提出了新穎的綜合適應(yīng)度函數(shù)，利用兩次遺傳算法尋找最優(yōu)路徑，在第一次規(guī)劃中使用部分適應(yīng)度函數(shù)，第二次規(guī)劃中使用整體適應(yīng)度函數(shù)；通過雙循環(huán)機制，實現(xiàn)了靜態(tài)規(guī)劃和動態(tài)避障相結(jié)合。與傳統(tǒng)遺傳算法相比，DCGA算法路徑規(guī)劃的結(jié)果更加符合實際。

文獻[7]提出了一種改進的自適應(yīng)蟻群算法(IAACO)，通過引入角度引導因子和障礙物排除因子，對ACO算法的實時性和安全性進行改進，同時改進了蟻群算法的信息素更新規(guī)則，并將路徑規(guī)劃問題轉(zhuǎn)化為多目標規(guī)劃問題，最后在二維柵格環(huán)境當中進行仿真實驗，通過與ACO算法和IACO算法的對比分析，驗證了IAACO算法在保證解的質(zhì)量的同時，具有更快的收斂速度和更強的全局尋優(yōu)能力。

文獻[8]運用BSO算法，其通過將粒子群算法(PSO)與天牛須算法(BAS)相結(jié)合，運用天牛覓食的方式代替粒子尋優(yōu)過程，并運用到三維路徑規(guī)劃當中，通過實驗證明BSO算法加快了迭代收斂速度，降低了算法陷入局部最優(yōu)解的概率。

文獻[9]提出用Lévy飛行軌跡改進的飛蛾撲火優(yōu)化算法，提高了路徑規(guī)劃的收斂速度和尋優(yōu)精度；文獻[10]通過引入自適應(yīng)慣性權(quán)重對火焰更新機制進行改進，通過對步長進行自適應(yīng)調(diào)整，對火焰位置產(chǎn)生擾動，充分利用了最優(yōu)火焰的位置，同時自適應(yīng)的方式很好地平衡了算法的全局搜索能力和局部搜索能力；其次引入遺傳算法交叉算子和高斯變異算子，將每次迭代產(chǎn)生的最優(yōu)火焰與其余火焰進行交叉重組，使得算法在前期搜索過程中能夠跳出局部最優(yōu)，加快算法的搜索效率。

文獻[11]通過Tent混沌映射對飛蛾種群的初始化過程進行優(yōu)化，增加了解的均勻性和多樣性，增強了算法的全局搜索能力；而后借鑒模擬退火算法中的Metropolis準則和遺傳算法的算術(shù)雜交操作，使得算法既能夠以一定概率接受當前的劣解，同時也能夠以一定概率產(chǎn)生擾動，起到了既能夠產(chǎn)生擾動，同時又能控制擾動誤差的作用。

本文通過分析人在密集障礙環(huán)境中的思想活動，參照人的發(fā)育式學習防碰撞機理，通過仿人的思維機制建立了面向混合空域中密集障礙的無人機實體模型和發(fā)育模型，最終構(gòu)建了基于仿人發(fā)育的無人機防碰撞方法。能夠有效解決無人機在進入混合空域時自主防碰撞飛行，以及幫助無人機自主逃脫規(guī)劃路徑中的“死區(qū)”，最終到達安全區(qū)域。并能在密集障礙環(huán)境中，隨著環(huán)境熟悉度的提升而不斷發(fā)育自身防碰撞行為，減少路徑規(guī)劃所需時間[12-13]。

1 人的發(fā)育式學習防碰撞機理分析

當人在陷入密集障礙中時，面對眾多的障礙，其會在密集障礙中進行思考，從而選擇最安全的路徑進行防碰撞。并在隨著對這種碰撞環(huán)境的熟悉程度提升，人會自身發(fā)育，從而“不假思索”地對環(huán)境產(chǎn)生反應(yīng)，思考出安全路徑的時間越來越短。圖1為人在密集障礙中進行發(fā)育式學習防碰撞的示意圖，黑色為障礙物，白色為身處障礙環(huán)境中的人，黑色曲線為人通過思考，對障礙環(huán)境所規(guī)劃的安全路徑。

圖1 人的發(fā)育式學習防碰撞示意圖

在初始遇見這種環(huán)境時，人往往需要大量的時間對障礙進行感知、預判，并通過大腦計算規(guī)劃出安全的路徑，但在密集動態(tài)障礙環(huán)境中，動態(tài)障礙在思考的時間內(nèi)會產(chǎn)生位移，影響人的安全，因此需要一種針對密集動態(tài)障礙的快速防碰撞方法。人在密集障礙環(huán)境中會有一種條件反射式的防碰撞行為，這是因為隨著人的成長，經(jīng)歷過許多的密集障礙環(huán)境，導致自身會對熟悉的環(huán)境進行反應(yīng)，并且隨著環(huán)境熟悉度的提升，對越熟悉的環(huán)境，往往需要思考的時間更為短暫[14-16]。

2 面向混合空域中密集障礙的實體模型

2.1 混合空域環(huán)境模型

在混合空域中由于靜態(tài)建筑與建筑之間的空隙通常比較狹窄，并且動態(tài)障礙密集難以預測，這就為無人機的防碰撞帶來極大困難。如圖2所示，本文構(gòu)建了一個典型的混合空域環(huán)境模型示意圖，無人機的探測范圍如圖中黑色圓形所示，圖中陰影部分為混合空域中動態(tài)障礙密集區(qū)，灰色為靜態(tài)建筑障礙，黑色為動態(tài)障礙。無人機需要根據(jù)自身攜帶的傳感器在混合空域中保證自身安全并能到達規(guī)定的目標點[17-18]。

圖2 混合空域環(huán)境模型

2.2 無人機模型

在無人機路徑規(guī)劃的過程中，無人機的飛行軌跡不僅受到環(huán)境因素的影響，同時也受到因其設(shè)計、制造過程中已經(jīng)決定的自身性能的限制。本文針對的是在城市中使用的中小型旋翼無人機，其具有靈活的機動性，可以在飛行時忽略最小轉(zhuǎn)彎半徑與過載等因素，因此，我們可以把無人機作為一個可操縱的質(zhì)點[9]，建立旋翼無人機的質(zhì)點運動方程：

圖3 無人機柵格化模型

3 仿人思想無人機發(fā)育準則模型

針對傳統(tǒng)算法難以滿足混合空域密集障礙這種特殊環(huán)境的防碰撞要求，本文綜合運用快速隨機生成樹模型以及廣度優(yōu)先搜索，在避障過程中仿照人的思想活動構(gòu)造出適用于無人機自主防碰撞的發(fā)育準則模型[19-20]。

快速隨機生成樹即快速遍歷隨機樹(RRT，rapidly-exploring random tree)，是一種在已知環(huán)境中通過采樣擴展的方式進行搜索的算法。就其名稱來看，Rapid-exploration指的是算法的效果，即實現(xiàn)快速的搜索；Random指的是搜索的方式，通過在環(huán)境中隨機采樣的方式探索整個環(huán)境；Tree指的是已搜索的位置通過樹狀結(jié)構(gòu)來存儲，每個位置都有自己的父節(jié)點和子節(jié)點，搜索完成的路徑通常是從樹的根節(jié)點到一個葉節(jié)點的路徑。該算法主要特點：一是搜索速度快，二是該算法是概率完備的，即如果規(guī)劃時間足夠長，且確實存在一條可行路徑，RRT總是可以找出這條路徑的?；谝陨蟽牲c，該方法經(jīng)常被應(yīng)用于無人機的路徑規(guī)劃問題。但同時該算法也有比較明顯的缺點，比如通常不最優(yōu)、規(guī)劃的路徑不平滑等。

廣度優(yōu)先搜索(BFS，breadth first search，寬度優(yōu)先搜索)，是最簡便的圖的搜索算法之一。BFS算法的核心思路就是：從某個點一直把其鄰接點走完，然后任選一個鄰接點把與之鄰接的未被遍歷的點走完，如此反復走完所有結(jié)點。類似于樹的層序遍歷。廣度優(yōu)先搜索算法關(guān)注的重點在于對每一層結(jié)點進行下一層的訪問。

本文將通過綜合以上兩種算法模擬人的思想活動及發(fā)育特性來實現(xiàn)無人機防碰撞路徑規(guī)劃。

3.1 探索準則

假設(shè)無人機機載傳感器能夠感知周圍障礙信息的距離為Rsensor，按照無人機的飛行區(qū)間將感知范圍進行數(shù)字柵格化，對可飛域定義為0，障礙區(qū)域定義為1，如圖4所示。

圖4 無人機感知范圍柵格化標注

利用廣度優(yōu)先算法，尋找一個飛行步長內(nèi)所到達位置并進行記錄，再從這些位置開始，尋找下一個飛行步長所能到達的所有位置(即兩個飛行步長的所有位置)，以此類推直到記錄完感知范圍內(nèi)所有飛行區(qū)間，如圖5所示。

圖5 廣度優(yōu)先算法感知障礙示意圖

對于無人機來說，這種廣度優(yōu)先的思想雖然可以遍歷感知范圍，但數(shù)據(jù)量也會呈指數(shù)型增長規(guī)劃時間也會不斷加大，影響算法的有效性。因此我們引入隨機生成樹模型[13]簡化探索過程，可以極大減少探索時間。利用隨機生成樹模型進行障礙感知的原理如圖6所示，對于可飛域算法將多個柵格合并進行劃分，而對障礙區(qū)域則不斷進行四等分，并進行數(shù)據(jù)記錄。由于隨機生成樹具有分層數(shù)據(jù)結(jié)構(gòu)的特點，而我們只需對障礙區(qū)域進行探索，提高了搜索效率[21-22]。

圖6 隨機生成樹簡化障礙搜索模型示意圖

3.2 最優(yōu)路徑準則

根據(jù)向廣性準則選取到飛行節(jié)點后，無人機有多條路徑進行飛行到達所選取的航點，設(shè)每條路徑的代價函數(shù)為路徑所遍歷的柵格數(shù)，柵格數(shù)越多代表路徑越長，長的飛行路徑不符合無人機飛行經(jīng)濟性要求?？捎嬎忝織l路徑的飛行代價函數(shù)并取得最優(yōu)飛行路徑即代價函數(shù)最小、經(jīng)歷的柵格數(shù)最小的規(guī)劃路徑：

gpath=min(g1，g2，…，gn)

(2)

3.3 死區(qū)脫逃準則

由于無人機不能獲取全局障礙信息而只能根據(jù)自身機載傳感器感知外界信息，因此在陷入某些死區(qū)時很難找到出路。而人在陷入死胡同時，會進行路徑的“試錯”，即隨機挑選一條路徑行走并進行記錄，當此路不通，則返回路口繼續(xù)尋找另外路徑直到找到正確的出口為止。本文仿照這種思想進行編程，在無人機發(fā)現(xiàn)進入死區(qū)后，則返回上一飛行航路點，并選擇其它點作為下一飛行節(jié)點，如下所示：

算法: 死區(qū)脫逃準則

重復

If 進入死區(qū)

Then 回到上一節(jié)點opt(dot)

重新挑選路徑節(jié)點

直到 逃離死區(qū)

3.4 鄰居集準則

在無人機從死區(qū)逃出，并選擇另外通路，此時雖然不會選擇上一航路點進行飛行，但選擇與上一航路點非常接近的航路點有時也可能會進入同一死區(qū)。如圖7所示，無人機在通過航點1進入死區(qū)并逃出后，此時還有航點2，3進行飛行，但選擇航點2則會進入同一死區(qū)，造成重復探索甚至威脅無人機安全。

圖7 不同航點進入相同死區(qū)示意圖

為了避免這種重復性的探索，我們定義鄰居集的概念，在無人機進入死區(qū)需要重新尋找路徑點時，避開當前位置點周圍一定范圍的點，這一定的范圍即我們定義的鄰居集，從而可以使無人機在同一死區(qū)僅探索一次，提高搜索效率。假設(shè)在t時刻，無人機從死區(qū)逃脫并已知其最后從死區(qū)脫逃點 ，則可定義與毗鄰點為其鄰居集，如式(3)所示：

(3)

尋找與D毗鄰點的鄰居，可找出下一次需要避免進入同一死區(qū)的所有鄰居集，則在進行航路點選取時，只需避免這些死區(qū)鄰居集D(X，Y) ，即可避免進入同一死區(qū)。如圖7中黑色點集，航路點1，2屬于同一鄰居集，而航路點3屬于另外鄰居集。

3.5 發(fā)育準則

無人機所感知到的所有信息被傳送到大腦思考模塊，進行經(jīng)驗知識和當前環(huán)境的對比判斷，將獲取到的知識在當前環(huán)境下，根據(jù)感知到的經(jīng)驗知識，進行推演、判斷，從而完成自身的發(fā)育行為。假設(shè)無人機的大腦為B(t)，則B(t)的時變狀態(tài)更新函數(shù)ft與以下參數(shù)有關(guān)：感知信號集合S(t)、動作控制集合C(t)、無人機自身參數(shù)E以及當前時刻的“大腦”B(t)，則可構(gòu)建無人機的發(fā)育準則為在當前變量基礎(chǔ)上的不斷更新記憶的過程：

B(t+1)=ft(S(t)，C(t)，E，B(t))

(4)

4 混合空域中無人機發(fā)育防碰撞方法的實現(xiàn)

通過本文對比人的發(fā)育式學習防碰撞思想，結(jié)合廣度優(yōu)先算法與快速生成隨機樹算法構(gòu)建出相應(yīng)的算法準則并考慮鄰居集概念以及死區(qū)脫離機制，繼而設(shè)計混合空域中無人機發(fā)育防碰撞算法體系如圖8所示。

圖8 混合空域中無人機發(fā)育防碰撞算法體系圖

如圖8所示，在進行無人機避撞航路規(guī)劃時，首先按照廣度優(yōu)先與隨機生成樹相結(jié)合的方式對柵格化的地圖進行搜索尋找代價函數(shù)最低的規(guī)劃路徑，并判斷當前是否進入死區(qū)，如果進入死區(qū)則返回上一個路徑點并在下一步的搜索中避免選擇進入同一死區(qū)的所有鄰居集路徑點，如果沒有進入死區(qū)則繼續(xù)進行路徑的規(guī)劃直到到達目標點。

5 仿真與分析

為了驗證本文所提出的面向混合空域的無人機發(fā)育防碰撞算法在復雜環(huán)境中的有效性，本節(jié)從兩個方面對算法性能進行仿真和分析：一是與傳統(tǒng)的A-Star算法進行避障比較以及與基于圖論思想的Voronoi算法進行對比分析，二是通過算法在同一環(huán)境中的不斷重復并記錄算法規(guī)劃航路的時間變化，測試其發(fā)育防碰撞性能。

5.1 仿真對比分析

假設(shè)無人機飛行速度2 m/s，初始位置在混合空域中。圖9是傳統(tǒng)A-Star算法與本文發(fā)育算法仿真結(jié)果對比圖。由圖中可以看出，傳統(tǒng)A-Star算法在陷入死區(qū)時并不能自主改出，無法為無人機提供安全的防碰撞航路。而本文所的發(fā)育算法能在進入死區(qū)后根據(jù)所構(gòu)建的規(guī)則合理地規(guī)避障礙，并逃離死區(qū)。

圖9 A-Star算法與發(fā)育算法自主防碰撞對比示意圖

圖10是基于Voronoi算法與本文發(fā)育算法的防碰撞效果仿真對比圖。從圖中可以看出，基于Voronoi算法很容易從障礙中穿行而過，而這種航線會嚴重威脅到無人機的安全。而在本文所構(gòu)建的發(fā)育防碰撞思想，可以避開密集障礙，且在有限的可飛域中選擇安全的航路。

通過與A-Star算法和基于圖論思想的Voronoi算法進行比較我們發(fā)現(xiàn)，本文提出的發(fā)育算法在進行無人機避障路徑規(guī)劃中可以給出合理的避障路徑并且避免了無人機為了避障而陷入“死胡同”無法到達目標點的情況。相比于兩種傳統(tǒng)方法而言，具有明顯優(yōu)勢。

5.2 發(fā)育防碰撞算法測試

設(shè)定無人機的仿真環(huán)境為統(tǒng)一仿真環(huán)境，為保證發(fā)育防碰撞算法測試的有效性，預先規(guī)劃好動態(tài)障礙的行進路線。在同一環(huán)境中對算法不斷進行測試，可以得到在環(huán)境中無人機防碰撞并且脫離混合空域的時間如圖11所示?？梢钥闯?，隨著環(huán)境熟悉度的提升，無人機脫離混合空域密集障礙的時間越來越短，如同人一樣在對環(huán)境進行記憶不斷提高熟悉程度，達到發(fā)育的目的。當發(fā)育到一定程度，無人機無法再進行時間上的提升，這是由于已經(jīng)到達了最優(yōu)化，因此在自身性能之內(nèi)，對環(huán)境已經(jīng)十分熟悉，發(fā)育完全，不能再進行時間上的縮短。

圖11 發(fā)育防碰撞算法測試圖

綜合上述仿真結(jié)果可知，根據(jù)仿人發(fā)育防碰撞思想構(gòu)建無人機飛行準則進行發(fā)育防碰撞路徑規(guī)劃的方法，使得無人機可以在混合空域密集障礙中進行高效合理的安全飛行，并且在進入死區(qū)后能夠自主尋找逃出死區(qū)的合理航路。并且隨著環(huán)境熟悉度的提升，無人機自主規(guī)劃脫離混合空域密集障礙的時間越來越短，如同人一樣在對環(huán)境進行記憶，不斷提高熟悉程度，達到發(fā)育的目的一樣。與其他算法相比，本文算法由于具有發(fā)育的特性，因此有更好的防碰撞性能，更加適合于混合空域密集障礙環(huán)境中無人機的安全飛行。

6 結(jié)束語

隨著航空技術(shù)與航空事業(yè)的不斷繁榮，尤其是無人機領(lǐng)域的蓬勃發(fā)展，在有限的空域資源內(nèi)有人機、無人機以及靜態(tài)障礙共存的混合空域已成必然趨勢，而對于混合空域密集障礙中無人機的安全飛行是非常重要的問題，現(xiàn)有的無人機避障路徑規(guī)劃方法普遍還有一定的局限性。本文通過考慮人的發(fā)育式學習防碰撞機理，基于仿人的思維機制建立相關(guān)的要素模型以及算法準則，結(jié)合廣度有限、快速生成隨機樹等經(jīng)典算法以及死區(qū)逃脫、鄰居集等概念，給出了混合空域密集障礙中的無人機仿人發(fā)育自主防碰撞算法。仿真實驗和分析證明，本文方法對于密集的靜態(tài)、動態(tài)障礙的防碰撞是有效的，同時和傳統(tǒng)的路徑規(guī)劃算法相比更加安全可靠。并且隨著對環(huán)境的熟悉，無人機通過自身發(fā)育，需要進行防碰撞算法計算的時間越來越短，如同人對陌生環(huán)境逐漸熟悉之后，路越走越通。后續(xù)對于如何將算法應(yīng)用于實踐，并且將算法拓展為三維防碰撞，是我們今后需要深入研究的方向。