基于点集群体的进化算法求解复杂3D环境中无人机路径规划问题

UAV Path Planning Based on Point Set Evolution in 3D Complex Environment

摘要: 随着无人机应用的日益广泛，对无人机路径规划的需求也越来越大，但大多数现有的基于进化算法的路径规划将整条路径作为一个个体进行优化，这可能导致一些潜在的路径点被忽视。此外，由于3D环境难以网格化，传统的基于网格的智能搜索算法，如蚁群算法等，在复杂3D环境中难以有效解决无人机路径规划问题。鉴于此，本文提出一种基于点集进化的无人机路径规划算法，该算法将每个控制点作为一个个体，根据路径的有序性设计了一种高效的杂交算子来生成新的控制点，基于控制点集使用经典的Dijkstra算法搜索并构建路径，从而计算每个控制点的适应度用来更新控制点集。该算法将经典路径规划算法与进化算法相结合，既具有经典算法的高搜索效率，又具有进化算法的全局搜索能力。实验结果表明，所提算法在解决复杂3D环境中的无人机路径规划问题时表现良好且稳定。

Abstract: With the increasing application of Unmanned Aerial Vehicle (UAV), there is a growing demand for UAV path planning. However, most existing path planning based on evolutionary algorithm opti-mize the whole path as an individual, which causes some potential waypoints are ignored. Addi-tionally, traditional algorithms, e.g. Ant Colony Optimization (ACO) struggle to effectively solve UAV path planning in complex 3D environments, where grid-based approaches are difficult to implement. Therefore, this paper proposes a UAV path planning based on Point Set Evolution (PSEA). In the proposed algorithm, each control point is treated as an individual, and Dijkstra algorithm is utilized to search and construct paths, thus calculating the fitness value for each control point. Fur-thermore, an efficient crossover operator is designed based on the order of the paths, and Evolu-tionary algorithm is employed to update the set of control points. The proposed algorithm features the efficiency of classical path planning algorithms with the global search capability of Evolutionary algorithm. The experiment results demonstrate that the proposed PSEA performs well and remains stable in solving UAV path planning in complex 3D environment.

1. 引言

无人驾驶飞行器简称“无人机”，英文缩写为“UAV”，是一种利用无线电遥控设备和自设定的程序控制装置操纵的不载人飞行器，具备体积小、操作方便、成本低以及生存能力强等优点，被广泛地应用在多个领域，例如军事作战 [1] [2] ，林业防护 [3] ，测绘 [4] [5] 等领域。为了使无人机能够顺利完成任务，需要对其进行路径规划，即寻找从任务出发点到目标位置的最优飞行路径，同时考虑能源消耗和避开障碍物和禁飞区。

进化算法(Evolutionary algorithm, EA)是以达尔文的进化论为基础，通过模拟自然界中生物的遗传进化过程，即选择、杂交和变异的智能优化方法，具有较好的全局搜索能力 [6] 。在解决路径规划问题时，进化算法能够得到一条全局最优路径，从而受到了学者们的关注，许多基于进化算法的路径规划算法被提出。在现有文献中，大部分基于进化算法的路径规划算法将路径作为种群的个体，再利用约束条件和目标函数对个体进行评估 [7] [8] [9] [10] 。然而，在路径规划中，一条路径只有在每个控制点都可行的情况下才是可行的，如果将一条完整的路径作为个体，一旦该路径存在不可行的控制点，则该路径上的所有控制点的适应度都较低，从而导致一些较优的控制点被忽视。考虑到一条完整路径可以是由控制点有序排列后生成的，同时控制点一旦发生改变，就可能产生新的路径，因此将控制点作为种群的个体会更加合适。然而，如何对单个控制点进行评估是一个值得研究的问题。

此外，3D环境比2D环境增加了高度这一维度，使得无人机无法一直在同一高度飞行，其飞行高度需要随着地形高度变化而改变。如果要将在2D环境中表现良好的路径规划算法应用在3D环境中，则需要先将3D环境网格化，即将3D环境划分为许多形状大小均相同的网格单元。网格化的精细程度越大，对原3D环境的表达就越准确，所得的路径也会更好，但同时也会加大运算量、增加运算时间和储存空间 [11] [12] 。复杂的3D环境所需的网格化精度高，使得对于传统的基于网格的智能搜索算法，如蚁群算法等，难以在复杂3D环境中有效解决无人机路径规划问题。

鉴于此，本文提出了一种基于点集进化的无人机路径规划算法(UAV path planning based on Point Set Evolution, PSEA)，该算法将控制点视为个体，种群为控制点的集合，利用经典的Dijkstra算法在多个随机控制点子集上生成多条路径，适应度函数综合考虑控制点生成路径的长度和数量对每个控制点进行评价。由于路径是由控制点的有序排列形成的，我们根据这一性质构造了新的杂交算子以产生有效的控制点。该算法将经典路径规划算法与进化算法相结合，既具有经典算法的高搜索效率，又具有进化算法的全局搜索能力。本文提出的算法与传统的进化算法和元启发式算法在多个测试问题上进行仿真对比，同时通过消融实验对本文设计的杂交算子的有效性进行验证。实验结果表明，所提算法在解决复杂3D环境中的无人机路径规划问题时表现良好且稳定。

2. 研究现状

随着无人机的发展，越来越多的学者对无人机路径规划进行了研究，目前，无人机路径规划算法主要分为以下三类。

第一类是传统的路径规划算法，如Dijkstra算法 [13] 和A^*算法 [14] 。在文献 [15] 中，提出了一种多智能体深度强化Dijkstra算法，可以优化疏散过程。A^*算法是一种在静态环境中求解最短路径最有效的直接搜索方法，但随着搜索区域的增大，所需的数据存储空间也会增大，同时消耗的时间也会增加。文献 [16] 针对特种无人机提出了一种增强的稀疏A^*搜索方法，能够在较少的时间内获得最优路径。在文献 [17] 中，Lucas P. Behnck提出了一种基于模拟退火的无人机路径规划算法，将多个小型无人机的路径规划问题视作商旅问题 [18] ，通过解决这个商旅问题，实现无人机的总路径最短和无人机与必须访问的点之间的匹配程度最大化。

第二类是以进化算法和粒子群算法 [19] 为代表的基于人工智能的路径规划算法。在文献 [20] 中，提出了一种基于分解的约束多目标进化算法，充分利用不可行信息，将搜索引导到潜在区域，设计了一种改进的变异算子，使路径更加平滑。蚁群优化算法是一种模拟自然界蚂蚁觅食过程的随机搜索算法。文献 [21] 从信息素更新策略、势场函数和启发函数三个方面进行改进，提出了一种基于蚁群算法的路径规划算法。文献 [22] 提出了一种基于改进混沌蚁群算法的无人机路径规划算法，并通过仿真实验验证了所提算法的有效性。

第三类是混合多种算法的路径规划算法。文献 [23] 中，将遗传算法与优化搜索区域相结合，提高算法的局部搜索能力，首先对种群个体进行分析，然后根据分析结果为搜索区域分配相应的权重，从而限制新个体产生的区域，使得在权重较高的区域搜索力度较大。文献 [24] 提出了一种基于进化算法和模拟退火算法相结合的路径规划算法，模拟退火算法能有效避免陷入局部最优，同时设计了自适应遗传算子，包括自适应杂交概率算子和自适应变异概率算子，以保证种群的多样性。文献 [25] 提出了一种基于混合初始化方法的遗传算法的无人机路径规划算法，将种群划分为两个子种群，然后生成路径分别利用随机初始化方法和贪婪算法，最后根据实际情况对路径进行修改。

3. 基于点集进化的无人机路径规划

在基于点集进化的无人机路径规划算法PSEA中，将控制点 $x=\left(x,y,h\right)$ 作为个体，将控制点集 $P=\left\{x^1,x^2,\cdots ,x^N\right\}$ 作为种群。选择、杂交和变异操作是进化算法的三个关键过程。选择操作是根据适应度在当前种群中选择更好的个体，杂交操作的目的是将最好的基因传递给后代，变异操作可以增加种群的多样性。

3.1. 基于地表距离和Dijkstra算法的适应值的计算

基于群体的搜索算法个体评估是一个关键问题，本文通过该控制点构建的路径来评价，因此我们需要在控制点集中构建路径。构建路径的方法有很多，如Dijkstra算法和Floyd算法，都需要先计算控制点之间的距离矩阵。在计算两个控制点之间的距离时，如果只考虑这两点之间的欧氏距离是不合理的，因为这两个控制点形成的路径段可能会穿过山体，这是不被允许的。为了更好地同时考虑路径的长度和安全性，我们在两个控制点之间等距取点来计算地表距离。

精确的地表距离矩阵 $D=\left(d_{ij}\right)$ 计算是一个十分困难的问题，本文通过等距采样的方法对地表距离进行计算。具体来说，我们首先自适应确定等距采样的间距。假设 $U=\left(u_1,u_2,u_3\right)$ 和 $V=\left(v_1,v_2,v_3\right)$ 为控制点坐标的最大值和最小值，即种群P中任意控制点 $x^i=\left(x,y,h\right),i=1,2,\cdots ,N$ ，有 $v_1\le x\le u_1$ ， $v_2\le y\le u_2$ ， $v_3\le h\le u_3$ 。等距采样的间距为：

$l=\frac{\sqrt{{\left(u_1-v_1\right)}^2+{\left(u_2-v_2\right)}^2}}{200}.$

然后，对任意两个控制点 $x^i$ 和 $x^j$ 的连线上每隔间距l进行均匀线性插值，则可以得到

$n=\lceil \frac{\Vert x^i-x^j\Vert }{l}\rceil ,1\le i\ne j\le N$

个中间点，并记这些中间点为 $M_1=\left({x^{\prime }}_1,{y^{\prime }}_1,{\bar{h}}_1\right),M_2=\left({x^{\prime }}_2,{y^{\prime }}_2,{\bar{h}}_2\right),\cdots ,M_n=\left({x^{\prime }}_n,{y^{\prime }}_n,{\bar{h}}_n\right)$ ，通过公式(1)计算其相应的坐标。

$M_k=\lambda x^i+\left(1-\lambda \right)x^j$ (1)

其中 $\lambda =\frac{k}{n+1},k=1,2,\cdots ,n$ ，为了保证无人机飞行时的安全，中间点的高度需要进行如下修正使得无人机的飞行高度在飞行高度范围之内：

${h^{\prime }}_k=\min \left[\max \left({\bar{h}}_k,v_3\right),u_3\right],k=1,2,\cdots ,n.$ (2)

得到修正后的中间点 $M_k$ 的坐标为 $\left({x^{\prime }}_k,{y^{\prime }}_k,{h^{\prime }}_k\right)$ ，则控制点 $x^i$ 和 $x^j$ 的地表距离可近似为

$d_{i,j}=\Vert x^i-M_1\Vert +\underset{k=1}{\overset{n-1}{{\displaystyle \sum }}}\Vert M_k-M_{k+1}\Vert +\Vert M_n-x^j\Vert ,1\le i\ne j\le N$ (3)

本文采用Dijkstra算法基于所有控制点集生成路径，所生成的路径是当前最优路径。但在对个体进行评估时，如果只考虑当前最优路径，可能会忽略一些具有潜在优势的控制点，也不利于控制点的分布和保持多样性。因此，我们通过随机选取部分控制点然后采用Dijkstra算法构建多条次最优路径来保持种群的多样性。

记当前最优路径上的控制点数目为 $N_C$ ，计算出比例

$p_s=\min \left(3N_c,0.8N\right).$ (4)

接着在种群P中随机抽取 $p_s$ 个控制点(个体)，基于抽取的个体所对应的地表距离矩阵，该矩阵为地表距离矩阵D中抽取个体所对应的子矩阵，然后用Dijkstra算法构建路径一条次优路径，重复这个过程直至构建p − 1条次优路径。

最后，每个控制点 $x^i$ 的适合度计算如下：

$Fi{t}_{x^i}=I_1\cdot \frac{p}{P{L}_1}+\underset{k=2}{\overset{p}{{\displaystyle \sum }}}{I}_k\cdot \frac{1}{P{L}_k},$ (5)

其中，p是路径的数量， $P{L}_k$ 表示第k条路径的长度， $I_k$ 是指示函数，当第k条路径上有控制点 $x^i$ ，则 $I_k=1$ ，否则 $I_k=0$ 。控制点适应值的计算过程如算法1所示：

1

从公式(5)以及算法1可以看出，在评估控制点时，所提出的算法PSEA不仅考虑了控制点 $x^i$ 生成的路径长度，还考虑了控制点 $x^i$ 生成的路径数量。

3.2. 基于改进前景的参与杂交变异个体选择

为了提高算法的搜索效率，需要分析对个体的改进前景进行度量，通过锦标赛选择让改进前景较大的个体以更大概率参与杂交变异。在优化过程中我们希望找到一条安全的最短路径，因此，我们从可改进距离和安全性两个方面对个体的改进前景进行度量。具体来说，假设如图1中的路径为第k条路径， $x^{i-1},x^i,x^{i+1}$ 是路径上的三个连续控制点，

(a) 如果 $x^{i-1}$ 和 $x^i$ 之间或者 $x^i$ 和 $x^{i+1}$ 之间存在违反高度限制的中间点，则控制点 $x^i$ 在第k条路径上的改进前景为

$Im{p}_k\left(x^i\right)=\mu ,$ (6)

其中， $\mu$ 是一个足够大的常数。

(b) 如果 $x^{i-1}$ 和 $x^i$ 之间和 $x^i$ 和 $x^{i+1}$ 之间都不存在违反高度限制的中间点，则控制点 $x^i$ 在第k条路径上的改进前景为

$Im{p}_k\left(x^i\right)=d_{i-1,i}+d_{i,i+1}-d_{i-1,i+1}.$ (7)

$Im{p}_k\left(x^i\right)$ 数值越小，代表 $x^i$ 越靠近线段 $x^{i-1}{x}^{i+1}$ 。

Figure 1. Illustration of the kth path

图1. 第k条路径的示意图

进而可以得到控制点 $x^i$ 的改进前景为

$Imp\left(x^i\right)=\underset{k=1}{\overset{p}{{\displaystyle \sum }}}Im{p}_k\left(x^i\right).$ (8)

再通过锦标赛选择出改进前景较大的个体参与杂交变异，即在种群P中随机选择s个个体，比较这s个个体的改进前景，让改进前景最大的个体参与杂交变异。在本文中， $s=3$ 。

3.3. 杂交变异算子

采用进化算法解决实际问题时根据问题的特性设计有效的个体生成策略，即杂交变异算子对于提高算法的效率至关重要。假设起点为S，有控制点 $x^1,x^2$ 和 $x^3$ ，终点为E，则可以生成路径

$\begin{array}{c}S\to x^1\to x^2\to x^3\to E.\end{array}$ (9)

因此，路径是由控制点有序排列后产生的，通过路径的这种有序性，我们可以得到路径上每个控制点的上一个路径点和下一个路径点。对于控制点 $x^i$ ，记 $x^i$ 所有上一个路径点组成的集合为左点集 $L_{x^i}$ ，所有下一个路径点组成的集合为右点集 $R_{x^i}$ 。例如，在路径(9)中，控制点 $x^2$ 的上一个路径点是 $x^1$ ，下一个路径点是 $x^3$ ，则有 $x^1\in L_{x^2}$ ， $x^3\in R_{x^2}$ 。 $x^{im}$ 为用于杂交的个体，其左右点集分别为 $L_{x^{im}}$ 和 $R_{x^{im}}$ 。分别从 $L_{x^{im}}$ 和 $R_{x^{im}}$ 随机抽取 $x_L$ 和 $x_R$ ，那么子代 $y$ 的生成如下：

$y=x^{im}+r_1\cdot d_1\cdot \left(x_L-x^{im}\right)+r_2\cdot d_2\cdot \left(x_R-x^{im}\right)$ (10)

其中， $r_1,r_2$ 是区间[0, 1]之间的两个随机数， $d_1,d_2$ 是两个常数。

如图2所示，蓝色向量表示 $r_1\cdot d_1\cdot \left(x_L-x^{im}\right)$ ，绿色向量表示 $r_2\cdot d_2\cdot \left(x_R-x^{im}\right)$ ，根据平行四边形法则，可以得到子代 $y$ 。此外，子代 $y$ 会比 $x^{im}$ 更靠近线段 $x_L{x}_R$ ，使得路径有被拉直的趋势，从而有效缩短路径长度。

Figure 2. Illustration of the crossover operator

图2. 杂交操作示意图

接着对每一个产生的子代 $y=\left(y_1,y_2,y_3\right)$ 进行以下的变异操作：

$y_q=\{\begin{array}{ll}r\cdot u_q+\left(1-r\right)\cdot v_q\hfill & rand<CR\text{}\hfill \\ y_q\hfill & \text{otherwise}\hfill \end{array}$ (11)

其中 $q\in \left\{1,2,3\right\}$ 是一个随机数，r和rand是区间[0, 1]之间的两个随机数，CR是区间[0, 1]之间的常数。

为了确保杂交变异算子产生的子代有效，需要利用公式(2)对子代进行修正，PSEA的杂交变异操作过程如算法2所示。

3.4. PSEA的算法框架

PSEA的算法过程如算法3所示。首先，初始化一个种群规模为2N的初始种群P₀，并计算P₀中个体之间的安全距离，根据算法1计算种群P₀中每个个体的适应度，并按照适应度对个体进行排序，选出前N个个体作为父代种群，通过算法2描述的杂交变异操作产生N个子代。然后将父代种群和子代种群合并为新种群P，继续下一次的迭代直至满足终止条件。

4. 实验与结果分析

4.1. 对比算法

为了检验所提算法PSEA的性能，我们将PSEA与经典进化算法(classsEA)，和6种元启发式算法进行对比实验，包括蜣螂优化算法(DBO) [26] 、狐猴优化算法(LO) [27] 、蜘蛛蜂优化算法(SWO) [28] 、小龙虾优化算法(COA) [29] 、光谱优化算法(LSO) [30] 和淘金优化算法(GRO) [31] 。在对比实验中，利用经典进化算法求解无人机路径规划时，种群个体是由w个控制点组成的，每个个体代表一条完整的路径，再利用个体生成的路径长度和安全性对个体进行评估。

此外，为了检验杂交算子(10)的有效性，我们进行了消融实验(Ablation)，该消融实验并不考虑PSEA中提到的路径有序性，采用如下普通的杂交算子产生新的个体：

$y=\lambda x^1+\left(1-\lambda \right)x^2,$

$y$ 是子代个体， $\lambda =\left({\lambda }_1,{\lambda }_2,{\lambda }_3\right)$ ，其中 ${\lambda }_1,{\lambda }_2,{\lambda }_3$ 是区间[0, 1]之间的三个随机数， $x^1$ 和 $x^2$ 是从父代种群K中随机抽取的两个控制点个体。

4.2.测试问题

在解决无人机路径规划问题之前，需要先将飞行环境用数学方式表达出来，本文采用了文献 [32] 的3D地形：

$$z\left(x,y\right)=\sin \left(x+a_1\right)+a_2\sin \left(x\right)+a_3\cos \left(y\right)+a_4\cos \left(y\right)+a_5\cos \left(a_6\sqrt{x^2+y^2}\right)+a_7\sin \left(a_7\sqrt{x^2+y^2}\right)$$ (12)

其中 $a_1,a_2,a_3,a_4,a_5,a_6,a_7$ 通常是常数，从而模拟有山脉和山谷的3D地形。例如，当 $a_1=3,a_2=3,a_3=3,$ $$a_5=4,a_6=1.8,a_7=3$$ 时，模型(12)所表示的地形如图3所示。

Figure 3. Illustration of the terrain

图3. 地形示意图

在本文的实验中，我们通过改变参数 $a_i\left(i=1,2,\cdots ,7\right)$ 的值来构造多个复杂3D地形，地形参数以及相应的起点和终点如表1所示，在每个地形中，飞行起点和终点都在地面上，即起点和终点的高度都是地形高度。

Table 1. The parameters of the test problems

表1. 测试问题的参数

4.3. 实验参数设置

4.4. 实验结果及分析

表2列出了PSEA、classEA、消融实验、DBO、LO、SWO、COA、LSO和GRO在每个测试问题上独立运行20次的路径长度结果。表格中的Mean、Std、Max、Min分别为路径长度的平均值、标准差、最小值和最大值，最好的结果已用粗体标出。选取每一个测试问题中，各算法运行结果最优的一次实验，实验结果的收敛曲线对比如图4所示。

Table 2. Comparison of the path length

表2. 路径长度的对比

测试问题中既有山体分布规律的地形(如UAV 1和UAV 6)，也有山体高度变化大的地形(如UAV 7和UAV 8)。在测试问题UAV 2、UAV 7和UAV 8中，对比算法DBO、COA和LSO生成的路径是不可行解，所以其路径长度比PSEA的小。从表2的数值结果上看，PSEA生成的平均路径长度最小，且路径长度的标准差最小，因此，PSEA算法生成最短路径的效果和稳定性都优于其他对比算法。此外，PSEA生成的路径更接近于一条连续的弧线。在转弯时，PSEA利用多个控制点使得路径更加平滑。在面对较高的山体时，PSEA通过改变飞行方向，绕过较高的山体，在经过高度不变的地形时尽可能保持直线飞行来缩短路径。从图4可以看出，与其他算法相比，PSEA和消融实验生成的初始路径长度都较小，与最终得到的最优路径长度差距小，能够在较少的迭代次数内得到较优的路径。

总体上看，PSEA和消融实验的算法均显著缩短了路径长度，因此PSEA算法是有效的。与消融实验相比，PSEA在面对UAV 7和UAV 8等复杂3D环境时表现更好，故所提出的杂交算子是有效的，在缩短路径长度的同时，也增加了路径的平滑性。

(a) (b) (c) (d) (e) (f) (g) (h)

Figure 4. Convergence curves of 9 algorithms based on test problems

图4. 测试问题中9种算法的收敛曲线

Table 3. Comparison of the number of control points

表3. 控制点数量的对比

表3列出了消融实验和PSEA在每个测试问题上所用的控制点数量，Median为控制点数量的中位数，Best为该算法所得最优路径的控制点数量。从表3可以看出，本文提出的PSEA算法可以根据地形的复杂程度自适应地调整控制点的数量，对于简单地形，如UAV 5和UAV 6，控制点的数量相对较少，而对于复杂地形，如UAV 7和UAV 8，控制点的数量较多。虽然UAV 2的地形比较简单，但实验中的飞行高度约束增加了无人机飞行的复杂性，导致控制点数量较多。此外，在改变飞行方向时，PSEA使用了更多的控制点来确保飞行路径的平滑，从而使得PSEA使用的控制点数量通常比消融实验使用的控制点数量多。

4.5. 进一步分析

在实验中，我们发现使用PSEA进行路径规划时，随着迭代次数的增加，生成的路径与地形的等高线重合部分增加，即无人机会在更多地方沿着等高线飞行。为了验证这一特征，我们做了一个实验：利用PSEA在一个地形上运行1500代，得到的第1500代的路径图如图5所示。

Figure 5. The path generated by PSEA in the 1500 generation

图5. PSEA在第1500代生成的路径

在第200代中，无人机仅在少数地方跟随等高线飞行，此时的路径长度为100.4516，在第500代中，无人机沿等高线飞行的距离增长，使路径长度减少。从图5可以明显看出，第1500代得到的路径与等高线重合程度更高，路径更加平滑，此时的路径长度为95.1995。结果表明，PSEA生成的路径可以使无人机在一部分区域沿着地形等高线飞行。

4.6. classEA控制点数目w的敏感度分析

在经典进化算法classEA中，w是一个重要的参数，为了说明本实验将w设置为10的合理性，我们将w分别设置为10、20、30、40、50后，在UAV 6和UAV 8这两个复杂程度不同的测试问题上独立运行20次，比较实验结果，比较的内容主要集中在路径长度和运行时间上，所得的直方图如图6所示，从图上可以看出 $w=10$ 的classEA在路径长度和运行时间方面都表现得更好。因此，本文将classEA的控制点数目w设置为10是合理的。

Figure 6. Histogram of the results of classEA with different w values

图6. w取值不同的classEA的运行结果直方图

5. 结论

本文提出了一种基于点集进化的无人机路径规划算法(PSEA)，该算法将控制点作为种群个体，用Dijkstra算法在种群中搜索并生成路径，然后利用进化算法结合提出的杂交算子对控制点集进行更新，该算法将经典路径规划算法与进化算法相结合，既具有经典算法的高搜索效率，又具有进化算法的全局搜索能力。通过一系列的测试问题对PSEA的性能进行了研究，实验结果表明PSEA能够有效解决复杂3D环境中无人机路径规划问题。

基金项目

广东省自然科学基金资助项目(2021A1515011839)