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

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

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

0 引言

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

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

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

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

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

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

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

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

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

1 人的發育式學習防碰撞機理分析

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

圖1 人的發育式學習防碰撞示意圖

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

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

2.1 混合空域環境模型

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

圖2 混合空域環境模型

2.2 無人機模型

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

圖3 無人機柵格化模型

3 仿人思想無人機發育準則模型

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

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

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

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

3.1 探索準則

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

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

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

圖5 廣度優先算法感知障礙示意圖

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

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

3.2 最優路徑準則

根據向廣性準則選取到飛行節點后，無人機有多條路徑進行飛行到達所選取的航點，設每條路徑的代價函數為路徑所遍歷的柵格數，柵格數越多代表路徑越長，長的飛行路徑不符合無人機飛行經濟性要求。可計算每條路徑的飛行代價函數并取得最優飛行路徑即代價函數最小、經歷的柵格數最小的規劃路徑：

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

(2)

3.3 死區脫逃準則

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

算法: 死區脫逃準則

重復

If 進入死區

Then 回到上一節點opt(dot)

重新挑選路徑節點

直到 逃離死區

3.4 鄰居集準則

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

圖7 不同航點進入相同死區示意圖

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

(3)

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

3.5 發育準則

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

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

(4)

4 混合空域中無人機發育防碰撞方法的實現

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

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

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

5 仿真與分析

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

5.1 仿真對比分析

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

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

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

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

5.2 發育防碰撞算法測試

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

圖11 發育防碰撞算法測試圖

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

6 結束語

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