基于蚁群算法的无人机航迹规划研究

牛昭文，罗银辉

（中国民用航空飞行学院计算机学院，广汉618307）

0 引言

无人机执行任务的复杂化，使得无人机航迹规划的研究越来越被重视。其目标是在现实允许的时间内寻找最优或较优的飞行航迹，是确保无人机提高飞行器效能，圆满完成任务的技术保障。无人机航迹规划是指在综合考虑无人机性能约束、威胁约束、任务约束等多方面约束条件下，为无人机规划出一条满足约束的飞行轨迹[1]。根据对各领域和常用路径规划算法的研究，参照算法的时间发展历程和对应的基本原理，可将算法种类分为：传统算法、图形学算法、智能仿生学算法和其他算法[2]。作为智能仿生学算法中的蚁群算法，以其优越的性能和特点，正逐步被应用到规划、商旅、调度、排序等诸多问题中。因此，蚁群算法可以作为实现无人作航迹规划的搜索算法，并输出无人机最优航迹解[3]。

本文通过运用蚁群算法，对无人机在三维电子地图中的航迹进行规划，并通过MATLAB 仿真软件编程加以实现，最终输出基于蚁群算法的无人机三维航迹最优解。

1 蚁群算法概述

1.1 蚁群算法描述

蚁群系统（Ant System 或Ant Colony System）最早是由意大利学者Dorigo 和Maniezzo 等人在20 世纪90年代所提出的。1992 年，Marco Dorigo 在他的博士论文中正式提出了这种寻找优化路径的概率型算法——蚁群算法，随后吸引了一大批世界各地的学者竞相研究[4]。

研究发现蚁群中单个蚂蚁的行为较为简单，但是整个蚁群却可以体现一些智能化的行为方式。以蚁群觅食为例，这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。在后续的研究中发现，蚂蚁会在其经过的路径上释放一种物质，称之为“信息素”。蚂蚁对“信息素”的感知能力极强，它们会沿着“信息素”浓度较高的路径行走，而每只经过的蚂蚁又会重新留下“信息素”以加深此路径上的信息浓度，因此形成了一种正反馈的机制。一段时间过后，整个觅食的蚁群就会沿着这条最短路径到达食物源所在的觅食区了[5]。

Goss 等学者在1989 年为了对蚁群的觅食行为做更深层次的研究，进行了“非对称双桥实验”。如图1所示，觅食去和蚁穴之间由非对称双桥相连，蚁群需要经过非对称双桥抵达觅食区觅食。在觅食初期阶段，由于蚁群未在所有可行的行动路径上留下信息素，因此，蚁群可随机自由选择路径抵达觅食区，即通过左右两侧路径的概率相等。分别在实验开始的4 分钟和8分钟做记录和比较，观察得较短路径上的蚂蚁个数逐渐增多，残留下的信息素也随之增多，越来越多的蚂蚁被此条最短路径所“吸引”。该实验表明，蚁群在觅食行为中，总能找到一条蚁穴至觅食区之间的最短路径，并且被绝大多数的蚂蚁共享，同时也印证了蚁群具有较强的适应能力，引申至蚁群算法中，表现为自适应性强。

图1 蚁群非对称双桥实验示意图

1.2 蚁群算法优点

蚁群算法是通过观察真实蚁群的生活习性，研究蚂蚁在觅食中的现象而形成的算法，因此蚁群算法继承了真实蚁群系统的诸多特点[6]。现将蚁群算法的优缺点进行罗列比对，其具体优点归纳如下：

（1）自适应性强

蚁群算法可以不借助外界因素的帮助而高效、有序地运行，具有较强的自适应性。蚁群特有的信息共享机制和搜索机制是蚁群自适应性的基本保障。基于此特性，蚁群在行为决策和系统调整时，也能保证蚁群整体架构继续可靠地运行。

（2）鲁棒性优越

蚁群算法之所以广泛应用在各个领域中，关键因素就是其鲁棒性优越，在外界干扰下，也能保证固有的特性继续保持，体现为稳定鲁棒性和性能鲁棒性两点。蚁群算法通过调整概率转移模型来求解问题的最优解，而算法的收敛程度不受参数、概率模型的改变而改变。

（3）并行计算能力强

并行计算是指能够同时使用多种运算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。蚁群算法能够独立有效地求解搜索空间中的最优解，使运算过程同步进行，在产生信息素的同时，协同合作，继续搜索，确保了搜索方向的可靠性。

（4）全局搜索能力强

在面对复杂环境的搜索任务时，往往需要算法将所有可能的解呈现出来，因此，在某些特定应用场景下，需要体现出相应算法的全局搜索能力。而蚁群算法中的每个蚂蚁都作为一个信息素，对全局进行搜索并传递信息，所以蚁群算法具有极强的全局搜索能力。

（5）易结合，通用性好

蚁群算法易于与其他算法相结合，通过在算法性能上的互补，来求解最优解以展现算法的高性能，此特点完善了混合智能算法的应用，使得蚁群算法在解决诸多问题上可以通用。

1.3 蚁群算法模型

蚁群算法在推广之初，主要应用于解决组合优化中旅行商（TSP）的问题，旅行商需要按照一定的顺序访问城市，保证从出发城市开始至返回出发城市的过程中，每个城市只访问一次，且所选路径最短[7]。

以旅行商问题为例，参照表1，引入以下蚁群算法数学模型中的参数符号。

表1 蚁群算法数学模型参数符号

蚁群算法数学模型的状态转移概率公式可表示为：

其中，allowedk为蚂蚁k 还未曾到访的城市，allowedk={C - tabuk} ；α、β 均为常数。蚂蚁在每走完一步或经过每一个城市之后，都要对路径上的信息素进行更新替换，此举是为了防止在某条路径上的信息素残留过多，导致启发信息失去作用，为此，城市i 与城市j 之间的信息素规则更新如下：

图2 蚁群算法流程图

2 航迹规划建模

2.1 栅格法划分三维空间

栅格法是一种地图建模方法，通过将地图进行单元分割，用大小相同的方块表示，来直观地分析路径规划等问题。栅格地图的精度取决于栅格块的大小，栅格区域越小，地图信息就越清晰。三维空间也同样采取栅格法进行划分。以中心点为起始点，在三维空间下，周围共计26 个相邻节点。设三维规划空间的8 个点坐标分别为：(xmin,ymin,zmin)、(xmax,ymin,zmin)、(xmax,ymin,zmin)、(xmin,ymin,zmax)、(xmax,ymax,zmin)、(xmax,ymin,zmax)、(xmin,ymax,zmax)、(xmax,ymax,zmax)；则三维空间各方向栅格数分别为nx、ny、nz，栅格节点总数为n=nx×ny×nz。

2.2 信息启发因子

3 仿真研究结果

为验证蚁群算法在航迹规划问题上的求解性能，本节以三维空间电子地图为例，如图3 所示，进行仿真验证。具体求解问题为：以图3 中三维电子地形图为依据，求解从A 点到B 点的基于蚁群算法的三维航迹规划问题。

图3 航迹规划问题起始点、目标点示意图

在电子地图中设置两点地形威胁，具体参数参照表2。

表2 三维路径规划参数及数值

设置地形威胁1#、2#的威胁半径分别为：2000m、3000m。地形威胁在电子地图中，可表示为以不同色圆柱体，其仿真结果如图4 所示。

图4 基于蚁群算法的三维航迹规划仿真示意图

4 结语

通过上述实验仿真结果，可以发现蚁群算法在求解无人机航迹规划问题中的优越性。本文研究了基于蚁群的无人机三维航迹规划，并利用MATLAB 软件进行编程，实现了该算法求解航迹的仿真结果，同时，蚁群算法可用于解决实际无人机飞行一些相关问题，具有一定的实际意义。而通过MATLAB 编程和仿真，有助于无人机航迹更好地展示。