基于Swarm的城市无人机4D路径规划

      无人机在城市环境中有着广泛的应用，通过各种操作和部署，可以增强人们的日常活动和商业活动。随着无人机数量的增加，飞行安全和效率成为人们关注的主要问题，有效的无人机操作可以发挥作用。因此，无人机作业的4D路径规划是本文研究的重点，提出了基于群的方法来解决这一复杂的优化问题。在“空中矩阵”框架下，该问题分为两个层次解决，即单个无人机的三维路径规划和无人机之间的冲突解决，在多路径规划层面，为每架无人机生成多个可供选择的飞行路径，以提高飞行请求的接受率，考虑了单一飞行路径和两种不同飞行路径的约束条件。目标是获得几种不同的短飞行路径作为选择。采用一种改进的聚类蚁群优化算法(CIACO)求解多路径规划问题，在聚类中采用了拥挤机制，并对聚类算法进行了改进，增强了迭代早期和后期的全局和局部搜索能力。在任务调度层面，定义了两种情况下两架无人机之间的冲突。一种是针对通过同一路径点的时间间隔，另一种是针对两架无人机的直角碰撞。根据安全要求，提出了一个三层适应度函数，以最大限度地增加允许飞行次数，同时考虑了空域的利用情况和操作者的要求。提出了一种“交叉”策略来计算适应度值，并应用了一种“分布式-集中式”策略来考虑无人机的任务优先级。基于遗传算法(GA)的任务调度算法也被开发到所建立模型的特征。仿真结果表明，该算法能够生成每架无人机的四维飞行路径，保证了无人机在特定空域内的安全高效作业。

      无人机路径规划问题受到了广泛的关注，引入了四旋翼机、太阳能UAV和倾转旋翼机等多种UAV在城市环境中执行不同的任务。根据路径规划的复杂性,可以有两类,即为一个UAV和路径规划协调路径规划为多个UAV和另一方面,路径规划可以进行基于需求在连续和离散空间的具体问题。上述问题与工作密切相关，下文将讨论最新进展。

     在单个UAV的路径规划问题中，有时需要同时生成多个路径作为可选方案。多路径规划问题主要由群算法和进化算法来解决，因为这些算法可以在子种群的思想下并行运行。很多文献都关注这个问题，通常通过计算不同个体之间的距离来初始化亚种群。两个距离最小的个体被认为在同一个亚种群中，重复上述过程，直到亚种群数量达到指定的值。对待亚群体有两种方式，即亚群体的作用相同或不同。在Ref.中，使用K-means聚类方法将整个种群划分为ksubpopulation。在每个子种群中，质量较差的解决方案将被抛弃。然后引入小生境的思想，在它们自己的亚种群中进行搜索，从而一次生成k条路径。

     目前对多用户群体路径规划的研究主要集中在连续空间的情况下，分布式路径规划方法受到了广泛的关注。为了平衡多目标优化和抢占优先级的要求，采用模糊满意优化方法求解具有抢占优先级的多目标模型。在多UAV路径规划问题中，经常将后退水平控制和分布式模型预测控制相结合，每个UAV可以根据仅与自身相关的约束来决定自己的行动。在模型预测控制的框架下，可采用各种基于自然的优化算法，如粒子群优化算法(PSO)、自适应蚱蜢优化算法(AGOA)和改进灰狼优化算法(IGWO)生成最优轨迹。

     在本节中，我们将引入“AirMatrix”概念来描述城市环境和无人机的飞行规则。

A.无人机环境建模与飞行规则

    “AirMatrix”中描述的建筑被定义为具有特定尺寸的立方体，如图1所示。图1中用立方体表示的建筑被认为是无人机操作的“禁止”区域。对于“空中矩阵”中定义的路径点，无人机可以沿着两个相邻节点之间的直线飞行。

图1 《AirMatrix》中的建筑插图

B.单无人机飞行的多路径规划模型

     根据上面的定义，每个飞行路径中都有一定数量的路径点，它们是待优化的变量，约束来自于单一飞行路径和多飞行路径两个方面。对于单一飞行路径，其所有路径点必须在“空中矩阵”所占用的空间内，并与地面保持一定距离，以保证安全。假设立方体的边长为isa，上述约束可表示为:

     此外，每个路径点必须与建筑物保持一定的距离，飞行路径上不允许重复路径点，以避免绕道。以上约束可以写成：

C.多无人机任务调度模型

     飞行请求提交给空中交通管制员后，将根据任务的重要性为每个无人机分配任务优先级。例如，救援、消防等应急应用的任务优先级较高，航拍、媒体广播等娱乐应用的任务优先级较低。此外，无人机在飞行过程中被调节为匀速飞行，飞行速度可以从以下三个值中选择:VH、VMand、VL，分别代表高速模式、中速模式和低速模式。在实际应用中，由于无人机种类繁多，对于异构无人机，Vh、VMand、VL的值可能会有所不同。

图2 两架无人机直角碰撞

     由于每架无人机都有多个可供选择的飞行路径，因此需要多路径规划算法。一些算法，如伪谱法、禁忌搜索算法和模拟退火算法，仅从一个初始解开始，不能满足需求。此外，最终最优解对初始解很敏感，增加了获得最优解的难度。

A.蚁群算法中基于拥挤机制的聚类算法

     首先确定聚类中心，良好的初始聚类中心既能加快算法的收敛速度，又能避免解陷入局部最优;一种直观的想法是，从几个不同的最佳初始解中选择聚类中心，其他初始解可以根据它们到聚类中心的距离放入相应的聚类中。请注意，每个集群中只有一个中心，并且一个初始解决方案只属于特定的集群。

     这些聚类具有以下特点:虽然一个解决方案可能接近多个聚类中心，但它只属于中心适应度值较小的聚类。此外，聚类的数量不是预先确定的，而是由解的适应度值决定的。与固定的集群数量相比，自适应的集群数量可以使每个集群区别于其他集群。最后，排在前几个位置的解决方案是不同的，可以成为集群中心。这有利于在以后的迭代过程中获得更好的解决方案，因为每个集群中至少有一个好的解决方案。

B.基于改进蚁群算法的多路径规划

    由于整个群被划分为一定数量的聚类，因此基于蚁群算法制定每个聚类的更新策略。蚁群算法虽然在工业上应用于许多优化问题，但仍存在容易陷入局部最优解和收敛速度较慢的缺点。在蚁群算法的框架下，针对上述缺点进行了改进。这些改进将在描述蚁群算法解决多路径规划问题的步骤时得到重点说明。

     其他参数，如antsNA的数量，最大迭代次数simax，有效因子α，启发式因子β，信息素矩阵τ，信息素常数q和信息素蒸发ρ，也需要初始化。注意信息素矩阵τ的大小与记录路径影响的搜索空间相同。假设簇数为nc，每个簇应有一个独立的信息素矩阵跟随。

    为了研究所提出的四维路径规划方法在无人机作业中的合理性和优越性，对不同路径规划算法和不同设置进行了仿真。在第一组中，使用标准ACO算法、IACO算法和CIACO算法生成给出了无人机的多种飞行路径，并对三种算法进行了比较。在第二个场景中，给出了不同无人机数量下的任务调度结果，并分析了无人机数量与航班验收率之间的关系。并与其他计算适应度值的方法进行了比较。最后，探讨了不同可选飞行路径数量对适应度值的影响，以进一步提高航班的接受率。

A.不同形式蚁群算法的多路径规划结果

     采用三种不同形式的蚁群算法对航迹进行了计算，并通过比较验证了所提出的蚁群算法的优越性。ACO算法的参数设置是列在表i的起点(750、810、60)和目标(1770、1710、90)作为一个例子,信息素constantQ0is设置asQ0 =(1770 - 750) +(1710 - 810) +(90 - 60),这是一笔位置差异alongOX开始和结束点,分别OYandOZaxes。信息素矩阵τ中的所有元素初始化为1。在上述设置下，ACO、IACO和CIACO算法中适应度值的变化情况如图3所示。

图3 三种算法的收敛曲线

B.不同无人机数量下的任务调度:比较与讨论

     在本节中，每个无人机将分配三个替代飞行路径的任务调度算法。其他输入包括请求的无人机起飞时间(设置为0 - 300秒之间的随机整数)、无人机的最新到达时间和无人机的任务优先级。在遗传算法中，染色体数目toNI=300，执行交叉算子和变异算子的概率分别为pc=0.2和pm=0.1。GA运行200次迭代，即IGmax=200，最优解将作为最优飞行方案输出。首先讨论了基于遗传算法的任务调度算法的收敛性。不同数量的无人机将进行比较。请注意，模拟是用越来越多的无人机进行的，使用了一些常见的数据。例如，无人机数量为100时，前半部分的初始设置与无人机数量为50时相同。这样可以使比较更加可靠，减少随机算子信息的影响。由于任务调度的适应度函数有三层，每一层的收敛曲线如图4所示。

图4 无人机平均航迹数收敛曲线

     为保障空域安全，提高空域运行效率，本文研究了无人机在城市环境下作战的4D路径规划问题。文献研究表明，无人机的协调路径规划问题是站在运营商的立场上解决的，缺乏对空域情况的全局考虑。引入空中交通管制员的视角，对无人机进行协调，确定其飞行方案。

     首先，使用“AirMatrix”的概念来描述城市环境和无人机的飞行规则。在多路径规划层面，考虑了单个飞行路径约束和两个飞行路径的差值，以最短飞行路径为适应度函数。在任务调度层，在任务优先级已知的情况下，以每架无人机的起飞延误、飞行速度和飞行路径数为输入，建模两架无人机飞行路径之间的冲突;从空域情况和运营商需求出发，建立了反映解决方案质量的三层适应度函数。

     为了求解所建立的模型，提出了CIACO算法，为每架无人机生成多个飞行路径。该算法在聚类过程中采用了拥挤机制，聚类的数量由解的质量决定，而不是由一个特定的数量决定。此外，在迭代的不同阶段，提出了多种策略来提高基本蚁群算法的探索和开发能力。在任务调度问题中，在“分布式-集中式”调度策略下，设计了基于遗传算法的最优飞行方案，并提出了“交叉”方法来计算复杂的三层适应度值。

    在仿真研究中，对CIACO多路径规划算法和基于GA的任务调度算法进行了验证。该算法能够为每架无人机生成多个可供选择的飞行路径，且与标准蚁群算法相比，飞行路径长度也可以缩短。在基于GA的任务调度算法中，随着无人机数量的增加，无人机的飞行接受率降低，平均延迟增加。通过与分布式策略、SA算法和EDA算法的比较，验证了所提出的“交叉”策略的优越性。此外，当可供选择的飞行路径数量增多时，飞行方案并不总是会变得更好。研究结果可为空域容量的设计和经营者的偏好提供参考。未来，其他形式的空中运输，如空中出租车、监视和紧急救援的路径规划问题可以建模，其他先进的生物启发算法有望提高无人机行动的安全性和效率。