李安醍，李誠龍,*，武丁杰，衛(wèi)鵬

1. 中國民用航空飛行學院 空中交通管理學院，廣漢 618307

2. 喬治·華盛頓大學 機械與航空航天工程學院，華盛頓特區(qū) 20052

隨著無人機技術(shù)的發(fā)展和世界城市化進程的推進，城市空中交通(Urban Air Mobility，UAM)的運輸概念被NASA[1]、Uber[2]、Airbus[3]等機構(gòu)重新提出。該交通方式旨在城市空域發(fā)展短程點對點運輸系統(tǒng)，利用具有無人駕駛功能的垂直起降(VTOL)或短距起降(STOL)飛行器進行載人或載物運輸以克服日益增長的地面交通擁堵問題[4]。但無人機在城市區(qū)域內(nèi)執(zhí)行運輸任務(wù)將面臨更復雜的空域環(huán)境，如部分高層建筑和限制飛行區(qū)域以及空中實時變化的密集交通流等因素將構(gòu)成動態(tài)變化的障礙空間，而環(huán)境感知和避撞決策技術(shù)將是提供無人機在這種空間中穿行所需自動安全間隔保持能力的關(guān)鍵[5]。

城市空中交通的避撞問題結(jié)合了民航基于合作相關(guān)監(jiān)視手段的避撞決策方法和移動機器人動態(tài)避撞路徑規(guī)劃的一般特性。相比于運輸航空，城市空中交通流密度更大，飛行器需要在動靜態(tài)障礙物中進行穿梭，且并不保證同一空域內(nèi)飛行器都接受合作相關(guān)監(jiān)視手段(廣播式自動監(jiān)視(Automatic Dependent Surveillance-Broadcast, ADS-B)、二次雷達)[6]；而相比于地面移動機器人，選擇傾轉(zhuǎn)旋翼(例如Airbus Vahana飛行器)等復雜氣動布局飛行器在巡航飛行過程中較難實現(xiàn)長時間懸停，這意味著大多數(shù)飛行器必須在前飛過程中同時完成避撞機動。面向該應(yīng)用場景，避撞決策算法不僅需要考慮無人機機載計算性能以滿足實時機動決策的需要，還需考慮無人機本身動力學特性，盡可能優(yōu)化避撞路徑，使無人機整個運輸過程安全高效。

文獻[5, 7-8]對各類空中交通避撞建模與決策方法做了詳細的總結(jié)和綜述性工作，根據(jù)技術(shù)路線不同主要可將避撞方法分為3類：① 以幾何方法為代表的被動式避撞決策，通過分析無人機和入侵對象幾何空間位置相對運動速度矢量，進行飛行器危險接近最終階段的沖突解脫[9]。對于飛行器間避撞問題較為有代表性的是最小接近點法(PCA)和碰撞錐法(CCA)[10-11]，這類方法計算簡單，能夠拓展到三維動態(tài)環(huán)境的飛行避撞問題上，但對多機避撞問題處理結(jié)果不夠理想，所計算得到的避撞路徑平滑程度得不到有效保障。文獻[12]更多考慮了飛行器本身的機動性能，從最優(yōu)控制理論角度給出了滾轉(zhuǎn)角速度和法向過載的解析形式最優(yōu)解，但該方法仍存在實時性不足的問題。② 基于無碰撞路徑規(guī)劃的主動避撞方法，即將避撞決策過程轉(zhuǎn)化為帶有安全間隔約束的無碰撞路徑規(guī)劃問題。其中人工勢場法[13]在單機對靜態(tài)障礙物避撞路徑規(guī)劃過程中，計算量小，具備機載部署所需的實時性，但容易陷入局部最優(yōu)陷阱。文獻[14]對傳統(tǒng)的人工勢場法進行改進，在斥力場表達式中乘上本機到目標地距離差因子，并將其他合作的無人機作為移動的障礙物進行計算，使得目標點位置能夠成為全局力場的唯一最小值，很好地克服了人工勢場法中路徑規(guī)劃的可達性和抖動性問題。文獻[15]引入張量場概念將勢場法拓展以解決4D航跡約束下的多機編隊飛行避撞問題，但該方法僅在沖突發(fā)生時重規(guī)劃，缺乏沖突的預(yù)測和事前調(diào)整，未考慮避撞對集群所帶來的連鎖反應(yīng)，不適合無人機群體規(guī)模較大時的應(yīng)用。文獻[16-17]創(chuàng)新性地提出將無人機繞飛障礙物的軌跡以流水繞石現(xiàn)象進行建模，在路徑規(guī)劃過程中引入流體計算方法，其中解析法計算時間短，所規(guī)劃的航路平滑且具有可飛性，但其對障礙物以球形邊界劃設(shè)保護區(qū)，對于不規(guī)則多邊形障礙物乃至凹形保護區(qū)劃設(shè)方式的避撞效果并未進行討論和驗證。針對空中多無人機交通流的合作式避撞問題，文獻[18]提出了混合整數(shù)線性規(guī)劃方法進行求解，甚至考慮了無人機沖突過程中的速度變化情形，但該方法隨無人機數(shù)量增多時計算量會成幾何倍數(shù)增加。③ 基于人工智能算法的避撞決策方法。早期的方法如A*算法[19]、蟻群算法[20]、遺傳算法[21]能夠解決無人機對靜態(tài)障礙物避撞路徑規(guī)劃問題，其本質(zhì)是用于路徑規(guī)劃的優(yōu)化算法，考慮的避撞對象主要為靜態(tài)障礙物，對于多無人機交通流避撞問題應(yīng)用需要較多次迭代計算，實時性不夠。近年來一些研究者開始將無人機避撞建模成多智能體決策問題[22-24]，從而便于利用強化學習等人工智能方法進行研究。Bai[25]和Mueller[26]等系統(tǒng)性考慮了無人機傳感器測量誤差等不確定性因素，并以部分可觀馬爾科夫決策過程(POMDP)進行建模，其中文獻[25]采用蒙特卡洛數(shù)值迭代方法對三維連續(xù)狀態(tài)空間進行求解，較好地解決了離散方法在應(yīng)對高維狀態(tài)空間過程中需要大量計算資源的問題。文獻[26]主要討論了如何自適應(yīng)求解避撞過程中影響飛行器對間隔保持和軌跡跟蹤之間性能的折中系數(shù)問題，拓展了部分可觀馬爾科夫決策過程建模解決避撞問題的通用性，但上述問題討論的計算工作需要離線計算。受此啟發(fā)，文獻[27]應(yīng)用馬爾科夫決策過程(Markov Decision Process，MDP)對城市地區(qū)高密度交通流運行場景進行建模并采用蒙特卡洛樹搜索(Monte Carlo Tree Search，MCTS)求解無人機避撞問題，該方法在實時性和避撞效果上取得了較好的效果，但其連續(xù)避撞飛行軌跡從全局來看并不是最優(yōu)的，存在飛行器原位置盤旋的問題。

面對城市空中交通這一場景中同時出現(xiàn)的靜態(tài)障礙和空中密集動態(tài)交通流，如何在保證算法實時性的前提下實現(xiàn)對動態(tài)障礙和靜態(tài)障礙雙重目標的自主避撞并優(yōu)化避撞決策路徑是本文研究的重點。本文將采用離散馬爾科夫過程對空中避撞問題進行建模，基于Yang等[27]所提出的蒙特卡洛樹搜索方法實時求解最優(yōu)避撞動作，引入A*改進算法跳點搜索(Jump Point Search，JPS)進行起止點間全局路徑規(guī)劃，自動生成合適間隔的離散路徑點以引導無人機進行更優(yōu)的避撞動作選擇，避開因搜索深度不足所導致的無人機陷入局部環(huán)境最優(yōu)情形，從而在保證算法實時性前提下，實現(xiàn)了對障礙的避撞和飛行路徑的優(yōu)化，最終達到降低沖突概率和縮短飛行時間的目的。

1 背景知識

1.1 馬爾可夫決策過程

馬爾可夫決策過程最早由Bellman提出[28]，其后被廣泛應(yīng)用在機器人、自動控制、最優(yōu)化等主題中，馬爾可夫決策過程可用一個五元組表示為

其中：S為一組有限狀態(tài)集；A為一組有限動作集；P為在時刻t對應(yīng)狀態(tài)St下采取動作a(a∈A)后轉(zhuǎn)換到t+1時刻狀態(tài)St+1的概率；R為通過執(zhí)行動作a，狀態(tài)St轉(zhuǎn)換到St+1所帶來的獎勵，在本文中獎勵值應(yīng)符合R∈[0,1][29]；γ為折扣因子，表示未來的獎勵在當前時刻的價值比例，即當前的獎勵相對于未來的獎勵能夠獲得更大的收益。

求解馬爾可夫決策過程的關(guān)鍵在于找到一個執(zhí)行策略。該策略是指從狀態(tài)S到動作A的映射，即在給定狀態(tài)下動作的概率分布，策略常用符號π表示為

π:S→A

最優(yōu)策略π*，是指該策略能使得最終期望的總獎勵值最大化，其表達式為

(1)

1.2 蒙特卡洛樹搜索

蒙特卡洛樹搜索算法是通過特定策略進行非對稱樹搜索的算法。搜索是一組沿著搜索樹的遍歷，單次遍歷是從根節(jié)點到未完全展開的節(jié)點的路徑，未完全展開的節(jié)點至少有一個子節(jié)點未被訪問。在搜索過程中，算法并不會訪問樹的每一個分支，而是用搜索樹上限置信區(qū)間(Upper Confidence bound apply to Tree，UCT)算法來尋找一個最佳的策略對樹進行搜索[30]。UCT是將上限置信區(qū)間(Upper Confidence Bound，UCB)[31]運用到MCTS的算法。對于搜索樹節(jié)點的選擇既要給期望值高的節(jié)點更大的選擇概率(Exploitation)，也要考慮探索那些暫時期望不高的分支節(jié)點(Exploration)。UCT算法通過各個節(jié)點的UCT值來決定訪問哪一個節(jié)點，可以很好地權(quán)衡這種探索和利用(Exploration and Exploitation)。UCT算法公式為

(2)

蒙特卡洛樹搜索主要由選擇(Selection)、拓展(Expansion)、模擬(Simulation)和反向傳播(Backpropagation)4個階段構(gòu)成[32]。Selection階段是在搜索樹中尋找一個最有價值的節(jié)點，通常優(yōu)先選擇未被探索的子節(jié)點，否則選擇UCT值最大的子節(jié)點。Expansion階段是在當前選中的節(jié)點上進行一個隨機動作并創(chuàng)建一個新的子節(jié)點。Simulation階段是使上一個階段中創(chuàng)造的新節(jié)點開始隨機模擬的過程，直至達到終末狀態(tài)。Backpropagation階段是從葉子節(jié)點到根節(jié)點的遍歷，并將Simulation階段的模擬結(jié)果傳送到根節(jié)點，對于反向傳播路徑上的每個節(jié)點，更新節(jié)點的回報價值、訪問次數(shù)及其他有用統(tǒng)計信息。

1.3 跳點搜索

跳點搜索是A*算法的一種改進版本，其改進之處在于修改了A*算法的搜索規(guī)則，使得搜索速度最快能提高一個數(shù)量級[33]。A*算法是一種啟發(fā)式算法[34]，擁有啟發(fā)式函數(shù)H(n)以及兩個列表：open列表和close列表，并用一個估值函數(shù)來評估節(jié)點的代價，估值函數(shù)的表達式為

F(n)=H(n)+G(n)

(3)

式中：G(n)為從搜索起始點到節(jié)點的實際代價；H(n)為搜索目標點到節(jié)點的估計代價。

A*算法首先從當前節(jié)點開始，將所有不在close列表的合法鄰近方格放入open列表中。從open列表中選取F(n)值最小的方格作為下一個節(jié)點，并把當前節(jié)點移出open列表，放入close列表中。將選中的下一個節(jié)點作為當前節(jié)點重復上述步驟，直到目標點出現(xiàn)在open列表當中。

跳點搜索同樣采用A*算法中的估值函數(shù)，但是不會逐一對鄰近方格進行搜索，而是從當前節(jié)點開始沿著水平、垂直和對角線3個方向進行搜索。當搜索到轉(zhuǎn)折點時，則把當前點移入close列表，并把轉(zhuǎn)折點加入到open列表中。選取open列表中F(n)值最小的點，若此點為目標點則結(jié)束搜索，否則作為當前點并按上述步驟重新開始搜索。

2 建模與求解

美國洛杉磯市是Uber Air公司進行城市空中交通(UAM)驗證飛行的試點城市之一。圖1為大疆無人機公司在洛杉磯城市某空域劃設(shè)的限制飛行區(qū)域，圖中紅色和灰色部分分別為禁飛區(qū)和限高區(qū)。從圖中可以看出該空域的限制飛行區(qū)域會對無人機在城市空域下運行形成帶狀或凹形的靜態(tài)障礙。

圖1 限制飛行區(qū)域

針對Yang和Wei[27]未考慮到成片的高層建筑群或限制飛行區(qū)域?qū)o人機在城市空域環(huán)境下運行的影響，本文在仿真場景中加入靜態(tài)障礙，對無人機在靜態(tài)和動態(tài)混合環(huán)境下的運行場景進行建模，并將場景之中的部分靜態(tài)障礙設(shè)計為局部凹形，使其形成局部陷阱區(qū)域以增加環(huán)境復雜性。

2.1 場景與模型描述

假設(shè)無人機在城市空域下沒有固定航路，而是按需自由飛行，城市空域高度層通常十分狹窄，因此無人機僅考慮在同一高度下進行水平機動避撞。本文將具有避撞算法的無人機稱為試驗機，沒有避撞算法的無人機稱為入侵機，用于模擬隨機交通流形成的動態(tài)障礙。每次仿真實驗，試驗機將從固定起始點出發(fā)無碰撞地抵達隨機生成的目標點位置，入侵機將以指定數(shù)量在模型中隨機位置生成并以一定的初速度做勻速直線運動，模型不考慮入侵機兩兩之間的碰撞。

圖2為仿真場景1(凹形限飛區(qū)空域)模型示意圖，其模擬了邊長為24 km含有凹形限飛區(qū)域的方形城市空域。模型縮放比例為1像素：30 m，那么該模型的大小為800像素×800像素。黃色帶有環(huán)形的飛機圖形代表具有避撞算法的試驗機；紅色飛機代表入侵機；綠色星形代表目標點；黑色圖形代表由限制飛行區(qū)域形成的靜態(tài)障礙。

圖3為仿真場景2(含有凹形區(qū)域的多個限飛區(qū)空域)和仿真場景3(不含凹形區(qū)域的多個限飛區(qū)空域)的模型示意圖，其縮放比例與圖形代表的含義與圖2保持一致。

圖2 仿真場景1模型示意圖

圖3 限飛空域場景模型示意圖

無人機之間的沖突與碰撞定義為

(4)

式中：ix、iy為入侵機位置的橫縱坐標；ox、oy為試驗機位置的橫縱坐標；Δd為試驗機與最近一架入侵機之間的距離；這里的碰撞指NMAC(Near Mid-Air Collision)[35]。

2.2 飛行器運動模型

無人機的運動學模型可表示為[27,36]

(5)

式中：ε為無人機運行過程中的不確定因素產(chǎn)生的噪聲，其大小服從正態(tài)分布；Δt為時間變化量；v為無人機速度，且v∈[50,80] m/s；av為無人機加速度；εv為速度誤差；φ為無人機傾斜角，且φ∈[-25°,25°]；εφ為傾斜角誤差；aφ為傾斜角的改變率；θ為無人機航向角；g為重力加速度；x和y分別為無人機的橫縱坐標；εx和εy分別為橫縱坐標位置誤差。

2.3 狀態(tài)集描述

模型以1 s為單位進行離散化，并定義為一個時間步長t(time step)。這意味著無人機的速度、航向角度、位置等參數(shù)將以1 s為單位進行改變，利用式(5)并令Δt=1 s即可確定下一時刻無人機的各項參數(shù)。模型假設(shè)每5個時間步長(5 s)， 無人機將會做一次避撞決策，即從動作集中選取最佳的飛行動作。由于小型無人機通常具有極高的功率重量比，因此無人機動力學相對于5 s的決策周期是快速的[37]。

因為MDP需要執(zhí)行一個動作后才進行狀態(tài)轉(zhuǎn)移，所以我們將模型中的狀態(tài)空間以避撞決策頻率，即5個時間步長為單位進行離散化，得到若干個中間狀態(tài)S1,S2,…,Sn。每次仿真開始，試驗機從初始時刻狀態(tài)S0開始立即執(zhí)行一次避撞決策并進入中間狀態(tài)，在狀態(tài)Sn的某時刻下觸發(fā)終止條件則立即從中間狀態(tài)轉(zhuǎn)移到終末狀態(tài)ST，因此完整的狀態(tài)集為{S0,S1,S2,…,Sn,ST}。對于進入終末狀態(tài)的終止條件

(6)

模型中，試驗機的狀態(tài)由坐標位置(ox,oy)、速度(ov)、航向角(oθ)4個變量表示；入侵機的狀態(tài)由坐標位置(ix,iy)、速度(iv)、航向角(iθ)4個變量表示；目標點的狀態(tài)由坐標位置(gx,gy)2個變量表示。設(shè)某時刻狀態(tài)為St，若模型中有n架入侵機，那么狀態(tài)St由(4×n+6)維狀態(tài)分量組成，即

2.4 動作集描述

在真實環(huán)境中，無人機能在性能范圍內(nèi)選取任意的加速度和傾斜角進行機動。但是從連續(xù)的動作空間中選取一個最佳的飛行動作，對于MCTS其計算復雜度將成指數(shù)上升。為了簡化計算，將模型中的動作空間離散為9維，由加速度動作子集和傾斜角動作子集組成有限動作集，動作集為

(7)

式中：Aa為加速度動作子集；Aφ為傾斜角動作子集；(av,aφ)為最優(yōu)加速度和傾斜角的一個組合動作。

試驗機每次執(zhí)行避撞決策會從動作子集Aa和Aφ中通過MCTS選取一個最優(yōu)加速度和傾斜角的組合作為當前的飛行動作。由于飛行動作有9種選擇方案，所以MCTS所構(gòu)建的樹狀結(jié)構(gòu)最多有9d個節(jié)點，d為搜索樹的深度。

2.5 獎勵函數(shù)描述

避撞過程建模為馬爾科夫決策過程后的原始獎勵函數(shù)式為

(8)

式中：R(S)為在狀態(tài)S時試驗機在不同飛行條件下獲得的獎勵值;d(g)為試驗機與目標點之間的歐式距離；max(d(g))為當前場景下，試驗機與目標點之間所能達到的最大距離。

MCTS算法需要進行大量的隨機過程模擬采樣以獲得最佳策略，所以將其應(yīng)用于無人機避撞時，考慮到對算法實時性的要求，不可能進行長時間的運算來得到全局最優(yōu)解，而只能在有限時間里得到當前狀態(tài)下的一個局部最優(yōu)解。因此，MCTS算法僅能滿足短期內(nèi)的局部沖突避撞。

原始的獎勵函數(shù)僅計算試驗機與目標點之間的歐氏距離，而為了獲得最大的累計獎勵值，MCTS算法選擇的飛行動作是使得連線長度最短，因此，其期望航跡為試驗機與目標點之間的連線。當試驗機與目標點的連線之間存在靜態(tài)障礙時，那么采取MCTS算法得到的飛行動作可能導致試驗機的實際飛行航跡非全局最優(yōu)，甚至陷入局部最優(yōu)的陷阱之中，即無法抵達目標點。

無人機在城市環(huán)境中運行難免會因為地形因素或者限制飛行區(qū)域形成的靜態(tài)障礙導致無人機無法直接到達目標點。MCTS算法能夠滿足對局部動態(tài)障礙避撞的要求，但是在城市空域下，無人機也需要同時對靜態(tài)障礙進行避撞。對于靜態(tài)障礙避撞的最優(yōu)決策不是當無人機靠近靜態(tài)障礙后再進行機動飛行避撞，而是應(yīng)該規(guī)劃一條無碰撞的最短路徑并主動對靜態(tài)障礙進行繞飛。因此，通過跳點搜索算法從全局規(guī)劃出一條繞開靜態(tài)障礙的路徑并以合適的距離等間距建立路徑點。無人機逐點飛行便可主動繞開靜態(tài)障礙，并在兩個路徑點之間的飛行過程中，同時以MCTS算法選擇飛行動作實現(xiàn)對局部動態(tài)障礙進行避撞。

考慮到目標點和路徑點同時對航跡的影響，改進了原始獎勵函數(shù)的表達式。改進后的獎勵函數(shù)加入了路徑點和試驗機之間的距離因素，并通過比例系數(shù)來權(quán)衡目標點與路徑點對試驗機飛行動作的影響，使得無人機能對靜態(tài)障礙主動進行繞飛并保持對動態(tài)障礙的有效避撞。試驗機的期望航跡不再是一條簡單的直線，而是由若干條線段組成近似曲線的線條。改進后的獎勵函數(shù)為

R(S)=

(9)

式中：d(p)為試驗機與最近路徑點之間的距離； max(d(p))為當前場景下，試驗機與路徑點之間所能達到的最大距離；a為獎勵函數(shù)的比例系數(shù)。

2.6 算法描述

為便于和原始的MCTS算法進行區(qū)分，本文將改進后的算法稱作JPS-MCTS。首先通過程序創(chuàng)建一個名為Way Point的列表來存儲路徑點位置信息，在每次仿真實驗中通過跳點搜索規(guī)劃出一條避開靜態(tài)障礙的最短路徑后，將此路徑按照合適的距離等間隔建立離散的路徑點，并將路徑點的位置信息加入Way Point列表。試驗機遍歷Way Point列表，從中選擇一個與其距離最近的路徑點，然后通過MCTS選擇一個當前狀態(tài)下所能獲得最大獎勵值的飛行動作并進入下一個狀態(tài)，算法流程如圖4所示。

圖4 算法流程示意圖

因為MCTS選擇的動作是使得獎勵值最大化，若試驗機選擇的動作能使得自身與路徑點之間的距離縮小，那么試驗機就能獲得更多的獎勵回報，其結(jié)果就是試驗機飛向路徑點。試驗機到達路徑點后，此路徑點將從Way Point列表中移除，并重新選擇一個與試驗機距離最近的一個路徑點。按照上述步驟，試驗機將以一條優(yōu)化過的航跡依次逐點飛行，并在飛行過程中同時實現(xiàn)對靜態(tài)障礙和動態(tài)障礙的避撞。

3 仿真與結(jié)果分析

圖5展示的是一次完整的仿真流程示意圖，即從每次仿真開始時刻的初始狀態(tài)S0到仿真結(jié)束時刻的終末狀態(tài)ST

圖5 仿真流程示意圖

3.1 設(shè)置實驗參數(shù)

本次實驗采用的蒙特卡洛樹搜索深度為3層， 隨機模擬采樣次數(shù)為100次。模型設(shè)置入侵機數(shù)量為60架，每個實驗項目重復仿真500次，部分仿真畫面如圖6所示，藍色實心圓點為引導試驗機飛行的路徑點。仿真中的各概率為

圖6 仿真畫面

(10)

式中：N為總仿真次數(shù)；Pn為NMAC概率；Pc為沖突概率；Pg為抵達目標點概率；Cn為NMAC的總次數(shù)；Cc為沖突的總次數(shù)；Cg為抵達目標點的總次數(shù)。

3.2 選取路徑點的間隔距離

首先將獎勵函數(shù)的比例設(shè)置為1.0，然后分別以40、60、80、100、120、140、160像素的距離等間距設(shè)置路徑點并分別進行仿真實驗，結(jié)果如表1所示。

表1 不同間隔路徑點條件下的仿真結(jié)果

對于無人機而言，安全性是最關(guān)鍵的要素，因此其性能參數(shù)首先應(yīng)保證NMAC概率最小，其次是抵達目標點概率、沖突概率以及平均飛行時間。綜合以上因素，這里選取80像素作為路徑點的間隔距離，按照縮放比例換算成真實距離則是約2.4 km。

3.3 選取獎勵函數(shù)的比例系數(shù)

首先將路徑點的間隔距離設(shè)置為80像素，然后設(shè)置獎勵函數(shù)的比例系數(shù)分別以1.0、0.9、0.8、 0.7、0.6、0.5、0.4進行仿真實驗，結(jié)果如表2所示。

按照相同的原則，這里選取a=0.8作為獎勵函數(shù)的比例系數(shù)。從表2仿真實驗數(shù)據(jù)中可以觀察到，不同的比例系數(shù)和不同間隔距離的路徑點對飛行時間影響不大，而對于NMAC概率和沖突概率的影響較大。對于不同的比例系數(shù)來說，其平均飛行時間隨比例系數(shù)減小而增加，這是因為比例系數(shù)越小，路徑點對試驗機的影響就越小，而目標點的位置對試驗機干擾越大，這從側(cè)面可以反映出原始的蒙特卡洛樹搜索算法規(guī)劃出的無碰撞航跡并不是最優(yōu)的。

表2 不同比例系數(shù)條件下的仿真結(jié)果

3.4 對比實驗

分別在仿真場景1、仿真場景2、仿真場景3中對原始的MCTS算法以及JPS-MCTS算法(間隔距離設(shè)置為80像素，比例系數(shù)a=0.8)進行仿真實驗，仿真結(jié)果分別如表3～表5所示。

表3 仿真場景1結(jié)果對比

表4 仿真場景2結(jié)果對比

表5 仿真場景3結(jié)果對比

從表3中可以看出，對于“凹形限飛區(qū)空域”，JPS-MCTS算法相對于MCTS算法，NMAC概率降低了75%、沖突概率降低了36%、抵達目標點概率提升了40%、平均飛行時間縮短了47.8%、平均路徑長度縮短了43.4%。

從表4中可以看出，對于“含有凹形區(qū)域的多個限飛區(qū)空域”，JPS-MCTS算法相對于MCTS算法，NMAC概率降低了75%、沖突概率降低了5.4%、 抵達目標點概率提升了5.4%、平均飛行時間縮短了15.9%、平均路徑長度縮短了16.7%。

從表5中可以看出，對于“不含凹形區(qū)域的多個限飛區(qū)空域”，JPS-MCTS算法相對于MCTS算法，NMAC概率降低了11%、沖突概率降低了5%、抵達目標點概率提升了0.6%、平均飛行時間縮短了6.4%、平均路徑長度縮短了3.8%。

從上述結(jié)果中可以看出，JPS-MCTS算法在場景1中的優(yōu)勢最大；JPS-MCTS算法在場景2中相對于場景3優(yōu)勢較為明顯。場景1中的靜態(tài)障礙是3個場景中對無人機阻礙范圍最大的，并且場景1和場景2中都包含有凹形區(qū)域，因此可以推論出：JPS-MCTS算法在無人機需要對靜態(tài)障礙進行大范圍繞飛的場景中性能優(yōu)勢最為明顯，對于含有凹形區(qū)域的場景其算法的穩(wěn)定性也較好。原始的MCTS算法對于較大范圍并含有凹形靜態(tài)障礙的場景，其算法性能會出現(xiàn)明顯下降。

同時，選取具有代表性的2個仿真場景：仿真場景1和仿真場景2，分別在仿真實驗中將2種算法的沖突點位置進行記錄，并繪制在地圖上，結(jié)果如圖7和圖8所示。兩圖中的綠色圓點為發(fā)生沖突時試驗機的位置，紅色圓點為發(fā)生NMAC時沖突點的位置。從沖突和碰撞的散點分布可以看出，實驗結(jié)果與預(yù)期一致。原始的MCTS求解避撞決策動作的算法容易陷入凹形區(qū)域且無法較好地實現(xiàn)對靜態(tài)障礙物避撞。經(jīng)過改進后的算法結(jié)合了全局路徑規(guī)劃和隨機搜索避撞算法的優(yōu)點，能夠同時實現(xiàn)對靜態(tài)障礙和動態(tài)障礙有效避撞，并避免無人機陷入凹形區(qū)域?qū)е聼o法抵達目標點。改進后的算法由于其獎勵函數(shù)通過權(quán)衡路徑點和目標點的影響，使得無人機飛行路線更趨近于有人駕駛航空器的飛行路線，能夠有效繞開靜態(tài)障礙并且提高無人機到達目標點的效率，同時保留了隨機搜索算法在避撞決策過程中實時性的優(yōu)點。

圖7 場景1中沖突點對比結(jié)果

圖8 場景2中沖突點對比結(jié)果

4 結(jié) 論

本文針對城市空域環(huán)境下的無人機避撞問題展開了研究，提出了一種基于跳點搜索引導的避撞決策算法。該算法本質(zhì)是將城市空間避撞問題進行解耦，針對先驗的地形環(huán)境，應(yīng)用跳點搜索預(yù)先建立最優(yōu)離散路徑點，結(jié)合這些離散路徑點引導無人機在飛行過程中采用改進的具有較強實時性的蒙特卡洛樹搜索算法解決試驗機與動態(tài)障礙和靜態(tài)障礙之間的避撞決策問題。相比于僅使用蒙特卡洛樹搜索算法，改進后的算法在復雜空域環(huán)境中體現(xiàn)了全局規(guī)劃的優(yōu)勢，能夠?qū)討B(tài)障礙避撞的同時對靜態(tài)障礙實現(xiàn)主動繞飛并獲得更優(yōu)的飛行路線。在特定場景下，改進算法能夠降低沖突碰撞發(fā)生的概率并且縮短飛行路程和飛行時間。

本實驗場景著重討論了復雜凹形靜態(tài)障礙和密集交通流動態(tài)障礙共同影響下無人機避撞決策算法的性能表現(xiàn)。下一步將考慮在真實城市空域環(huán)境下進行建模仿真，用以測試該算法的通用性和實時性，并進一步對其魯棒性進行探究。