李安醍，武丁杰，李誠(chéng)龍

(中國(guó)民用航空飛行學(xué)院，四川 廣漢 618000)

摘 要：隨著民用無(wú)人機(jī)技術(shù)的廣泛應(yīng)用，將無(wú)人機(jī)融入國(guó)家空域，與有人機(jī)共享空域在低空開展飛行任務(wù)的做法已成為今后發(fā)展的趨勢(shì)。無(wú)人機(jī)“感知避讓”系統(tǒng)對(duì)于未來(lái)在融合空域內(nèi)安全航行起著至關(guān)重要的作用，其中,自主避障算法是保證整個(gè)系統(tǒng)高效運(yùn)行的關(guān)鍵部分。目前，對(duì)無(wú)人機(jī)自主避障算法的研究已經(jīng)十分深入。根據(jù)避障算法的特點(diǎn)和避障機(jī)制對(duì)現(xiàn)有的避障算法進(jìn)行分類，并在此基礎(chǔ)上對(duì)每一種類型的算法展開詳細(xì)介紹，闡述其優(yōu)點(diǎn)以及局限性，最后展望了無(wú)人機(jī)自主避障算法的發(fā)展方向。

關(guān)鍵詞：無(wú)人機(jī)；避障算法；路徑規(guī)劃；低空

0 引言

民用無(wú)人機(jī)作為先進(jìn)生產(chǎn)力的重要載體，被廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、搜救、交通監(jiān)控、物流貨運(yùn)、農(nóng)林植保、航拍攝影、城市巡查、遙感探測(cè)等多個(gè)領(lǐng)域?？紤]到相關(guān)技術(shù)以及運(yùn)行安全等因素，目前民用無(wú)人機(jī)大多被要求在隔離空域運(yùn)行[1]。然而，將無(wú)人機(jī)限制在特定空域內(nèi)，與有人機(jī)進(jìn)行隔離運(yùn)行的做法，已無(wú)法適應(yīng)于目前對(duì)無(wú)人機(jī)日益增長(zhǎng)的需求。歐美等航空業(yè)發(fā)達(dá)國(guó)家及地區(qū)提出了融合空域的概念，旨在將無(wú)人機(jī)系統(tǒng)集成于現(xiàn)有低空空域內(nèi)，與有人機(jī)共同運(yùn)行[2-4]。在低空環(huán)境下，無(wú)人機(jī)不僅要面對(duì)如地形、建筑物等靜態(tài)障礙以及其他動(dòng)態(tài)障礙，同時(shí)還要面對(duì)空域內(nèi)的其他飛行器。

低空環(huán)境下運(yùn)行對(duì)無(wú)人機(jī)自主飛行技術(shù)的安全性提出了更大的挑戰(zhàn)，其中保證無(wú)人機(jī)安全自主飛行的關(guān)鍵在于自主避障算法。本文將根據(jù)求解方式、機(jī)動(dòng)軌跡、關(guān)聯(lián)感知檢測(cè)機(jī)制等要素的總體特點(diǎn)，把無(wú)人機(jī)自主避障算法分為幾何法、路徑規(guī)劃法、數(shù)值求解法3種類型，并對(duì)每一類方法展開詳細(xì)闡述。

1 幾何算法

在幾何算法中，無(wú)人機(jī)通常被看作是具有一定速度的質(zhì)點(diǎn)，根據(jù)無(wú)人機(jī)之間的相對(duì)速度、相對(duì)位置、航向等信息建立幾何關(guān)系,從而在線計(jì)算避障軌跡。

1.1 最接近點(diǎn)法

2008年，PARK等[5]在最接近點(diǎn)法(Point of Closest Approach，PCA)[6]的基礎(chǔ)上提出矢量共享解脫法(Vector Sharing Approach,VSA)，其通過(guò)在解脫距離矢量rm上分別構(gòu)建兩架無(wú)人機(jī)的共享矢量，實(shí)現(xiàn)無(wú)人機(jī)自主避障，如圖1所示，其中，rVSA，rVSB以及vA，vB分別代表無(wú)人機(jī)A與無(wú)人機(jī)B的共享矢量和速度，但是該算法需要無(wú)人機(jī)在避障過(guò)程中保持恒定的速度。其次，對(duì)于多機(jī)沖突，由于需要處理所有無(wú)人機(jī)之間的幾何關(guān)系，導(dǎo)致計(jì)算量增大，無(wú)法滿足實(shí)時(shí)性。

   

圖1 矢量共享解脫法
Fig.1 Vector sharing approach

針對(duì)PCA算法難以適用于多機(jī)沖突以及無(wú)人機(jī)之間未建立通信的情形，CHOI等[7]在PCA的基礎(chǔ)上提出了一種反應(yīng)式實(shí)時(shí)避障算法。該算法將無(wú)人機(jī)的速度矢量以顯式形式表示，并將其轉(zhuǎn)化為安全邊界集合，然后沿安全邊界進(jìn)行采樣并投影到有限路徑角區(qū)域，有限路徑角區(qū)域提供了無(wú)人機(jī)在不發(fā)生碰撞的情況下移動(dòng)的方向。但是，有限路徑角區(qū)域所提供的避障方向可能超出無(wú)人機(jī)性能范圍，導(dǎo)致無(wú)人機(jī)無(wú)法準(zhǔn)確沿著期望軌跡進(jìn)行機(jī)動(dòng)。此外，由于傳感器存在誤差，其投影的有限路徑角區(qū)域可能將不再是有效的避障方向。

1.2 碰撞錐法

HAN等[8]在碰撞錐(Collision Cone Approach,CCA)[9]的基礎(chǔ)上，提出了一種基于比例導(dǎo)航的避障算法，該算法利用碰撞錐進(jìn)行沖突檢測(cè)。無(wú)人機(jī)通過(guò)從導(dǎo)航模式轉(zhuǎn)換為避障模式，并將碰撞錐中的相對(duì)速度矢量引導(dǎo)為避障矢量來(lái)求解避障軌跡。該算法能夠利用無(wú)人機(jī)傳感器或機(jī)載通信有效地實(shí)現(xiàn)對(duì)不同初始條件下目標(biāo)飛行器的實(shí)時(shí)避障。但是該算法只有當(dāng)入侵機(jī)以恒定的速度矢量移動(dòng)時(shí)，才能得到最優(yōu)導(dǎo)航系數(shù)，否則算法無(wú)法收斂，造成避障失效。

SMITH等[10]提出了聚合碰撞錐法，并將其推廣至多機(jī)沖突的情況。該算法通過(guò)碰撞錐在水平面和垂直面形成一個(gè)錐體，因此無(wú)人機(jī)僅能在水平或垂直兩個(gè)面上避障，而無(wú)法在三維空間下任意機(jī)動(dòng)，降低了在高密度障礙下的避障效率。此外，在垂直面中，圓柱體以矩形的形式出現(xiàn)，所以必須將矩形分解為圓，其降低了算法的實(shí)時(shí)性。

LIN等[11]提出靈活幾何算法(Fast Geometric Avoi- dance,FGA)，該算法通過(guò)碰撞錐檢測(cè)沖突情況并利用PCA選擇臨界避障時(shí)間，最后結(jié)合微分幾何的思路求解避障軌跡。但是該算法假設(shè)傳感器為理想狀態(tài)，且無(wú)人機(jī)只能在恒定速度下以固定大小的傾斜角和俯仰角進(jìn)行避障機(jī)動(dòng)，而未考慮更多運(yùn)動(dòng)約束條件。

1.3 速度障礙法

速度障礙法(Velocity Obstacle,VO)[12]在碰撞錐模型的基礎(chǔ)上將碰撞錐沿速度矢量VB進(jìn)行平移，其平移后的幾何圖形便是無(wú)人機(jī)A對(duì)于無(wú)人機(jī)B的速度障礙，如圖2所示?；谒俣日系K法的典型改進(jìn)算法有RVO[13]，HRVO[14]，ORCA[15]等。

   

圖2 速度障礙法
Fig.2 Velocity obstacle approach

JENIE等[16]針對(duì)無(wú)人機(jī)在航線上飛行時(shí)發(fā)生沖突的情況，參考有人機(jī)目視飛行規(guī)則(VFR)提出選擇速度障礙法(Selective Velocity Obstacle,SVO)。選擇速度障礙法使得無(wú)人機(jī)在遵循一定的飛行規(guī)則情況下進(jìn)行避障，同時(shí)最大程度地限制無(wú)人機(jī)偏離原來(lái)航線的距離。該算法的局限性在于需要人為建立避障規(guī)則體系，無(wú)法對(duì)不執(zhí)行該規(guī)則的入侵機(jī)進(jìn)行有效避障。

針對(duì)速度障礙法僅能解決二維平面上運(yùn)動(dòng)體的碰撞問(wèn)題，文獻(xiàn)[17]提出三維速度障礙法(3DVO)。三維速度障礙法將保護(hù)區(qū)設(shè)定為球體，并引入緩沖速度集(Buffer Velocity,BV)的概念以確保無(wú)人機(jī)有額外的機(jī)動(dòng)空間進(jìn)行避障。但是，由于其求解過(guò)程涉及到對(duì)每個(gè)避碰平面的迭代，算法的實(shí)時(shí)性受到限制。

由于在文獻(xiàn)[17]中，當(dāng)避讓面與速度障礙圓錐相交，但不與速度障礙圓錐的對(duì)稱線相交時(shí)，會(huì)產(chǎn)生雙曲線誤差。對(duì)此，TAN等[18]提出對(duì)代表圓錐截面的方程進(jìn)行修正，以消除雙曲線的誤差，同時(shí)提出金字塔錐法，將長(zhǎng)方體形狀的靜態(tài)障礙建模為圓柱形保護(hù)區(qū)。但是金字塔錐法對(duì)于靜態(tài)障礙保護(hù)區(qū)的建立方法，無(wú)法適用于長(zhǎng)寬差別很大的長(zhǎng)方體，如圖3所示。

   

圖3 算法適用范圍
Fig.3 Applicable range of the algorithm

2 路徑規(guī)劃法

路徑規(guī)劃是按照預(yù)先設(shè)定的指標(biāo)在起始點(diǎn)和終止點(diǎn)之間選擇出一條最優(yōu)或次優(yōu)的無(wú)碰撞路徑，其本質(zhì)是在約束條件下得到最優(yōu)解或可行解的過(guò)程。

2.1 圖搜索法

應(yīng)用于無(wú)人機(jī)避障的圖搜索法通常有A*算法及其改進(jìn)算法如D*[19-20]，D* lite[21-22]，LPA*[23]等。

針對(duì)原始A*算法僅能在靜態(tài)環(huán)境下提供路徑規(guī)劃[24]的問(wèn)題，HWANGBO等[25]提出用于小型固定翼無(wú)人機(jī)的兩段式避障算法。該算法首先在離散的三維空間中計(jì)算出滿足無(wú)人機(jī)運(yùn)動(dòng)約束的最優(yōu)無(wú)碰撞路徑，然后利用局部運(yùn)動(dòng)規(guī)劃器計(jì)算出基于Dubins曲線具有更高細(xì)節(jié)層次且更精確的運(yùn)動(dòng)軌跡。當(dāng)需要細(xì)化路徑時(shí)，利用局部運(yùn)動(dòng)規(guī)劃器進(jìn)行迭代，直到抵達(dá)目標(biāo)點(diǎn)。該算法局限性在于隨著空域的增大和復(fù)雜化，一方面計(jì)算復(fù)雜度明顯增加，另一方面可能沒有足夠的精度來(lái)規(guī)劃有效、無(wú)碰撞的路徑。

針對(duì)A*算法搜索空間增大導(dǎo)致算法實(shí)時(shí)性下降的問(wèn)題，黃文剛等[26]提出使用變步長(zhǎng)稀疏A*算法。當(dāng)無(wú)人機(jī)在安全區(qū)域時(shí)，采用較大的搜索步長(zhǎng)以提高實(shí)時(shí)性，而在遭遇沖突時(shí)，則縮小搜索步長(zhǎng)以保證搜索精度和魯棒性，防止無(wú)人機(jī)發(fā)生碰撞。但是較小的搜索步長(zhǎng)會(huì)導(dǎo)致算法效率下降，可能無(wú)法面對(duì)突發(fā)的多重威脅情形。

針對(duì)同一高度上兩機(jī)沖突問(wèn)題，宋雪倩等[27]提出利用Dubins曲線結(jié)合A*算法分別為工作區(qū)域內(nèi)的無(wú)人機(jī)構(gòu)建最短避障路徑，當(dāng)出現(xiàn)兩機(jī)沖突情況時(shí)，通過(guò)矢量共享法求解航向偏離量，實(shí)時(shí)重規(guī)劃兩機(jī)的飛行路徑避免發(fā)生碰撞。該算法綜合了Dubins曲線、矢量共享法和A*算法的優(yōu)點(diǎn)，保證了路徑的光滑和可飛性。但是該算法需要將障礙物建模為圓形，并且無(wú)人機(jī)之間的避障依賴于一個(gè)集中式的規(guī)劃器，在高密度多機(jī)沖突情景下，其規(guī)劃器的實(shí)時(shí)性將面臨巨大挑戰(zhàn)。

2.2 采樣法

針對(duì)搜索類算法在多維狀態(tài)空間下容易出現(xiàn)“維數(shù)災(zāi)難”的問(wèn)題，可采取基于采樣的方法，例如快速擴(kuò)展隨機(jī)樹(Rapidly-exploring Random Tree,RRT)[28]及其改進(jìn)算法RRT*[29]以實(shí)現(xiàn)漸近最優(yōu)。

AGUILAR等[30]提出RRT* GL算法，其結(jié)合了RRT*目標(biāo)算法以及RRT*限制算法的特點(diǎn)，在降低尋找可靠解計(jì)算成本的同時(shí)，增加了路徑周圍的樹枝密度，從而產(chǎn)生一個(gè)更短的路徑而不會(huì)增加迭代次數(shù)。但是該算法僅能實(shí)現(xiàn)漸近最優(yōu)，即在有限的時(shí)間內(nèi)僅能得到次優(yōu)解。

LIN等[31]提出閉環(huán)快速擴(kuò)展隨機(jī)樹算法(Closed-Loop RRT),其采用了簡(jiǎn)化節(jié)點(diǎn)連接策略并利用軌跡上的中間點(diǎn)來(lái)提高算法規(guī)劃效率。其次，該算法采用了可達(dá)集的方法來(lái)預(yù)測(cè)碰撞，從而有效實(shí)現(xiàn)在線重規(guī)劃。但是，對(duì)于無(wú)人機(jī)之間的碰撞情形，該算法被簡(jiǎn)化成二維平面，因此無(wú)法應(yīng)用于三維空間避障。

MECHALI等[32]提出對(duì)RRT*算法生成的最終路徑進(jìn)行平滑和修正，以降低飛行過(guò)程中的能量消耗。但是，該算法在通過(guò)多次迭代實(shí)現(xiàn)全局最優(yōu)的同時(shí)，消耗了大量的時(shí)間。其次，環(huán)境改變會(huì)導(dǎo)致迭代次數(shù)增加，進(jìn)一步降低算法效率。因此，該算法無(wú)法應(yīng)用于動(dòng)態(tài)環(huán)境下的無(wú)人機(jī)避障。

2.3 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法是由KHATIB[33]提出的一種虛擬力場(chǎng)方法，其基本思想是假設(shè)機(jī)器人處于人為的虛擬勢(shì)場(chǎng)環(huán)境之中。

LIU等[34]將人工勢(shì)場(chǎng)法拓展到三維空間下，并結(jié)合李雅普諾夫穩(wěn)定性定理避免無(wú)人機(jī)陷入局部最小點(diǎn)。該算法能夠使無(wú)人機(jī)在動(dòng)態(tài)或靜態(tài)環(huán)境下有效避障，但是其避障路徑并不能保證全局最優(yōu)性。

BUDIYANTO等[35]為工作區(qū)域內(nèi)的每一架無(wú)人機(jī)設(shè)置排斥力場(chǎng)，從而實(shí)現(xiàn)了無(wú)人機(jī)之間的動(dòng)態(tài)避障。但是該算法需要提前為動(dòng)態(tài)目標(biāo)設(shè)置排斥力場(chǎng)，無(wú)法面對(duì)突然入侵工作區(qū)域的動(dòng)態(tài)障礙。

熊超等[36]提出結(jié)合碰撞錐的改進(jìn)人工勢(shì)場(chǎng)算法。該算法利用碰撞錐的碰撞檢測(cè)機(jī)制，設(shè)計(jì)障礙物斥力勢(shì)場(chǎng)判定其系數(shù),以排除由無(wú)關(guān)障礙物勢(shì)場(chǎng)產(chǎn)生的不利影響。同時(shí)，通過(guò)設(shè)計(jì)模糊斥力增益調(diào)節(jié)系數(shù)來(lái)防止無(wú)人機(jī)陷入局部最優(yōu)。但是，該算法需要提前針對(duì)環(huán)境設(shè)計(jì)調(diào)節(jié)系數(shù)，當(dāng)無(wú)人機(jī)處于不確定環(huán)境中時(shí)，其可能對(duì)無(wú)人機(jī)的運(yùn)動(dòng)造成負(fù)面影響。

3 數(shù)值求解法

數(shù)值求解法是將無(wú)人機(jī)碰撞過(guò)程抽象為數(shù)學(xué)模型，在指定的運(yùn)動(dòng)約束條件下通過(guò)數(shù)值運(yùn)算等方式求得當(dāng)前狀態(tài)下的最優(yōu)解，即偏離原方向程度最小的避障飛行動(dòng)作或航跡。

3.1 最優(yōu)化法

SUNBERG等[37]提出近似動(dòng)態(tài)規(guī)劃的算法用于無(wú)人機(jī)避障。該算法基于插值網(wǎng)格，并采用線性值函數(shù)逼近產(chǎn)生的策略提高無(wú)人機(jī)避障性能。但是該算法對(duì)于計(jì)算空間的要求較高，難以在高維空間下求得最優(yōu)解，所以只考慮了二維平面上的避障。其次，該算法假設(shè)傳感器處于理想狀態(tài)，而在真實(shí)環(huán)境下若受到噪聲影響，插值得到的結(jié)果會(huì)出現(xiàn)較大的誤差，從而影響避障效果。

DE WAEN等[38]采用Theta*算法快速規(guī)劃出一條連接起止點(diǎn)的無(wú)碰撞路徑，然后將路徑進(jìn)行分割，通過(guò)MILP求解每一段軌跡，最后根據(jù)無(wú)人機(jī)外形和運(yùn)動(dòng)約束條件生成連續(xù)凸形安全區(qū)域。但是將路徑進(jìn)行分割逐一通過(guò)MILP求解只能實(shí)現(xiàn)局部最優(yōu)，并且如果加入更多約束條件會(huì)造成求解時(shí)間顯著增加。

宋敏等[39]提出一種基于非線性模型預(yù)測(cè)控制(NMPC)的無(wú)人機(jī)非合作式避障算法。該算法以無(wú)人機(jī)的位置和速度關(guān)系建立相撞沖突判決準(zhǔn)則，其次，構(gòu)建無(wú)人機(jī)避障機(jī)動(dòng)決策樹，并通過(guò)剪枝搜索方法提高算法效率。但是該算法隨著預(yù)測(cè)時(shí)域的增加，求解時(shí)間將顯著延長(zhǎng)，并且該算法假設(shè)每架無(wú)人機(jī)所提供的信息都是確定可靠的，而未考慮到不確定性因素對(duì)算法魯棒性的影響。

3.2 馬爾可夫決策過(guò)程

馬爾可夫決策過(guò)程(Markov Decision Process,MDP)最早由BELLMAN[40]提出，其用于具有馬爾可夫性質(zhì)的環(huán)境中，通過(guò)模擬智能體與環(huán)境交互獲得回報(bào)，是在不確定性動(dòng)態(tài)系統(tǒng)中最優(yōu)化的決策方法。

針對(duì)多旋翼無(wú)人機(jī)在不確定環(huán)境下的避障問(wèn)題，MUELLER等[41]提出將無(wú)人機(jī)碰撞過(guò)程表述為部分可觀察馬爾可夫決策過(guò)程，并通過(guò)值迭代求解可行的避障動(dòng)作。但是該算法需要通過(guò)離線調(diào)整參數(shù)以達(dá)到最佳效果，無(wú)法適用于不同情形下的應(yīng)用。其次，該算法為了保證實(shí)時(shí)性，需要將無(wú)人機(jī)速度、位置等狀態(tài)信息進(jìn)行離散化處理，這意味著無(wú)人機(jī)速度無(wú)法在性能限制內(nèi)進(jìn)行連續(xù)變化。

BERTRAM等[42]提出基于馬爾可夫決策過(guò)程的多智能體分布軌跡規(guī)劃算法，通過(guò)構(gòu)建正負(fù)獎(jiǎng)勵(lì)以適應(yīng)三維環(huán)境不同高度下的避障。但是該算法需要根據(jù)空域內(nèi)的環(huán)境特征提前構(gòu)建負(fù)值獎(jiǎng)勵(lì)，無(wú)法適用于陌生環(huán)境，并且不能保證避障機(jī)動(dòng)時(shí)的最小化軌跡偏離程度。

針對(duì)利用蒙特卡羅樹搜索解決無(wú)人機(jī)避障無(wú)法獲得最優(yōu)航跡以及在面對(duì)凹形障礙時(shí)算法性能下降的問(wèn)題，文獻(xiàn)[43]提出結(jié)合跳點(diǎn)搜索算法在全局規(guī)劃上的優(yōu)勢(shì)，建立離散路徑點(diǎn)引導(dǎo)無(wú)人機(jī)，同時(shí)將線性系數(shù)引入獎(jiǎng)勵(lì)函數(shù)來(lái)權(quán)衡無(wú)人機(jī)在避障過(guò)程中避障效率和最優(yōu)路徑的關(guān)系。但是該算法需要通過(guò)先驗(yàn)的地形環(huán)境來(lái)建立路徑點(diǎn)，不適用于陌生環(huán)境。此外，路徑點(diǎn)的間隔距離無(wú)法自適應(yīng)，不能直接應(yīng)用于任何場(chǎng)景，其算法的通用性有待提高。

3.3 智能算法

JULIAN等[44]提出采用壓縮深度神經(jīng)網(wǎng)絡(luò)以優(yōu)化避障策略中的離散數(shù)值表，通過(guò)非對(duì)稱損失函數(shù)和梯度下降算法對(duì)數(shù)值表進(jìn)行逼近，從而得到一個(gè)近似表。但是該算法依賴于原始數(shù)值表的性能，由于采用了集中式的方法控制無(wú)人機(jī)避障，只能應(yīng)用于合作式避障。當(dāng)無(wú)人機(jī)面對(duì)外來(lái)入侵飛行器或者其他非合作動(dòng)態(tài)障礙時(shí)，無(wú)人機(jī)將無(wú)法獨(dú)立進(jìn)行避障。

HAN等[45]將動(dòng)態(tài)障礙物環(huán)境下的三維避障問(wèn)題建模為連續(xù)狀態(tài)下的馬爾可夫決策過(guò)程。該算法不需要對(duì)狀態(tài)空間進(jìn)行離散化處理，無(wú)人機(jī)能以連續(xù)的速度進(jìn)行避障機(jī)動(dòng)。但是該算法需要進(jìn)行離線學(xué)習(xí)，并且在外部噪聲影響下容易出現(xiàn)過(guò)擬合的情況。

蘇黎世大學(xué)無(wú)人機(jī)團(tuán)隊(duì)專注于利用視覺攝像頭感知環(huán)境，并結(jié)合機(jī)器學(xué)習(xí)的方法解決無(wú)人機(jī)避障問(wèn)題。2015年,該團(tuán)隊(duì)實(shí)現(xiàn)在森林環(huán)境下采用基于深度神經(jīng)網(wǎng)絡(luò)的微型四軸無(wú)人機(jī)進(jìn)行自主避障飛行[46]。2018年，該團(tuán)隊(duì)提出DroNet算法[47]，是一種可以實(shí)現(xiàn)無(wú)人機(jī)在城市街道環(huán)境下安全飛行的卷積神經(jīng)網(wǎng)絡(luò)。2020年,該團(tuán)隊(duì)在無(wú)人機(jī)視覺避障過(guò)程中采用了一種名為“事件相機(jī)”的新型攝像頭[48]，從而使無(wú)人機(jī)快速感知周圍環(huán)境。但是該類方法所面臨的問(wèn)題在于過(guò)度依賴硬件性能，例如相機(jī)容易受到光照的影響、鏡頭視場(chǎng)存在局限等。除此之外，這類方法需要采集數(shù)據(jù)集并提供給算法訓(xùn)練學(xué)習(xí)，且該類避障算法的泛化能力也有待驗(yàn)證。

4 結(jié)論

幾何類算法從無(wú)人機(jī)與障礙物的相對(duì)幾何關(guān)系入手解決避障問(wèn)題，具有求解迅速的特點(diǎn)。但是對(duì)于復(fù)雜環(huán)境，幾何關(guān)系的構(gòu)建將變得困難，求解難度也將增加。此外，由于幾何關(guān)系的構(gòu)建依賴于相對(duì)速度、位置等信息，對(duì)于環(huán)境狀態(tài)信息敏感，容易受到噪聲影響。

路徑規(guī)劃類算法采用離線預(yù)規(guī)劃或在線重規(guī)劃的方式指導(dǎo)無(wú)人機(jī)的飛行軌跡。雖然采用圖搜索的方法能夠獲取一條全局最優(yōu)的路徑，但是存在高維空間下的搜索效率降低的問(wèn)題；基于采樣法(如RRT算法)雖然能夠適用于高維空間動(dòng)態(tài)規(guī)劃，但是該方法為概率完備，當(dāng)無(wú)人機(jī)處于某些狹窄通道時(shí)，其算法收斂速度未知；勢(shì)場(chǎng)法雖然求解迅速，但是需要人為設(shè)定力場(chǎng)函數(shù)，且容易存在局部最小點(diǎn)。

數(shù)值求解法能夠充分利用環(huán)境狀態(tài)信息、無(wú)人機(jī)飛行動(dòng)態(tài)數(shù)據(jù)等信息，具有良好的魯棒性。但是對(duì)于復(fù)雜的高維空間，傳統(tǒng)方法將難以建立模型，而智能算法的避障性能依賴于數(shù)據(jù)集的質(zhì)量。

當(dāng)前各類避障算法具有各自的優(yōu)點(diǎn)和特性，同時(shí)也存在自身的局限性。因此，可采用多種方法結(jié)合的方式來(lái)解決不同情況下的無(wú)人機(jī)避障問(wèn)題。今后，針對(duì)民用無(wú)人機(jī)在融合空域內(nèi)低空環(huán)境下運(yùn)行這一情景，可根據(jù)無(wú)人機(jī)性能劃分不同的飛行高度層，在空域內(nèi)飛行的無(wú)人機(jī)需要向統(tǒng)一的無(wú)人機(jī)管理平臺(tái)實(shí)時(shí)上報(bào)飛行動(dòng)態(tài)數(shù)據(jù)，以提供合作式避障支持。同時(shí)，對(duì)于進(jìn)行自主飛行的無(wú)人機(jī)還必須支持非合作式避障，以應(yīng)對(duì)非法入侵的飛行器。對(duì)于執(zhí)行定期飛行任務(wù)的無(wú)人機(jī)來(lái)說(shuō)，可考慮劃設(shè)固定航線并接入集中式系統(tǒng)進(jìn)行統(tǒng)一調(diào)度。當(dāng)該類無(wú)人機(jī)在航線上產(chǎn)生沖突時(shí)，則可按照飛行規(guī)則或根據(jù)集中式系統(tǒng)的指令來(lái)進(jìn)行相互避讓。此外，空域內(nèi)的有人駕駛航空器和載人航空器應(yīng)具有最高優(yōu)先級(jí)，無(wú)人機(jī)必須主動(dòng)進(jìn)行避讓以保持與該類飛行器的安全間隔。

參 考 文 獻(xiàn)

[1] International Civil Aviation Organization.Unmanned Aircraft Systems (UAS):ICAO CIRCULAR 328-2011[S].Montreal:International Civil Aviation Organization,2011.

[2] COOKSP,BROOKSD.A quantitative metric to enable unmanned aircraft systems to remain well clear[J].Air Traffic Control Quarterly，2015,23(2/3):137-156.

[3] United States Department of Defense (DoD).Unmanned aircraft system airspace integration plan:Version 2.0[S].Washington:United States Department of Defense,2011.

[4] DALAMAGKIDISK,VALAVANISK P,PIEGLL A.On integrating unmanned aircraft systems into the national airspace system:issues,challenges,operational restrictions, certification, and recommendations[M].2nd ed.Dordrecht: Springer Netherlands,2012.

[5] PARK J W,OH H D,TAHK M J.UAV collision avoidance based on geometric approach[C]//SICE Annual Conference,2008:2122-2126.

[6] KROZEL J,PETERS M.Strategic conflict detection and resolution for free flight[C]//Proceedings of the 36th IEEE Conference on Decision and Control,1997:1822-1828.

[7] CHOI H,KIM Y,LEE Y,et al.A reactive collision avoidance algorithm for multiple midair unmanned aerial vehicles[J].Transactions of the Japan Society for Aeronautical and Space Sciences,2013,56(1):15-24.

[8] HAN S C,BANG H,YOO C S.Proportional navigation-based collision avoidance for UAVs[J].International Journal of Control,Automation and Systems,2009,7(4):553-565.

[9] CHAKRAVARTHY A,GHOSE D.Obstacle avoidance in a dynamic environment:a collision cone approach[J].IEEE Transactions on Systems,Man,and Cybernetics,Part A:Systems and Humans,1998,28(5):562-574.

[10] SMITH A L,HARMON F G.UAS collision avoidance algorithm based on an aggregate collision cone approach[J].Journal of Aerospace Engineering,2011,24(4):463-477.

[11] LIN Z J,CASTANO L,MORTIMER E,et al.Fast 3D collision avoidance algorithm for fixed wing UAS[J].Journal of Intelligent & Robotic Systems,2020,97:577-604.

[12] FIORINI P,SHILLER Z.Motion planning in dynamic environments using velocity obstacles[J].The International Journal of Robotics Research,1998,17(7):760-772.

[13] VAN DEN BERG J,GUY S J,LIN M,et al.Reciprocal n-body collision avoidance[C]//The 14th International Symposium of Robotic Research,2009：3-19.

[14] SNAPE J,VAN DEN BERG J,GUY S J,et al.The hybrid reciprocal velocity obstacle[J].IEEE Transactions on Robotics,2011,27(4):696-706.

[15] VAN DEN BERG J,GUY S J,LIN M,et al.Optimal reciprocal collision avoidance for multi-agent navigation[C]//Proceedings of the IEEE International Conference on Robotics and Automation,2010:1-8.

[16] JENIE Y I,VAN KAMPEN E J,DE VISSER C C,et al.Selective velocity obstacle method for deconflicting maneuvers applied to unmanned aerial vehicles[J].Journal of Guidance,Control,and Dynamics,2015,38(6):1140-1146.

[17] JENIE Y I,VAN KAMPEN E J,DE VISSER C C,et al.Three-dimensional velocity obstacle method for UAV’s uncoordinated avoidance maneuver[C]//AIAA Guidance,Navigation,and Control Conference,2016:1-16.

[18] TAN C Y,HUANG S,TAN K K,et al.Three dimensional collision avoidance for multi unmanned aerial vehicles using velocity obstacle[J].Journal of Intelligent & Robotic Systems,2020,97:227-248.

[19] STENTZ A.The focused D* algorithm for real-time replanning[C]//Proceedings of the 14th International Joint Conference on Artificial Intelligence,1995:1652-1659.

[20] STENTZ A.Optimal and efficient path planning for partially-known environments[C]//Proceedings of the 1994 IEEE International Conference on Robotics and Automation,1994:3310-3317.

[21] KOENIG S,LIKHACHEV M.D* lite[C]//Proceedings of AAAI,2002:476-483.

[22] 陳俠，劉冬.應(yīng)用D*Lite算法的目標(biāo)移動(dòng)時(shí)無(wú)人機(jī)三維航跡規(guī)劃[J].電光與控制,2013,20(7):1-5.

[23] KOENIG S,LIKHACHEV M,FURCY D.Lifelong planning A*[J].Artificial Intelligence,2004,155(1/2):93-146.

[24] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.

[25] HWANGBO M,KUFFNER J,KANADE T.Efficient two-phase 3D motion planning for small fixed-wing UAVs[C]//IEEE International Conference on Robotics and Automation,2007:1035-1041.

[26] 黃文剛，張怡，姜文毅，等.變步長(zhǎng)稀疏A*算法的無(wú)人機(jī)航路規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(29):206-209.

[27] 宋雪倩，胡士強(qiáng).基于Dubins路徑的A*算法的多無(wú)人機(jī)路徑規(guī)劃[J].電光與控制,2018,25(11):25-29.

[28] LAVALLE S M,KUFFNER J J.Randomized kinodynamic planning[C]//IEEE International Conference on Robotics and Automation,1999:473-479.

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

[30] AGUILAR W G,MORALES S,RUIZ H,et al.RRT* GL based optimal path planning for real-time navigation of UAVs[C]//International Work-Conference on Artificial Neural Networks,2017:585-595.

[31] LIN Y C,SARIPALLI S.Sampling-based path planning for UAV collision avoidance[J].IEEE Transactions on Intelligent Transportation Systems,2017,18(11):3179-3192.

[32] MECHALI O,XU L M,WEI M Z,et al.A rectified RRT* with efficient obstacles avoidance method for UAV in 3D environment[C]//IEEE 9th Annual International Conference on CYBER Technology in Automation,Control,and Intelligent Systems,2019:480-485.

[33] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[C]//IEEE International Conference on Robotics and Automation,1985:500-505.

[34] LIU J Y,GUO Z Q,LIU S Y.The simulation of the UAV collision avoidance based on the artificial potential field method[J].Advanced Materials Research,2012,591/592/593:1400-1404.

[35] BUDIYANTO A,CAHYADI A,ADJI T B,et al.UAV obstacle avoidance using potential field under dynamic environment[C]//International Conference on Control,Electronics,Renewable Energy and Communications (ICCEREC),2015:187-192.

[36] 熊超，解武杰，董文瀚.基于碰撞錐改進(jìn)人工勢(shì)場(chǎng)的無(wú)人機(jī)避障路徑規(guī)劃[J].計(jì)算機(jī)工程,2018,44(9):314-320.

[37] SUNBERG Z N,KOCHENDERFER M J,PAVONE M.Optimized and trusted collision avoidance for unmanned aerial vehicles using approximate dynamic programming[C]//IEEE International Conference on Robotics and Automation,2016:1455-1461.

[38] DE WAEN J,DINH H T,TORRES M H C,et al.Scalable multirotor UAV trajectory planning using mixed integer linear programming[C]//European Conference on Mobile Robots,2017:1-6.

[39] 宋敏,戴靜,孔韜.基于NMPC的無(wú)人機(jī)自主防撞控制方法[J].系統(tǒng)工程與電子技術(shù),2019,41(9):2092-2099.

[40] BELLMAN R.A Markovian decision process[J].Journal of Mathematics and Mechanics,1957,6(5):679-684.

[41] MUELLER E R,KOCHENDERFER M.Multi-rotor aircraft collision avoidance using partially observable Markov decision processes[C]//AIAA Modeling and Simulation Technologies Conference,2016:1-18.

[42] BERTRAM J,WEI P.Distributed computational guidance for high-density urban air mobility with cooperative and non-cooperative collision avoidance[C]//AIAA Scitech 2020 Forum,2020.doi：10.2514/6.2020-1371.

[43] 李安醍,李誠(chéng)龍,武丁杰,等.結(jié)合跳點(diǎn)引導(dǎo)的無(wú)人機(jī)隨機(jī)搜索避撞決策方法[J].航空學(xué)報(bào),2020,41(8):325-337.

[44] JULIAN K D,KOCHENDERFER M J,OWEN M P.Deep neural network compression for aircraft collision avoidance systems[J].Journal of Guidance,Control,and Dynamics,2019,42(3):598-608.

[45] HAN X,WANG J,XUE J Y,et al.Intelligent decision-making for 3-dimensional dynamic obstacle avoidance of UAV based on deep reinforcement learning[C]//The 11th International Conference on Wireless Communications and Signal Processing (WCSP),2019:1-6.

[46] GIUSTI A,GUZZI J,CIRESAN D C,et al.A machine learning approach to visual perception of forest trails for mobile robots[J].IEEE Robotics and Automation Letters,2015,1(2):661-667.

[47] LOQUERCIO A,MAQUEDA A I,DEL-BLANCO C R,et al.DroNet:learning to fly by driving[J].IEEE Robotics and Automation Letters,2018,3(2):1088-1095.

[48] FALANGA D,KLEBER K,SCARAMUZZA D.Dynamic obstacle avoidance for quadrotors with event cameras[J].Science Robotics,2020,5(40):1-14.

A Survey on Autonomous Collision Avoidance Algorithms for UAVs at Low Altitude

LI Anti, WU Dingjie, LI Chenglong

(Civil Aviation Flight University of China,Guanghan 618000,China)

Abstract： With the extensive application of civil UAV technology,the practice of integrating UAV into national airspace,and executing flight missions with manned aircraft in shared airspace at low altitude has become a trend of future development.UAV “sensing and avoiding” system plays a crucial role in ensuring flight safety in the integrated airspace in the future,and the autonomous collision avoidance algorithm is a key part to ensure efficient operation of the whole system.At present,the research on autonomous collision avoidance algorithms of the UAV has been very in-depth.The existing collision avoidance algorithms are classified based on the characteristics and mechanism of collision avoidance,different types of collision avoidance algorithms are introduced in detail,and their advantages and limitations are expounded.Finally,the development direction of autonomous collision avoidance algorithms for UAVs is prospected.

Key words： UAV; collision avoidance algorithm; path planning; low-altitude airspace

引用格式：李安醍，武丁杰，李誠(chéng)龍.低空無(wú)人機(jī)自主避障算法綜述[J].電光與控制，2021，28(8)：59-64.LI A T,WU D J,LI C L.A survey on autonomous collision avoidance algorithms for UAVs at low altitude[J].Electronics Optics & Control,2021,28(8):59-64.

中圖分類號(hào)：V279

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1671-637X.2021.08.013

收稿日期：2020-08-14

修回日期：2020-08-30

基金項(xiàng)目：中國(guó)民用航空局安全能力建設(shè)項(xiàng)目(0241928)

作者簡(jiǎn)介：李安醍(1993 —),男，四川達(dá)州人，碩士生。