美团内部讲座｜北航全权：一种城市空中移动性管理分布式控制框架
总第419篇
2020年 第43篇
全权｜北京航空航天大学
全权，北京航空航天大学副教授，多伦多大学客座教授（E-mail：qq_buaa@buaa.edu.cn）。长期从可靠飞行控制。作为第一作者，完成英文著作三部，发表文章近百篇。获第二届全国高校自动化专业青年教师实验设备设计“创客大赛”金奖（排名第一）。
/报告摘要/
无人机交通以及最近兴起的空中移动性管理得到了广泛的关注。为此，波音、空客、霍尼韦尔和贝尔等传统航空巨头以及Uber等新兴世界级影响力的企业纷纷加入。本报告提出了空中高速公路方案以及仿真测试。该方案基于时空大数据，考虑了交通网络、航线规划和分布式控制设计。在空中高速公路上，每架无人机都有自己的规划的航线，可以自主地自由飞行，从而支持密集立体的飞行交通。
1. 背景
今天我给大家带来我们实验室（北航可靠飞行控制研究组）做的一些工作，主要内容是讲一种城市空中移动性管理分布式控制框架。
相信美团的同学一定也很非常期待实现无人机配送的一天早日到来。未来无人机配送服务将会极大地改变我们目前的生活方式。尽管在人群密集的区域，我们仍然需要靠人来完成配送服务，但是在人口比较稀疏，比如郊区等地带，使用无人机配送会更好。报告表明，网联无人机将为产业带来7~10倍的产业机会，这也是我们在大概三年前就开始着手做这方面相关的工作的原因。
无人机的交通网和交通管理，是否可以利用现有的交通方式呢？我们通过研究发现，像传统的民航网其实是不适合的，民航的飞行器其实非常稀疏，在三维空间，整个网络的变化频率是比较低的，有入网申请时，基本上是通过集中式的规划。而公路网络尽管很密集，但是二维空间，因此交通网络管理也是偏自主的。铁路同样也是二维的。网络动态变化是说就像我们上互联网一样，我们需要接入网络，而公路不可能马上为我们修一条公路出来。无人机交通与公路、铁路具有共同点，不同的是无人机处于三维空间， 网络动态变化比较高。因此我们在设计无人机飞行控制框架时，希望设计一种能够适应包括无人机的增加、网络的扩展等变化的框架。关于路径规划，其实可以采用集中式加自主的方式来进行。关于这部分的内容我们今年发表了一篇综述文章《低空无人机交通管理概览与建议综述》，感兴趣的同学可以参阅。
规划无人机的航线、起飞时间，确保无人机在避免冲突的前提下起飞：无人机航线起飞时间跟我们目前坐飞机的感觉是一样的，有时候飞机会停在某个地方延迟起飞，目的是为了不与其他飞机在航路上发生碰撞及冲突，当然有时候也会因为天气等原因，需要飞机延迟起飞，因为飞机在地面等待，代价是最小的。 在避免碰撞的前提下顺利完成飞行任务 应对天气、禁飞区等不确定因素的影响：无人机临时在飞行过程中，我们有时需要切断某些航线，这种情况下，我们希望飞行器仍然能够能够飞到目的地，至少它能安全的回到附近的机场。
开展空中高速公路研究，我们需要有网络和时空大数据的一些研究基础。
首先我们需要有通信、导航、监视功能等基础设施，这些功能充当着整个无人机交通管理系统的眼睛、耳朵和神经系统，负责态势感知和信息传输。其中，通讯就是4G/5G、卫星通讯等，这是我们的网络。导航是我们飞行器需要导航，比如说通过基站定位、雷达、卫星、惯导以及视觉的导航。而监视跟导航的区别在于导航是给飞行器用的，监视是我们作为官方需要了解飞行器在空中的动态。有些飞行器可能会自己导航，通过导航或者通信告诉地下的地面站，这样的话我们可以监视。但有些飞行器是航模，没有通讯的功能，只能被动的被看到，那么我们可以通过一些可见光、声波等来监视，还有飞行器可能通过一些ADS-B等来广播自己的信息。因此通过以上这些功能，可以实现我们对飞行器飞行周边环境的了解，地面对空中环境的了解，这是我们做空中高速公路研究的一个基础。另一方面，我们需要时空大数据的支撑。首先我们需要了解所有禁飞区，禁飞区也会动态的变化。其次我们需要了解气象大数据，以便我们规划飞行器避开极端天气。同时我们也需要获取地理大数据的信息，比如通过地理大数据我们可以了解什么位置有障碍物，哪些区域下方是草地等，根据这些信息可以进一步的提取一些信息，来规划飞行器的航路、航路网等以及规划飞行器的航线。另外我们还可以通过移动互联网知道哪些地方人口密集，这样在规划航路网或者航线的时候，就能避开这些人口密集的地方。以上这些都是我们研究需要的时空大数据基础。
前面提到，网络是我们研究空中高速公路的基础，目前在空中交通，主要是通过网络来分享信息。但是网络会有网络质量，那么网络质量与飞行安全是什么样的关系呢？网络质量通常由三个因素决定：噪声，延迟，丢包（Packet loss）。由于网络质量原因，无人机获取到的障碍物位置，和障碍物实际的位置可能就不一样了。以下图为例，无人机估计自身的位置产生了偏差，随之估计障碍物位置也发生了偏差。因此我们需要设计一个飞行的安全距离，以应对网络质量造成的这种不确定性。这跟我们在高速公路上开车需要保持车间距是一个道理，我们车间距这个概念用到无人机的空中交通，希望以此来应对这些丢包延迟。当然也有人通过一些控制的方法来解决这些问题，我们这种方法应该更适合交通的场景。
另一方面，我们需要通过一些数据做风险评估，如下图所示，至少有两个因素：事故概率评估（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 集中式空中交通控制
集中式控制可以分为两个部分：离线规划和在线控制。离线规划就是说飞机起飞前需要申报自己的飞行计划，然后接受审核。如果当前的航路网非常堵塞的话，那么审核就不会通过，就需要等待或者重新申报飞行计划。如果审核通过的话，就会产生一个包含起飞时间、地点等信息的待飞计划，将待飞计划写入空中交通管理系统的数据库中，进而对空中交通情况进行预测。
但是飞行器在飞行过程中受天气、本身状态等因素影响会有很多不确定性，飞行器的飞行速度变化就会产生冲突。因此在飞行器飞行过程中，我们需要对飞机进行一些定量的控制，这就是飞行器的在线控制。我们可以通过控制飞行器的高度、速度等，使它能够避免冲突，如果在整个航路网中冲突无法避免，那么我们肯定不希望发生多米勒骨牌一样的效应，因为局部一个因素，使整个航路网都发生变化。避免冲突最简单的方法就是避障，一个飞行器向上飞，一个飞行器向下飞，这是空中交通的优势，汽车没有办法做到，大概是这样一个逻辑。
以下是基于集中式的低空交通控制系统中几个关键模块的算法过程：
计划审核求解算法
冲突检测和流量控制求解算法
步骤一：获取预估时间 𝑇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的一个仿真环境，其中有航路网信息，待审核无人机的信息，输入的禁飞区的信息等等，如下图所示：
我们在实验室也做了一些相应的平台，用这种定位设施来做，如下图所示：
无人机空中交通或城市空中移动是大势所趋，无线网络和时空大数据是交通的基础，同时交通设计也对网络提出了新需求。我们对空中高速公路做了一系列的工作：
设计了航路网模型和无人机模型、基于集中式的低空交通控制算法，以及最重要的基于分布式的低空交通控制算法，在确保无人机安全飞行的前提下增大了流量。 搭建了仿真和实验平台，并通过用例测试验证了基于集中式的低空交通控制算法和基于分布式的低空交通控制算法的可行性。
未来我们希望继续在以下方面开展工作：
提升飞行状态预估算法效率。 机场高效调度。 固定翼飞行器的调度算法。 异构系统（旋翼机和固定翼混合空域）鲁棒性调度算法。 半物理仿真空管测试系统开发。 基于真实场景的飞行验证。
---------- END ----------招聘信息美团信息安全部正在招聘风控策略工程师、高级产品经理（风控策略）、移动安全工程师/专家、系统安全工程师、云原生安全工程师/专家、蓝军专家/高级蓝军专家、业务蓝军专家/高级业务蓝军专家、账户安全专家、前端架构师/专家、Java开发工程师、资深Java工程师、安全管理高级工程师、安全综合解决方案专家、数据安全专家、产品经理-反爬方向、审核策略管理、入侵对抗专家、数据安全产品专家、数据挖掘高级专家、大数据研发工程师、大数据资深架构师、深度学习算法工程师、高级数据挖掘/专家（反作弊算法方向）等岗位。
欢迎投递简历至 sunny.fang@meituan.com。邮件主题请注明（意向岗位-城市-美团技术团队公众号）。
也许你还想看
| 美团内部讲座｜清华大学莫一林：信息物理系统中的安全控制算法| 喜讯！美团-清华大数据课程对外开放啦！| 美团OCTO万亿级数据中心计算引擎技术解析