叶家君， 刘学文， 蒋 莎

(重庆师范大学 数学科学学院 重庆 401331)

近年来，由于地震、洪水等的频繁发生使得无人机的研究成为国内外的一种新潮。如何规划无人机的路线，快速探测生命迹象以及对灾区的信号传输是无人机的一个重要使命。目前国内外学者对无人机的航迹规划进行了大量的研究。孙小雷等[1]研究了多无人机交会过程的协同航迹规划，提出了沿Dubins路径飞行，建立了以最小化执行时间降低风险的双目标规划方法，实现了无人机可攻击范围的交会。李牧等[2]提出了基于3层决策模型的平滑航迹规划方法，在不同场景地形的仿真，得到了较高的可执行性、安全、平滑的飞行路径。Wen等[3]建立了规划成本最低、路径搜索最快和路径威胁最小的多目标优化模型，引入RH方法解决了动态未知局部环境下的航迹规划，用蒙特卡洛进行结果仿真，证明了该算法在实际路径规划中具有突防可能性。Chen等[4]提出了改进的狼群搜索算法，计算了三维真实空间和虚拟空间中无人机的最优航迹，构建了多目标成本优化模型，仿真结果证明，改进后的WPS算法生成轨迹优于原算法和随机搜索方式。周青等[5]分析了无人机航迹规划的路径有效性和到达时间约束，并将遗传算法应用到动态环境中，通过编码，明确适应度函数和进化操作，实现了针对移动目标的规划和突然出现威胁的局部重规划。傅阳光等[6]在分析时间误差分配基础上，研究了起飞时间误差、速度调节能力以及飞行速度误差3个因素对目标点时间误差的不同影响。张延松[7]指出了无人机航迹规划的定义，根据威胁及障碍分布情况，构造了无人机可能飞行的航路集voronoi图，采用Dijkstra算法搜索威胁及障碍分布图，最后通过遗传算法优化初始路径，并进行仿真实验。马华伟等[8]建立了UAV流模型，提出了一种两阶段启发式算法。第一阶段提出了一种基于“最迟完成服务优先”规划的航迹，第二阶段利用模拟退火算法对初始值进行改进，表明了该算法能有效求解带有时间窗的UAV航迹问题。

本文以总路程最少和时间均衡度最小为目标，在无人机飞行约束条件下，建立了双目标优化模型。在模型求解时，通过引入混沌序列遗传算法对模型进行求解，充分对双目标进行平衡，得到更合适的航迹优化路线。

1 多目标优化模型

1.1 问题描述与假设

无人机航迹优化路线是一个动态的过程，航迹过程中最显著的特点表现在路线的最短化。以往的无人机航迹优化路线局限于把“路线最短”作为优化目标，容易导致不同无人机航迹时间间隔较大。因此，考虑“路线最短”和“时间均衡度最小”，在巡查有效区域内，构建综合可靠性高的优化路线。为了更好地分析问题，设立6个假设如下。

假设1 无人机在执行任务时不存在强风、暴雨等天气问题影响。

假设2 无人机在拐点处均以其最小转弯半径进行方向转变，且行驶距离不变。

假设3 不同无人机飞行状态不影响飞行速度。

假设4 无人机的位置始终处于最大有效探测距离内。

假设5 无人机看成质点，忽视无人机大小、质量。

假设6 所有无人机同时起飞。

1.2 多目标优化模型

由以上问题和分析可知，在无人机飞行高度及巡查范围受到限制的情况下，构建的目标优化模型如下。

(1) 目标函数。首先考虑无人机航迹路线最短化，即无人机从各基地出发到最后返回各基地距离的加权值最小。子目标如下：

考虑到无人机航迹时间间隔最小化，即第一架无人机飞出时间与最后一架无人机返回时间的间隔最小。子目标如下：

保证同一架无人飞机pk受到燃油消耗的限制，其航行时间不超过8小时，即

根据上述分析，构建多目标优化模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

在本文中，将采用参数规划方法中的加权法来求解上述两个目标的航迹规划模型。通过调节两个目标赋值的权数，可以得出较为理想的结果。例如若α=1时，不再考虑均衡度，则所得结果将会出现第一架飞机飞出到最后一架飞机完成任务飞回到基地的时间间隔较长。若β=1，将不再考虑无人机飞行的总路程，则无人机可能在规定的时间无法完成任务。所以通过调整α和β的不同取值，将获得一组权衡节解。

2 遗传算法

显然，无人机航迹规划问题是一个NP问题，由于其解空间不连续，解空间表达困难，所以运用传统的运筹学优化方法不能满足其需求[9]。那么，结合模型特点及实际应用，将采用收敛性强，收敛速度快的遗传算法。

(1) 染色体编码。无人机航迹优化模型转换为遗传算法问题，在编码过程中将采用二进制串。根据无人机的架数将整个解空间分解为N个子种群，设每架无人机的航迹优化路线是一条染色体，将染色体分为I段，I表示无人机飞过的有效区域点的位置。

(2) 初始种群的产生。遗传算法尽可能获取全局最优解，与初始种群的选取有很大的联系，子种群生成n条染色体作为无人机航迹路线。

(4) 染色体轮盘选择。根据染色体的适应度，计算出每条染色体的选择概率以及累计概率pi，生成[0,1]间的随机数ri，若ri≥pi，则选择该染色体，重复这样n次操作，将得到n条染色体。

(5) 改进的交叉操作。传统的遗传算法交叉操作通常采用断点交叉法、多点交叉法和均匀交叉。根据本文的数学模型将采用改进型交叉。首先以“门当户对”为原则，对父代的适应度函数值进行排序，然后将父代目标函数值小的与小的配对，大的与大的配对。将采用Logistic混沌序列xn+1=4xn(1-xn)，随机产生一个数Q，从而确定交叉点的位置，最后对确定的交叉项进行交叉。

(6) 改进的变异操作。同样采用Logistic混沌序列xn+1=4xn(1-xn)，随机产生一个数Q，对选定的染色体Q处选择变异点进行变异。

(7) 终止。若满足则算法终止，计算结束，输出最佳适应值和染色体编码。根据染色体编码绘制出相应的无人机航迹路线。

3 实例分析

3.1 实例描述

为验证上述改进算法的有效性，以2017年全国研究生数学建模竞赛A题“无人机在抢险救灾中的优化应用”实例来验证。为了及时探测生命迹象，提供准确的目标定位，欲使无人机携带生命探测仪从基地H(110，0)和J(110，55)(单位：km)处总共派出30架无人机(各15架)对生命迹象进行探测。其中无人机探测仪的有效探测距离不超过1 000 m，最大侧视角为60°，最大续航时间为8 h，飞行时的转弯半径不小于100 m。在满足无人机的飞行条件和生命探测仪的工作条件下，规划合理路线，使得全区域内海拔3 000 m以下部分能被探测到的面积尽可能大，且使从第一架无人机飞出到最后一架完成任务的无人机回到基地的时间间隔尽量短。

3.2 栅格分区

通过无人机探测仪的有效探测距离以及最大侧视角，可知无人机可探测的最大面积以及无人机与地面的最大飞行高度。其次，分析哪些区域需要被巡查，可以利用“网络取点”的方法确定有效的巡查点。由于有效巡查点是由两个不同基地的无人机分别巡查。所以，将所有有效巡查点分成两个区域，分别由两个基地的无人机进行巡查，分区原则是两个基地分别到区域各点并且最后返回各基地的用时基本相等，并且最长航迹与最短航迹路线距离相差较短。通过分区将两个基地问题转化成了单个基地问题，分别对两个基地的无人机进行航迹规划，如图1所示。

图1 H，J基地航迹有效区域

3.3 路线优化

根据以上的有效巡查的分区，基于混沌遗传算法和构建的双目标模型，用MATLAB进行编程，得到无人机从H,J基地出发的航迹路线(图2)以及每架无人机的航迹路程和时间(表1)。

图2 H，J基地航迹路线

在仿真实验中，无人机航迹优化问题分别利用了单点交叉和换位变异结合的遗传算法，多点交叉和均匀变异结合的遗传算法以及本文中的混沌序列遗传算法进行求解比较(表2)，且都是以种群规模60，交配概率0.85，变异概率0.1和迭代次数500求解的无人航迹优化路程。

表1 H，J基地的无人机航迹路程及时间Table.1 Flight path and time of H，J base UAV

表2 遗传算法路程优化比较Table.2 Distance optimization comparison of genetic algorithms

〗 最后，通过对H基地和J基地计算时间对比，来说明改进遗传算法的时间性能(表3)。

表3 遗传算法时间性能比较Table.3 Time performance comparison of genetic algorithms

利用改进后强度最弱的单点交叉，保证了算法的收敛精度，削弱了算法因交叉强度大而产生的寻优抖振问题，而且文中采用了强度较大的多个基因变异解决了早熟问题。从表2可以看出改进后的算法效果更明显，减少了无人机航迹路程。通过以上的图和表格，可以得出以下的结论：

(1) 目标最小化模型可以有效处理无人机航迹问题，对于时间的均衡性可以有效调节无人机之间的时间间隔，能尽快完成全部任务。

(2) 从图1和图2可以看出，栅格分割以及将不同基地出发的无人机进行分区，更能避免无人机在执行任务时发生碰撞。

(3) 由表1数据可知，无人机最少花费时间2.456h，最多花费时间3.950h，则时间间隔为1.494h。所以本文所给的航迹优化模型以及混沌遗传算法是具有一定的可行性。

(4) 根据表2和表3可知，混沌遗传算法在求解无人机航迹优化模型时有较好的性能。

4 结 论

针对无人机探测生命迹象这一难题，构建了路程最短和时间均衡度最少的数学模型，设计了一种基于混沌遗传算法的求解。但是，本文仅对无人机探测生命迹象做了一个初步探索，旨在能探测到更多的有效区域。因此，今后的研究工作将进一步推广数学模型，希望无人机更广泛地应用在灾情巡查、灾区通信终端以及对地的数据传输。

参考文献(References)：

[1] 孙小雷，孟宇麟，齐乃明，等. 多无人机交会过程的协同航迹规划方法[J]. 机器人，2015，37(5)：621-627

SUN X L，MENG Y L，QI N M，et al. Cooperative Path Planning for Rendezvous of Unmanned Aerial Vehicles[J]. Robot,2015，37(5)：621-627

[2] 李牧东，赵辉，黄汉桥，等. 基于TLD模型的UAV三维实时平滑航迹规划[J]. 系统工程与电子技术，2017，39(1)：93-100

LI M D，ZHAO H，HUANG H Q，et al.3-D Real-Time Smooth Path Planning for UAV Based on TLD Model[J]. Systems Engineering and Electronics,2017，39(1)：93-100

[3] WEN N,ZHAO L L,SU X H,et al. UAV Online Path Planning Algorithm in a Low Altitude Dangerous Environment[J]. IEEE/CAA Journal of Automatica Sinica,2015，2(2)：173-185

[4] CHEN Y B,MEI Y S,YU J Q,et al. Three Dimensional Unmanned Aerial Vehicle Path Planning Using Modified Pack Search Algorithm[J]. Neurocomputing, 2017，266(29)：445-457

[5] 周青，张锐，索晓洁，等. 具有时间约束的无人机遗传算法航迹规划[J]. 航空计算技术，2016，46(2)：93-96，101

ZHOU Q，ZHANG R，SUO X J，et al. Genetic Algorithm for UAV Trajectory Planning with Timing Constraints[J]. Aeronautical Computing Technique,2016，46(2)：93-96，101

[6] 傅阳光，周成平，王长青，等. 考虑时间约束的无人机飞行器航迹规划[J]. 宇航学报，2011，32(4)：749-755

FU Y G，ZHOU C P，WANG C Q，et al. Path Planning for UAV Considering Time Constraint[J]. Journal of Astronautics,2011，32(4)：749-755

[7] 张延松.基于遗传算法的无人机航迹规划研究[J]. 中国西部科技，2010，9(11)：44-45

ZHANG Y S. Study on a Path Planning for UAV with Genetic Algorithm[J]. Science and Technology of West China,2010，9(11)：44-45

[8] 马华伟，王天晓，胡笑旋. 带有时间窗的无人机航迹规划两阶段启发式算法[J]. 火力与指挥控制，2014，39(8)：12-16，21

MA H W，WANG T X，HU X X. A Two-Stage Heuristic Method for UAV Path Planning with Time Windows[J]. Fire Control & Command Control,2014，39(8)：12-16，21

[9] 司守奎，孙玺菁. 数学建模算法与应用[M].北京：国防工业出版社，2011

SI S K，SUN X J. Mathematical Modeling and Application[M]. Beijing：National Defense Industry Press,2011