結(jié)合跳點(diǎn)引導(dǎo)的無人機(jī)隨機(jī)搜索避撞決策方法

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

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

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

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

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

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

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

1 背景知識

1.1 馬爾可夫決策過程

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

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

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

π:S→A

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

(1)

1.2 蒙特卡洛樹搜索

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

(2)

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

1.3 跳點(diǎn)搜索

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

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

(3)

式中：G(n)為從搜索起始點(diǎn)到節(jié)點(diǎn)的實(shí)際代價(jià)；H(n)為搜索目標(biāo)點(diǎn)到節(jié)點(diǎn)的估計(jì)代價(jià)。

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

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

2 建模與求解

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

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

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

2.1 場景與模型描述

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

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

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

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

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

無人機(jī)之間的沖突與碰撞定義為

(4)

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

2.2 飛行器運(yùn)動模型

無人機(jī)的運(yùn)動學(xué)模型可表示為[27,36]

(5)

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

2.3 狀態(tài)集描述

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

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

(6)

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

2.4 動作集描述

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

(7)

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

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

2.5 獎(jiǎng)勵(lì)函數(shù)描述

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

(8)

式中：R(S)為在狀態(tài)S時(shí)試驗(yàn)機(jī)在不同飛行條件下獲得的獎(jiǎng)勵(lì)值;d(g)為試驗(yàn)機(jī)與目標(biāo)點(diǎn)之間的歐式距離；max(d(g))為當(dāng)前場景下，試驗(yàn)機(jī)與目標(biāo)點(diǎn)之間所能達(dá)到的最大距離。

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

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

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

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

R(S)=

(9)

式中：d(p)為試驗(yàn)機(jī)與最近路徑點(diǎn)之間的距離； max(d(p))為當(dāng)前場景下，試驗(yàn)機(jī)與路徑點(diǎn)之間所能達(dá)到的最大距離；a為獎(jiǎng)勵(lì)函數(shù)的比例系數(shù)。

2.6 算法描述

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

圖4 算法流程示意圖

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

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

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

圖5 仿真流程示意圖

3.1 設(shè)置實(shí)驗(yàn)參數(shù)

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

圖6 仿真畫面

(10)

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

3.2 選取路徑點(diǎn)的間隔距離

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

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

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

3.3 選取獎(jiǎng)勵(lì)函數(shù)的比例系數(shù)

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

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

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

3.4 對比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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