基于蚁群算法的一种无人机二维航迹规划方法研究

杨雅宁+蔺勇

摘要：蚁群算法是一种启发式搜索算法，具有全局搜索、强鲁棒性、并行性等特点，近年来在无人机航迹规划领域中的研究与应用十分广泛。本文针对中小型民用无人机的使用背景、模式和使用环境，引入对应的航迹约束条件，基于蚁群算法提出了一种新的无人机二维航迹规划方法，并进行了仿真验证。实验结果表明，该方法能够有效的规划出满足飞行要求的最优航迹路径。

关键词：无人机；航迹规划；蚁群算法

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）28-0189-03

近几年，随着国内无人机产业的迅猛发展，无人机在民用领域得到了广泛应用，主要用于执行监控安防、测绘勘察、农情监测、新闻采集、电影制作、灾害救援、电力巡线等任务，占据了无人机市场98%的销售额。航迹规划[1]技术是无人机飞行和任务控制系统的重要组成部分，也是实现无人机智能控制的关键技术之一，它是指在特定约束环境下，寻找满足无人机机动性能及作业环境信息限制的，从起飞点到任务点，再回着陆点的最优飞行轨迹。因此，无人机航迹规划问题可以转化为带有特定约束条件的TSP最优路径求解问题。蚁群算法是启发式搜索算法的一种，自1992年由M. Dorigo等提出以来，基于其全局搜索、并行式分布计算、鲁棒性强、易于其他算法结合等优点，被广泛应用于求解TSP问题。经过多年的研究与发展，呈现出了众多的蚁群算法的改进版本，为解决高难度复杂优化问题提供了高效的手段，在无人机航迹规划领域也得到了广泛的研究与应用[3]。

本文首先研究了中小型民用无人机的应用背景、模式、环境和约束条件，分析了民用无人机的航迹规划模型需求和现有基于蚁群算法的无人机航迹规划问题的研究现状，建立了一种新的航迹规划模型，并基于此提出了一种无人机二维航迹规划方法，最后进行了仿真验证，并对仿真结果进行了分析。

1 问题描述

1.1 民用无人机航迹规划需求

民用无人机在使用时，为降低使用成本，首先，无人机执行完任务后的要进行回收，且一般起飞点与回收点为同一区域；其次，一个飞行架次一般包含多个任务，有多个任务航点。因此，除无人机转场外，一般情况下，无人机的飞行航迹都是从起飞航点出发，到各个任务航点执行任务，然后再返回着陆回收航点（即原起飞航点）的过程。同时，民用无人机在使用时还受任务区地理环境、气象环境等威胁及无人机自身航时航程等限制。

一般情况下，民用无人机执行任务前就已明确本次飞行的起飞航点、着陆回收航点、一个或多个任务航点以及航路上的威胁区域，航迹规划问题转化为从起飞航点出发，避开威胁区域，寻找一条历经所有任务航点的最优路径问题，如图1所示，图中椭圆区域为地理或气象等威胁区域，无人机起飞航点和着陆（回收）航点为同一航点，共包含7个任务航点。因此，航迹规划问题可以转化为在一定的约束条件下求解TSP最优路径问题。

文献[4]、文献[5]、文献[6]和文献[7]都基于蚁群算法提出了不同的航迹规划模型，并能有效规划出从起飞点到目标任务航点的折线最优航迹，如图2所示，。归纳起来，文献中所提出的航迹规划模型都未考虑无人机的回收问题和多任务航点问题，这并不符合无人机的使用模式，如图2所示。

1.2无人机航迹规划模型

在一般情况下，无人机执行任务都是在固定高度定速飞行，只有在起飞和着陆阶段才有高度和速度的变化，同时为了便于分析，可以忽略高度影响，本文在二维环境下研究无人机航迹规划问题。

设定航点集合为

其中，为航点个数，为起飞和着陆回收航点，其它航点为任务航点。设无人机某一飞行架次的总航程为：

其中，为每段航迹的航程。航迹段受该段航路上约束条件控制，例如气象威胁、地理等。设约束集合为，其中，为威胁区域的个数，可以等效为圆心为、半径为的圆形区域。对于任意两个航点和，形成的航段为，

因此，无人机的航迹规划问题就是剔除威胁航段后，从起飞航点出发，寻求一条经历所有任务航点的最优路径问题，这与TSP问题的描述是一致的。

理论上，以下三种情况下当所有航点之间的航段均属于威胁航段时，或者某个航点仅与其他航点中的一个航点存在安全路径时，在这种情况下，可能无法得到一条最优化航迹，这不属于本文讨论的范围。

2 基于蚁群算法的航迹规划方法

2.1 蚁群算法基本原理

蚁群算法的定义及其基本原理由Dorigo给出了完整的描述。在解决TSP组合优化问题领域有广泛的应用及研究。在基本蚁群算法中，蚂蚁根据各个城市节点连接路径上的信息素浓度决定其下一个访问的城市，是选择路径时的转移概率，其计算公式为：

是城市与之间的信息素浓度，是城市与之间的可见距离，是城市与之间的距离，是信息素系数，是绝对距离系数。

信息素更新公式可以用式（3）表示：

其中，表示信息素挥发系数，其值介于0和1之间。是城市与之间的信息素，由式（5）表示。

是蚂蚁信息素增加强度系数。

2.2 基于蚁群算法的航迹规划方法

在无人机航迹规划问题中，起飞航点是已知的，因此，在蚁群算法中蚂蚁的出发城市不是随机的，而是指定为起飞航点；同时由于存在威胁区域，导致某些航段属于禁忌航段，应该剔除。因此，基于蚁群算法的航路规划步骤如下：

1）初始化信息素系数、绝对距离系数、信息素增加强度系数和信息素挥发系数，蚂蚁个数、航点个数，威胁区域；

2）判断任意两个航点构建的航段是否属于禁忌航段，若属于禁忌航段，则被赋予为及大的值，同时，标识该航段被剔除；否则是航点与航点之间的欧拉距离，标识该航段为安全航段；

3）将蚂蚁放置于起飞航点，并将起飞航点添加到蚂蚁禁忌表中；

4）按照蚂蚁转移概率，选择下一个转移航点，直至遍历完所有航点；

5）计算本次历经总航程，比较航迹路径；

6）更新航段上的信息素；

7）输出最优航迹路径。

3 仿真与分析

为了验证本文航迹规划方法的有效性，分别用表1中的两组数据进行实验。实验环境硬件为Intel（R）Core（TM）i7-5820K @3.30GHz CPU，软件环境为Win7操作系统、VS2010、MATLAB11.0。实验中首先在MATLAB11.0下绘制无人机飞行区域，包括任务航点及威胁区域；其次，在VS2010开发环境下建立无人机航迹规划模型，计算出最优的安全航迹路径；最后，为了更明了地表述规划出的迹路径，手动将路径依次添加到无人机飞行区域，形成航迹路径图。仿真结果如图3和图4所示，结果表明，航迹规划如表1所示条件下，本文的方法能够规划出满足飞行要求的最优航迹路径。

理论上，当所有航点之间的航段均属于威胁航段时，或者某个航点仅与其他航点中的一个航点存在安全路径时，在这种情况下，可能无法得到一条最优化航迹，这不属于本文讨论的范围。

4 结束语

本文首先研究了中小型民用无人机的应用背景、模式、环境和约束条件，分析了民用无人机的航迹规划模型需求和现有基于蚁群算法的无人机航迹规划问题的研究现状，建立了一种新的航迹规划模型，并基于此提出了一种无人机二维航迹规划方法，最后进行了仿真验证。仿真结果表明，在给出的任务航点和威胁区域满足一定要求的情况下，本文提出的方法可以有效规划出满足飞行要求的最优航迹。

参考文献：

[1] 缪永飞，钟珞，陈艳恩，等.改进免疫算法在无人机航线规划中的应用[J].武汉理工大学学报（信息与管理工程版）， 2015（2）.

[2] 牛治永，李锦军，岳冬梅，等.无人机三维航迹规划算法研究[J].自动化技术与应用， 2013， 32（11）.

[3] 房建卿，王和平.云模型蚁群算法在无人机航迹规划中的应用[J].科学技术与工程，2012（2）.

[4] 唐必伟，方群，朱占霞，等.基于改进蚁群算法的无人飞行器二维航迹规划[J].西北工业大学学报， 2013，31（5）.

[5] 唐必伟，朱占霞，方群，等.基于改进蚁群算法的无人驾驶飞行器三维航迹规划与重规划[J].西北工业大学学报， 2013， 31（6）.

[6] 郭琦，潘广员，杨江涛.基于Voronoi图和动态自适应蚁群算法的UAV航迹规划[J]. 计算机测量与控制， 2014， 22（9）.

[7] 高颖，陈旭，周士军，等. 基于改进蚁群算法的多批次协同三维航迹规划. 西北工业大学学报[J]， 2016（1）.

[8] David B. KirK， Wen-mei W. Hwu. 大规模并行处理器编程实战[M]. 北京： 清华大学出版社， 2013.