吳健發(fā)，王宏倫，劉一恒，姚 鵬

（1. 北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院，北京100191；2. 北京航空航天大學(xué)飛行器控制一體化技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100191；3. 北京航空航天大學(xué)高等理工學(xué)院，北京100191；4. 中國(guó)海洋大學(xué)工程學(xué)院，青島266100）

1 引 言

無(wú)人機(jī)（Unmanned Aerial Vehicle，UAV）因其具有性價(jià)比高、使用靈活、不受飛行員生理?xiàng)l件限制等優(yōu)勢(shì)，在軍用和民用領(lǐng)域得到廣泛應(yīng)用，受到世界各國(guó)的認(rèn)可。最近30 多年來(lái)，隨著航空、控制和電子信息等技術(shù)的發(fā)展，世界各國(guó)對(duì)無(wú)人機(jī)領(lǐng)域持續(xù)關(guān)注并加大投入，無(wú)人機(jī)技術(shù)取得了長(zhǎng)足的進(jìn)步與發(fā)展，代表了當(dāng)今高新技術(shù)的發(fā)展方向。

隨著無(wú)人機(jī)的作業(yè)空域從中、高空不斷向低空甚至超低空拓展，所面臨的障礙環(huán)境的復(fù)雜性逐漸上升，具體表現(xiàn)為低空障礙環(huán)境具有密集性、非凸性、動(dòng)態(tài)性（存在突發(fā)威脅、移動(dòng)障礙等）和不確定性（存在部分未知或完全未知的障礙信息等）的特點(diǎn)［1］。復(fù)雜的障礙環(huán)境給無(wú)人機(jī)的飛行安全帶來(lái)極大的挑戰(zhàn)，例如，2016年2月4日，一架小型無(wú)人機(jī)在拍攝電影過(guò)程中失誤撞擊紐約帝國(guó)大廈［2］；2019年11月16日，俄羅斯獵戶座軍用無(wú)人機(jī)在低空試飛時(shí)與樹木發(fā)生碰撞，導(dǎo)致飛機(jī)墜毀［3］。這些事故的發(fā)生對(duì)無(wú)人機(jī)的自主控制能力提出了更高的要求。

作為反映無(wú)人機(jī)自主控制能力的關(guān)鍵技術(shù)之一——避障航路規(guī)劃技術(shù)受到了廣泛的關(guān)注［4］。無(wú)人機(jī)避障航路規(guī)劃是指在特定的任務(wù)背景下，尋找使無(wú)人機(jī)由起始點(diǎn)按照一條較優(yōu)的飛行路徑，最終到達(dá)目標(biāo)點(diǎn)的飛行航路，這種飛行航路應(yīng)滿足無(wú)人機(jī)自身的物理約束條件，同時(shí)應(yīng)能夠安全躲避障礙和威脅。目前，國(guó)內(nèi)外學(xué)者針對(duì)該問題從不同角度開展了大量研究，并提出各種不同的理論與方法，本文將對(duì)當(dāng)前主要的規(guī)劃方法進(jìn)行綜述，重點(diǎn)介紹方法組成、基本原理、代表性研究以及優(yōu)缺點(diǎn)。在此基礎(chǔ)上，對(duì)其未來(lái)可能的發(fā)展方向進(jìn)行展望。

2 避障航路規(guī)劃方法

避障航路規(guī)劃是無(wú)人機(jī)任務(wù)規(guī)劃的基礎(chǔ)與重要組成部分。依據(jù)航路規(guī)劃所建立優(yōu)化模型的不同，可將其大致分為基于數(shù)學(xué)規(guī)劃的方法、基于路標(biāo)圖的方法、基于空間分解的方法、基于勢(shì)場(chǎng)的方法、基于隨機(jī)規(guī)劃的方法和基于機(jī)器學(xué)習(xí)的方法六大類。但需注意的是，航路規(guī)劃方法的分類并無(wú)統(tǒng)一界定，且許多學(xué)者在使用時(shí)將兩種或多種方法結(jié)合，可發(fā)揮各自方法的優(yōu)勢(shì)。本文僅提供一種分類思路。

2.1 基于數(shù)學(xué)規(guī)劃的方法

數(shù)學(xué)規(guī)劃是指在滿足一系列約束條件下，尋找目標(biāo)函數(shù)最優(yōu)解的過(guò)程。航路規(guī)劃問題，從本質(zhì)上可看作是一種非線性的、包含狀態(tài)約束與控制約束的最優(yōu)控制問題，因此較為直觀的思路是采用數(shù)學(xué)規(guī)劃方法來(lái)解決該問題。在面向避障任務(wù)的航路規(guī)劃研究中，無(wú)人機(jī)需躲避規(guī)劃空間中的靜態(tài)障礙或動(dòng)態(tài)威脅，因此數(shù)學(xué)規(guī)劃法需將障礙物或威脅源等效為相應(yīng)的不等式約束；航路可飛性是航路規(guī)劃的基本要求，因此必須考慮無(wú)人機(jī)的動(dòng)力學(xué)約束條件；然后，將各項(xiàng)指標(biāo)（如飛行時(shí)間、路徑長(zhǎng)度、能量消耗、威脅程度等）建模為目標(biāo)函數(shù)，通過(guò)優(yōu)化計(jì)算求解最終使目標(biāo)函數(shù)取極值。數(shù)學(xué)規(guī)劃方法［5］主要包括動(dòng)態(tài)規(guī)劃法、混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming，MILP）、模型預(yù)測(cè)控制法（Model Predictive Control，MPC）/滾動(dòng)時(shí)域控制法（Receding Horizon Control，RHC）、基于Markov決策過(guò)程的方法等。

傳統(tǒng)的動(dòng)態(tài)規(guī)劃法是應(yīng)用較為廣泛的一種方法，通過(guò)將規(guī)劃問題等效為多級(jí)決策問題，依據(jù)Bellman 最優(yōu)性原理，確定每步?jīng)Q策與狀態(tài)轉(zhuǎn)移，最終生成一個(gè)決策序列。Denton R V 等［6］采用了動(dòng)態(tài)規(guī)劃技術(shù)，并與樹形搜索相結(jié)合，通過(guò)將三維航路分解為水平與垂直兩個(gè)方向進(jìn)行計(jì)算，求得三維最優(yōu)地形跟隨/地形回避航路。Bousson K［7］提出了一種單網(wǎng)格點(diǎn)動(dòng)態(tài)規(guī)劃方法來(lái)解決一些典型的在線最優(yōu)控制問題，如飛行器碰撞規(guī)避問題。動(dòng)態(tài)規(guī)劃方法原理較為簡(jiǎn)單，一般具有全局最優(yōu)解，易于工程實(shí)現(xiàn)。但該方法最大的不足在于需要大存儲(chǔ)空間，對(duì)于大規(guī)模的航路規(guī)劃問題，會(huì)出現(xiàn)組合爆炸現(xiàn)象，因此比較適合小規(guī)模航路搜索。

MILP方法將無(wú)人機(jī)的控制指令（如航向角、速度等）建模為整數(shù)或二值約束，然后通過(guò)線性規(guī)劃計(jì)算最優(yōu)航路［8］。Radmanesh M等［9］提出一種基于有限視野的動(dòng)態(tài)MILP航路規(guī)劃算法，從而有效地克服了傳統(tǒng)MILP在規(guī)劃航路時(shí)計(jì)算量較大的缺點(diǎn)。Turnbull O等［10］將MILP與MPC相結(jié)合，作為參考避障航路規(guī)劃器，用于離線訓(xùn)練改進(jìn)的語(yǔ)言決策樹（Linguistic Decision Trees，LDTs），然后再利用訓(xùn)練好的具有高實(shí)時(shí)性的LDTs進(jìn)行在線航路規(guī)劃。Sarim M等［11］將航路規(guī)劃分為兩個(gè)階段，首先用A*算法在僅考慮靜態(tài)障礙的前提下實(shí)施粗略航路規(guī)劃生成初始規(guī)劃航路，在此基礎(chǔ)上，利用MILP進(jìn)行精細(xì)化航路規(guī)劃，從而生成可規(guī)避動(dòng)態(tài)障礙的最終航路。MILP算法的計(jì)算量較大，難以滿足航路規(guī)劃實(shí)時(shí)性要求。

MPC/RHC 算法提供了一種適于復(fù)雜動(dòng)態(tài)環(huán)境下實(shí)時(shí)優(yōu)化決策的理論方法，通過(guò)模型預(yù)測(cè)與實(shí)時(shí)校正，在滾動(dòng)時(shí)域內(nèi)進(jìn)行局部?jī)?yōu)化來(lái)實(shí)現(xiàn)全局優(yōu)化。該類方法的最大優(yōu)勢(shì)在于可應(yīng)對(duì)動(dòng)態(tài)環(huán)境中的各種不確定性因素，保證算法的實(shí)時(shí)性。Grancharova A等［12］采用分布式線性MPC 算法解決多無(wú)人機(jī)協(xié)同航路規(guī)劃問題，將通信航路損失、動(dòng)態(tài)威脅程度等約束用線性函數(shù)表示，并利用凸二次規(guī)劃方法進(jìn)行求解。Wu J 等［13］將城市環(huán)境下無(wú)人機(jī)持續(xù)跟蹤目標(biāo)航路規(guī)劃問題建模為一個(gè)分布式MPC問題，并利用自適應(yīng)草蜢優(yōu)化算法在線解算無(wú)人機(jī)的最優(yōu)控制輸入，從而使規(guī)劃出的航路能夠兼顧避障和目標(biāo)跟蹤。Luo G 等［14］將RHC 與人工勢(shì)場(chǎng)法相結(jié)合，利用RHC優(yōu)化人工勢(shì)場(chǎng)中的附加控制力，從而實(shí)現(xiàn)無(wú)人機(jī)的在線避障。

此外，其它數(shù)學(xué)規(guī)劃方法也被應(yīng)用于無(wú)人機(jī)避障任務(wù)過(guò)程。寧芊等［15-16］將Markov生存模型引入航路規(guī)劃算法中，得到一個(gè)可用來(lái)評(píng)估路徑點(diǎn)生存概率的航路規(guī)劃問題模型，從而實(shí)現(xiàn)對(duì)最優(yōu)航路的動(dòng)態(tài)搜索。Ragi S等［17］提出一種基于部分可觀Markov決策過(guò)程（Partially Observable Markov Decision Processes，POMDPs）的航路規(guī)劃框架，在該框架下，通過(guò)適當(dāng)?shù)貥?gòu)造POMDP的動(dòng)作空間、過(guò)渡律和目標(biāo)函數(shù)，可使無(wú)人機(jī)在復(fù)雜動(dòng)態(tài)障礙環(huán)境下執(zhí)行目標(biāo)跟蹤任務(wù)。

通過(guò)分析上述文獻(xiàn)可知，數(shù)學(xué)規(guī)劃算法是一種較為直觀的方法，但由于數(shù)學(xué)優(yōu)化本身的特性，該類方法仍存在如下缺陷：當(dāng)動(dòng)力學(xué)或環(huán)境約束較為復(fù)雜時(shí)（特別對(duì)于存在多個(gè)非凸約束的情況），求解難度和計(jì)算量較大，難以保證算法的實(shí)時(shí)性。

2.2 基于路標(biāo)圖的方法

基于路標(biāo)圖的方法最初應(yīng)用于機(jī)器人運(yùn)動(dòng)規(guī)劃中，由于問題相似性，該類方法也可應(yīng)用到二維環(huán)境下的無(wú)人機(jī)航路規(guī)劃問題中。其基本思路是，首先根據(jù)一定的規(guī)則將規(guī)劃空間表示成由一維線段構(gòu)成的路標(biāo)圖，并對(duì)路線圖上的每條邊賦予一定的代價(jià)值（路徑長(zhǎng)度、威脅度等），然后采用某一種搜索算法在該圖上尋找使搜索代價(jià)最小的聯(lián)通路徑，這樣二維路徑規(guī)劃問題被轉(zhuǎn)化為一維圖搜索問題。典型的路標(biāo)圖方法包括可視圖法（Visibility Graph）和Voronoi圖法等。

圖1 可視圖法（左）和Voronoi圖法（右）示意圖Fig.1 Visibility graph(left)and Voronoi graph(right)

可視圖法的基本思路為［18］：在二維空間中，構(gòu)建連接各障礙物多邊形頂點(diǎn)的可視圖，其中需保證任意兩頂點(diǎn)的連線不經(jīng)過(guò)障礙物區(qū)域，然后從中尋找最短的路徑作為規(guī)劃航路。雖然可保證算法的完備性與最優(yōu)性，但該方法不能表達(dá)無(wú)人機(jī)的方向性約束，即無(wú)法保證航路是可飛的，難以將其應(yīng)用于實(shí)際航路規(guī)劃中。

Voronoi圖法的基本思路為［19］：根據(jù)障礙物布置情況，依次畫出相鄰兩個(gè)障礙物的中垂線，從而形成圍繞各障礙物的多邊形，所有邊界即構(gòu)成Voronoi圖，可保證路徑與威脅的距離最大；然后，對(duì)每條路徑賦權(quán)值（如路徑長(zhǎng)度、威脅度等）；最后，采取某種搜索算法尋找代價(jià)和最小的最優(yōu)航路。由于該方法考慮了航路最優(yōu)性與障礙物距離約束，因此廣泛應(yīng)用于無(wú)人機(jī)航路規(guī)劃中。Bhattacharya P 等［20］在指定區(qū)域內(nèi)構(gòu)建Voronoi圖，并采取迭代平滑處理策略優(yōu)化航路，最終實(shí)現(xiàn)動(dòng)態(tài)航路的在線規(guī)劃。朱杰等［21］提出了一種改進(jìn)型的Voronoi圖構(gòu)造模型，該模型通過(guò)引入威脅源的不可穿越區(qū)域邊界，利用折中原理，在Delaunay 三角網(wǎng)的基礎(chǔ)上構(gòu)建航跡拓?fù)淇臻g，在此基礎(chǔ)上，采用D*算法進(jìn)行航路重規(guī)劃。此外，由于三維空間內(nèi)Voronoi 圖將變得非常復(fù)雜，因此部分學(xué)者采用平面分割方法將三維空間航路規(guī)劃問題轉(zhuǎn)換為二維平面的搜索問題［22］。

路標(biāo)圖法原理簡(jiǎn)單，但必須表示出規(guī)劃空間內(nèi)的所有可能路徑，否則可能丟失最優(yōu)解。此外，該類方法本質(zhì)上屬于二維航路規(guī)劃算法，在三維環(huán)境下的路標(biāo)圖將變得非常復(fù)雜，其在線規(guī)劃能力較差，并且規(guī)劃的航路不平滑甚至不滿足飛行器運(yùn)動(dòng)學(xué)約束。

2.3 基于空間分解的方法

空間分解法的基本思路為：首先，采用柵格法等將任務(wù)空間分解成一些具有規(guī)則形狀的單元（通常為正方形），并判斷這些單元是否被障礙物覆蓋或與障礙物相交；然后，找到包含起始點(diǎn)與目標(biāo)點(diǎn)的單元，并采用某一搜索算法（如A*、D*等啟發(fā)式算法，遺傳算法、粒子群算法等智能優(yōu)化算法等）尋找一系列連通的單元將起始單元和目標(biāo)單元連接起來(lái)。

啟發(fā)式搜索算法是一種決策性搜索算法，以A*算法為代表，它根據(jù)問題求解的目標(biāo)信息引入啟發(fā)式信息，使搜索過(guò)程具有導(dǎo)向性，極大地提高了搜索效率［23］。A*搜索算法的代價(jià)函數(shù)可表示為f（n）=g（n）+h（n），其中g(shù)（n）為初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的航路代價(jià)，h（n）為當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的預(yù)測(cè)代價(jià)。在路徑搜索過(guò)程中，以代價(jià)函數(shù)f（n）作為啟發(fā)信息，選擇代價(jià)值最小的節(jié)點(diǎn)并插入到路徑鏈表中。經(jīng)證明，只要啟發(fā)式因子滿足單調(diào)性條件時(shí)，A*算法一定能找到最優(yōu)路徑。Szczerba R J 等［24］利用稀疏A*算法將無(wú)人機(jī)約束條件進(jìn)行簡(jiǎn)化并將其引入到代價(jià)函數(shù)中，減小了搜索空間，因此航路規(guī)劃時(shí)間得到有效縮短。占偉偉等［25］將二維A*算法擴(kuò)展到三維空間中，分別在二維平面內(nèi)和垂直方向上規(guī)劃航路，并通過(guò)Monte Carlo方法進(jìn)行了仿真。

由于傳統(tǒng)A*僅能用于靜態(tài)環(huán)境規(guī)劃，因此許多學(xué)者對(duì)其進(jìn)行了改進(jìn)，其中最為典型的為D*算法［21］或D*Lite 算法［26］。D*算法與A*算法的區(qū)別在于，當(dāng)環(huán)境改變時(shí)，或無(wú)人機(jī)探測(cè)到的周圍環(huán)境信息變化時(shí)，對(duì)路徑代價(jià)值進(jìn)行相應(yīng)更新。當(dāng)探測(cè)到環(huán)境變化時(shí)，由于該類算法只對(duì)直接受到影響的節(jié)點(diǎn)的代價(jià)值進(jìn)行更新，且在啟發(fā)式信息中保證該節(jié)點(diǎn)的優(yōu)先級(jí)，因此該方法能夠快速規(guī)劃出最優(yōu)路徑，保證了動(dòng)態(tài)航路規(guī)劃的實(shí)時(shí)性與高效性。

智能算法屬于隨機(jī)型智能搜索算法范疇，通過(guò)在求解空間內(nèi)基于隨機(jī)的方式搜尋最優(yōu)值。智能算法是近年來(lái)興起的模擬生物進(jìn)化或種群行為等自然現(xiàn)象的一類優(yōu)化方法，具有全局優(yōu)化能力強(qiáng)、并行機(jī)制、靈活性高、易與具體應(yīng)用問題相結(jié)合等優(yōu)勢(shì)，因此近年來(lái)越來(lái)越多地應(yīng)用于無(wú)人機(jī)二維或三維航路規(guī)劃問題中，例如遺傳算法（Genetic Algorithm，GA）［27］、粒子群算法（Particle Swarm Optimization，PSO）［28］、鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）［29］、蟻獅算法（Ant Lion Optimizer，ALO）［30］、鴿群算法（Pigeon-Inspired Optimization，PIO）［31］等。

空間分解法中網(wǎng)格地圖的構(gòu)建需要耗費(fèi)大量的計(jì)算時(shí)間，因此當(dāng)網(wǎng)格數(shù)較多、分辨率較高、地形信息動(dòng)態(tài)變化時(shí)，該類算法難以保證路徑規(guī)劃的實(shí)時(shí)性。此外，在復(fù)雜情景下，用于航路搜索的啟發(fā)式算法或智能算法的計(jì)算量較大，因此實(shí)際中大多應(yīng)用于處理環(huán)境不確定性低、地形簡(jiǎn)單的靜態(tài)航路規(guī)劃問題。同時(shí)該類算法所規(guī)劃航路的平滑性也不夠理想。

2.4 基于勢(shì)場(chǎng)的方法

基于勢(shì)場(chǎng)的方法通過(guò)將規(guī)劃空間建模為一種具有高低不同勢(shì)場(chǎng)的區(qū)域來(lái)進(jìn)行規(guī)劃，通常起始點(diǎn)的勢(shì)場(chǎng)最低而目標(biāo)點(diǎn)勢(shì)場(chǎng)最高，然后在該勢(shì)場(chǎng)區(qū)域內(nèi)進(jìn)行路徑搜索。該類方法將物體的運(yùn)動(dòng)看成是作用力的結(jié)果，從而進(jìn)行路徑規(guī)劃研究，典型算法包括人工勢(shì)場(chǎng)法（Artificial Potential Field，APF），流函數(shù)法（Stream Function，SF），擾動(dòng)流體動(dòng)態(tài)系統(tǒng)法（Interfered Fluid Dynamical System，IFDS）等。

APF 算法最早由美國(guó)學(xué)者Khatib O 提出［32］，其基本思想是將運(yùn)動(dòng)體在周圍環(huán)境中的運(yùn)動(dòng)設(shè)計(jì)成在一種抽象的人造力場(chǎng)中的運(yùn)動(dòng)，其中目標(biāo)點(diǎn)對(duì)運(yùn)動(dòng)體產(chǎn)生吸引力場(chǎng)，障礙物對(duì)運(yùn)動(dòng)體產(chǎn)生排斥力場(chǎng)，根據(jù)可加性原理，多障礙物存在時(shí)的總排斥力為各障礙物排斥力的累加，這樣將合力引入底層控制，可以得到有效的局部防撞路徑。APF 算法計(jì)算量較小，適用于在線路徑規(guī)劃，但存在著局部極小點(diǎn)和目標(biāo)不可達(dá)等問題。針對(duì)這種狀況，許多研究者對(duì)該算法進(jìn)行了分析與改進(jìn)，其中最有代表性的是新加坡國(guó)立大學(xué)的葛樹志，其團(tuán)隊(duì)改進(jìn)了APF中排斥勢(shì)場(chǎng)函數(shù)，初步解決了APF 中局部極小點(diǎn)、目標(biāo)不可達(dá)以及規(guī)避移動(dòng)威脅的問題［33-34］，同時(shí)還將APF 的應(yīng)用拓展至多機(jī)器人編隊(duì)協(xié)同路徑規(guī)劃中［35-37］。受上述文獻(xiàn)啟發(fā)，部分研究者開始探索各種新構(gòu)型APF，并嘗試APF 與其他航路規(guī)劃方法相結(jié)合。Cao L 等［38］提出一種基于Gaussian 斥力函數(shù)的APF用于飛行器避障三維航路規(guī)劃，從而實(shí)現(xiàn)更優(yōu)的抗局部最優(yōu)特性和可達(dá)性。文獻(xiàn)［14，39-41］為APF引入了附加吸引場(chǎng)的概念，通過(guò)適當(dāng)調(diào)節(jié)附加吸引場(chǎng)的大小和方向，在一定條件下可有效避免局部最小情況的發(fā)生。

APF 可迅速規(guī)劃出光滑的避障路徑，因此其經(jīng)常被用于在線避障規(guī)劃。但該類方法存在如下問題：（1）在APF 中，沒有障礙形狀（包絡(luò)）的概念，完全依靠調(diào)整力場(chǎng)生成航路，因此當(dāng)力場(chǎng)參數(shù)調(diào)整不恰當(dāng)時(shí)，無(wú)人機(jī)有可能進(jìn)入障礙內(nèi)部，導(dǎo)致避障失??；（2）APF的力場(chǎng)容易陷入局部極小。

針對(duì)APF 存在的問題，立足于勢(shì)場(chǎng)的基本思想，文獻(xiàn)［42-43］提出了流函數(shù)法，該方法具有規(guī)劃速度快、路徑平滑等優(yōu)點(diǎn)，其基本思路如下：在規(guī)劃空間內(nèi)引入某種初始流場(chǎng)，可根據(jù)流體力學(xué)知識(shí)求得其速度勢(shì)；當(dāng)流場(chǎng)中存在障礙物時(shí)，可建立障礙物勢(shì)場(chǎng)與原初始流場(chǎng)疊加得到總勢(shì)場(chǎng)，對(duì)其速度勢(shì)求導(dǎo)獲得流場(chǎng)流速；對(duì)流速積分得到流體流線即規(guī)劃航路。該方法是APF的一種變形，具有APF函數(shù)的一般特性，但能在一定程度上避免局部極小問題。一些研究工作對(duì)該算法進(jìn)行了改進(jìn)。梁宵等［44］提出一種基于行為伸縮功能的滾動(dòng)窗口啟發(fā)方向計(jì)算方法，使其跟蹤目標(biāo)，并在滾動(dòng)窗口內(nèi)采取流函數(shù)法規(guī)劃局部避障航路，經(jīng)驗(yàn)證該方法可有效減少計(jì)算時(shí)間與空間復(fù)雜度，實(shí)現(xiàn)動(dòng)態(tài)航路規(guī)劃。Daily R 等［45］在采用流函數(shù)法解決躲避單障礙物問題的基礎(chǔ)上，采用加權(quán)求和法解決了兩個(gè)甚至多個(gè)障礙物存在時(shí)的航路規(guī)劃問題。

圖2 流體擾動(dòng)示意圖Fig.2 Schematic diagram of IFDS original fluid flows and interfered fluid flows

然而，當(dāng)規(guī)劃空間由二維擴(kuò)展到三維時(shí)，流函數(shù)的概念將不復(fù)存在，因此該方法主要用于二維環(huán)境下的路徑規(guī)劃。針對(duì)這一情況，本課題組在參考流函數(shù)法中相應(yīng)流體概念的基礎(chǔ)上，進(jìn)一步提出了基于流水避石思想的三維航路規(guī)劃方法［46］。該方法借鑒了自然界水流流動(dòng)的宏觀特征：當(dāng)無(wú)障礙物時(shí)，水流沿直線流動(dòng)；當(dāng)遇到障礙物時(shí)，水流會(huì)平滑地繞過(guò)該障礙并最終流向終點(diǎn)。同時(shí)，引入三維障礙外包絡(luò)的概念，將航路規(guī)劃與流體計(jì)算有機(jī)結(jié)合，通過(guò)流體力學(xué)方法對(duì)三維地形進(jìn)行流場(chǎng)模擬，并綜合考慮無(wú)人機(jī)性能約束、飛行安全性、航路代價(jià)等指標(biāo)進(jìn)行航路優(yōu)選，最終得到滿足任務(wù)要求的三維光滑可飛航路。其計(jì)算方法分為解析計(jì)算和數(shù)值計(jì)算兩種，解析法適合障礙分布簡(jiǎn)單的情況，計(jì)算量小，航路分布于起點(diǎn)至終點(diǎn)的航路帶間；數(shù)值法適合復(fù)雜的地形情況，航路能夠充滿規(guī)劃區(qū)域。

遺憾的是，傳統(tǒng)流水避石方法仍存在一定的局限性：其中的解析法僅能處理球體障礙，對(duì)于其他立體障礙（例如柱形、錐形等）難以獲得其解析解；而數(shù)值法由于需要采用CFD 進(jìn)行模擬，計(jì)算量過(guò)大，僅能用于離線航路規(guī)劃。另外，傳統(tǒng)流水避石方法由于自身的復(fù)雜性，難以與其他任務(wù)背景相結(jié)合，僅能做單純的避障機(jī)動(dòng)，極大的限制了其應(yīng)用。

從航路規(guī)劃的角度來(lái)講，對(duì)于更為復(fù)雜的障礙物，可以放寬對(duì)流體物理性質(zhì)的限制，重點(diǎn)關(guān)注流體的避障特性，從而降低方程求解的難度。因此，針對(duì)傳統(tǒng)流水避石方法存在的問題，本課題組首次提出了擾動(dòng)流體動(dòng)態(tài)系統(tǒng)（Interfered Fluid Dynamical System，IFDS）避障算法［47］，該算法以解析法為基礎(chǔ)，但避免了求解帶有復(fù)雜邊界條件的流體方程，便于處理復(fù)雜的地形和不同形狀的障礙物。規(guī)劃航路不僅具有仿流水避石的自然特性，而且環(huán)境建模簡(jiǎn)單，計(jì)算量小，大大拓展了流水避石方法的適用范圍。

IFDS 提取了自然界流水避石現(xiàn)象與避障航路規(guī)劃問題的相似之處：河流中的石頭可看作無(wú)人機(jī)需躲避的障礙物；筆直的流水可看作初始流場(chǎng)，初始流場(chǎng)流線即為無(wú)障礙環(huán)境下的初始航路；繞過(guò)石頭的流水可等效為擾動(dòng)流場(chǎng)，擾動(dòng)流場(chǎng)流線即為障礙環(huán)境下的規(guī)劃航路。IFDS 算法的關(guān)鍵在于求解擾動(dòng)流場(chǎng)的流速，算法的基本步驟為：首先建立初始流場(chǎng)即匯流，然后將障礙物對(duì)初始流場(chǎng)的擾動(dòng)影響用擾動(dòng)矩陣量化表示，接著通過(guò)修正初始流場(chǎng)流速獲得擾動(dòng)流場(chǎng)流速，最后對(duì)其迭代積分即可得到擾動(dòng)流場(chǎng)流線，即無(wú)人機(jī)的規(guī)劃航路。在靜態(tài)IFDS的基礎(chǔ)上，文獻(xiàn)［48-49］進(jìn)一步引入相對(duì)初始流場(chǎng)的概念，從而使IFDS 能夠同時(shí)應(yīng)對(duì)靜態(tài)障礙與動(dòng)態(tài)威脅。為解決規(guī)劃過(guò)程中存在的駐點(diǎn)和陷阱區(qū)問題，虛擬障礙［47］、虛擬目標(biāo)點(diǎn)［50］、切向矩陣［51-54］等策略被引入IFDS中。為解決規(guī)劃航路的可飛性問題，文獻(xiàn)［50］、文獻(xiàn)［53-54］和文獻(xiàn)［29，55］分別將軌跡延拓方法、RHC 方法和無(wú)人機(jī)運(yùn)動(dòng)學(xué)模型與IFDS 相結(jié)合，從而使規(guī)劃航路更加符合無(wú)人機(jī)的運(yùn)動(dòng)學(xué)特性。

相較于其他避障航路規(guī)劃方法，基于勢(shì)場(chǎng)的方法的計(jì)算量小、實(shí)時(shí)性高，便于執(zhí)行在線航路規(guī)劃任務(wù)，且規(guī)劃的航路相對(duì)平滑，但在設(shè)計(jì)使用時(shí)仍需要著重考慮規(guī)避局部極小問題。

2.5 基于隨機(jī)規(guī)劃的方法

基于隨機(jī)規(guī)劃的方法最初用來(lái)解決基于APF的路徑規(guī)劃算法中存在的局部極小問題，其基本思路是在狀態(tài)空間中以隨機(jī)采樣的方式擴(kuò)展構(gòu)建可行路徑集合，然后在以圖結(jié)構(gòu)或樹結(jié)構(gòu)表達(dá)的路徑集合中尋找完整可行路徑。隨機(jī)規(guī)劃法主要包括隨機(jī)路標(biāo)圖法（Probabilistic Roadmaps，PRM）和快速擴(kuò)展隨機(jī)樹（Rapid Exploring Random Trees，RRT）。

PRM法以圖的方式表示路徑集合，其主要包括兩個(gè)階段：學(xué)習(xí)階段，在狀態(tài)空間內(nèi)進(jìn)行隨機(jī)采樣并進(jìn)行碰撞檢測(cè)，若采樣點(diǎn)在自由空間內(nèi)，則將該采樣點(diǎn)加入路線圖中，否則丟棄該采樣點(diǎn)，從而構(gòu)建起包含若干連通單元的路徑圖；查詢階段，從上述路徑圖中尋找從起始點(diǎn)到目標(biāo)點(diǎn)的連通路徑。Lien J M等［56］采用中軸線采樣方法，解決了PRM算法中隨機(jī)采樣點(diǎn)難以覆蓋狹窄通道的問題。Sanchez-Lopez J L 等［57］利用PRM 對(duì)規(guī)劃空間進(jìn)行采樣，然后利用人工場(chǎng)圖作為代價(jià)函數(shù)的離散搜索算法對(duì)生成的PRM進(jìn)行搜索，得到原始的最優(yōu)無(wú)碰撞路徑，再將其縮短。由于PRM 算法規(guī)劃航路的優(yōu)越性很大程度上取決于采樣階段的分配時(shí)間，且該算法不能通過(guò)局部更新航路應(yīng)對(duì)動(dòng)態(tài)情況，因此PRM算法主要應(yīng)用于離線航路規(guī)劃。此外由于PRM 算法在規(guī)劃過(guò)程中不考慮無(wú)人機(jī)動(dòng)力學(xué)約束，故該算法難以保證規(guī)劃航路的可飛性。

與PRM算法相比，RRT算法采用樹表示路徑集合，且將系統(tǒng)狀態(tài)模型引入路徑規(guī)劃過(guò)程中，因此可處理無(wú)人機(jī)復(fù)雜動(dòng)力學(xué)與運(yùn)動(dòng)學(xué)約束問題［58］。其計(jì)算速度快，實(shí)時(shí)性好，可用于動(dòng)態(tài)不確定性環(huán)境，得到了廣泛的應(yīng)用。但隨機(jī)思想的引入也導(dǎo)致了規(guī)劃結(jié)果優(yōu)化的不足，且其避障特性不甚理想，許多學(xué)者對(duì)此進(jìn)行了改進(jìn)。尹高揚(yáng)等［59］通過(guò)引入航跡距離約束，使搜索樹沿路徑距離最短的近似最優(yōu)航跡方向進(jìn)行擴(kuò)展，克服了RRT方法隨機(jī)性強(qiáng)的缺陷。溫乃峰等［60］通過(guò)引入代價(jià)模型，提出約減域逐步構(gòu)造方法，引導(dǎo)規(guī)劃樹快速有效擴(kuò)展，改善了RRT算法中存在的采樣空間過(guò)度約減問題。

圖3 RRT節(jié)點(diǎn)擴(kuò)展示意圖Fig.3 Expansion of nodes in RRT

基于隨機(jī)規(guī)劃的方法尤其是RRT 算法能處理無(wú)人機(jī)的復(fù)雜動(dòng)力學(xué)與運(yùn)動(dòng)學(xué)約束，且具有概率意義上的完備性。但節(jié)點(diǎn)的隨機(jī)采樣過(guò)程使得該算法規(guī)劃的航路難以保證最優(yōu)性。此外，由于該方法在隨機(jī)采樣過(guò)程中需判斷某一節(jié)點(diǎn)是否屬于自由空間，屬于被動(dòng)的避障策略，因此不適用于復(fù)雜地形或動(dòng)態(tài)環(huán)境。

2.6 基于機(jī)器學(xué)習(xí)的方法

近年來(lái)，以強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）和深度學(xué)習(xí)（Deep Learning，DL）為代表的機(jī)器學(xué)習(xí)方法蓬勃發(fā)展，在無(wú)人機(jī)自主飛行控制與決策領(lǐng)域發(fā)揮著越來(lái)越大的作用［61］。

強(qiáng)化學(xué)習(xí)采用了人類和動(dòng)物學(xué)習(xí)中的“嘗試與失敗”機(jī)制，強(qiáng)調(diào)在與環(huán)境的交互中學(xué)習(xí)，利用評(píng)價(jià)性的反饋信號(hào)實(shí)現(xiàn)決策的優(yōu)化。其過(guò)程是一個(gè)試探與評(píng)價(jià)的過(guò)程，基本原理為：智能體在環(huán)境s下選擇并執(zhí)行一個(gè)動(dòng)作a，環(huán)境接受動(dòng)作后變?yōu)閟′，并把一個(gè)獎(jiǎng)賞信號(hào)r 反饋給智能體，智能體再根據(jù)獎(jiǎng)賞信號(hào)選擇后續(xù)動(dòng)作。由于強(qiáng)化學(xué)習(xí)在學(xué)習(xí)過(guò)程中不需要給定各種狀態(tài)下的教師信號(hào)，因此其在求解復(fù)雜的優(yōu)化決策問題方面有著廣泛的應(yīng)用前景。強(qiáng)化學(xué)習(xí)可分為基于值函數(shù)的強(qiáng)化學(xué)習(xí)和基于策略的強(qiáng)化學(xué)習(xí)。在基于值函數(shù)的強(qiáng)化學(xué)習(xí)中，最常用的學(xué)習(xí)算法為Q 學(xué)習(xí)算法，大量研究將其應(yīng)用于無(wú)人機(jī)或機(jī)器人的路徑規(guī)劃中，例如，Low E S 等［62］提出一種部分引導(dǎo)的Q 學(xué)習(xí)算法，該算法在實(shí)施Q學(xué)習(xí)前利用花授粉算法初始化Q 表，從而提高了算法的收斂速度；Konar A等［63］提出一種確定性Q學(xué)習(xí)方法，它具有從當(dāng)前狀態(tài)到下一個(gè)狀態(tài)以及目標(biāo)的距離的假定知識(shí)，因此不必像傳統(tǒng)Q 學(xué)習(xí)算法重復(fù)更新知識(shí)，從而使移動(dòng)機(jī)器人在迷宮中進(jìn)行路徑規(guī)劃時(shí)具有更小的時(shí)間復(fù)雜度。然而，由于Q 學(xué)習(xí)算法的狀態(tài)空間和動(dòng)作空間均為離散的，因此其規(guī)劃航路的可飛性較差，且難以應(yīng)付動(dòng)態(tài)威脅。針對(duì)此缺陷，研究者提出將深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)相結(jié)合，組成深度強(qiáng)化學(xué)習(xí)算法（Deep Reinforcement Learning，DRL），以滿足狀態(tài)空間或動(dòng)作空間連續(xù)化的需求。DRL 的開端是深度Q 網(wǎng)絡(luò)（Deep Q Network，DQN），由DeepMind公司于2013年提出［64］。文獻(xiàn)［65-66］在路徑規(guī)劃中引入了不同改進(jìn)型的DQN，取得了較好的效果，但由于DQN 的動(dòng)作空間仍然是離散形式的，因此規(guī)劃的路徑質(zhì)量仍有進(jìn)一步提升的空間。

為了實(shí)現(xiàn)連續(xù)的狀態(tài)空間和動(dòng)作空間，研究者進(jìn)一步將強(qiáng)化學(xué)習(xí)的另一個(gè)分支：基于策略的強(qiáng)化學(xué)習(xí)與深度學(xué)習(xí)相結(jié)合，提出了基于策略的DRL算法，包括深度確定性策略梯度算法（Deep Deterministic Policy Gradient，DDPG）［67］和分布式近似策略優(yōu)化算法（Distributed Proximal Policy Optimization，DPPO）［68］等。盡管一些學(xué)者已嘗試將其應(yīng)用于無(wú)人機(jī)和無(wú)人車的路徑規(guī)劃中［69-71］，但這些研究所涉及的場(chǎng)景相對(duì)于無(wú)人機(jī)的復(fù)雜作業(yè)環(huán)境來(lái)說(shuō)仍相距甚遠(yuǎn)。此外，由于復(fù)雜環(huán)境中約束較多，因此相較于Q學(xué)習(xí)和DQN等基于離散空間的方法，基于策略的DRL算法可能存在不易收斂的問題，該問題的解決方法還有待進(jìn)一步的探索。

圖4 DDPG深度強(qiáng)化學(xué)習(xí)系統(tǒng)結(jié)構(gòu)圖Fig.4 DDPG deep reinforcement learning system

除了上述基于強(qiáng)化學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)的方法外，還有一些其他的機(jī)器學(xué)習(xí)方法被應(yīng)用于無(wú)人機(jī)或其他運(yùn)動(dòng)體的路徑規(guī)劃中，例如，Zhang B 等［72］提出一種合作和幾何學(xué)習(xí)算法用于多無(wú)人機(jī)協(xié)同避障；Rodríguez-Fdez I 等［73］提出一種迭代量化模糊規(guī)則學(xué)習(xí)方法用于機(jī)器人執(zhí)行沿墻跟隨任務(wù)的路徑規(guī)劃中。

盡管還處于探索和發(fā)展階段，但基于機(jī)器學(xué)習(xí)的方法已經(jīng)展現(xiàn)出了廣闊的應(yīng)用前景。相較于其他傳統(tǒng)方法，其優(yōu)點(diǎn)和缺點(diǎn)目前都比較明顯。優(yōu)點(diǎn)是規(guī)劃的實(shí)時(shí)性較好、不易陷入局部極小且不依賴于環(huán)境先驗(yàn)信息；缺點(diǎn)是當(dāng)狀態(tài)空間和動(dòng)作空間均為連續(xù)時(shí)，模型的訓(xùn)練不易收斂，導(dǎo)致其離線學(xué)習(xí)時(shí)間較長(zhǎng)，甚至可能導(dǎo)致訓(xùn)練失敗。

3 未來(lái)可能的發(fā)展方向

目前有關(guān)無(wú)人機(jī)避障航路規(guī)劃理論與方法的研究成果不斷涌現(xiàn)，其未來(lái)的發(fā)展趨勢(shì)也受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。根據(jù)對(duì)相關(guān)文獻(xiàn)的調(diào)研情況并結(jié)合作者自身在研究過(guò)程中發(fā)現(xiàn)的問題，下面簡(jiǎn)要介紹其未來(lái)可能的發(fā)展方向：

（1）對(duì)于復(fù)雜環(huán)境下的三維航路規(guī)劃方法的研究仍有進(jìn)一步提升的空間，特別是對(duì)于復(fù)雜凹型障礙環(huán)境（例如U 形障礙、洞穴等）和密集動(dòng)態(tài)障礙環(huán)境（常見于集群系統(tǒng)中）的探索仍相對(duì)較少。

（2）在未來(lái)應(yīng)考慮將傳統(tǒng)規(guī)劃方法（例如基于數(shù)學(xué)規(guī)劃的方法、基于勢(shì)場(chǎng)的方法）與以DRL 為代表的新一代人工智能技術(shù)相結(jié)合，優(yōu)勢(shì)互補(bǔ)，從而進(jìn)一步解決傳統(tǒng)規(guī)劃方法中依然存在的問題，例如局部極小問題等；同時(shí)也應(yīng)積極攻克現(xiàn)有人工智能方法在航路規(guī)劃應(yīng)用中存在的一些問題，例如收斂速度較低等。

（3）在未來(lái)的航路規(guī)劃方法研究中應(yīng)充分考慮機(jī)載傳感器的實(shí)際性能和工作特性。目前有相當(dāng)比例的研究在設(shè)計(jì)航路規(guī)劃方法時(shí)僅將無(wú)人機(jī)的機(jī)載傳感器歸結(jié)為一個(gè)統(tǒng)一而理想化的模型，障礙物信息（速度、尺寸、位置等）可以通過(guò)這個(gè)理想化模型被直接獲取進(jìn)行障礙預(yù)建模，進(jìn)而應(yīng)用于規(guī)劃當(dāng)中。而在實(shí)際中，不同機(jī)載傳感器（毫米波雷達(dá)、激光雷達(dá)、攝像頭等）的工作原理和所獲取的障礙信息形式差別較大，而且還存在時(shí)間延遲、測(cè)量誤差等問題。因此在未來(lái)應(yīng)進(jìn)一步對(duì)機(jī)載傳感器的建模進(jìn)行細(xì)化處理，針對(duì)不同特性的傳感器設(shè)計(jì)相應(yīng)的障礙信息處理策略及其對(duì)應(yīng)的航路規(guī)劃方法，從而實(shí)現(xiàn)無(wú)人機(jī)感知環(huán)節(jié)到?jīng)Q策規(guī)劃環(huán)節(jié)的無(wú)縫銜接。

（4）規(guī)劃航路的可跟蹤性問題亟待解決。目前的航路規(guī)劃方法大多僅考慮了無(wú)人機(jī)的運(yùn)動(dòng)學(xué)特性（例如最大轉(zhuǎn)彎角速率、最大爬升角、最大可用過(guò)載等），對(duì)于所規(guī)劃的航路是否切實(shí)能被無(wú)人機(jī)所精確跟蹤，尚無(wú)過(guò)多考慮。因此，有必要進(jìn)一步將無(wú)人機(jī)控制器（軌跡、姿態(tài)、動(dòng)力、執(zhí)行機(jī)構(gòu)）的特性考慮到規(guī)劃算法中，從而實(shí)現(xiàn)規(guī)劃-控制一體化。

4 結(jié)束語(yǔ)

本文闡述了無(wú)人機(jī)避障航路規(guī)劃方法的研究現(xiàn)狀，并對(duì)未來(lái)可能的研究方向進(jìn)行了分析。目前航路規(guī)劃理論已日趨成熟，但相應(yīng)的工程化研究卻相對(duì)滯后，因此在未來(lái)應(yīng)著力推動(dòng)這方面的工作，使規(guī)劃方法由理論向?qū)嵺`邁進(jìn)。