美團內里講座｜北航全權：一種都市空中挪動性辦理分布式控制框架

【Top Talk/大咖說】由美團武藝學院和科研互助部主理，面向全體武藝同硯，定期約請美團資深武藝專家、業界大咖、高校學者及熱銷書作者，為各位分享最佳實踐、互聯網搶手話題、學術界前沿武藝歷程等外容，協助美團同硯開發視野、提升認知。

2020年10月20日，Top Talk約請到了北京航空航天大學全權教師，請他帶來題為《基于時空大數據的空中高速公路：一種都市空中挪動性辦理分布式控制框架》的分享。本文系全權教師分享的筆墨實錄，渴望能對各位有所協助大概啟示。

/報告高朋/ 全權｜北京航空航天大學

全權，北京航空航天大學副傳授，多倫多大學客座傳授（E-mail：qq_buaa@buaa.edu.cn）。長時從可靠飛行控制。作為第一作者，完成英文著作三部，公布文章近百篇。獲第二屆舉國高校主動化專業青年教員實行裝備計劃“創客大賽”金獎（排名第一）。

/報告擇要/

無人機交通以及邇來崛起的空中挪動性辦理取得了廣泛的眷注。為此，波音、空客、霍尼韋爾和貝爾等傳統航空巨頭以及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. 總結與展望

無人機空中交通或都市空中挪動是場面所趨，無線網絡和時空大數據是交通的基本，同時交通計劃也對網絡提出了新需求。我們對空中高速公路做了一系列的事情：

• 計劃了航路網模子和無人機模子、基于會合式的俯空交通控制算法，以及最緊張的基于分布式的俯空交通控制算法，在確保無人機寧靜飛行的條件下增大了流量。
• 搭建了仿真和實行平臺，并經過用例測實驗證了基于會合式的俯空交通控制算法和基于分布式的俯空交通控制算法的可行性。

將來我們渴望持續在以下方面展開事情：

• 提升飛行形態預預算法聽從。
• 機場高效調治。
• 安穩翼飛行器的調治算法。
• 異構體系（旋翼機和安穩翼殽雜空域）魯棒性調治算法。
• 半物理仿真空管測試體系開發。
• 基于真實場景的飛行驗證。

---------- END ----------

招聘信息

美團信息寧靜部正在招聘風控戰略工程師、高等產物司理（風控戰略）、挪動寧靜工程師/專家、體系寧靜工程師、云原生寧靜工程師/專家、藍軍專家/高等藍軍專家、業務藍軍專家/高等業務藍軍專家、賬戶寧靜專家、前端架構師/專家、Java開發工程師、資深Java工程師、寧靜辦理高等工程師、寧靜綜合處理方案專家、數據寧靜專家、產物司理-反爬朝向、稽核戰略辦理、入侵反抗專家、數據寧靜產物專家、數據發掘高等專家、大數據研發工程師、大數據資深架構師、深度學習算法工程師、高等數據發掘/專家（反作弊算法朝向）等崗亭。

接待投遞簡歷至 sunny.fang@meituan.com。郵件主題請注明（意向崗亭-都市-美團武藝團隊群眾號）。