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

低空交通控制算法包括集中式空中交通控制和分布式空中交通控制。
3.2.1 集中式空中交通控制
集中式控制可以分为两个部分：离线规划和在线控制。离线规划就是说飞机起飞前需要申报自己的飞行计划，然后接受审核。如果当前的航路网非常堵塞的话，那么审核就不会通过，就需要等待或者重新申报飞行计划。如果审核通过的话，就会产生一个包含起飞时间、地点等信息的待飞计划，将待飞计划写入空中交通管理系统的数据库中，进而对空中交通情况进行预测。
但是飞行器在飞行过程中受天气、本身状态等因素影响会有很多不确定性，飞行器的飞行速度变化就会产生冲突。因此在飞行器飞行过程中，我们需要对飞机进行一些定量的控制，这就是飞行器的在线控制。我们可以通过控制飞行器的高度、速度等，使它能够避免冲突，如果在整个航路网中冲突无法避免，那么我们肯定不希望发生多米勒骨牌一样的效应，因为局部一个因素，使整个航路网都发生变化。避免冲突最简单的方法就是避障，一个飞行器向上飞，一个飞行器向下飞，这是空中交通的优势，汽车没有办法做到，大概是这样一个逻辑。

本文插图

以下是基于集中式的低空交通控制系统中几个关键模块的算法过程：

计划审核求解算法

步骤一：获取新加入的无人机的避障距离 a和计划信息合集；
步骤二：更新航路网信息和当前时刻，通过Dijkstra算法得到无人机的航路点 ? ，并计算飞完全程所需的时间；
步骤三：对无人机解优化问题；
步骤四：若有解则直接执行步骤五；若无解且原因是冲突问题，则判断与其发生冲突的无人机们优先级 , ∈ ,collision是否均小于自己。若是则拒绝无人机的申请后执行步骤五，否则拒绝无人机的申请，等待时长后执行步骤二；若无解且原因是容量问题，则暂时先令超容对应的航路固定容量为 0，再执行步骤二；其余情况均建议过时长后执行步骤二；
步骤五：如果满足超时约束条件，则反馈无人机航路点和起飞时间；否则建议过时长后执行步骤二。

本文插图

冲突检测和流量控制求解算法

步骤一：获取预估时间 max和避障距离 a ；
步骤二：更新航路网信息，当前时刻，所有已通过起飞授权的无人机信息 , ∈ active。对已通过起飞授权的无人机进行冲突检测，若有冲突无人机则输出发生冲突的无人机 ,collision和可能的冲突时间；否则执行步骤五；
步骤三：解优化问题；
步骤四：若有解则输出无人机在当前航路的新速度Vn,?1,n,,new；若无解则输出事件刺激无人机启动自身防碰撞算法；
步骤五：间隔 max时长后，执行步骤二。

本文插图

异常处理求解算法

考虑异常天气、交通管制等（外部因素）产生的冲突进行改航。
步骤一：获取航路网信息，受影响的航路ban ，受影响的节点ban ，所有已通过起飞授权的无人机计划信息 , ∈ active；
步骤二：将受影响的航路ban和节点ban剔除，更新航路网信息；
步骤三：通过比对计划信息 , ∈ active中的航路点? ，筛选出受影响的无人机集合ban ，若ban = ?则输出无影响并终止程序；否则执行步骤四；
步骤四：对受影响的无人机采用迪杰斯特拉算法，输出新的航路点? , ∈ ban并更新 , ∈ ban 。
3.2.2 分布式空中交通控制