美团内里讲座｜北航全权：一种都市空中挪动性办理分布式控制框架

【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。邮件主题请注明（意向岗亭-都市-美团武艺团队群众号）。