北航全权：一种城市空中移动性管理分布式控制框架

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. 总结与展望

无人机空中交通或城市空中移动是大势所趋，无线网络和时空大数据是交通的基础，同时交通设计也对网络提出了新需求。我们对空中高速公路做了一系列的工作：

• 设计了航路网模型和无人机模型、基于集中式的低空交通控制算法，以及最重要的基于分布式的低空交通控制算法，在确保无人机安全飞行的前提下增大了流量。

• 搭建了仿真和实验平台，并通过用例测试验证了基于集中式的低空交通控制算法和基于分布式的低空交通控制算法的可行性。       

未来我们希望继续在以下方面开展工作：

• 提升飞行状态预估算法效率。

• 机场高效调度。

• 固定翼飞行器的调度算法。

• 异构系统（旋翼机和固定翼混合空域）鲁棒性调度算法。

• 半物理仿真空管测试系统开发。

• 基于真实场景的飞行验证。

头图：Unsplash

作者：美团技术学院

原文：https://mp.weixin.qq.com/s/pri6N7rK9FhOfqEFruY0uw

原文：美团内部讲座｜北航全权：一种城市空中移动性管理分布式控制框架

来源：美团技术团队 - 微信公众号 [ID：meituantech]

转载：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。