電子發燒友App
2020年10月20日，Top Talk邀請到了北京航空航天大學全權老師，請他帶來題為《基于時空大數據的空中高速公路：一種城市空中移動性管理分布式控制框架》的分享。本文系全權老師分享的文字實錄，希望能對大家有所幫助或者啟發。
全權｜北京航空航天大學
全權，北京航空航天大學副教授，多倫多大學客座教授。長期從可靠飛行控制。作為第一作者，完成英文著作三部，發表文章近百篇。獲第二屆全國高校自動化專業青年教師實驗設備設計“創客大賽”金獎（排名第一）。
無人機交通以及最近興起的空中移動性管理得到了廣泛的關注。為此，波音、空客、霍尼韋爾和貝爾等傳統航空巨頭以及Uber等新興世界級影響力的企業紛紛加入。本報告提出了空中高速公路方案以及仿真測試。該方案基于時空大數據，考慮了交通網絡、航線規劃和分布式控制設計。在空中高速公路上，每架無人機都有自己的規劃的航線，可以自主地自由飛行，從而支持密集立體的飛行交通。
1. 背景
今天我給大家帶來我們實驗室（北航可靠飛行控制研究組）做的一些工作，主要內容是講一種城市空中移動性管理分布式控制框架。
相信美團的同學一定也很非常期待實現無人機配送的一天早日到來。未來無人機配送服務將會極大地改變我們目前的生活方式。盡管在人群密集的區域，我們仍然需要靠人來完成配送服務，但是在人口比較稀疏，比如郊區等地帶，使用無人機配送會更好。報告表明，網聯無人機將為產業帶來7~10倍的產業機會，這也是我們在大概三年前就開始著手做這方面相關的工作的原因。
無人機的交通網和交通管理，是否可以利用現有的交通方式呢？我們通過研究發現，像傳統的民航網其實是不適合的，民航的飛行器其實非常稀疏，在三維空間，整個網絡的變化頻率是比較低的，有入網申請時，基本上是通過集中式的規劃。而公路網絡盡管很密集，但是二維空間，因此交通網絡管理也是偏自主的。鐵路同樣也是二維的。網絡動態變化是說就像我們上互聯網一樣，我們需要接入網絡，而公路不可能馬上為我們修一條公路出來。無人機交通與公路、鐵路具有共同點，不同的是無人機處于三維空間， 網絡動態變化比較高。因此我們在設計無人機飛行控制框架時，希望設計一種能夠適應包括無人機的增加、網絡的擴展等變化的框架。關于路徑規劃，其實可以采用集中式加自主的方式來進行。關于這部分的內容我們今年發表了一篇綜述文章《低空無人機交通管理概覽與建議綜述》，感興趣的同學可以參閱。
我們希望能夠為低空持續增長無人機及應用提供一個低空的智能大腦。對于技術研究來說話，低空高空的區別沒有那么大，但目前我們主要是考慮低空多一些。比如說開放120米以下的低空，它的特點在于這些地方會有非常多的建筑，如果無人機掉下來的話，會對下方區域的人身及財產安全造成一些危害，這是對我們城市交通的一個非常大的挑戰。因此我們主要考慮以下三個需求：
規劃無人機的航線、起飛時間，確保無人機在避免沖突的前提下起飛：無人機航線起飛時間跟我們目前坐飛機的感覺是一樣的，有時候飛機會停在某個地方延遲起飛，目的是為了不與其他飛機在航路上發生碰撞及沖突，當然有時候也會因為天氣等原因，需要飛機延遲起飛，因為飛機在地面等待，代價是最小的。
在避免碰撞的前提下順利完成飛行任務
應對天氣、禁飛區等不確定因素的影響：無人機臨時在飛行過程中，我們有時需要切斷某些航線，這種情況下，我們希望飛行器仍然能夠能夠飛到目的地，至少它能安全的回到附近的機場。
2. 空中高速公路基礎：網絡和時空大數據
開展空中高速公路研究，我們需要有網絡和時空大數據的一些研究基礎。
首先我們需要有通信、導航、監視功能等基礎設施，這些功能充當著整個無人機交通管理系統的眼睛、耳朵和神經系統，負責態勢感知和信息傳輸。其中，通訊就是4G/5G、衛星通訊等，這是我們的網絡。導航是我們飛行器需要導航，比如說通過基站定位、雷達、衛星、慣導以及視覺的導航。而監視跟導航的區別在于導航是給飛行器用的，監視是我們作為官方需要了解飛行器在空中的動態。有些飛行器可能會自己導航，通過導航或者通信告訴地下的地面站，這樣的話我們可以監視。但有些飛行器是航模，沒有通訊的功能，只能被動的被看到，那么我們可以通過一些可見光、聲波等來監視，還有飛行器可能通過一些ADS-B等來廣播自己的信息。因此通過以上這些功能，可以實現我們對飛行器飛行周邊環境的了解，地面對空中環境的了解，這是我們做空中高速公路研究的一個基礎。
另一方面，我們需要時空大數據的支撐。首先我們需要了解所有禁飛區，禁飛區也會動態的變化。其次我們需要了解氣象大數據，以便我們規劃飛行器避開極端天氣。同時我們也需要獲取地理大數據的信息，比如通過地理大數據我們可以了解什么位置有障礙物，哪些區域下方是草地等，根據這些信息可以進一步的提取一些信息，來規劃飛行器的航路、航路網等以及規劃飛行器的航線。另外我們還可以通過移動互聯網知道哪些地方人口密集，這樣在規劃航路網或者航線的時候，就能避開這些人口密集的地方。以上這些都是我們研究需要的時空大數據基礎。
前面提到，網絡是我們研究空中高速公路的基礎，目前在空中交通，主要是通過網絡來分享信息。但是網絡會有網絡質量，那么網絡質量與飛行安全是什么樣的關系呢？網絡質量通常由三個因素決定：噪聲，延遲，丟包（Packet loss）。由于網絡質量原因，無人機獲取到的障礙物位置，和障礙物實際的位置可能就不一樣了。以下圖為例，無人機估計自身的位置產生了偏差，隨之估計障礙物位置也發生了偏差。因此我們需要設計一個飛行的安全距離，以應對網絡質量造成的這種不確定性。這跟我們在高速公路上開車需要保持車間距是一個道理，我們車間距這個概念用到無人機的空中交通，希望以此來應對這些丟包延遲。當然也有人通過一些控制的方法來解決這些問題，我們這種方法應該更適合交通的場景。
傳統的空中交通的距離沒有這么復雜，飛機之間的距離間隔非常遠，那么無人機之間的距離應該怎么來控制呢？通過研究，我們認為無人機的安全半徑應該滿足上圖中的關系，rm是飛行器本身的半徑，ro是障礙物本身的半徑，rv是跟飛行器速度以及機動性相關的，re表示網絡的影響。網絡影響怎么來理解？延遲丟包率是Θ，如果丟包率為1的話，那就表示飛機完全失聯了。從保守角度來說，飛行器可能在任何位置。所以Θ越接近于1，安全半徑越大，τd表示延遲，網絡傳遞會有延遲。有些同學可能認為像我們現在打電話的延遲已經非常小了，但是在空中，我們通過實驗證實網絡存在一定的延遲，另一方面丟包率會隨著距離的增加而增加。因此，我們需要對網絡影響進行評估，根據評估結果設計飛行器安全半徑。在安全半徑下，可以認為飛行器沒有網絡噪聲，是完全精確的，只要保證兩個飛行器的安全半徑不相交，那么飛機器肯定不會相撞，這就是我們安全半徑的設計。
另一方面，我們需要通過一些數據做風險評估，如下圖所示，至少有兩個因素：事故概率評估（fGIA）和事故傷亡評估。事故概率評估就是說飛行器不連續飛行就墜落的可能性，可以通過統計方法預估。無人機相比于飛機的一個好處是，即使墜落也未必會砸傷人。飛行器墜落有一個暴露模型，比如說掉落到樹上或者房頂上對人的影響就會比較小。因此我們需要有地理信息支撐，一旦飛行器需要迫降，我們可以通過地理信息找到比如草坪等適合迫降的地帶。同時暴露模型也與人口密度相關。而傷害模型與飛行器設計相關，與飛行器下落的動量相關。以上這些因素共同得到風險評估，可以用來進行航路網規劃、路徑規劃、緊急迫降等。制定相關標準，相關法律法規的部門會比較關心飛行器的風險評估，一些風險評估公司也會基于風險評估結果去舉證飛行器的風險究竟有多大。
? ? ? ?
3. 空中高速公路
空中高速公路分為模型建立，算法設計，實驗驗證三部分為大家介紹。其中，模型建立分為兩種：航路網模型和無人機模型，我們管理無人機需要對無人機進行建模，而地面也需要給無人機發送指令，這相當于一個標準的模型；算法方面可以分為集中式空中交通控制和分布式空中交通控制，集中式可以認為所有的指令都是由地面站給飛行器發的，飛行器之間互不通信，通信完全通過地面來協調，而分布式相對來說更加靈活一些。最后是我們的仿真和實驗。
?? ? ?
3.1 模型建立
3.1.1 航路網模型
航路網模型可以認為是節點和邊構成的一個網絡。我們的設計目標是不同航路的無人機相互不干擾，保持安全距離。如果飛行器在不同航道上面，比如說一條公路上面有兩個方向，但不同航道上面的飛行器，需要保持相應的安全距離，類似兩條路，它們之間的夾角非常小，要往一個節點過去，如果夾角小到一定程度的話，那么不同航道上的兩個飛行器之間的距離就很近了，就可能會有危險。在實際過程中，我們無法得知無人機的具體位置，只能知道一個大概的不是特別精準的位置，因此就需要無人機之間保持安全距離。
?? ? ?
航路網建網需要對空域有了解，剛剛前面我們提到的地理信息，人口信息。如下圖所示，可以認為黑色區域為禁飛區，它有兩種，一種是比較稀疏的，一種是比較密集的。無論哪一種，都可以通過節點把它們連接在一起，這些節點可能是飛行器的起降點，還有一些節點可能是航路的交叉點，就像公路的交叉路口一樣。
航路網建網有兩個優化目標，一是希望航路網的總長度越短越好，因為建設航路網，這也相當于一個基建工程，需要保證航路網上面的通信、導航、監視，這些都需要成本；二是希望航路網的風險最低，考慮到比如人口密度等因素，我們希望畫出下圖所示的航路網，但是這是一個多目標的優化問題。
?? ? ?
我們在航路網建模上做了一些工作，用了下圖的幾種方法。
首先是形態學骨架法，這個跟圖像處理的骨架類似，給定一張圖片需要生成它的骨架。原理很簡單，黑色是危險的邊界，生成的骨架就是這些航路，航路和兩邊的距離要盡可能的遠。
其次是三角剖分法，連接3個點的最短路徑不是把三個邊連成一個三角形，可能是通過費馬點把它們連在一起。
最后是綜合法，形態學骨架法適合密集的地圖，而三角法更適合稀疏的地圖，綜合法兼顧密集與稀疏兩種情況，通過半自動的方式建成航路網。
?? ? ?
形態學骨架法的實現過程如下圖所示，首先是骨架提取，有些同學可能會問為什么骨架提取之后會產生這些變量，這是是因為我們要保證提取出來的骨架距離兩邊黑色危險區的距離要大于一定的閾值，如果不滿足的話，就要斷開去除，之后再進行直線擬合。當然還要在里面加入一些目標點，與整個網絡連接在一起。最后需要提取圖的結構，把節點和邊的關系按照圖論的建模方式提取出來。
?? ? ?
三角剖分法就是通過費馬點把這些節點連接在一起，有些邊會穿過障礙物，我們再通過優化方法避開，最后形成一個網絡。另外，我們可以將人口密度等因素等效為黑色禁飛區添加到地圖中。通常在地圖中，“1”表示有障礙物，“0”表示沒有障礙物。我們在航路網建模中做了一個進一步的工作，用0～1之間的概率來表示，有些禁飛區比如墻等是絕對不能飛進去的，但是有些區域人口稀疏一些，就不適合用“1”來表示，這種情況下可以使用0.4、0.5這樣的概率來表示。我們希望能夠通過這種方式來構建航路網，這在下圖中沒有體現。
?? ? ?
綜合法就是在下圖這種情況下，我們在障礙物密集區內部使用形態學骨架法來做，在外部稀疏區使用費馬點來做，最后把它們聯立成網絡。有時候我自己的學生會問我，什么叫密集的，什么叫稀疏的？我覺得不要考慮這個問題，自己來判斷，因為航路網建模不是一定要完全自動化的過程，而且一旦建成之后以后就不需要改變了，所以在建模的過程中需要人為的去確定每個區域的航路網是什么形狀。這樣就能很好的兼顧上述兩種方法，最終形成不同的航路網。
下圖是航道的抽象結構示意圖，航道內部我們參考了目前的高速公路，中間有一個隔離帶，這個隔離帶就是我們前面提到的兩架飛行器之間的安全距離，它可以是雙向的。
另一方面，航路網的節點也有結構，如下圖所示，我們一般是以圓柱形結構。節點有多個航道相接，需要考慮不同航道的飛行器不能間隔太近，因此需要增加節點的半徑，確保不同航道的飛行器間隔足夠遠。
?? ? ?
航路網有抽象的結構，內部也有具體的結構，通過一些約束條件，確保不同飛行器在任何情況下都能大于安全距離，這就讓我們知道怎樣去設計整個航路網。
3.1.2 無人機模型
我們需要對無人機發出指令，這就需要有一定的標準的接口，接口我們有一些模態比如斷電模態、等待授權模態、預位模態、飛行模態、避障模態、迫降模態給無人機發指令，這樣的話，無人機就相當于被我們的交通控制系統控制了。這個接口我們目前還不是那么標準，我希望最終我們能有一套空中交通系統的標準。
3.2 算法設計
低空交通控制算法包括集中式空中交通控制和分布式空中交通控制。
3.2.1 集中式空中交通控制
集中式控制可以分為兩個部分：離線規劃和在線控制。離線規劃就是說飛機起飛前需要申報自己的飛行計劃，然后接受審核。如果當前的航路網非常堵塞的話，那么審核就不會通過，就需要等待或者重新申報飛行計劃。如果審核通過的話，就會產生一個包含起飛時間、地點等信息的待飛計劃，將待飛計劃寫入空中交通管理系統的數據庫中，進而對空中交通情況進行預測。
但是飛行器在飛行過程中受天氣、本身狀態等因素影響會有很多不確定性，飛行器的飛行速度變化就會產生沖突。因此在飛行器飛行過程中，我們需要對飛機進行一些定量的控制，這就是飛行器的在線控制。我們可以通過控制飛行器的高度、速度等，使它能夠避免沖突，如果在整個航路網中沖突無法避免，那么我們肯定不希望發生多米勒骨牌一樣的效應，因為局部一個因素，使整個航路網都發生變化。避免沖突最簡單的方法就是避障，一個飛行器向上飛，一個飛行器向下飛，這是空中交通的優勢，汽車沒有辦法做到，大概是這樣一個邏輯。
?? ? ?
以下是基于集中式的低空交通控制系統中幾個關鍵模塊的算法過程：
計劃審核求解算法
步驟一：獲取新加入的無人機 ???? 的避障距離 ????a和計劃信息合集 ???????? ；
步驟二：更新航路網信息????和當前時刻 ???? ，通過Dijkstra算法得到無人機的航路點 ?????，并計算飛完全程所需的時間 ???????? ；
步驟三：對無人機 ???? 解優化問題；
步驟四：若有解則直接執行步驟五；若無解且原因是沖突問題，則判斷與其發生沖突的無人機們優先級???????????????????????????????????? , ???? ∈ ???????? ,collision是否均小于自己。若是則拒絕無人機 ???? 的申請后執行步驟五 ，否則拒絕無人機 ???? 的申請 ， 等待 ???????????????????? 時長后執行步驟二；若無解且原因是容量問題， 則暫時先令超容對應的航路固定容量為 0 ，再執行步驟二；其余情況均建議過 ????????????????????時長后執行步驟二 ；
步驟五：如果滿足超時約束條件，則反饋無人機航路點和起飛時間；否則建議過 ????????????????????時長后執行步驟二。
?? ? ?
沖突檢測和流量控制求解算法
步驟一：獲取預估時間 ????max和避障距離 ????a ；
步驟二：更新航路網信息???? ，當前時刻 ???? ，所有已通過起飛授權的無人機信息 ???????? , ???? ∈ ????active 。對已通過起飛授權的無人機進行沖突檢測，若有沖突無人機則輸出發生沖突的無人機 ???????? ,collision和可能的沖突時間；否則執行步驟五 ；
步驟三：解優化問題；
步驟四：若有解則輸出無人機在當前航路的新速度V?n????,?????????????1,n????,????????????,new；若無解則輸出事件刺激無人機啟動自身防碰撞算法 ；
步驟五：間隔 ????max時長后 ，執行步驟二。
?? ? ?
異常處理求解算法
考慮異常天氣、交通管制等（外部因素）產生的沖突進行改航。
步驟一：獲取航路網信息????，受影響的航路????ban，受影響的節點????ban，所有已通過起飛授權的無人機計劃信息???????? ,???? ∈ ????active；
步驟二：將受影響的航路????ban和節點????ban剔除，更新航路網信息????；
步驟三：通過比對計劃信息???????? , ???? ∈ ????active中的航路點?????，篩選出受影響的無人機集合????ban，若????ban = ?則輸出無影響并終止程序；否則執行步驟四；
步驟四：對受影響的無人機采用迪杰斯特拉算法，輸出新的航路點????? , ???? ∈ ????ban并更新???????? , ???? ∈ ????ban。
3.2.2 分布式空中交通控制
集中式空中交通控制系統中如果有某架飛行器要改變飛行計劃，那么與之相關的所有無人機都需要重新在線規劃，更新飛行計劃，且規劃復雜度隨飛機增加而增大。因此，集中式框架計算復雜度太高了，我們希望有另一種框架。就像開車一樣，我們要導航去哪個地方，地圖告訴我們從a到b點怎么走。這個規劃是我們在開車之前，地圖就給我們設計好的。對于飛行器來說，起飛之前系統會根據空中交通情況確定飛行計劃，但一旦起飛之后，就由飛行器自主決定怎么做，這就是分布式整體的框架。分布式框架把很多控制從地面站轉移到了飛行器上，每個飛行器只管自己，整體上是有組織的，但在飛行過程中，飛行器會按照一定協議，與其他飛行器避障。這一部分我們提出一個概念叫Sky Highway 空中高速公路，我們有一篇論文《Sky Highway Design for Dense Traffic》簡單的闡述了我們整個的思路，感興趣的同學可以看一下。
關于航路避障的話，飛機可以直接在航道上進行一些避障的飛行，為了增加整個航路網的帶寬，我們在節點處做了一些設計，比如說這個節點是為了改變方向的，我們也希望飛行器能夠直接通行，這樣話就不用等待。如果是多個航道相交的話，這叫做交叉節點，也就是交叉路口。平時我們經過交叉路口時，最常見的是紅綠燈，但是紅綠燈就意味著飛機要在這里等待。所以目前我們采取了環島結構，應對像紅綠燈這種低效率的等待策略。然后控制，我們大體上是像人工勢場法這種思路來進行的，保證無人機在航道里面往前飛行，同時又不卡死。人工勢場法有一些缺點，有可能會導致卡死，比如說我們大家都往一個點走，那可能誰都到達不了這個點，大家都想到達，但是無法同時到達，這就是卡死問題。我們目前把這些問題都解決了。然后還有環島，我們做了比較細的一些研究，飛行器都能進入航道，又能夠順暢的出去，這個環島設計算是我們的一個創新。
? ? ? ??
3.3 仿真與實驗
最后來介紹一下我們的仿真，我們自己搭建了MATLAB的一個仿真環境，其中有航路網信息，待審核無人機的信息，輸入的禁飛區的信息等等，如下圖所示：
我們在實驗室也做了一些相應的平臺，用這種定位設施來做，如下圖所示：
? ? ? ?
? ? ? ??
4. 總結與展望
無人機空中交通或城市空中移動是大勢所趨，無線網絡和時空大數據是交通的基礎，同時交通設計也對網絡提出了新需求。我們對空中高速公路做了一系列的工作：
設計了航路網模型和無人機模型、基于集中式的低空交通控制算法，以及最重要的基于分布式的低空交通控制算法，在確保無人機安全飛行的前提下增大了流量。
搭建了仿真和實驗平臺，并通過用例測試驗證了基于集中式的低空交通控制算法和基于分布式的低空交通控制算法的可行性。? ? ? ?
未來我們希望繼續在以下方面開展工作：
- 提升飛行狀態預估算法效率。
- 機場高效調度。
- 固定翼飛行器的調度算法。
- 異構系統（旋翼機和固定翼混合空域）魯棒性調度算法。
- 半物理仿真空管測試系統開發。
- 基于真實場景的飛行驗證。
編輯：hfy
工商網監
評論