一种多火星飞行器路径规划方法

敖海跃 刘燕斌 李 瑜

1.南京航空航天大学航天学院，南京 211106 2.北京空天技术研究所，北京 100074

0 引言

火星探测一直是国际上深空探测的重点和热点[1]，1960年开始美国和苏联在火星探测领域进行了激烈的竞争，在2020年7月的火星探测窗口期，中国的火星探测器“天问一号”、美国的“毅力号”和阿联酋的“希望号”相继发射升空，将国际火星探测又推向一个新的高潮[2]。

火星环绕器能拍摄较为清晰的卫星照片，且工作寿命较长，但是无法做细致的探测；火星着陆车可以对火星表面进行细致的探测，但是探测范围很小，且火星着陆车的移动受到火星表面复杂地形的严重限制[3]；而火星飞行器则可以进行较为细致的探测，同时拥有较大的探测范围[4]，因此火星飞行器在国内外获得了广泛的研究。随着火星探测的深入、任务多样性程度的增加，由于单飞行器的探测范围和探测效率有限，有些任务依靠单架飞行器难以完成。而通过实现多架火星飞行器间的有效协同，则可以提高探测任务的效率[5]，因此多飞行器的协同任务规划问题被广泛研究。

路径规划是协同任务规划的重点，对提高飞行器的生存率和任务完成率有重要意义。路径规划是指给定起始点和目标点，考虑危险区等信息，在多种约束下，寻找到一条符合特定指标的最优路径[6]。目前有很多经典的路径规划算法：Dijkstra算法是较为经典的用于搜索最短路径的算法[7-8]，可在带有权重的复杂图中得到最短路径；A*算法基于Dijkstra算法，引入了启发式策略的思想[9]，该算法在很多场景都得到了较好的运用，但是对于复杂的地图信息求解的时间复杂度很高；人工势场法引入了虚拟力，规划出的路线较为平滑，且实时性好[10]，但是存在目标点不可达的问题。

随着智能优化算法的兴起，鸽群优化(PIO)算法、遗传算法和蚁群算法等也被应用到飞行器的路径规划中[11-12]。但是由于智能优化算法也存在易陷入局部最优的问题，规划出的路径通常为次优而非最优[13]，所以若想将智能优化算法更好地应用于路径规划中，还需要将智能优化算法进行改进[11]。

文献[14]在Voronoi图上使用A*算法实现战术导弹的路径规划，但得到的路径代价和转向角较大；文献[15]使用改进粒子群优化算法实现飞行器路径规划，但是当问题维度升高时规划可能失败。本文针对多火星飞行器，提出一种基于改进鸽群优化算法的多机协同路径规划方法，首先利用Dijkstra算法对Voronoi图划分的二维平面进行路径预规划，再利用改进鸽群优化算法进行路径优化。相比于文献[14-15]，该方法能保证规划成功且得到代价和转向角更小的路径。同时针对标准鸽群优化算法易陷入局部最优、收敛精度低的问题，本文提出采用柯西变异、交流因子和梯度信息改进的鸽群优化算法。

1 多火星飞行器路径规划系统建模

多火星飞行器进行路径规划的过程，首先要根据环境中各种危险区的分布情况，建立威胁模型。然后，对环境空间进行划分，建立相应的路径代价模型。此外，路径必须满足火星飞行器的飞行性能，这样才能保证规划出的路径具有实际意义。

1.1 威胁源建模

Voronoi图是一种表示点或实体集合近似信息的几何结构，被广泛应用于路径规划问题中[14]。根据环境威胁信息，取所有危险区的中心，依次生成危险区中心的中垂线(即Voronoi边)，将二维平面进行划分，生成初始的可飞路径集。由于Voronoi边上的点到相邻的两个危险区中心的距离相等，所以飞行器沿着Voronoi边飞行受到两个相邻危险区的威胁最小，安全系数较高。

如图1所示，Voronoi图中黑色填充的圆形是300m×300m飞行空域内的危险区，虚线表示的是Voronoi边，多机路径规划问题可以简化为在Voronoi图中寻找从起始点到目标点飞行代价最小的可飞路径。

图1 Voronoi图法环境建模

1.2 路径代价建模

威胁源建模后，还要为每条Voronoi边分配代价。由于多火星飞行器路径规划的目的是：在保证飞行器安全的前提下，尽可能地节省燃料，故本文主要考虑燃料代价和危险区代价。

飞行器可沿着Voronoi边的两个方向飞行，假设所有的飞行器都以恒定的速度飞行，那么每条边的长度和飞行该段距离所需时间成正比，同时也和燃料消耗成正比。每条边燃料的代价可以表示为：

(1)

式中：(x1,y1)为一条边的起始点坐标，(x2,y2)为结束点坐标，Jfuel为该条边的燃料代价。

本文主要考虑因火星的地形和气象等因素而产生的危险区，穿越该类危险区产生的代价非常昂贵，以至于飞行器不会选择进入危险区。若某条Voronoi边与危险区相交，所产生的危险区代价可表示为：

Jthreat=1010×Jfuel

(2)

式中：Jthreat为每条边为危险区代价。

1.3 火星飞行器的飞行性能

路径规划时必须考虑火星飞行器的飞行性能，否则得到的路径就没有意义。由于本文在二维平面内进行路径规划，所以主要考虑火星飞行器的最大航程约束和最大转向角约束。

飞行器在飞行的过程中，受到燃料和任务时间的限制，不能无限地飞行，假设一条完整的飞行路径由n条分段组成，则存在飞行器的最大航程约束：

(3)

式中li为第i条分段的长度，Lmax为最大航程。

本文以最大转向角描述飞行器的机动能力。假设一条完整的飞行路径有m个节点，则存在飞行器的最大转向角约束：

θj≤θmax

(4)

式中θj为第j个节点处的转向角，θmax为最大转向角。

2 多火星飞行器路径规划方法

2.1 多火星飞行器路径规划总体结构

本文提出的基于改进鸽群优化算法的多火星飞行器路径规划方法在总体上采用分层规划的结构，分为路径规划层、协同规划层和路径优化层。首先在路径规划层，利用Dijkstra算法在Voronoi图上为每一架飞行器预规划出到每一个目标点的备选路径[16]，并用视线路径法对预规划路径进行缩短[8]，初步消除不必要的转弯。然后在协同规划层，通过求解多维多选择背包问题(MMKP)在所有的备选路径中确定每一架飞行器的唯一路径。最后在路径优化层，利用改进鸽群优化算法优化路径规划层得到的路径，得到代价更小且符合火星飞行器飞行性能的最终路径。图2描述了基于改进鸽群优化算法的多火星飞行器路径规划方法的总体结构。

图2 多火星飞行器路径规划的总体结构

2.2 改进鸽群优化算法

针对标准鸽群优化算法易陷入局部最优、收敛精度低的缺点，为了提高路径规划问题的全局求解能力和最优解质量，本文在标准鸽群优化算法的基础上，利用柯西变异、学习因子和梯度信息3种策略改进标准鸽群优化算法。

2.2.1 标准鸽群优化算法流程

鸽群优化(pigeon-inspired optimization, PIO)算法[17]模型的建立主要包括：鸽群速度、位置等信息的初始化，在算法前期利用地图罗盘算子更新鸽群的速度与位置，在后期利用地标算子进行更新。

首先，初始化鸽群优化算法中的种群数量、迭代次数等信息，确定适应度值的计算方法。同时随机初始化鸽群的速度与位置。第i只鸽子的位置Xi、速度Vi可表示为：

Xi=[Xi(1)Xi(2) …Xi(n)]T

(5)

Vi=[Vi(1)Vi(2) …Vi(n)]T

(6)

算法前期利用地图罗盘算子迭代更新，第i只鸽子在第t次迭代中的速度为Vi(t)，位置为Xi(t)，当前鸽群中最优个体的速度为Vg，位置为Xi，迭代更新方法为：

Vi(t)=Vi(t-1)·exp(-Rt)+
r·(Xg-Xi(t-1))

(7)

Xi(t)=Xi(t-1)+Vi(t)

(8)

式中，R为地磁因子，视具体问题取值。r为在[0,1]上均匀分布的随机数。

算法后期利用地标算子迭代更新，第i只鸽子在第t次迭代中的位置为Xi(t)，当前鸽子的中心位置为Xc，更新后根据适应度值的大小将所有鸽子进行排序，每次迭代淘汰掉一半的鸽子，迭代更新方法为：

(9)

(10)

Xi(t)=Xi(t-1)+r·(Xc-Xi(t-1))

(11)

式中，NP(t)为第t次迭代后鸽子种群数量，F为适应度函数。

2.2.2 柯西变异

柯西分布在原点处峰值较小，而两端的分布较长，利用柯西变异可在当前变异个体附近产生较大扰动。因此，可通过引入柯西变异来增加种群的多样性，解决鸽群优化算法易陷入局部最优的问题[18]。

本文选取标准柯西逆累积分布函数对鸽子个体产生变异，标准柯西逆累积分布函数如式所示。在初始化后和地图罗盘算子后对全局最优Xg进行柯西变异，若变异后更优，则按式更新全局最优Xg。

(12)

Xg→Xg·kCauchy

(13)

式中：kCauchy为柯西算子，r为[0,1]上均匀分布的随机数。

2.2.3 交流因子

鸽群优化算法在地图罗盘算子后期存在过早收敛的问题，所以在算法寻优的过程中，可以通过控制后期局部搜索的速度避免这一问题[19]。

本文在鸽群优化算法中引入交流因子，来调节全局最优位置在地图罗盘算子阶段的影响权重，使算法后期具有较强的局部搜索能力。交流因子随着迭代次数的增加从0非线性地增加到1。因此将鸽群优化算法中速度更新公式更改为：

Vi(t)=c1·Vi(t-1)+c2·r·(Xg-Xi(t-1))

(14)

(15)

c2=1-c1

(16)

式中c1为惯性权重，c2为交流因子，A、B、C为常数，视具体问题取值。

2.2.4 梯度信息

鸽群优化算法依赖鸽群的随机搜索，没有考虑具体问题的特性，不利用求解对象的梯度信息，但利用梯度信息可以使鸽群的移动更有针对性和效率[20]。一个多元函数f的梯度可以表示如下：

(17)

式中NP表示鸽群的数量。

本文利用梯度信息影响鸽群的迭代更新。在地图罗盘算子阶段，鸽群中有一定比例P1的鸽子将沿着当前位置的负梯度方向前进。以第i只鸽子在第t次迭代中，其速度更新公式改为：

(18)

利用柯西变异、交流因子和梯度信息的改进鸽群优化算法(GCCPIO)的流程图如图3所示。

图3 GCCPIO流程图

3 仿真校验

为验证基于改进鸽群优化算法的多火星飞行器路径规划方法的可行性和性能，在300m×300m坐标系内进行不同威胁环境下的仿真实验。飞行器的约束为最大航程424m，最大转向角45°。本文考虑3架飞行器和3个目标的情况，危险区均为圆形，半径为10m。在不同威胁环境下分别测试利用Voronoi图和Dijkstra算法的传统协同路径规划方法(下文简称VD法)以及本文提出的基于GCCPIO的协同路径规划方法(下文简称VDP法)的性能。飞行器、目标的坐标如表1所示：

表1 飞行器、目标参数

实验中GCCPIO相关参数设置为：种群个数取300，NC1max=80,NC2max=20，R=0.5，A=1.2，B=0.5，C=-1，P1=5%，路径分为20段，适应度函数的公式如下：

(19)

在一般威胁环境下的仿真测试结果如图4～ 5所示，其中菱形为飞行器的起始点，五角星为目标点，黑色填充圆形为危险区。

图4 一般威胁环境下VD法得到的路径

图5 一般威胁环境下VDP法得到的路径

当增加环境复杂度时，仍按照表1实验参数进行测试，测试结果如图6～ 7所示。

图6 复杂威胁环境下VD法得到的路径

图7 复杂威胁环境下VDP法得到的路径

在2种威胁环境下，分别使用VD法和VDP法得到的测试结果见表2。

表2 2种环境下2种路径规划方法的测试结果

测试结果显示，使用传统的VD法得到的路径因转向角过大而不满足飞行器的约束。而不论是在一般的还是较复杂的威胁环境下，本文提出的基于改进鸽群优化算法的多火星飞行器路径规划方法都能得到满足约束的可飞路径，克服了传统VD法所得路径不平滑的问题，且具有代价更小的优势。

4 结论

提出了一种融合经典路径规划算法和改进鸽群优化算法的协同路径规划方法，设计了基于3种策略改进的鸽群优化算法，可为保持一定高度飞行的多火星飞行器提供二维平面内的可飞协同路径。与经典路径规划方法相比，该方法所得路径转向角更小，在解决多火星飞行器路径优化问题中具有较好的应用前景。