基于传教士优化算法的无人机航迹规划方法

1.本发明属于机器人控制领域，具体涉及无人机航迹规划方法，是一种利用飞行器控制与导航技术、最优化以及计算机科学与技术等来实现基于传教士优化的无人机航迹规划方法。


背景技术：

2.随着自动控制以及人工智能领域的蓬勃发展，无人机(unmanned aerial vehicle,uav) 被广泛应用于各种场景之中，如灾难营救、未知环境勘探，战场中远程精确打击目标以及针对某一环境的覆盖式探索。这一领域的发展可以极大的提高任务完成效率并避免不必要的人员伤亡，对于军事领域以及民用领域都具有重要意义。
3.目前常见的群智能优化算法包括蚁群算法(ant colony optimization,aco)、差分进化算法(differential evolution,de)，果蝇优化算法(fruit fly optimization algorithm, foa)、粒子群优化算法(particle swarm optimization,pso)等。其中，专业人员改进了 aco算法中的信息素分布以及转移概率，实现了复杂障碍环境下的uav航迹规划。针对存在u型障碍物环境的航迹规划场景，可以利用splicing method和dijkstramethod搜索算法消除多余的路径，以避免蚂蚁陷入u型障碍的死胡同。为了提升航迹规划算法的性能，可以将de算法与逼近策略结合，形成一种混合差分进化算法，并用于固定翼uav 在复杂三维环境下的航迹规划。此外，基于拐点的de/best/1策略可以增强de算法的收敛速度，以应对灾难场景对于uav营救速度的需求。为了提升算法收敛速度，可以采用基于最优参考点果蝇优化算法，将两个连续航迹点的中点设置为参考点以提高foa算法的收敛速度。多种群foa算法则将所有果蝇分为多个种群，以扩展搜索空间并增加算法的全局搜索能力。并且在搜索开始阶段倾向于全局搜索而在搜索后半段倾向于局部搜索。为了避免各自的种群陷入局部最优，在产生后代时引入了其它种群的最优解。针对阵型汇合型任务背景，专业人员提出了一种基于精英保持策略的分布式合作pso算法(elitekeeping strategy distributed cooperative pso,dcpso)。该dcpso算法在每次迭代中各个子群落首先分别执行pso算法输出各自的最优解，然后形成最优解集并重新计算合作代价。为了提升pso算法在航迹规划领域的表现，专业人员将综合改进粒子群算法 (comprehensively improved pso,cipso)应用于uav航迹规划。其中，混沌logistic 映射可以令算法的初始值更加随机，并利用一种自适应线性变化策略来调整cipso算法中的参数。仿真结果证明了该算法在收敛速度以及航迹规划结果方面的优势，但其采用的地形图过于简单，无法评估在复杂地形下的算法性能。
4.传教优化算法(preaching optimization algorithm,poa)是近年提出的一种群智能优化算法，该算法结合个体适应度以及位置之间的关系计算权重，以维持个体的多样性，且利用精英策略以及人工免疫算法加速收敛。最终专业人员通过cec’17数据集的测试结果说明了该算法在收敛速度以及精度方面的性能。但将poa算法应用于uav航迹规划时，poa算法中随机初始化传教士位置的方式并没有结合航迹的方向特性，且对于三维坐标以
及边界条件的处理仍存在一些问题需要解决。


技术实现要素：

5.本发明的目的是为了解决目前uav航迹规划算法存在收敛速度慢，规划效果差的问题，以及没有结合uav飞行的三维方向特性，因此需要极大的计算资源来完成uav的航迹规划的问题，而提出基于传教士优化算法的无人机航迹规划方法。
6.基于传教士优化算法的无人机航迹规划方法具体过程为：
7.步骤一：初始化参数，主要包括地形图三维笛卡尔坐标(x,y,z)、uav最小飞行安全距离d
safe
、uav最大飞行高度h、线性插值步长d、传教士数量p、迭代次数n
iter
、继承人个数in以及精英数量ein；
8.步骤二：根据旋转坐标系生成p个初始航迹作为传教士优化算法的个体，每个初始航迹为航迹点组成的集合，并将第i个个体的航迹点集合记作loc(i)＝{wn|1≤n≤n}，其中i＝1,2,...,p，wn为uav航迹点坐标wn＝(xn,yn,zn)，n为1个个体的航迹点个数，wn为uav第n个航迹点坐标，xn为uav第n个航迹点的x轴坐标，yn为uav第n个航迹点的y轴坐标，zn为uav第n个航迹点的z轴坐标；
9.迭代索引n
iter
＝1，目标函数最小值f
min
(0)＝+∞；
10.步骤三：利用第i个个体的航迹点集合loc(i)计算在第n
iter
次迭代中所有个体航迹的目标函数数值f(i,n
iter
)及目标函数数值f(i,n
iter
)最小值
11.步骤四：若|f
min
(n
iter
)-f
min
(n
iter-1)|≤τ或n
iter
＞n
iter
停止迭代，执行步骤九；否则进行步骤五；
12.其中τ为迭代停止门限；
13.步骤五：确定高斯分布方差r
x
/3，ry/3以及rz/3，并向继承人传播知识生成loc
′
(i)；
14.步骤六：经步骤五后poa算法共生成了p
×
(in+1)个个体，包括p个传教士以及 p
×
in个继承人；
15.计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；
16.然后计算除去精英的p
×
(in+1)-ein个个体的权重weight(i)，将权重由大到小排序，选择前p-ein个个体作为传教士loc
″
(i)的另一部分；生成loc
″
(i)；
17.步骤七：进行局部搜索生成loc
″′
(i)；
18.步骤八：比较目标函数并对loc(i)进行更新，即
[0019][0020]
此外，令n
iter
＝n
iter
+1，重复步骤三至步骤八；
[0021]
步骤九：输出最优航迹loc(j)，
[0022]
本发明的有益效果为：
[0023]
本发明提出了基于poa算法的uav航迹规划优化方法。首先，本发明提出了结合航迹长度，地形代价以及飞行高度代价的目标函数。其次，在初始化传教士位置时引入旋转坐标系，通过这种方式使得初始化的航迹结果具有一定的方向性，极大的缩短了算法收敛时间。此外，本发明详细说明了航迹坐标点在poa中的具体处理方式，解决了poa 与航迹规划相结合的问题。本发明可以快速高效的完成uav航迹规划，在规划航迹长度、收敛速度以及针对不同地形的适应程度方面具有优势。
[0024]
本发明的意义在于增强uav航迹规划的收敛速度，并生成目标函数更低的uav航迹，以更加适应uav自身的各项限制以及具体场景的需求。
附图说明
[0025]
图1是uav航迹规划地形图表示方式示意图；
[0026]
图2是旋转坐标系与笛卡尔坐标系示意图，x1为起始点在笛卡尔坐标系下的x轴坐标，x2为任意航迹点在笛卡尔坐标系下的x轴坐标，xn为终点在笛卡尔坐标系下的x轴坐标，y1为起始点在笛卡尔坐标系下的y轴坐标，y2为任意航迹点在笛卡尔坐标系下的y 轴坐标，yn为终点在笛卡尔坐标系下的y轴坐标，l1为将x
′o′y′
平面沿o
′
x
′
方向等分成 n-2份的第一条直线，l2为将x
′o′y′
平面沿o
′
x
′
方向等分成n-2份的第二条直线，l
n-3
为将x
′o′y′
平面沿o
′
x
′
方向等分成n-2份的第n-2条直线，x
′2为任意航迹点在旋转坐标系下的x
′
轴坐标，y
′2为任意航迹点在旋转坐标系下的y
′
轴坐标，d
′
为终点在x
′o′y′
平面上的投影；
[0027]
图3是基于旋转坐标系的航迹点初始化结果示意图；
[0028]
图4是基于poa优化的uav航迹规划方法流程示意图；
[0029]
图5a是航迹规划结果三维视图，
[0030]
图5b是航迹规划结果俯视图；
[0031]
图6是收敛速度示意图。
具体实施方式
[0032]
具体实施方式一：本实施方式基于传教士优化算法的无人机航迹规划方法具体过程为：
[0033]
基于poa优化的uav航迹规划方法包括下述步骤：
[0034]
步骤一：初始化参数，主要包括地形图三维笛卡尔坐标(x,y,z)、uav最小飞行安全距离d
safe
、uav最大飞行高度h、线性插值步长d、传教士数量p、迭代次数n
iter
、继承人个数in以及精英数量ein；
[0035]
步骤二：根据旋转坐标系生成p个初始航迹作为传教士优化算法的个体，每个初始航迹为航迹点组成的集合，并将第i个个体的航迹点集合记作loc(i)＝{wn|1≤n≤n}，其中i＝1,2,...,p，wn为uav航迹点坐标wn＝(xn,yn,zn)，n为1个个体的航迹点个数(经过优化之后选择最优的个体作为uav的航迹，因此也同样是uav的航迹点个数，本专利做的都是关于单uav的航迹规划)，wn为uav第n个航迹点坐标，xn为uav第n 个航迹点的x轴坐标，yn为uav第n个航迹点的y轴坐标，zn为uav第n个航迹点的z 轴坐标；
[0036]
迭代索引n
iter
＝1，目标函数最小值f
min
(0)＝+∞；
[0037]
个体指的是传教士优化算法中的个体，并不是uav，多个个体经过优化之后选取最
优者作为单uav的航迹；
[0038]
步骤三：利用第i个个体的航迹点集合loc(i)计算在第n
iter
次迭代中所有个体航迹的目标函数数值f(i,n
iter
)(式(7))及目标函数数值f(i,n
iter
)最小值
[0039]
步骤四：若|f
min
(n
iter
)-f
min
(n
iter-1)|≤τ或n
iter
＞n
iter
停止迭代，执行步骤九；否则进行步骤五；
[0040]
其中τ为迭代停止门限；
[0041]
步骤五：结合影响权重因子以及人工免疫算法确定高斯分布方差r
x
/3，ry/3以及 rz/3，并向继承人传播知识生成loc
′
(i)；
[0042]
步骤六：经步骤五后poa算法共生成了p
×
(in+1)个个体，包括p个传教士以及 p
×
in个继承人；
[0043]
计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；
[0044]
然后计算除去精英的p
×
(in+1)-ein个个体的权重weight(i)，将权重由大到小排序，选择前p-ein个个体作为传教士loc
″
(i)的另一部分；生成loc
″
(i)；
[0045]
步骤七：进行局部搜索生成loc
″′
(i)；
[0046]
步骤八：比较目标函数并对loc(i)进行更新，即
[0047][0048]
此外，令n
iter
＝n
iter
+1，重复步骤三至步骤八；
[0049]
步骤九：输出最优航迹loc(j)，基于poa优化的uav 航迹规划方法流程如图4所示。
[0050]
具体实施方式二：本实施方式与具体实施方式一不同的是，所述步骤二中根据旋转坐标系生成初始航迹；具体过程为：
[0051]
步骤二一：根据uav起始点和终点构建旋转坐标系x
′y′z′
，如图1所示，其中uav 起始点为x
′y′z′
的坐标原点o
′
，起始点与终点的连线为x
′
轴，x
′o′y′
平面与笛卡尔坐标系中的xoy平面平行，z
′
轴垂直于x
′o′y′
平面，同时x
′y′z′
满足右手系；
[0052]
为航迹点在x
′o′y′
平面投影与旋转坐标系原点连线和旋转坐标系x
′
轴的夹角，φ为旋转坐标系x
′
轴和笛卡尔坐标系x轴的夹角；
[0053]
步骤二二：通过n-3条与y
′
轴平行且在x
′o′y′
平面上的直线将x
′o′y′
平面沿x
′
轴方向等分为n-2份，其中n为1个个体的航迹点个数；
[0054]
步骤二三：除了起始点和终点外的航迹点坐标依次在这n-2个区域内随机选择且服从均匀分布；对应的
[0055]
其中，zn为uav初始航迹的飞行高度，d
safe
为uav最小飞行安全距离，h为uav 最大飞行高度，为(xn,yn)处的地形高度，u(a,b)表示参数为a，b的均匀分布随机变量，
则表示uav初始航迹的飞行高度在之间且服从均匀分布；基于旋转坐标系的航迹点初始化结果如图3所示。
[0056]
其它步骤及参数与具体实施方式一相同。
[0057]
具体实施方式三：本实施方式与具体实施方式一或二不同的是，所述步骤三中利用第 i个个体的航迹点集合loc(i)计算在第n
iter
次迭代中所有个体航迹的目标函数数值 f(i,n
iter
)；具体过程为：
[0058]
步骤三一：根据地图大小确定uav飞行的范围；具体过程为：
[0059]
利用三维笛卡尔坐标(x,y,z)来表示地形图，其中x与y分别表示地形图在水平面上的横纵坐标，z表示(x,y)处的地形高度，uav航迹规划地形图表示方式如图1所示；对于uav的具体航迹而言，若uav航迹点的总个数为n，n中任意的第n个航迹点坐标 wn＝(xn,yn,zn)应在地形图范围内，即
[0060][0061]
其中，x
min
、y
min
、z
min
分别对应于地形图x轴、y轴、z轴坐标的最小值，x
max
、 y
max
、z
max
分别对应于地形图x轴、y轴、z轴坐标的最大值；
[0062]
步骤三二：通过uav飞行的航迹点计算路径长度比率，并将路径长度比率设置为航迹长度代价；具体过程为：
[0063]
考虑到uav的燃料限制，更短的航迹意味着uav可以在燃料消耗完毕之前完成任务。另外，飞行时间越短被未知威胁发现的概率同样更低。本发明采用路径长度比率来描述uav航迹长度代价f
l
，即
[0064][0065]
其中，||
·
||2为向量的二范数；
[0066]fl
越小表示航迹长度越短，越有利于飞行任务的完成。且f
l
这种表示方式并不会因为地图大小或起始点以及终点位置的改变显著影响航迹长度代价数值，即f
l
对于不同地形图的适应能力更强。
[0067]
步骤三三：结合地形高度、uav最小飞行安全距离以及uav航迹点计算地形代价；
[0068]
步骤三四：结合地形高度，uav最大飞行高度以及uav航迹点计算飞行高度代价；
[0069]
步骤三五：将航迹长度代价，地形代价以及飞行高度代价加权得到uav航迹规划总代价。
[0070]
其它步骤及参数与具体实施方式一或二相同。
[0071]
具体实施方式四：本实施方式与具体实施方式一至三之一不同的是，所述步骤三三中结合地形高度、uav最小飞行安全距离以及uav航迹点计算地形代价；具体过程为：
[0072]
为了实现安全飞行，uav在整个航行过程中不能与地形发生任何碰撞，且uav与地面的距离要满足最低安全距离的要求，即飞行高度应大于地形高度z与uav最小飞行安全距
离d
safe
的和。虽然本发明所提航迹规划算法的优化变量为航迹点wn，但uav在航迹点之间航行时同样要避免同地形发生碰撞，因此本发明将相邻航迹点按线性插值间距d 分为mn份，且为了降低算法复杂度，w
n-1
与wn之间第m个点的坐标w
m,n
通过线性插值获得；
[0073]
另外，d的取值应综合考虑算法复杂度以及航迹规划结果的精度。那么本发明所提地形代价f
t
表示为
[0074][0075]
且
[0076][0077]
其中，a
m,n
为w
m,n
是否满足最小安全距离限制，a
m,n
＝1表示w
m,n
与地形图坐标之间的垂直距离小于等于最小安全距离d
safe
；a
m,n
＝0则表示w
m,n
与地形图坐标之间的垂直距离大于最小安全距离d
safe
；w
m,n
为w
n-1
与wn之间经过线性插值的第m个点；x
m,n
为w
m,n
的x轴坐标，y
m,n
为w
m,n
的y轴坐标，z
m,n
为w
m,n
的z轴坐标，为(x
m,n
,y
m,n
)处的地形高度。
[0078]
其它步骤及参数与具体实施方式一至三之一相同。
[0079]
具体实施方式五：本实施方式与具体实施方式一至四之一不同的是，所述步骤三四中结合地形高度，uav最大飞行高度以及uav航迹点计算飞行高度代价；具体过程为：
[0080]
受uav动力学性能的影响，其飞行高度受限，且对于一些特殊的任务类型而言，飞行高度越高被未知威胁发现的概率就越大。本发明提出的飞行高度代价和地形代价类似，即飞行高度代价fh表示为
[0081][0082]
且
[0083][0084]
其中，h为uav最大飞行高度，b
m,n
为w
m,n
是否满足最大飞行高度限制；b
m,n
＝1表示uav飞行高度大于最大飞行高度即不满足最大飞行高度限制，b
m,n
＝0表示uav飞行高度小于最大飞行高度即满足最大飞行高度限制。
[0085]
其它步骤及参数与具体实施方式一至四之一相同。
[0086]
具体实施方式六：本实施方式与具体实施方式一至五之一不同的是，所述步骤三五中将航迹长度代价，地形代价以及飞行高度代价加权得到uav航迹规划总代价；具体过程为：
[0087]
本发明设计的优化目标函数综合考虑了航迹长度，uav和地形之间的避碰以及uav 飞行高度的限制，该基于uav航迹长度代价f
l
、地形代价f
t
以及飞行高度代价fh，目标函数表
示为
[0088]
f＝p1f
l
+p2f
t
+p3fhꢀꢀꢀꢀꢀ
(7)
[0089]
其中，f为uav航迹规划总代价，p1为uav航迹长度代价f
l
对应的权重，p2为地形代价f
t
对应的权重，p3为飞行高度代价fh对应的权重；通过调整权重可以调整优化目标。
[0090]
其它步骤及参数与具体实施方式一至五之一相同。
[0091]
具体实施方式七：本实施方式与具体实施方式一至六之一不同的是，所述步骤五中结合影响权重因子以及人工免疫算法确定高斯分布方差r
x
/3，ry/3以及rz/3，并向继承人传播知识生成loc
′
(i)；具体过程为：
[0092]
首先定义归一化的目标函数值，即影响权重
[0093][0094]
其中
[0095][0096]
其中，r
x
为笛卡尔坐标系x轴坐标搜索高斯分布方差系数，ry为笛卡尔坐标系y轴坐标搜索高斯分布方差系数，rz为笛卡尔坐标系z轴坐标搜索高斯分布方差系数，f
aff
(i)为影响权重，f
max
为目标函数最大值，f
min
为目标函数最小值，f(i)为第i个个体的目标函数数值，ε为计算机可输入的最小正常数，通常为2.2204
×
10-16
，以避免算法迭代过程中出现错误；
[0097]
在poa算法的全局搜索步骤中，采用了文化传播中向继承人传播宗教知识的概念，即影响力越大的传教士可将继承人吸引在其附近。对应到优化算法中，即目标函数数值越小，其子代距离父辈的距离应越短，反之距离应越大。poa算法利用人工免疫算法实现了上述目的，定义
[0098][0099]
其中，range
x
、rangey以及rangez分别为航迹点对应笛卡尔坐标系x、y以及z轴坐标搜索空间大小，coef
x
(n
iter
)、coefy(n
iter
)以及coefz(n
iter
)分别为第n
iter
次迭代的x、 y以及z轴坐标收缩系数，
[0100]
最终更新后的继承人位置为
[0101]
[0102]
其中，loc(i,xn)、loc(i,yn)以及loc(i,zn)分别表示第i个传教士的第n个航迹点的 x、y以及z坐标；loc
′
(i,xn)、loc
′
(i,yn)以及loc
′
(i,zn)分别代表loc(i,xn)、loc(i,yn) 以及loc(i,zn)继承人的三维坐标，每个传教士对应in个继承人；randn(0,r
x
(i,n
iter
)/3)为均值为0方差为r
x
(i,n
iter
)/3的高斯分布，randn(0,ry(i,n
iter
)/3)为均值为0方差为 ry(i,n
iter
)/3的高斯分布，randn(0,rz(i,n
iter
)/3)为均值为0方差为rz(i,n
iter
)/3的高斯分布；
[0103]
其它步骤及参数与具体实施方式一至六之一相同。
[0104]
具体实施方式八：本实施方式与具体实施方式一至七之一不同的是，所述coef
x
(n
iter
)、 coefy(n
iter
)以及coefz(n
iter
)定义为：
[0105][0106]
其中，coef
x_min
、coef
y_min
、coef
z_min
分别为coef
x
(n
iter
)、coefy(n
iter
)、coefz(n
iter
) 的下限，coef
x_max
、coef
y_max
、coef
z_max
分别为coef
x
(n
iter
)、coefy(n
iter
)、coefz(n
iter
) 的上限。
[0107]
其它步骤及参数与具体实施方式一至七之一相同。
[0108]
具体实施方式九：本实施方式与具体实施方式一至八之一不同的是，所述步骤六中经步骤五后poa算法共生成了p
×
(in+1)个个体，包括p个传教士以及p
×
in个继承人；
[0109]
计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；
[0110]
然后计算除去精英的p
×
(in+1)-ein个个体的权重weight(i)，将权重由大到小排序，选择前p-ein个个体作为传教士loc
″
(i)的另一部分；生成loc
″
(i)；具体过程为：
[0111]
社会中的各种文化通常存在着竞争，为了描述这种行为，poa算法首先针对所有传教士及其继承人进行目标函数的计算并根据数值由小到大进行排列，同时引入精英策略，即对于全部p
×
(in+1)个个体，其目标函数数值的前ein个体直接成为传教士loc
″
(i)的一部分进入下一步，剩余p-ein个传教士则在剩余p
×
(in+1)-ein个体中进行选择。
[0112]
定义个体中心为
[0113][0114]
其中，loc表示包括loc以及loc
′
的所有个体；
[0115]
计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；
[0116]
计算剩余p
×
(in+1)-ein个个体中每个个体距离center(n
iter
)的欧式距离dis
′
(i)，并对dis
′
(i)进行归一化处理，得到剩余p
×
(in+1)-ein个个体中每个个体归一化处理后的欧式距离dis
′
(i)；
[0117]
根据式(8)计算剩余p
×
(in+1)-ein个个体中每个个体的影响权重f
aff
′
(i)；
[0118]
基于剩余p
×
(in+1)-ein个个体中每个个体的影响权重和剩余p
×
(in+1)-ein个个体中每个个体归一化处理后的欧式距离dis
′
(i)得到权重，权重表达式
[0119]
weight(i)＝dis
′(i)×
exp(f
aff
′
(i))
ꢀꢀꢀꢀ
(14)
[0120]
该权重的大小可以表征个体距离中心的离散程度，为了保证个体多样性，poa算法将权重由大到小排序，选择前p-ein作为传教士loc
″
(i)的另一部分。
[0121]
其它步骤及参数与具体实施方式一至八之一相同。
[0122]
具体实施方式十：本实施方式与具体实施方式一至九之一不同的是，所述步骤七中进行局部搜索生成loc
″′
(i)，即
[0123][0124]
其中，randn(0,1)为均值为0方差为1的高斯分布。
[0125]
其它步骤及参数与具体实施方式一至九之一相同。
[0126]
表1符号说明表
[0127]
[0128]
[0129]
本发明在60次迭代后实现了收敛。
[0135]
本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，本领域技术 人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发 明所附的权利要求的保护范围。

技术特征：
1.基于传教士优化算法的无人机航迹规划方法，其特征在于：所述方法具体过程为：步骤一：初始化参数，主要包括地形图三维笛卡尔坐标(x,y,z)、uav最小飞行安全距离d
safe
、uav最大飞行高度h、线性插值步长d、传教士数量p、迭代次数n
iter
、继承人个数in以及精英数量ein；步骤二：根据旋转坐标系生成p个初始航迹作为传教士优化算法的个体，每个初始航迹为航迹点组成的集合，并将第i个个体的航迹点集合记作loc(i)＝{w
n
|1≤n≤n}，其中i＝1,2,...,p，w
n
为uav航迹点坐标w
n
＝(x
n
,y
n
,z
n
)，n为1个个体的航迹点个数，w
n
为uav第n个航迹点坐标，x
n
为uav第n个航迹点的x轴坐标，y
n
为uav第n个航迹点的y轴坐标，z
n
为uav第n个航迹点的z轴坐标；迭代索引n
iter
＝1，目标函数最小值f
min
(0)＝+∞；步骤三：利用第i个个体的航迹点集合loc(i)计算在第n
iter
次迭代中所有个体航迹的目标函数数值f(i,n
iter
)及目标函数数值f(i,n
iter
)最小值步骤四：若|f
min
(n
iter
)-f
min
(n
iter-1)|≤τ或n
iter
＞n
iter
停止迭代，执行步骤九；否则进行步骤五；其中τ为迭代停止门限；步骤五：确定高斯分布方差r
x
/3，r
y
/3以及r
z
/3，并向继承人传播知识生成loc
′
(i)；步骤六：经步骤五后poa算法共生成了p
×
(in+1)个个体，包括p个传教士以及p
×
in个继承人；计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；然后计算除去精英的p
×
(in+1)-ein个个体的权重weight(i)，将权重由大到小排序，选择前p-ein个个体作为传教士loc
″
(i)的另一部分；生成loc
″
(i)；步骤七：进行局部搜索生成loc
″′
(i)；步骤八：比较目标函数并对loc(i)进行更新，即此外，令n
iter
＝n
iter
+1，重复步骤三至步骤八；步骤九：输出最优航迹loc(j)，2.根据权利要求1所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤二中根据旋转坐标系生成初始航迹；具体过程为：步骤二一：根据uav起始点和终点构建旋转坐标系x
′
y
′
z
′
，其中uav起始点为x
′
y
′
z
′
的坐标原点o
′
，起始点与终点的连线为x
′
轴，x
′
o
′
y
′
平面与笛卡尔坐标系中的xoy平面平行，z
′
轴垂直于x
′
o
′
y
′
平面，同时x
′
y
′
z
′
满足右手系；为航迹点在x
′
o
′
y
′
平面投影与旋转坐标系原点连线和旋转坐标系x
′
轴的夹角，φ为旋转坐标系x
′
轴和笛卡尔坐标系x轴的夹角；步骤二二：通过n-3条与y
′
轴平行且在x
′
o
′
y
′
平面上的直线将x
′
o
′
y
′
平面沿x
′
轴方向
等分为n-2份，其中n为1个个体的航迹点个数；步骤二三：除了起始点和终点外的航迹点坐标依次在这n-2个区域内随机选择且服从均匀分布；对应的其中，z
n
为uav初始航迹的飞行高度，d
safe
为uav最小飞行安全距离，h为uav最大飞行高度，为(x
n
,y
n
)处的地形高度，u(a,b)表示参数为a，b的均匀分布随机变量，则表示uav初始航迹的飞行高度在之间且服从均匀分布。3.根据权利要求1或2所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤三中利用第i个个体的航迹点集合loc(i)计算在第n
iter
次迭代中所有个体航迹的目标函数数值f(i,n
iter
)；具体过程为：步骤三一：根据地图大小确定uav飞行的范围；具体过程为：利用三维笛卡尔坐标(x,y,z)来表示地形图，其中x与y分别表示地形图在水平面上的横纵坐标，z表示(x,y)处的地形高度；若uav航迹点的总个数为n，n中任意的第n个航迹点坐标w
n
＝(x
n
,y
n
,z
n
)应在地形图范围内，即其中，x
min
、y
min
、z
min
分别对应于地形图x轴、y轴、z轴坐标的最小值，x
max
、y
max
、z
max
分别对应于地形图x轴、y轴、z轴坐标的最大值；步骤三二：通过uav飞行的航迹点计算路径长度比率，并将路径长度比率设置为航迹长度代价；具体过程为：采用路径长度比率来描述uav航迹长度代价f
l
，即其中，||
·
||2为向量的二范数；步骤三三：结合地形高度、uav最小飞行安全距离以及uav航迹点计算地形代价；步骤三四：结合地形高度，uav最大飞行高度以及uav航迹点计算飞行高度代价；步骤三五：将航迹长度代价，地形代价以及飞行高度代价加权得到uav航迹规划总代价。4.根据权利要求3所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤三三中结合地形高度、uav最小飞行安全距离以及uav航迹点计算地形代价；具体过程为：将相邻航迹点按线性插值间距d分为m
n
份，w
n-1
与w
n
之间第m个点的坐标w
m,n
通过线性插值获得；
地形代价f
t
表示为且其中，a
m,n
为w
m,n
是否满足最小安全距离限制，a
m,n
＝1表示w
m,n
与地形图坐标之间的垂直距离小于等于最小安全距离d
safe
；a
m,n
＝0则表示w
m,n
与地形图坐标之间的垂直距离大于最小安全距离d
safe
；w
m,n
为w
n-1
与w
n
之间经过线性插值的第m个点；x
m,n
为w
m,n
的x轴坐标，y
m,n
为w
m,n
的y轴坐标，z
m,n
为w
m,n
的z轴坐标，为(x
m,n
,y
m,n
)处的地形高度。5.根据权利要求4所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤三四中结合地形高度，uav最大飞行高度以及uav航迹点计算飞行高度代价；具体过程为：飞行高度代价f
h
表示为且其中，h为uav最大飞行高度，b
m,n
为w
m,n
是否满足最大飞行高度限制；b
m,n
＝1表示uav飞行高度大于最大飞行高度即不满足最大飞行高度限制，b
m,n
＝0表示uav飞行高度小于最大飞行高度即满足最大飞行高度限制。6.根据权利要求5所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤三五中将航迹长度代价，地形代价以及飞行高度代价加权得到uav航迹规划总代价；具体过程为：基于uav航迹长度代价f
l
、地形代价f
t
以及飞行高度代价f
h
，目标函数表示为f＝p1f
l
+p2f
t
+p3f
h
ꢀꢀꢀꢀꢀꢀꢀ
(7)其中，f为uav航迹规划总代价，p1为uav航迹长度代价f
l
对应的权重，p2为地形代价f
t
对应的权重，p3为飞行高度代价f
h
对应的权重。7.根据权利要求6所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤五中确定高斯分布方差r
x
/3，r
y
/3以及r
z
/3，并向继承人传播知识生成loc
′
(i)；具体过程为：首先定义归一化的目标函数值，即影响权重
其中其中，r
x
为笛卡尔坐标系x轴坐标搜索高斯分布方差系数，r
y
为笛卡尔坐标系y轴坐标搜索高斯分布方差系数，r
z
为笛卡尔坐标系z轴坐标搜索高斯分布方差系数，f
aff
(i)为影响权重，f
max
为目标函数最大值，f
min
为目标函数最小值，f(i)为第i个个体的目标函数数值，ε为计算机可输入的最小正常数；定义其中，range
x
、range
y
以及range
z
分别为航迹点对应笛卡尔坐标系x、y以及z轴坐标搜索空间大小，coef
x
(n
iter
)、coef
y
(n
iter
)以及coef
z
(n
iter
)分别为第n
iter
次迭代的x、y以及z轴坐标收缩系数，最终更新后的继承人位置为其中，loc(i,x
n
)、loc(i,y
n
)以及loc(i,z
n
)分别表示第i个传教士的第n个航迹点的x、y以及z坐标；loc
′
(i,x
n
)、loc
′
(i,y
n
)以及loc
′
(i,z
n
)分别代表loc(i,x
n
)、loc(i,y
n
)以及loc(i,z
n
)继承人的三维坐标，每个传教士对应in个继承人；randn(0,r
x
(i,n
iter
)/3)为均值为0方差为r
x
(i,n
iter
)/3的高斯分布，randn(0,r
y
(i,n
iter
)/3)为均值为0方差为r
y
(i,n
iter
)/3的高斯分布，randn(0,r
z
(i,n
iter
)/3)为均值为0方差为r
z
(i,n
iter
)/3的高斯分布。8.根据权利要求7所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述coef
x
(n
iter
)、coef
y
(n
iter
)以及coef
z
(n
iter
)定义为：
其中，coef
x_min
、coef
y_min
、coef
z_min
分别为coef
x
(n
iter
)、coef
y
(n
iter
)、coef
z
(n
iter
)的下限，coef
x_max
、coef
y_max
、coef
z_max
分别为coef
x
(n
iter
)、coef
y
(n
iter
)、coef
z
(n
iter
)的上限。9.根据权利要求8所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤六中经步骤五后poa算法共生成了p
×
(in+1)个个体，包括p个传教士以及p
×
in个继承人；计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；然后计算除去精英的p
×
(in+1)-ein个个体的权重weight(i)，将权重由大到小排序，选择前p-ein个个体作为传教士loc
″
(i)的另一部分；生成loc
″
(i)；具体过程为：定义个体中心为其中，loc表示包括loc以及loc
′
的所有个体；计算p
×
(in+1)个个体中每个个体的目标函数数值，将目标函数数值由小到大排列，取前ein个个体直接成为传教士loc
″
(i)的一部分；计算剩余p
×
(in+1)-ein个个体中每个个体距离center(n
iter
)的欧式距离dis
′
(i)，并对dis
′
(i)进行归一化处理，得到剩余p
×
(in+1)-ein个个体中每个个体归一化处理后的欧式距离dis
′
(i)；根据式(8)计算剩余p
×
(in+1)-ein个个体中每个个体的影响权重f
aff
′
(i)；基于剩余p
×
(in+1)-ein个个体中每个个体的影响权重和剩余p
×
(in+1)-ein个个体中每个个体归一化处理后的欧式距离dis
′
(i)得到权重，权重表达式weight(i)＝dis
′
(i)
×
exp(f
aff
′
(i))
ꢀꢀꢀꢀꢀ
(14)将权重由大到小排序，选择前p-ein作为传教士loc
″
(i)的另一部分。10.根据权利要求9所述基于传教士优化算法的无人机航迹规划方法，其特征在于：所述步骤七中进行局部搜索生成loc
″′
(i)，即其中，randn(0,1)为均值为0方差为1的高斯分布。

技术总结
基于传教士优化算法的无人机航迹规划方法，本发明涉及无人机航迹规划方法。本发明的目的是为了解决目前UAV航迹规划算法存在收敛速度慢，规划效果差的问题，以及需要极大的计算资源来完成UAV的航迹规划的问题。过程为：一：初始化参数；二：生成loc(i)，迭代索引n


技术研发人员：马琳 贾汉博 魏守明 陈舒怡 叶亮 何晨光
受保护的技术使用者：哈尔滨工业大学
技术研发日：2022.01.26
技术公布日：2022/7/5