摘要
具有最优路径的自主任务能力是无人机在各种应用中导航的严格要求。所提出的研究框架是为无人机在各种约束和密集障碍物易发区域中导航，确定一种节能的最优路径，以实现指定的任务。因此，本工作旨在通过将改进蚁群优化算法(MACO)与a *算法的一种变体，即内存高效a *算法(MEA*)相结合，开发一种最优节能路径规划算法，以避免三维环境中的障碍物，并以最小的能量消耗到达最优路径。该方法的新颖性在于将上述两种高效算法结合起来对无人机路径规划任务进行优化。本研究的基本设计是，在MACO中利用改进版的信息素策略，使局部陷阱和过早收敛最小化，并通过奖惩机制找到最优路径。集成MEA*算法的唯一概念源于克服传统A*算法严格的内存要求并解决仅跟踪网格边缘的问题至关重要。结合MACO和MEA*的能力，提出了一种混合避障算法，以寻找有效路径。通过改变三维区域内障碍物的数量来进行仿真研究。通过实现所获得的最优路径，在无人机上进行了实时飞行试验。对无人机的总能耗与理论分析进行了比较。本研究的重要发现是，与MACO-A*相比，MACO-MEA*算法的能耗降低21%，执行时间缩短55%。此外，仿真方法和实验方法所遍历的路径一致性达到99%。验证了所开发的混合MACO-MEA*节能算法是无人机在三维障碍物易发区域导航的可行解决方案。
1 介绍
无人机越来越受欢迎，因为它可以携带更多的有效载荷，用于广泛的应用，并在危险和危险的环境中航行。它们应具有良好的机动性和灵活性，以适应在混乱的环境中进行有效的导航。在这些具有严格能源需求的情况下，自主无人机导航是在多方面环境和应用中部署无人机的一个重大问题(Aggarwal和Kumar 2020)。很少有例子是交通监测、公路基础设施评估(Outay等人，2020)、灾后搜救行动(Shakhatreh等人，2019)、在广阔的农田喷洒农药(Radoglou-Grammatikis等人，2020)、地雷检查(Park和Choi, 2020)和其他远程监视(Valsan等人，2020)和侦察防御任务(Sigala和Langhals, 2020)。在这方面，多旋翼无人机(muav)被认为是突出的解决方案，因为它们具有固有的悬停能力，快速和快速的机动能力，现在能够携带更重的有效载荷，包括运送人员(Liu et al. 2021)。通过替代人执行指定任务，可以有效部署各种尺寸、不同载荷能力的无人飞行器。在3D环境中，如何在最优路径上避开障碍物实现安全导航是一个具有挑战性的问题。最优路径规划对提高无人机的自主能力具有重要意义。在无人机实际飞行过程中，有许多静态和动态障碍物影响着无人机的导航。需要有效的路径规划策略来避开障碍物，找到最短最安全的路径来完成预期的任务。许多开创性的作品处理了2D环境(Khan等人，2021a, b)，很少有作品关注通过避开障碍物来规划3D环境中的路径(Vashisth等人，2021;Zhang et al. 2021)。无人机在低空飞行时，会遇到许多静态障碍物的阻碍，因此需要一种高效的路径规划算法。路径规划的目标是在密集的环境中找到一条最优路径，使其无碰撞。为了使无人机在特定任务所需的轨迹上导航，必须做出最优决策，以在最短的时间内到达目的地。它在递送包裹、医疗包、地形跟踪飞行和救灾活动等方面具有巨大潜力。与这些无人机有关的其他问题是由于有限的电池存储容量而影响其飞行耐力。因此，节能最优路径规划(Monwar et al. 2018;Ahmad et al. 2017;Yacef et al. 2020)是在给定能量约束下实现指定任务的可行解决方案。为了解决这些问题，本文重点研究了在全局和局部意义上开发一种节能路径规划算法，以便在3D环境中通过避开障碍物进行导航。
2 使用最先进技术的
无人机路径规划是指在集群环境下，在不与空域障碍物发生碰撞的情况下，寻找最佳路径，使无人机从源点飞到目的点。这是一个基于环境的建模过程，该过程应考虑给定空域中的静态障碍物和可能突然侵入同一空域的动态威胁。为了在静态和动态环境中找到最优路径，有效的路径规划算法(Shin and Chae 2020;Qian et al. 2016)是必要的。在道路规划和地面车辆自主导航方面的许多开创性工作(Lipp and Boyd 2014;Herrmann et al. 2020a, b;Ozatay et al. 2017)。他们专注于优化车辆在固定路径上的速度，以最短的时间穿越，生成最佳轨迹，并确定最佳能量轨迹。然而，对于无人机来说，路径规划算法分为基于图的、基于种群的进化算法和分布式方法。其中，蚁群优化(Ant colony Optimization, ACO) (Dorigo and st
提出了迭代深化A* (IDA*) (Bu和Korf 2021)来解决A*算法所施加的巨大内存需求。然而，IDA*在识别和选择后续可能的节点方面表现不佳。多次选择同一节点，性能不如A*。此外，为了解决沿着单个网格单元的网格边缘确定最优路径的问题，a Theta* (Daniel et al. 2010;提出了Wu et al. 2020)算法。结果发现，在寻找最优路径时，Theta*的表现要比A*慢得多。然而，A*的另一种变体，即Field D* (FD*)被制定(Ferguson et al. 2006)，以避免遵循网格单元的边缘。观察到FD*比A*算法进行了更多不必要的转弯(Ferguson et al. 2006;沃伦1993;Botea et al. 2004)。Aghababaie等人(2017)利用超分辨率技术提出了卷积神经网络(CNN)的非线性多层映射，以提高无人机导航的图像质量。仿真结果表明，该方法在峰值信噪比(PSNR)方面优于其他基准技术。KhazaeiPoul等人(2017)通过结合超分辨率技术提高了使用无人机收集的图像质量。Khisheh等人(2016)开发了两种混合算法，蚁狮:神经网络和基于生物地理的优化算法:神经网络，用于选择传感器以提高自主水下航行器的性能。最近，针对无人系统应用开发了许多路径规划算法，表1比较了各种路径规划算法及其优缺点和应用。
最近对各种无人机路径规划和避碰算法的调查可以在(Basiri et al. 2022;Khan et al. 2021a, b).为了在无人机应用中以较好的精度解决高维问题并避免其路径的突然变化，上述算法可能不是一种有效的选择。为了克服这些问题，实现了Memory Efficient A* (MEA*)算法(Noreen et al. 2019)来进行有效的路径规划。它之所以变得流行，是因为它不需要大内存，并且与前面提到的寻找最优路径的其他算法相比，它避免了网格单元的边缘。实践证明，该算法能够在最短的执行时间内以较少的轮数确定最优路径，其主要优点是对内存的需求较小。因此，本文结合MACO算法和MEA*算法的能力，提出了一种MACO-MEA*混合算法，以在三维环境中避开障碍物，并有效地确定无人机应用的最优路径。总的来说，无人机的续航时间(飞行时间)较短，在多方面的环境中，包括灾害任务、监视和侦察行动、民用基础设施检查和社会应用等，对节能无人机的导航需求很高。能源管理是主要问题(Herrmann et al. 2019;Herrmann et al. 2020a, b)自动驾驶汽车。有相当多的工作集中在使用粒子群优化(Ding et al. 2018)，无人机路径规划的深度学习方法(Nie et al. 2020)的无人水面飞行器(usv)的节能路径规划上，并解决了无人机的能量约束问题(Monwar et al. 2018;Abeywickrama et al. 2017;Yang et al. 2018)讨论了无人机前飞和悬停飞行的能量计算。因此，本工作设想将飞行和悬停无人机的能量计算与最优路径规划器相结合，以确定节能的最优路径。任务可以根据最佳节能条件事先规划，从而可以了解实时部署无人机的严格能源需求。
结合目前的研究现状，本工作的主要贡献、新颖性和应用性有:
-
结合能量需求确定节能最优路径的混合MACO-MEA*算法的开发
-
该工作的新颖之处在于将MACO和MEA*算法集成在一起，实现了现有技术中未结合的有效的全局和局部路径规划。
-
开发的框架提供了一个有效的解决方案，通过在集群环境中导航，有效地规划和执行关键任务，例如在灾害易发地区，货物交付等。
其余部分组织如下。第2节简要讨论了ACO、A*和MEA*算法。第3节重点研究了无人机在飞行和悬停工况下的能量需求。第4节讨论了无障碍物的MACO和有障碍物的混合MACO- a *和MACO- MEA*的仿真结果。第5节介绍了MACO-MEA*和MACO-A*混合算法的实验平台和实现，并对这两种算法进行了比较分析。第6节提供结束语和未来的方面。
3.无人机路径规划算法
无人机应用中的路径规划(Zhang et al. 2014)在受限环境中避开障碍物具有挑战性。本研究的重点是结合MACO算法和A*/MEA*算法的能力来寻找最优避障路径。利用A* /MEA*算法避开障碍物，以最小的距离行进，这被认为是一种局部路径规划。MACO用于寻找整个区域的最短路径，在本研究中被认为是一个全局寻路者。因此，本文讨论了一种通过避障和寻找最优路径来寻找最优路径的混合方法。MACO、A*和MEA*算法概述如下。
3.1 改进蚁群算法
蚂蚁算法的基本思想(Dorigo and st
首先，采用一种改进的启发式函数来改进由
（1）其中I和j为节点位置;是边ij的权值，是曼哈顿距离。
其次，他们考虑了奖惩机制，其中最好的路径被存储，最差的路径被忽略，避免了局部陷阱。
信息素沉积的更新由，
（2）．
其中I是信息素强度的系数，是奖励因素，是惩罚因素。Nr是奖励蚂蚁的数量，Np是惩罚蚂蚁的数量。Lr是奖励的路径长度，lp是惩罚的路径长度。在传统蚁群算法中对这两个任务进行了更新，以提高算法的效率，以达到最佳可能路径。
3.2 意味着*算法
MEA*算法是a *算法的一种变体，主要关注a *算法的严格内存要求和解决高维网格环境(Noreen et al. 2019)。A*也有跟踪网格边缘的问题，它可能不会提供一个有效的最优路径。为了克服在高维空间中确定最优路径的这些瓶颈，提出了MEA*算法。它有三个列表，一个空列表包含要探索的节点，一个闭合列表包含已经探索过的节点，父列表包含当前节点的父节点。在初始阶段，所有列表都设置为空。
其代价函数为
（3）其中为从初始节点到当前节点的代价，为从当前节点到结束节点的启发式估计代价。最初，为起始点设置为0，并且假定映射中的所有其他节点为无穷大。在每次迭代过程中，考虑最小的f值并将其添加到打开列表中，而忽略其他节点。因此，执行时间和内存需求被最小化。但是，A*会考虑所有不适合最优路径的相邻节点，这会增加内存需求，增加执行时间。与A*不同的是，MEA*算法使用欧几里得距离并适当考虑障碍物来进行下一步移动，从而避免了A*算法中出现的更多回合数。因此，它用一次迭代找到下一个可能的最佳节点，而忽略其他节点。因此，消除了大内存存储，并将时间消耗降至最低。
2D和3D环境中有无障碍物的无人机路径规划(Ghambari et al. 2020;Zhang et al. 2020)在实际应用中是一个值得关注的问题。在此，设想了在具有静态障碍物的三维环境下的工作路径规划，进行了仿真和实验研究。对MACO-A*和MACO-MEA*混合算法进行了仿真，并对其性能进行了比较。图1显示了所提出的混合算法通过避开障碍物确定最优路径的示意图。
混合MACO与A*/MEA*
目录
摘要 1 介绍 2 使用最先进技术的 3.无人机路径规划算法 4 能源有限公司 前飞和悬停飞行时的消耗 5 仿真与实验结果的比较 6 通过无人机飞行测试实时实现开发的算法 7 结论 缩写 参考文献 致谢 作者信息 道德声明 搜索 导航 ＃＃＃＃＃4 能源有限公司前飞和悬停飞行时的消耗
对大地理区域的自主检测是滑坡监测、基础设施检查、水质和环境监测的重要要求。无人机的能量需求是主要瓶颈(Stolaroff等人，2018)。为了克服这一问题，必须部署节能无人机(Ahmed et al. 2016;Kumbhare等人，2017;Pereira de Carvalho 2018)。无人机所消耗的能量主要是由于在向前飞行过程中与风条件相关的阻力以及它以一定角度向下倾斜。以下关系式适用于计算前向飞行条件下的能量消耗(Ahmed et al. 2016)。
向前运动时对阻力的功率消耗由
（4）式中为诱导速度，为无人机平均对地速度，β为俯仰角，T为电机产生的推力。
（5）式中，m为无人机包括电池的质量，g为重力常数，为阻力。
感应速度由，
（6）其中r和q是无人机旋翼的直径和数量，ρ是空气的密度。
无人机的实际功耗为:
(7）是无人机的功率效率。
任意无人机飞行距离d的总飞行能量为:
（8）为了实现悬停飞行，无人机的总重量必须与所有旋翼产生的推力总和相平衡。
无人机悬停实际功耗为:
(9)5 仿真与实验结果的比较
MACO算法主要用于寻找无障碍区域的最优路径。它有三个参数，即信息素指数(α)、距离指数(β)和信息素衰减率(ρ)，这三个参数对算法的影响最大。这些参数设置因应用程序而异，每种情况下都必须达到最优值。为了获得寻找最短距离的最优参数，通过改变这三个参数进行灵敏度分析。
5.1 敏感性分析
通过改变这三个重要的MACO参数(α、β和ρ)进行灵敏度分析，对所提出的算法进行了分析。参数α控制信息素沉积的权重，β对计算的欧几里得距离施加权重，ρ控制信息素衰变的速率。通过大量的试错运行来改变这些参数值的主要目的是找到这些参数的最优值，从而实现高效的性能。考虑这些参数在四个不同水平上的变化，进行多次实验所需的敏感性分析，如表2所示。表3给出了实验结果与计算均方误差(MSE)的正交数组，图2显示了这些参数的水平变化趋势
各层次MSE趋势
所有这三个参数在决定整个模型的性能时都是相互关联的。此外，选择参数α和β的值从0.25开始的意图源于这样一个事实，即如果我们选择α = 0，那么它意味着模型将纯启发式(距离度量)。如果我们选择β = 0，则表示该模型完全取决于信息素浓度，而与ρ值无关。同样，ρ的水平从指定0.5开始，使信息素沉积的贡献达到最小值。这些方面在目前的实验研究中都是有益的。此外，每个参数在确定最优路径方面的灵敏度如图3所示。显然，达到最优路径的最佳参数设置是α = 1， β = 1， ρ = 0.95。
模型参数的灵敏度
图4展示了二维箱形图分析，以百分比表示MACO算法的三个参数(α， β和ρ)变化的性能分布。alpha的指数和距离参数的指数在0到2之间均匀变化，以显示它们在该模型上的性能分布。显然，参数α在获得88 ~ 95%的性能百分比范围内具有更大的影响，参数β在88 ~ 93%的性能百分比范围内具有更大的影响。从ρ参数也可以看出，衰减率对性能的影响更大，达到65 ~ 69%的低范围。表4提供了用于模拟研究的参数及其值的列表。
模型参数的分布及其性能
5.2 三维环境下的最优路径规划没有障碍的政府
使用Python编程对有障碍物和无障碍物环境进行了仿真。仿真中考虑的无人机和电池的各项参数如表5所示。选择无人机的巡检区域为100 × 100 m，检查点随机分布在指定区域内。用于模拟的操作系统是64位ubuntu 18.04.5，在一台具有16gb内部RAM和Nvidia Quadro k620的PC上。模拟环境被认为是一个100 × 100的网格，每个单元大小为1个单元。节点、悬停点集合及其坐标如图5所示。在此无障碍物环境下，采用MACO算法求解最优路径。
3D无障碍环境
模拟是通过改变蚂蚁的数量来实现的。从表6可以明显看出，在考虑蚂蚁数量最多为6的情况下，路径得到了优化。由于MACO，与没有蚂蚁相比，路径长度减少18%，执行时间减少10%。
5.3 三维环境下的最优路径规划有障碍的政府
无人机导航在易障碍物地区，特别是在3D环境中，是具有挑战性的(Pereira de Carvalho 2018)。有效的路径规划算法是避免障碍物和寻找最优路径的必要条件。本文采用MEA*算法避障，采用MACO算法确定最优路径。最近，由于电池的存储容量有限，无人机应用的节能路径规划已经很有前景。确定了一种节能的最优路径规划器，并将理论计算的能耗与实验结果进行了比较。在三维环境中障碍物的数量是变化的，如图6所示，使用这两种算法进行仿真，通过避开这些障碍物找到最优路径。
带有障碍物的3D环境a 5个障碍物，b 10个障碍物，c 15个障碍物
仿真结果如图7所示。观察到，混合MACO-A*算法对障碍物边缘的跟踪是不利的，并且会增加路径长度和执行时间。然而，Hybrid MACO-MEA*算法并没有对图8所示的边缘进行跟踪，也没有有效地找到最优路径。MACO-A*和MACO-MEA*算法在避免障碍物数量增加的各种性能指标上的比较如表7所示。观察到MACO-MEA*的性能优于MACO-A*的各种参数，如行驶距离减少3%至4%，转数减少50%，执行时间减少20%，能耗减少21%。
混合ACO-A*算法的仿真结果a为5个障碍物，b为10个障碍物，c15个障碍物
混合ACO-MEA*算法的仿真结果a为5个障碍物，b为10个障碍物，c为15个障碍物
6 通过无人机飞行测试实时实现开发的算法
飞行试验使用定制的无人机平台在室外环境中进行。所提出的实验工作所使用的四旋翼无人机集成了Digi Xbee模块，机载计算机树莓派3系统作为同伴计算机和飞行控制器如图9所示。利用机载处理器向飞行控制单元提供必要的控制命令，实现有效导航。Xbee模块被用来通过地面控制站与无人机通信。该算法部署在同伴机上，指导内置飞行控制器有效地选择最优路径规划策略。同时，在地面控制站(GCS)中对无人机飞行最优路径的实时监控任务执行情况进行可视化。硬件和软件架构，包括使用GCS的任务规划器，其中最优路径是从仿真环境中输入的。
实验模型
预先给出巡检节点(无人机悬停位置)，实时确定最优路径。在此基础上，结合MACO算法和A*/MEA*算法，确定了节能的最优路径。确定的最佳路径使用机载计算机与无人机套件平台进行处理。它将位置信息、高度、速度和悬停时间发送给Pixhawk控制器。控制器采取必要的动作，实时实现节能最优路径。图10显示了整个硬件设置与机载计算机和飞行控制器。在航行的情况下。GCS提供最佳航路点，这是通过一个节能的最优路径规划算法确定的，该算法将被馈送到飞行控制器中。每个航路点的经纬度信息由车载GPS传感器获取。GCS软件显示从最优路径中提取的路点列表作为输出。
实现路径规划算法的实验框架
室外实验通过实时实现确定的最优路径进行。UAV的高度保持在15米，车速保持在2米/秒。图11显示了在我们大学校园进行的实时飞行试验。车载计算机从GCS接收航路点列表，并实时执行路径规划算法。基于航路点得到无人机的期望位置、速度和偏航角，控制器将控制信号发送给电机实现导航。此外，对无人机进行避障测试，如图12所示。
无人机实时飞行试验导航
无人机避障
无人机在导航过程中的稳定性被认为是一个重要的因素。无人机的姿态、位置和高度由飞行控制器产生的反馈信号控制。研究了无人机在机动过程中的横摇、俯仰和偏航运动。从图13a-c可以明显看出这一点。无人机的大部分飞行稳定性良好，无人机的位置在跟踪期望航路点到达目的地方面也取得了良好的性能，如图14a-c所示。此外，在飞行模式下也监测了电压和电流消耗，从图15中可以明显看出令人满意的性能
无人机姿态
.jpg)
无人机位置
无人机的电压和电流消耗
计算了两种情况下无人机的总能耗，从表8中可以明显看出，在障碍物数量区域的三种情况下，在3D环境中，通过避开障碍物到达目的地，Hybrid MACO-MEA*算法比Hybrid MACO-A*算法减少了21%的能量。执行时间是最小的，这将非常适合无人机路径规划在一个3D环境。因此，混合MACO-MEA*算法可以很好地用于集群环境中的导航。表8比较了两种算法的仿真和实验结果，可以明显看出Hybrid MACO-MEA*算法在执行时间、路径长度和避障能力方面都优于Hybrid算法。结果表明，理论计算结果与实际计算结果具有99%的一致性。此外，MACO-MEA*算法的执行时间比MACO-A*算法少55%左右，因此它可以很好地适应在集群环境中通过避障找到最优路径。
图16描绘了导航中遇到不同数量障碍物时MACO-A*和MACO-MEA*的避障3D路径，图17显示了MACO-A*和MACO-MEA*算法在飞行轨迹成功后在QGCS软件中执行的15个障碍物情况下的飞行轨迹样本。很明显，混合MACO-MEA*遵循了最短路径，通过避开障碍物到达预期目的地。结果表明，该算法具有较强的全局搜索能力，可以进行并行和分布式计算，收敛速度快，对环境的适应性强。它避免了边缘的跟踪，非常适合于高维空间。该算法的缺点是需要选择蚂蚁的数量来寻找最优路径。它需要大量的试验来最终确定要考虑的蚂蚁数量。此外，障碍物数量的增加会导致迭代次数的增加，从而导致收敛时间的增加。结合黑猩猩优化算法(Khishe and Mosavi 2020)，通过自适应调整对最优距离敏感的各种参数，避免了局部最优，提高了算法在无人机路径规划应用中的收敛速度，提高了算法的混沌性。此外，GWO (Lv et al. 2022)、GSA (Wang et al. 2021)和IPO (Mozaffari et al. 2016)算法可以与MACO-MEA*相结合，在动态环境下进行高效导航，确定先验蚂蚁数量，提高搜索能力。
MACO-A*和MACO-MEA*避障路径。A 5个障碍，b 10个障碍，c 15个障碍
15个障碍物的飞行轨迹。a MACO-A*， b MACO-MEA*算法
7 结论
目前的工作重点是将MACO和A* /MEA*算法的能力相结合，并对无人机的能量消耗进行模拟，以在3D环境中找到节能的最优路径，同时避开障碍物。利用MACO算法对有障碍物和无障碍物情况进行了仿真。研究发现，与没有蚂蚁相比，路径长度减少了18%，执行时间减少了10%。此外，对于障碍物数量不同的情况，所提出的混合MACO-MEA*算法在不跟踪路径长度最小的网格的情况下，在避开障碍物方面取得了优异的性能。它在各种参数方面都优于MACO-A*，如行驶距离缩短3 - 4%，避开障碍物的圈数减少50%，执行时间缩短20%，能耗减少21%。
另一方面，通过实现最优路径，在室外环境下进行无人机实时飞行试验，无人机能耗比MACO-A*算法降低21%。MACO-MEA*算法的执行时间比MACO-A*缩短55%。仿真结果与实验结果具有99%的一致性，表明所提出的算法及其结果可以很好地用于更密集环境下的路径规划。因此，所开发的Hybrid MACO-MEA*算法已被证明是一种精通的框架，可以在三维环境中避开障碍物并有效地找到节能的最优路径。该实验框架可以很好地用于在易障碍物区域部署无人机，用于无人机能源消耗是主要关注的多方面应用。此外，开发的节能框架的含义将非常适合各种类别的无人系统，移动机器人和其他具有严格记忆要求的自动驾驶车辆，以实现高效的自主导航。该方法在已知环境下性能良好，能有效避开静态障碍物。相比之下，在不久的将来，它也可以进一步扩展到通过避免未知环境中的动态障碍物来应对。此外，在未来，将尝试使用深度学习方法来理解障碍物的几何特征，从而使它们能够避开实时障碍物。
下载原文档：https://link.springer.com/content/pdf/10.1007/s12652-022-04098-z.pdf