面向城市空中交通的eVTOL 飛行器路徑規(guī)劃算法對比

李 明，陳金良,3*，劉 文，王 琳，趙健竹

（1.西華大學(xué)航空航天學(xué)院,四川 成都 610039；2."智能空地融合載具及管控"教育部工程研究中心,四川 成都 610039；3.吉利科技航空航天學(xué)院,四川 成都 641423）

城市化效應(yīng)使得城市地面交通擁堵問題日益突出。據(jù)百度地圖發(fā)布的《2022 年度中國城市交通報告》[1]顯示，全國大中城市的單次通勤耗時普遍在35～50 min?？梢姡鞘械孛娼煌ǖ膿矶聠栴}日益嚴峻。展望城市上空，電動垂直起降飛行器（eVTOL 飛行器）憑借100 km/h 以上的速度能將城市通勤時間縮短至20 min 內(nèi)，可有效避免城市的交通擁堵、尾氣污染和噪聲污染等問題。高效的路徑規(guī)劃方案則是實現(xiàn)這目的的關(guān)鍵，通過智能算法能為單架或多架飛行器生成集群化下的單機最優(yōu)飛行路徑。為此，本文主要從空域規(guī)劃和路徑規(guī)劃算法兩方面展開研究。

1 城市空中交通基本概況

1.1 基本概念

城市空中交通起源于20 世紀60 年代，少數(shù)公司用直升機在美國西海岸地區(qū)提供點對點的空中通勤服務(wù)，但由于安全性、公眾承受力和運營成本等問題，這些服務(wù)被迫減少以至終止。2017 年，美國國家航空航天局（National Aeronautics and Space Administration，NASA）提出了城市空中交通（urban air mobility，UAM）的概念，即指“在城市中用于客運或貨運的、安全高效的有人駕駛/無人駕駛（空中）交通工具系統(tǒng)”[2]。目前，UAM 行業(yè)是以電動垂直起降飛行器（eVTOL 飛行器）為最理想化載具。eVTOL 飛行器目前正逐步進入了驗證試飛和適航取證階段，其集成了分布式電力推進、垂直起降和自動駕駛等技術(shù)，能在城市低空空域提供安靜、快捷的載人和物流服務(wù)。

1.2 UAM 的發(fā)展前景

由于地面交通的局限性，相關(guān)行業(yè)與政府機構(gòu)對城市空中交通的發(fā)展前景做了具體調(diào)研和分析。在公眾層面，2021 年5 月，歐洲航空安全局（EASA）在歐盟進行的關(guān)于城市空中交通的一項調(diào)查結(jié)果[3]顯示：83%的受訪者對UAM 持積極態(tài)度，71%的受訪者準備試用UAM 服務(wù)；在緊急情況或醫(yī)療運輸?shù)阮I(lǐng)域，UAM 得到了受訪者的有力支持。在運行成本層面，表1 的億航發(fā)布的一份交通載具成本對比表[4]，可以看到eVTOL 飛行器在購置成本、道路建設(shè)和運營等方面相比傳統(tǒng)交通載具都有明顯的經(jīng)濟優(yōu)勢。在產(chǎn)業(yè)前景方面，據(jù)摩根士丹利預(yù)計，到2025 年，全球?qū)⒂? 000 架飛行汽車投入使用，隨后在2050 年將呈指數(shù)式增長至10 萬架左右，屆時全球空中交通產(chǎn)業(yè)將達到1.5 萬億美元的規(guī)模[5]。

表1 交通載具成本對比Tab.1 Comparison of transport carrier costs

2 空域規(guī)劃

2.1 相關(guān)空域規(guī)劃理念

城市低空空域具有高密度、高流量和復(fù)雜多變等特點。對于未來綜合性的城市低空空域主要有2 種規(guī)劃方向：一是空域結(jié)構(gòu)化，結(jié)構(gòu)化空域是容納高密度空域最有效的途徑，Andrews 等[6]認為結(jié)構(gòu)化空域可以有效降低空域的復(fù)雜性和空域管理難度，并且還能促進態(tài)勢感知，簡化警報邊界和通過集中式交通中心進行沖突檢測；二是空域自由化，Hoekstra 等[7]認為自由飛行優(yōu)于空域結(jié)構(gòu)化，其航線呈現(xiàn)分布式特點，能有效降低沖突概率，用戶可自由選擇合適航線，每架飛行器均有獨立的分離保障機制，從而減輕了空域的流量限制和結(jié)構(gòu)限制，以應(yīng)對更高的交通密度。另外，Sunil 等[8]比較了全混合(自由飛行)、層、區(qū)和管4 種不同空域結(jié)構(gòu)對高密度空域容量、安全性和效率的影響，其仿真結(jié)果表明，分層式空域規(guī)劃在兼顧容量、安全性和效率方面是最優(yōu)的。

結(jié)合上述空域規(guī)劃方法，本文以AirMatrix 的綜合路由網(wǎng)絡(luò)[9]為基礎(chǔ)，輔以飛行高度層，形成了分層式網(wǎng)格化的城市低空空域規(guī)劃方案。在AirMatrix 的概念中，城市空間被離散成塊，通過防止區(qū)塊使用中的沖突，形成了一個可管理的整體空域框架，為動態(tài)空域的使用提供解決方案。當然，AirMatrix 空域的應(yīng)用還可以擴展到有人駕駛和無人駕駛的空中交通，以一種協(xié)調(diào)的方式管理整個城市空域。

2.2 AirMatrix 空域規(guī)劃方法

AirMatrix 空域規(guī)劃方法是將城市空域分割成固定大小的三維區(qū)塊，通過加入時間函數(shù)為每一區(qū)塊形成唯一的四維坐標函數(shù)，通過一個城市空域的集中式服務(wù)系統(tǒng)對空域使用情況進行精確記錄和管理，如圖1 所示。在AirMatrix 空域中，飛行器要實時且精準地將飛行數(shù)據(jù)傳輸?shù)椒?wù)器，而且為了清楚顯示每一區(qū)塊狀態(tài)，將每一區(qū)塊的狀態(tài)可視化為如圖1 所示的綠色（未占用狀態(tài)）、黃色（已計劃占用狀態(tài)）和紅色塊（占用狀態(tài)），服務(wù)器及其操作人員通過比較實際區(qū)塊利用率和計劃區(qū)塊利用率來識別每一區(qū)塊的正常和異常狀態(tài)[10]，從而保障其監(jiān)控整個城市空域的運行狀態(tài)，并為實時的運行規(guī)劃、避障和應(yīng)急管理的UAM 導(dǎo)航服務(wù)供應(yīng)商提供態(tài)勢感知。

圖1 基于AirMatrix 概念的四維空域示意圖Fig.1 Four-dimensional airspace management based on the AirMatrix concept

在 AirMatrix 空域中，將城市低空空域建模為區(qū)塊狀的三維數(shù)組，為

式中：Al,w,h是三維區(qū)塊的物理三維坐標，l、w、h分別是該小塊在AirMatrix 空域中X、Y、Z三軸上的方位坐標；Ni由建?？沼虻拇笮『兔總€塊的大小計算。對于小塊的占用狀態(tài)則用四維數(shù)組表示為{Occupl,w,h,t,t∈{0,1}}，即表示為在t時刻Al,w,h的占用狀態(tài)：若t為0 則沒有占用；若t為1 則表示該小塊處于占用狀態(tài)；與靜態(tài)障礙物和特殊空域重疊的區(qū)塊則被永久識別為占用狀態(tài)。

3 eVTOL 飛行器路徑規(guī)劃算法

當前關(guān)于路徑規(guī)劃有多種算法，包括：基于概率論的算法，如快速探索隨機樹(rapidly exploring random trees，RRT)算法和概率路線圖(PRM)算法；基于圖的優(yōu)化算法，如Dijkstra 算法和A-star(A*)算法；基于種群的仿生類算法，例如遺傳算法和粒子群算法等。由于城市低空空域的環(huán)境復(fù)雜多變，同時根據(jù)NASA 預(yù)測的城市空中交通行業(yè)發(fā)展階段模型，未來城市低空空域的密度將日益增加。為了實現(xiàn)eVTOL 飛行器在AirMatrix 空域環(huán)境下的路徑規(guī)劃，本文根據(jù)前人的研究成果[10-13]和AirMatrix 空域環(huán)境，從算法細分角度分別選擇RRT 算法、改進A*算法和PSO 算法進行分析，以便為eVTOL 飛行器找到更優(yōu)的路徑規(guī)劃算法。

3.1 快速搜索隨機樹（RRT）算法

快速搜索隨機樹(rapidly-exploring random trees，RRT)算法是一種基于對目標點進行概率性采樣的遞增式路徑規(guī)劃方法。在搜索過程中，算法不斷在可行域空間中隨機生成狀態(tài)點，如果該點位于無碰撞位置，則尋找搜索樹中離該節(jié)點最近的節(jié)點，即為中轉(zhuǎn)點，由中轉(zhuǎn)點出發(fā)以一定步長向該隨機節(jié)點進行搜索，該步長搜索的最遠點所在的位置被當作有效節(jié)點加入搜索樹中。搜索樹的生長過程一直持續(xù)到目標點與搜索樹的距離在一定范圍內(nèi)時終止。隨后搜索算法在搜索樹中反向回溯尋找一條連接目標點到起點的最短路徑。

相較A*算法和PSO 算法，RRT 算法通過對狀態(tài)空間中的采樣點進行碰撞檢測，由于無須對空間進行復(fù)雜的建模，因此節(jié)省了算法的運行時間，并且通過狀態(tài)空間的隨機采樣點，把搜索導(dǎo)向空白區(qū)域，減少了大量無效搜索區(qū)域，并最終尋找到一條從起始點到目標點的規(guī)劃路徑[12]。RRT 算法憑借上述優(yōu)勢能夠有效地解決高維空間和復(fù)雜約束的路徑規(guī)劃問題。但RRT 算法正因為無須對空間建模，當?shù)竭_NASA 預(yù)測的UAM 成熟階段，該算法的適用性將變得愈發(fā)受限[11]。圖2 是RRT 算法偽代碼，其主要是在給定起始點、目標點和搜索概率的基礎(chǔ)上，由起始點向目標點方向通過搜索概率和一定步長向前探查找到幾個中間點，再將中間點與目標點間的距離做對比，篩選出最優(yōu)節(jié)點作為下一個探查節(jié)點，以此方式直至探查到目標點，最終從目標點反向回溯至起始點找到最優(yōu)路徑。

圖2 RRT 算法偽代碼Fig.2 RRT algorithm pseudo-code

3.2 A＊算法

3.2.1 A*算法

A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，它在Dijkstra 算法的基礎(chǔ)上引入了啟發(fā)式搜索[14]。圖3 為A*算法偽代碼。其核心為：使用優(yōu)先隊列，每次從O penList中選擇F(ni)最小的節(jié)點將其加入 CloseList中，同時擴展相鄰節(jié)點，可把 OpenList 看成一個優(yōu)先隊列，key值為f(ni)，優(yōu)先級最高的先出。其公式表示為

圖3 A*算法偽代碼Fig.3 A* algorithm pseudo-code

式中：f(ni)是從初始節(jié)點經(jīng)由中間節(jié)點n到目標節(jié)點的最小代價估計；g(ni)是在狀態(tài)空間中從初始節(jié)點到中間節(jié)點n的實際最小代價；h(ni)是中間節(jié)點n到節(jié)點的最小估計代價。當h(n)≡0 時，由g(n)決定中間節(jié)點n的優(yōu)先級，此時算法也就退化為Dijkstra 算法；當h(n)＞＞g(n)時，由h(n)決定中間節(jié)點n的優(yōu)先級，則算法就退化為最佳優(yōu)先搜索。h(n)是A*算法的啟發(fā)式函數(shù)，也是算法的核心和改進部分[15]。啟發(fā)式函數(shù)的設(shè)計影響A*算法的性能：如果啟發(fā)式值大于實際代價值，算法搜索速度會更快，但不能保證最優(yōu)性；如果啟發(fā)式值小于實際代價，則可以達到最優(yōu)，但會延長算法的搜索時間；最佳啟發(fā)式函數(shù)應(yīng)接近但不大于實際成本。與Dijkstra 算法相比，A*算法能有效減少算法的搜索步驟，使A*算法速度更快。與RRT 算法相比，通過空域建模，改進A*算法能夠?qū)崿F(xiàn)高密度空域場景下的飛行器路徑規(guī)劃[10]。

3.2.2 改進的A*算法

傳統(tǒng)A*算法適用于二維平面的搜索環(huán)境，通過曼哈頓距離來實現(xiàn)節(jié)點到目標點之間的成本（距離）估計。但eVTOL 飛行器的路徑規(guī)劃環(huán)境則是在三維動態(tài)空間中，在最短飛行時間軌跡規(guī)劃中，最小的代價是飛行時間，但eVTOL 飛行器在垂直速度和水平速度有顯著差異，這導(dǎo)致在垂直和水平方向上相同的距離會導(dǎo)致不同的時間成本，曼哈頓距離或歐幾里得距離也將變得不再適用[16]。因此，需要基于三維路徑規(guī)劃場景下改進啟發(fā)式函數(shù)。圖4 是三維鄰域下雙向A*算法（改進的A*算法）流程圖。具體改進策略如下。

圖4 三維鄰域下雙向A*算法流程圖Fig.4 Flow chart of bidirectional A* algorithm in threedimensional neighborhood

1）結(jié)合AirMartix 空域理念，將每一個三維區(qū)塊的幾何中心點作為算法規(guī)劃節(jié)點，且運用歐氏（歐幾里得）距離作為節(jié)點到目標點的成本估計，計算公式為

2）將二維場景的8 個搜索鄰域擴展至三維場景的26 個搜索鄰域，以保證啟發(fā)函數(shù)有最大的遍歷范圍，提高搜索效率并形成更平滑的規(guī)劃路徑。

3）設(shè)置新的啟發(fā)函數(shù)，改進為加權(quán)A*算法[17]，新的A*算法計算公式為

式中w(ni)是h(ni)的權(quán)重系數(shù)，w(ni)≥1，權(quán)重系數(shù)w(ni)改進為動態(tài)加權(quán)法，提高三維場景下路徑規(guī)劃效率。

4）采用雙向A*算法[18]，在保證算法路徑規(guī)劃質(zhì)量的同時提高算法的搜索速率。

3.3 粒子群算法

粒子群算法是模擬鳥類聚集飛行行為的一種仿生類算法。算法中每個粒子個體可感知一定范圍內(nèi)其他粒子個體的飛行信息，并結(jié)合當前自身的飛行狀態(tài)，做出下一步的飛行決策。該算法共有3 條規(guī)則：1）避免與相鄰個體碰撞；2）相鄰個體速度一致；3）向中心聚集。在三維路徑規(guī)劃中，將飛行器的三維坐標看作一個粒子，將可飛空域作為粒子的可行域，城市建筑和其他障礙物作為約束條件，將三維規(guī)劃路徑的長度、平均曲率等視為適應(yīng)度函數(shù)[19]。因此可以將飛行器的三維路徑規(guī)劃過程看成是眾多粒子在解空間尋找最優(yōu)位置的過程[20]。具體算法流程如下：1）將數(shù)據(jù)初始化，以隨機的方式求出每個粒子的初始位置與速度；2）根據(jù)每個粒子的3 個散點，擬合得到三維路徑；3）依次計算每一個粒子所得到的三維路徑的路徑長度，作為粒子的適應(yīng)度值；4）選取這一代適應(yīng)度最高（即路徑長度最低）的最優(yōu)粒子；5）更新粒子群，根據(jù)上一代的位置、上一代更新的速度，得到這一代的位置，粒子速度和位置的更新表達式為

式中：w是慣性權(quán)重，表示對當前速度方向的信任程度；c1、c2是加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長；r1、r2是2 個 [0，1]的隨機值，以增加搜索隨機性。粒子群算法主要通過將飛行器的三維坐標粒子散點化，憑借自身粒子本身的過去最優(yōu)位置和臨近粒子過去最優(yōu)位置來擬合最優(yōu)的三維飛行路徑，其連續(xù)性較強，但不適合于離散化問題的路徑規(guī)劃，容易陷入局部最優(yōu)性，因此要合理分配慣性權(quán)重w的取值。w較小，算法的局部搜索能力較強；w較大，算法的全局搜索能力較強[21]。因此要在算法迭代前期賦予w較大值，以盡可能幫助飛行器探測更多較優(yōu)飛行區(qū)域，但在算法迭代后期要賦予w較小值，以期提升算法在極值點的搜索精度，使算法以較大概率向全局最優(yōu)規(guī)劃路徑收斂，最終找到全局最優(yōu)路徑[22]。

然而，以粒子群算法為代表的這些基于種群的方法存在一些先天缺陷，例如，算法的收斂速率較慢或難以保證，具有不確定性，極易陷入局部最優(yōu)解[23]，從而導(dǎo)致在此基礎(chǔ)上進行改進的算法也較難以擺脫這些缺點，使其在UAM 應(yīng)用的難度較大且成本較高。

4 算法仿真驗證及對比

本文在MATLAB(R2022a)平臺下，所用計算機操作系統(tǒng)為Windows11，配置64 位CPU，3.2 GHz運算頻率，16 GB 運行內(nèi)存，對RRT 算法、改進的A*算法和PSO 算法進行仿真分析。

RRT 算法的仿真結(jié)果如圖5 所示。地圖大小為1 000×1 000×100，設(shè)置起點坐標為（40,129,5），終點坐標為（951,833,10）。在本次仿真飛行中，共進行3 次路徑規(guī)劃，平均解算時間為1.301 706 s，平均最短規(guī)劃路徑為1 431.011 1。

圖5 三維地形圖中的RRT 算法路徑規(guī)劃Fig.5 RRT algorithm path planning in 3D topographic maps

改進的A*算法的仿真結(jié)果如圖6 所示。地圖大小、起點坐標、終點坐標均與RRT 算法仿真條件一樣。在本次仿真飛行中，同樣進行3 次路徑規(guī)劃，平均解算時間為7.955 766 67 s，平均最短規(guī)劃路徑為1 151.330 5 。

圖6 三維地形圖中的改進的A-Star 算法路徑規(guī)劃Fig.6 A-star algorithm path planning in 3D topographic maps

PSO 算法的仿真結(jié)果如圖7 所示。地圖大小、起點坐標、終點坐標均與RRT 算法仿真條件一樣，設(shè)置了N=10、N=30、N=50 的迭代次數(shù)，其中N=50 的迭代次數(shù)（歷時25.093 678）使算法得到的最短路徑長度為1 512.97。

圖7 三維地形圖中的PSO 算法路徑規(guī)劃Fig.7 PSO algorithm path planning in 3D topographic maps

由以上仿真結(jié)果可知，本文基于RRT 算法、改進的A*算法和PSO 算法在同一三維地形圖中均能實現(xiàn)較好的路徑規(guī)劃效果。算法具體規(guī)劃效率如表2 所示 。改進的A*算法的規(guī)劃路徑最短，RRT算法的平均耗時最少。綜合可得出，改進的A*算法的路徑規(guī)劃效果最好且耗時適中。

表2 算法綜合對比Tab.2 Algorithm synthesis comparison

5 總結(jié)

本文以分層式四維AirMatrix 空域規(guī)劃方案作為未來城市低空空域的規(guī)劃方法，再結(jié)合這一空域規(guī)劃方案對RRT 算法、改進的A*算法和PSO 算法做了綜合對比分析，發(fā)現(xiàn)改進的A*算法在低密度城市低空空域環(huán)境下為eVTOL 飛行器進行路徑規(guī)劃的綜合效率好，RRT 算法和PSO 算法則各有所欠缺。未來，本文將考慮在高密度的AirMatrix空域環(huán)境中驗證改進的A*算法的路徑規(guī)劃效率。