基于优化蚁群算法的无人机海岛监测航迹规划

文/陈乐珠 李钢

无人机作为一种新的遥感监测平台起着非常重要的作用。在粤东地域的四个城市中特别是汕尾市，五个县区中有四个县区濒临南海，利用无人机进行近海海岛监测，可大大减少人力物力的浪费。然而，无人机在进行海岛监测时会遇到气流不稳定等因素而影响无人行飞行，因此对无人机进行航迹规划非常有意义。目前，国内外的航迹规划控制算法主要分为两大类，传统经典与人工智能算法。传统经典包括动态规划法，导数相关法，最优控制法，动态规划算法在解决多级决策最优化问题中比较常见的算法之一，该算法受状态空间限制，对于无人机的航迹规划大范围的搜索，比较有局限性；导数相关法中，常见的有牛顿法和最小二乘法等，要求导函数有连续性，迭代运算量大，容易陷入局部最优解。最优控制比较广泛应用于火箭、卫星轨道等。智能算法中包括遗传算法，例如文献，对于遗传算法，在进行规划路径时比较费时，另外一种常见的蚁群算法，例如文献，该方法收敛速度较慢。以上国内外所提到的各种路径算法都有各自的局限性，适应于完成特定的路径规划等任务。然而，对于本课题的研究来说，因为本课题有一种的空间及环境因素，所以，本文结合以上的研究基本上，通过MAKLINK 图论建立二维路径规划空间模型 ，利用Dijkstra 算法规划无人机初始航迹，融合蚁群算法优化路径，根据蚂蚁搜索到更短、更准的航迹规划。

1 Dijkstra算法和蚁群算法

在二十世纪50年代，荷兰计算机科学家狄克斯特拉提出了一种典型的单源最短路径算法，命名为Dijkstra 算法，用于计算非负权值图中一个节点到其他所有节点的最短路径。

蚁群算法是由Dorigo.M 等人提出来的，启发于蚂蚁在寻找食物的过程中，蚂蚁所经过的地方会释放一种分泌物，该分泌物叫信息素，只要在一定范围内，其它蚂蚁就能通过该信息素获取路径信息，后继蚂蚁也会选择信息素浓度较高的路径，同时把自己的信息素留下，从而使该路径信息素不断增加，蚂蚁们选择的路径概率大的就是蚁群算法寻找的最优路径。

以上两种算法都能找到最短路径，蚁群算法通过信息素更新得到最优路径，然而信息素更新速度较慢，严重地会影响无人机的航行任务，Dijkstra 算法规划速度快，但是迭代次数多的情况下误差率较高。通过研究设想，如果先由Dijkstra 算法规划初始航迹，再与蚁群算法融合，这样即提高无人机航迹规划效率又提高航迹规划最优率。

2 优化蚁群算法的实现

算法流程图如图1所示。

利用Dijkstra 算法在MAKLINK 图上产生依次通过路径节点 的一条次最优路径。节点对应的自由链接线依次为。设 和 为Li的两个端点，链路上的其他点表示方法为：

图1：算法流程图

其中，i 为链接线上所有点的集合；q 为[0,1]区间的随机数；q0为[0,1]区间的可调参数；为启发值；为信息素。j 的计算方法为：首先依次计算当前链接线节点i 到下条链接钱节点j 的选择概率，然后根据选择概率采用轮盘赌法找出下一个节点j，的计算公式为：

式中，信息素更新公式：

3 仿真与分析

为了验证优化算法的有效性，使用Matlab 软件编程实现优化蚁群算法的仿真，在200×200 的二维空间，设置四个二维障碍物仿真为海岛群，海岛1 顶点坐标分别为（40 140；60 160；80 140；60 120），海岛2顶点坐标分别为（50 30；30 40；80 80；100 40），海岛3 顶点坐标分别为（120 160；140 100；180 170；165 180），海岛4 顶点坐标分别为（120 40；170 40；140 80），S（20，180）作为起点，T（160，90）作为终点。蚁群算法种群数量m=10，循环次数N=500，信息素初始值 =2。

表1：算法优化前后运行时间统计

图2：航迹规划图

图3：航迹规划迭代变化

仿真结果如图2所示；图2中，黄色虚线为改进前算法得到的航迹，红色实线为算法优化后的航迹，后者航迹总距离更短，大大提高无人机完成航行飞行任务。图3为航迹规划迭代变化曲线。为了验证优化后的蚁群算在运算过程中消耗的时间更短，对系统运行十次，把测试的结果记录下来，如表1所示。从表1可看出，优化后算法运行时间比未优化的算法运行时间平均快30%，前者效率较高。

4 结束语

本文通过融合蚁群算法仿真得到优化航迹规划路径，仿真结果表明，该融合得到的优化算法，比改进前的蚁群算法求解时间快、规划路径准确、迭代过程中系统稳定的特点，从而保证无人机在复杂的海岛监测中飞行航迹规划零失误。通过该算法应用于海岛监测，具有一定的应用价值。然而该算法模型局限于二维空间，为了使模型更真实，规划路径更准确，可在此基础上对三维空间进行建模改进研究。