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

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

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

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

1 城市空中交通基本概況

1.1 基本概念

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

1.2 UAM 的發展前景

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

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

2 空域規劃

2.1 相關空域規劃理念

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

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

2.2 AirMatrix 空域規劃方法

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

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

在 AirMatrix 空域中，將城市低空空域建模為區塊狀的三維數組，為

式中：Al,w,h是三維區塊的物理三維坐標，l、w、h分別是該小塊在AirMatrix 空域中X、Y、Z三軸上的方位坐標；Ni由建模空域的大小和每個塊的大小計算。對于小塊的占用狀態則用四維數組表示為{Occupl,w,h,t,t∈{0,1}}，即表示為在t時刻Al,w,h的占用狀態：若t為0 則沒有占用；若t為1 則表示該小塊處于占用狀態；與靜態障礙物和特殊空域重疊的區塊則被永久識別為占用狀態。

3 eVTOL 飛行器路徑規劃算法

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

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

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

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

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

3.2 A＊算法

3.2.1 A*算法

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

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

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

3.2.2 改進的A*算法

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

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

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

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

3）設置新的啟發函數，改進為加權A*算法[17]，新的A*算法計算公式為

式中w(ni)是h(ni)的權重系數，w(ni)≥1，權重系數w(ni)改進為動態加權法，提高三維場景下路徑規劃效率。

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

3.3 粒子群算法

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

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

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

4 算法仿真驗證及對比

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

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

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

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

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

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

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

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

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

5 總結

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