Multi-objective path planning based on improved RRT and GA: a case study of UAV forest patrol
-
摘要:目的
为解决无人机在人工林区巡检任务（如病虫害监测、火灾预防等）中的路径规划问题，即求解巡检点的最优遍历序列以及生成避障飞行轨迹，本文融合改进了快速随机扩展树（RRT）算法和遗传算法（GA），提出了一种多目标路径规划算法。
方法首先改进传统GA，使其能够在三维空间中遍历所有巡检点并求解最优序列。其次，依据该序列进行路径搜索，改进RRT算法的随机采样原理，通过靶心和绕树策略实现避障效果，并采用连续选择父节点策略，取消因避障产生的多余转折点。最后，通过3次B样条曲线优化，生成最终路径。
结果仿真结果表明，本算法能够在复杂林区环境中遍历所有巡检点，并在短时间内规划出高质量、无碰撞的路径。与粒子群算法（PSO）、蚁群算法（ACO）和RRT算法相比，当巡检点从3个增加到9个时，PSO、ACO、RRT算法搜索时间分别增加了221.77%、332.42%、184.78%，而本算法仅增加了102.35%。在9个巡检点的复杂环境中，本算法的路径耗散分别比PSO、ACO和RRT算法降低了14.46%、30.28%、24.76%，且路径质量显著提高，消除了路径交叉重合现象。此外，通过ROS平台，利用无人机在林区点云上进行模拟飞行并验证成功，证明本算法适用于林区巡检的多目标路径规划。
结论针对人工林区无人机巡检任务中的飞行路线规划问题，本文通过改进RRT与GA，成功规划出一条遍历所有巡检点且避开林区障碍物的无碰撞路径。相较于PSO、ACO和RRT算法，本算法在路径质量、路径耗散和搜索时间上均表现出显著优势。
-
关键词:
- 多目标优化 /
- 路径规划 /
- 快速随机扩展树(RRT) /
- 遗传算法(GA) /
- 无人机 /
- 粒子群算法(PSO) /
- 蚁群算法
Abstract:ObjectiveTo address the path planning problem of UAVs in artificial forest areas for inspection tasks (such as pest and disease monitoring and fire prevention), which involves solving the optimal traversal sequence of inspection points and generating collision-free flight trajectories, this paper proposes a multi-objective path planning algorithm by integrating and improving the rapidly-exploring random tree (RRT) algorithm and genetic algorithm (GA).
MethodFirst, the traditional GA was improved to enable traversal of all inspection points in 3D space and solve the optimal sequence. Second, based on this sequence, the path search was conducted by improving the random sampling principle of the RRT algorithm. Obstacle avoidance was achieved through target and tree-avoidance strategies, and redundant turning points generated by obstacle avoidance were eliminated by continuously selecting parent nodes. Finally, the final path was generated through three iterations of B-spline curve optimization.
ResultSimulation results show that the proposed algorithm can traverse all inspection points and plan high-quality, collision-free paths in complex forest environments within a short time. Compared with particle swarm optimization (PSO), ant colony optimization (ACO), and RRT algorithms, when the number of inspection points increased from 3 to 9, the search times of PSO, ACO, and RRT algorithms increased by 221.77%, 332.42%, and 184.78%, respectively, while the proposed algorithm only increased by 102.35%. In a complex environment with 9 inspection points, the path cost of the proposed algorithm was reduced by 14.46%, 30.28%, and 24.76% compared with PSO, ACO, and RRT algorithms, respectively. The path quality was significantly improved, eliminating path crossing and overlap. Additionally, the algorithm was successfully validated through simulation flights on forest point clouds using a UAV on the ROS platform, demonstrating its applicability for multi-objective path planning in forest inspections.
ConclusionFor the path planning problem of UAVs in artificial forest inspections, the proposed algorithm successfully planned a collision-free path that traversed all inspection points while avoiding obstacles in the forest. Compared with PSO, ACO, and RRT algorithms, the proposed algorithm showed significant advantages in path quality, path cost, and search time.
-
无人机因其小巧灵活且具备实时检测能力，在林区巡检和监测领域得到了越来越广泛的应用[1,2]。随着人工林区面积的不断扩大，为了更高效地完成巡检任务并扩大监测范围，以实现病虫害监测和林火灾害预防等功能，提升无人机的自主飞行能力并使其能够执行连续巡检任务变得至关重要[3]。因此，路径规划成为实现无人机自主飞行巡检的关键问题。林区巡检通常涉及多个巡检点，而单一目标的路径规划往往无法满足无人机在林区巡检的任务需求。因此，多目标路径规划成为无人机林区巡检的主要任务之一[4]。其核心目标是规划一条连接多个目标点且无碰撞的路径。在面向林区巡检的多目标路径规划中，需要解决两个关键问题：一是确定访问目标点的最优序列；二是生成各目标点之间无碰撞的路径。此外，为提高巡检效率，还需重点研究如何避免不同路径之间的重复交叉。
在工作环境中，寻找访问所有目标点的最优序列可以视为旅行推销员问题（traveling salesman problem, TSP）的一种应用场景[5]。在经典的TSP中，销售员需要访问若干指定城市，且每个城市仅访问一次。基于给定的城市之间的距离，目标是筛选出一条连接所有城市的最短路径[6]。最短路径从一个指定城市出发，经过所有其他城市后返回起始城市[7]。目前，TSP已受到广泛关注，并发展出许多有效的求解算法，例如启发式算法、遗传算法（genetic algorithm，GA）、模拟退火算法和蚁群算法等[8]。此外，在三维空间中应用遗传算法求解TSP也已取得相关研究成果。例如，Yang等[9]通过改进的遗传算法获得最短路径，并进一步进行分析和建模，基于数据分析和前人研究，提出了最短路径期望长度的回归模型。然而，TSP的研究通常未考虑目标之间路径的避障需求。在实际应用中，路径规划不仅需要确定最佳访问序列，还需要确保目标之间的轨迹无碰撞。例如，Yang等[10]针对机器人在仓库中运送货物的问题，提出了一种基于二维网格模型的路径规划算法，将传统仓库简化为基于节点的二维网格模型，并引入“最大凸多边形”的概念，用于在理想条件下求解遍历所有货物位置的最短路径。为提高求解速度，陈璐等[11]通过改良圈算法优化初始解，并在进化过程中自适应调整遗传操作的概率，结合模拟退火算法和逆转操作，改进了遗传算法在旅行商问题中的应用。韦念念等[12]则通过改进传统的分支定界算法，设计了一种由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组成的深度学习模型，用于学习分支规则，该方法在小规模旅行商问题上表现出较好的求解效果。此外，在动态旅行商问题中，刘孟莹等[13]提出了一种探索-利用权衡策略：在环境变化后，先通过模拟退火算法快速获得近优解，再利用自适应轮盘赌选择避免陷入局部极值。尽管已有研究在TSP的求解方法上取得了显著进展，但这些研究大多未涉及路径轨迹的避障问题。因此，对于无人机在复杂环境中的路径规划，不仅要确定最佳访问序列，还需确保路径的无碰撞性，这为路径规划问题带来了新的挑战。
目标之间的避障路径轨迹可以通过多种避障算法来解决。目前，避障算法的研究已取得大量成果，并形成了多种优秀的算法。这些算法主要包括全局路径规划算法（如A*算法和快速探索随机树RRT算法）、局部路径规划算法（如人工势场法和D*算法），以及智能路径规划算法（如粒子群算法PSO、蚁群算法ACO和遗传算法GA）。基于均匀随机采样RRT算法[14]因其概率完备性，已成为全局路径规划中的重要方法，尤其在机器人和无人机领域得到了广泛应用。然而，RRT算法存在一些不足，例如未考虑路径耗散，导致规划路径较为曲折。为解决这些问题，研究者们提出了多种改进方法，例如：RRT-Connect通过双向搜索加快路径规划速度[14]、Q-RRT* [15]、Informed RRT*[16]、BIT* [17] 等变体进一步优化了路径质量和规划效率。此外，吴语等[18]改进了RRT算法，使其适用于离散城市环境，并满足在线航线规划对计算速度的要求；栾添添等[19]提出了一种动态变采样区域路径规划方法，降低了无人车在传统RRT路径规划中的节点搜索盲目性和随机性；Kang等[20]针对RRT-Connect提出了一种基于三角不等式的重新布线方法，进一步加快了规划速度；Wang等[21]提出了一种基于圆弧圆角（CAF-RRT*）的路径规划算法，通过优化路径策略，显著提高了路径质量。尽管这些改进显著提升了RRT算法在复杂环境下的性能，但在多路径规划中，避免路径之间的相互影响仍需进一步研究。
多目标路径规划需要同时解决TSP和避障问题[23]。在传统解决方案中，通常先为每两个目标点之间规划无碰撞路径，然后基于这些路径进行TSP求解，以找到一条连通所有目标点且总路程最短的避障路径[24]。然而，在目标点和障碍物数量众多的复杂环境中，为每对目标点之间构建无碰撞路径的计算成本极高[25]。随着环境复杂度的增加，这种计算负担会急剧上升。由于其复杂性[26]，针对林区的无人机多目标路径规划在以往的研究中并不广泛。主要难点在于如何在复杂的林区环境中规划出高质量的无碰撞路径，同时避免不同路径之间的交叉重合。随着环境复杂度的提高和目标点的增加，这一问题的难度呈指数级增长。基于上述分析，本文拟提出一种改进的RRT与GA相结合的多目标路径规划算法，用于无人机林区巡检。首先，在GA中引入自适应调整机制，根据迭代次数动态改变交叉和变异概率，从而使其能够在三维空间中稳定地求解TSP。接着，提出一种绕树策略和靶心策略，对RRT算法进行改进，使其能够根据访问序列向指定目标进行避障路径规划，避免路径向其他目标偏移。最后，提出一种分类策略，并结合连续访问父节点的方法，优化路径中多余的转折和过大的弯曲，同时避免不同目标之间路径的相互干扰。
1. 改进的GA与RRT算法
1.1 林区环境建模
林区环境极其复杂，如图1a所示。在无人机执行巡检任务时，必须覆盖每个巡检点（图1a中标记的红色目标点），并避开错综复杂的障碍物，主要包括树干和树枝。为了使无人机能耗降至最低并实现总路程最短的目标，需要确定一种最优的访问序列来遍历所有巡检点，如图1a中黄色虚线所示的访问顺序。同时，还需避开树干、树枝等复杂障碍物，最终形成一条避障路径，如图1a中绿色曲线所示。目前，本研究考虑的林区障碍因素包括树干、树枝、地面以及林区相关建筑设施等。
根据林区障碍物的分布，搭建仿真林区环境（图1b）。林区环境是根据真实林区模拟生成的，树木的行间距在3 ~ 5 m之间随机分布，树的高度在4 ~ 7 m之间随机生成，每个树干上的树枝数量、大小和方向也各不相同。在传统的多目标路径规划方法中，先为每两个目标点之间规划避障路径的方式存在明显缺陷。当目标点数量较多时，这种方法会显著增加计算成本。因此，本文提出的算法分为两个阶段：第一阶段，遍历所有巡检点，使用改进的GA确定最佳访问序列，在此过程中，不考虑避障问题，仅以两点之间的欧氏距离作为路径成本；第二阶段，使用本文改进的快速探索随机树算法（绕树RRT，BT-RRT），根据第一阶段确定的访问序列规划避障路径，从而求得连通所有目标点的最终访问路径。
1.2 最佳访问序列求解
1.2.1 路径代价计算
在第一阶段，需要求解的最佳访问序列是三维旅行商问题（3D-TSP）。在林区自主巡检时，无人机需访问N个巡检点（目标点）中的每个点一次，最终以最低的总旅行成本返回原点。形式化定义如下：假设存在一个完全连通图G = （V，E），其中V = {0, 1, 2，…，N − 1}表示包含原点在内的N个巡检点的顶点集合；E为任意两个不同点i和j的连线组成边的集合，其中i ≠ j，i∈V, j∈V。每条边（i，j）∈ E与一个权重dij相关联，dij表示巡检点i和j之间的访问成本或距离。由于暂不考虑障碍物避让，因此采用欧氏距离来衡量。
最终目标是规划一条路径，使无人机从原点出发，依次访问每个巡检点一次，并返回原点，同时最小化总旅行成本。3D-TSP的核心在于确定最优的访问顺序，以最小化无人机在返回原点前的飞行距离总和，且每个点在返回原点前仅被访问一次。
3D-TSP的整体规划模型[27]定义如下：引入一个二进制变量xij，表示无人机是否经过边（i, j），当且仅当无人机通过边（i, j）时，xij = 1，其中i ≠ j，i, j∈V；否则，xij = 0。该问题的目标函数是最小化无人机飞行总距离 F。
min (1) 受以下约束条件限制。首先，无人机从编号为0的巡检点（起点）出发，并返回到起点，即
\sum\limits_{j = 1}^{N - 1} {{x_{0j}}} = 1 (2) \sum\limits_{i = 0}^{N - 2} {{x_{i0}}} = 1 (3) 除了0以外的每个需求点，无人机必须恰好访问一次，即
\sum\limits_{j = 1}^{N - 1} {{x_{ij}}} = 1 (4) \sum\limits_{i = 0}^{N - 2} {{x_{ij}}} = 1 (5) 为避免无人机在路径中形成子循环，引入一个决策变量μi， \forall i ∈ V，μi ≥ 0。其中，μi表示巡检点i的访问顺序。例如，当μi = 5时，表示点i是从起点开始访问的第5个点。通过μi确定每个巡检点的访问顺序，从而得出最佳的访问序列。
1.2.2 改进的遗传算法
GA因其良好的全局搜索能力，易于与其他算法结合改进，以及在TSP求解中的广泛应用，被选为第一阶段求解最佳序列的方法。然而，三维空间中的TSP研究并不广泛，其求解结果更加多样化且复杂。在林区巡检任务中，巡检点数量会根据任务动态变化，因此提高3D-TSP求解质量至关重要。
在遗传算法中，交叉操作和变异操作对算法的搜索能力起着关键作用，它们直接影响算法的收敛速度和解的质量。当交叉和变异概率过低时，基因交换次数减少，算法搜索能力下降，可能导致过早收敛，陷入局部最优。相反，当交叉和变异概率过高时，虽然搜索空间增大，但优秀解被破坏的可能性增加，导致效率降低。因此，合理设置交叉和变异概率，以平衡搜索效率和准确性，是优化算法性能的关键。
自适应遗传算法（AGA）通过动态调整交叉和变异概率，克服了传统遗传算法中参数固定的问题。例如，Srinivas等[28]提出的经典AGA算法，根据种群的适应度动态调整交叉概率Pc和变异概率Pm。其调整公式为
{P_{\text{c}}} = \left\{ \begin{gathered} \frac{{{k_1}({f_{\max }} - f')}}{{{f_{\max }} - {f_{avg}}}},f' \geqslant {f_{avg}} \\ {k_2},f' < {f_{avg}} \\ \end{gathered} \right. (6) {P_{\text{m}}} = \left\{ \begin{gathered} \frac{{{k_3}({f_{\max }} - f)}}{{{f_{\max }} - {f_{avg}}}},f \geqslant {f_{avg}} \\ {k_4},f < {f_{avg}} \\ \end{gathered} \right. (7) 式中：fmax为当前种群的最大值，favg为当前种群的平均值，f'为两个交叉对象中适应度函数值较大个体的值，f为要变异个体的值，k1、k2、k3、k4为 0 ~ 1 之间的任意数，通过对k1、k2、k3、k4的设置，在进行遗传操作时便可以自适应调整交叉概率与变异概率的数值。文献[28]通过调节参数，设置k2 = 0.5，k4 = 0.5，以利用种群中适应值低于平均值的个体来搜索全局最优解，同时推荐k1 = 1.0，k3 = 1.0。Srinivas等[28]提出的自适应交叉与变异概率虽然能够根据种群适应度值进行动态调整，但在算法初期，优秀个体的交叉与变异概率可能接近于零。这使得优秀个体在进化过程中过于稳定，难以与其他个体进行有效的基因交换或变异操作。因此，在全局寻优阶段，算法可能因缺乏足够的多样性而陷入局部最优，无法有效找到全局最优解。
本文在已有自适应遗传算法的交叉和变异概率基础上，进一步改进了交叉概率和变异概率的计算公式。具体而言，我们将自适应交叉概率函数映射到指数函数上，将变异概率函数映射到三角函数上，并引入迭代次数对交叉概率的影响。通过这些改进，使交叉概率和变异概率能够更灵活地适应算法的进化过程，从而提升算法的全局搜索能力和收敛性能。具体公式为
{P_{\text{c}}} = \left\{ \begin{gathered} {k_1} \times \frac{1}{{1 + \exp \left( {\dfrac{{(f' - {f_{{\text{avg}}}})}}{{{f_{\max }} - {f_{{\text{avg}}}}}} \times \dfrac{{3g}}{G}} \right)}},f' \geqslant {f_{{\text{avg}}}} \\ {k_2},f' < {f_{{\text{avg}}}} \\ \end{gathered} \right. (8) {P_{\text{m}}} = {k_3} \times \cos \left( {\frac{{(f - {f_{{\text{min}}}})}}{{{f_{\max }} - {f_{{\text{avg}}}}}} \times \frac{\varOmega }{2}} \right) (9) 式中：g为当前迭代次数，G为算法的迭代次数，fmin为当前种群的最小值。通过引入迭代参数，来影响交叉和变异概率，避免了其前期的个体因为适应度较高而导致交叉和变异概率几乎为零的情况，并且适应度越低，其交叉和变异概率越高，随着适应度的增大，交叉和变异概率逐渐减小。在不考虑迭代次数的情况下，参数具体变化值如图2所示。在整个迭代过程中，交叉和变异概率随着迭代次数增加整体呈减小趋势。算法前期以较高交叉概率为主，快速搜索解空间；后期以适度变异概率为主，保护优秀个体的同时增强搜索能力。这种动态调整机制避免了算法因前期个体适应度高而导致交叉和变异概率过低，进而陷入局部最优，从而提高了算法的全局搜索能力和求解质量。
![]()
图 2 交叉（a）、变异（b）概率变化图k2. 调节参数，Pc. 交叉概率；Pm. 变异概率；favg. 当前种群的适应度平均值；f'. 两个交叉对象中适应度较大个体的值；f. 要变异个体的适应度值Figure 2. Graph of crossover (a) and mutation (b) probability variations1.2.3 改进GA的求解步骤
改进GA的求解分为以下7步，算法流程图如图3所示。
（1）设置种群的大小为 M，初始迭代次数 g，最大迭代次数为 G，选择个体数量为 N，并将交叉概率Pc和变异概率Pm设置为自适应调节参数。
（2）对种群个体进行实数编码，采用贪心算法和替换策略初始化种群，生成初始种群 pop。
（3）计算每个个体的适应度函数值。
（4）选择操作：采用轮盘赌法进行选择，将适应度值转化为选择概率并映射到轮盘赌过程中，适应度较高的个体具有更大的选择概率，从而更有可能被选为父代个体进行交叉操作，以保留优良基因。
（5）交叉操作：使用多点交叉方式，交叉概率根据式（8）计算。
（6）变异操作：使用基本位变异方式，变异概率根据式（9）计算。
（7）判断是否满足停止条件，若满足则输出最优解，否则返回第（3）步继续执行。
1.2.4 3D-TSP规划
在此示例中（图4），共有9个巡检点，通过改进的GA获得了最优序列。图4中的蓝线表示最短路径，该路径仅基于巡检点之间的欧氏距离计算，未考虑障碍物，因此图中多处路线穿越了障碍物。在获得最佳访问序列后，后续将按照此序列进行避障路径规划。
1.3 避障路径规划
1.3.1 避障路径代价计算
在得到最佳访问序列后，进入第二阶段，根据该序列进行目标点之间的避障路径规划。在第一阶段，路径距离成本dij仅基于欧氏距离计算，忽略了障碍物的存在。而在第二阶段，考虑到障碍物的影响，路径代价采用避障后的实际代价Dij。此时，新的目标函数更改为最小化无人机避障路径长度F2。
\min {F_2} = \sum\limits_{i = 0}^{N - 2} {\sum\limits_{j = 1}^{N - 1} {{D_{ij}}} } {x_{ij}} (10) 在考虑避障后，真实的无人机路径可以视为由一系列坐标点连接而成的线段。因此，采用实数编码方式对路径进行编码，其表示为（xi, yi, zi），其中xi、yi、zi分别表示第i个航迹点在 x、 y 和 z 轴上的坐标，i = 1, 2, …, n，n为路径节点的数量。
需要避开的障碍物主要为树干和树枝，本研究采用不同大小、位置、方向的圆柱体进行建模（如图1所示）。这些圆柱体的数学表示为
\Gamma \left( \varepsilon \right) = {\left( {\frac{{(x - {x_0})}}{a}} \right)^{2d}} + {\left( {\frac{{(y - {y_0})}}{b}} \right)^{2e}} + {\left( {\frac{{(z - {z_0})}}{c}} \right)^{2f}} _{ } (11) 式中：（x0，y0，z0）为干扰中心的坐标，参数 a = b，d = e = 1，f > 1；当 \Gamma \left( \varepsilon \right) = 1时，所有点围成的曲面是一个圆柱，其中（x0，y0，z0）为该圆柱体的中心坐标。
假设环境模型中有m个圆柱体障碍物，用rk表示第k个圆柱体的半径，其中k∈{1, 2, …, m}。第k个圆柱体的中心高线为线段Hk，其两个端点的坐标分别为（xk1, yk1, zk1）和（xk2，yk2，zk2），其中k∈{1, 2, …, m}。为了避免路径与障碍物发生碰撞，规划出的路径需要满足避障约束。
\left\{ \begin{gathered} {L_{ik}} = \frac{{\left| {\left( {{x_{k1}}{\text{ }} - {\text{ }}{x_{\text{i}}},{\text{ }}{y_{k1}}{\text{ }} - {\text{ }}{y_i},{\text{ }}{z_{k1}}{\text{ }} - {\text{ }}{z_i}} \right){\text{ }} \times \left( {{x_{k2}}{\text{ }} - {\text{ }}{x_2},{\text{ }}{y_{k2}}{\text{ }} - {\text{ }}{y_2},{\text{ }}{z_{k2}}{\text{ }} - {\text{ }}{z_2}} \right)} \right|}}{{\left| {\left( {{x_{k2}}{\text{ }} - {\text{ }}{x_{k1}},{\text{ }}{y_{k2}}{\text{ }} - {\text{ }}{y_{k1}},{\text{ }}{z_{k2}}{\text{ }} - {\text{ }}{z_{k1}}} \right)} \right|}},\; k \in m,\; i \in n \\ \mu {{\text{r}}_k} \leqslant {L_{ik}},\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad k \in m,\; i \in n \\ \end{gathered} \right. (12) 式中： × 表示叉乘（外积）；|…| 表示向量的长度；Lik表示第i个航迹点到第k个圆柱中心线段的距离；μ为膨胀系数，本文取1.5，使航迹点到障碍物的距离不得小于最小安全距离。
在满足所有约束条件后，设每两个目标点之间的路径代价为Dij，路径上共有pij个航迹点，最终形成的航迹长度即为真实的路径代价Dij。
{D_{ij}} = \sum\limits_{i = 1}^{{p_{ij}}} {\sqrt {{{({x_{i + 1}} - {x_i})}^2} + {{({y_{i + 1}} - {y_i})}^2} + {{({z_{i + 1}} - {z_i})}^2}} } (13) 1.3.2 靶心策略
传统的RRT算法在空间中随机生成采样点（如图5a所示），其中绿色的点均为采样点。虽然这种随机生成的方式可以实现避障效果，但容易偏离目标。理想情况下，每一个采样点都应朝着目标点goal Ⅰ生成，然而传统RRT算法为了避障而随机生成采样点，很容易偏移至另一个目标点goal Ⅱ。在多目标路径规划中，这种偏移会对最终路径的质量产生极大影响。为了解决这一问题，使采样点更好地朝着理想目标进行避障规划，而不向其他目标偏移，本文引入了靶心策略（如图5b所示）。该策略从起始点start point出发，将下一个目标点goal Ⅰ设定为靶心G1。每次生成的采样点只能在靶心及其周围范围内随机分布，例如可能生成的采样点为G1、G2、G3等。这些采样点的生成受到概率函数P的约束，其表达式如式（14）所示。该概率函数P规定，采样点与靶心的距离d越远，其生成的概率越小，反之亦然。通过这种方式，可以使规划出的路径最大程度地贴合第一阶段的直线路径，从而降低向其他目标偏移的概率。
P = \frac{1}{{{e^{(d/k)}}}} (14) 式中：d 为与目标点偏移的距离；k为调节参数，根据树干直径调整，本文取0.75倍树干直径。
1.3.3 绕树策略
引入靶心策略虽能朝着下一个目标点采样，但遇到障碍物时，受靶心策略约束，无法避开。因此，本文提出绕树策略（如图6a）。当采样点rand point生成于障碍物内，或路径穿过障碍物（如图6a中绿色虚线路径）时，将该采样点推出障碍物。推出方向分为10种（如图6b）：垂直于树干轴截面（xy平面）有8种方向，沿树干轴方向（z轴）有2种。在本文搭建的环境中，经训练模拟，采样点被推出的距离取1.25倍步长较为合适。推出后的采样点为新采样点new point，与父节点连接。若new point仍在障碍物内，或其与父节点的连接路径检测到碰撞，则继续将new point往外推，循环此过程，直至检测到无碰撞路径，从而绕开障碍物。
1.3.4 连续选择父节点
经过绕树策略后，被推出障碍物的采样点new point与其父节点parent point连接时，路径会产生较大偏折，转向角α增大，路径代价也随之增加（图7a）。因此，本文在采样点访问父节点的同时，进一步访问父节点的父节点（祖父节点grandparent point），即每次采样点同时访问父节点和祖父节点。如果采样点与祖父节点连接后的路径代价小于当前与父节点连接的路径代价，则删除父节点，直接连接祖父节点（如图7b）。这一方法可显著降低路径偏折，减少路径代价。
1.3.5 分类树
为避免这种情况，本文提出分类树方法。每两个目标点之间的避障路径规划被划分为一个独立的搜索树类别。在每一类搜索树中，采样点只能搜索同类别树上的节点。例如，目标点goal Ⅰ与goal Ⅱ之间的路径为Ⅰ类树，对应蓝色路径；目标点goal Ⅱ与goal Ⅲ之间的路径为Ⅱ类树，对应红色路径（图8b）。不同类别的路径间节点搜索互不影响，从而避免路径重合。
1.3.6 3次B样条曲线优化
经过连续访问父节点后，路径的平滑度提高，总节点数减少，转弯点数量、总转弯角度和路径长度也随之减少。然而，由于存在一些必要的拐角，路径的平滑度仍未达到理想状态。B样条曲线作为一种特殊的样条曲线，具有凸包性、几何不变性、局部支座性和非负性等优点，能够灵活地平滑路径[29]，更好地适应各种实际轨迹要求。为确保优化后的路径包含起始点和目标点，并保持连续的平滑度，本文采用准均匀3次B样条曲线对路径进行平滑处理。然而，过度光滑可能导致路径与障碍物发生碰撞的风险。为此，研究中对障碍物体积进行了膨胀，膨胀系数μ取前文的1.5，以确保经准均匀3次B样条曲线处理后的路径不会与障碍物相撞。
2. 仿真验证
为了验证本算法在多目标路径规划中的有效性，进行了一系列仿真试验。试验搭建了简单环境和复杂环境两种不同的林区地图（图9、10），并根据环境大小设置不同数量的巡检点进行对比。当巡检点数量达到9个时，巡检区域可覆盖大部分地图，且分布不会过于密集，从而在目标点数量较多时更好地检验算法的避障性能。简单环境中树木障碍物数量较少、间隙较大、分布稀疏；而复杂环境中树木障碍物数量较多、间隙较小、分布密集。
为了凸显本算法的避障优势，选用三维空间搜索效果较好的RRT算法、蚁群算法（ACO）和粒子群算法（PSO）进行对比，主要对比搜索时间、路径耗散和路径质量等指标。在这些环境中，工作空间是完全已知的，且假设障碍物为静态。PSO和ACO算法的搜索时间以达到最优适应度所消耗的时间为准。所有仿真均在配置为英特尔（TM）Core（TM）i7-12700H 2.70 GHz和16GB RAM的笔记本电脑上进行，采用Matlab编程实现。
2.1 简单环境仿真试验
为了充分体现本算法的性能，先将避障环境简化为9棵树（3 × 3）的林区环境（图9），分别设置3、6、9个巡检点进行多目标路径规划，数据结果取运行20次的平均值。从最终生成的路径质量来看，所有算法均能达到避障效果。然而，由于林区障碍物复杂，PSO算法生成的路径较为曲折，RRT算法存在较大迂回路径。本文改进的BT-RRT算法引入靶心策略，约束路径生成方向，避免了迂回现象。ACO算法随着目标点数量增加，甚至出现路径交叉现象。而本算法采用绕树策略和连续选择父节点策略，显著减少了路径转折。针对林区障碍物复杂导致随机生成采样点易陷入障碍物的问题，本文直接使采样点朝向下一个目标生成，若在障碍物内则将其推出，减少了重复生成采样点的时间，提高了计算效率。同时，通过连续选择父节点避免了过大转折角，进一步降低了路径代价。
在简单环境中，树木障碍物稀疏，4种算法的路径耗散差距不大，但本算法的路径耗散始终最少（表1）。在搜索时间方面，PSO和ACO算法因需不断迭代以获取最优结果，耗时较长；而BT-RRT和传统RRT直接搜索路径，耗时较短。当巡检点从3个增加到6个时，PSO、ACO、RRT和BT-RRT算法的搜索时间分别增加了74.47%、53.73%、9.42%和4.56%；从3个增加到9个时，搜索时间分别增加了173.63%、155.51%、67.13%和21.90%。从受到目标点数量和环境复杂度的影响来看，BT-RRT对树木障碍物的适应能力更强。
表 1 简单环境中各算法的搜索时间和路径耗散Table 1. Search time and path dissipation of various algorithms in simple environments算法名称 巡检点数量 搜索时间/s 路径耗散/m PSO 3 40.565 62.169 6 70.773 80.303 9 110.996 96.200 ACO 3 70.695 68.965 6 108.677 86.732 9 180.632 99.802 RRT 3 7.530 67.778 6 8.239 85.609 9 12.585 98.163 BT-RRT 3 6.735 60.999 6 7.042 75.848 9 8.210 86.960 2.2 复杂环境仿真试验
本文的绕树RRT（BT-RRT）算法是针对复杂林区环境改进的。通过提升模拟环境复杂度，采用25棵树（5 × 5）构建林区环境，更能体现算法在多目标路径规划中的优势。实验数据取运行20次的平均值。从图10可见，其他算法在复杂环境中生成的路径明显变得曲折，尤其在巡检点数量达到9个时（图10c），PSO和ACO算法路径出现扭曲折叠，ACO甚至出现路径交叉，RRT算法出现路径重合（图10b），路径质量随目标点增多显著下降。而BT-RRT算法由于引入靶心策略，每条路径均朝向下一个目标点生成，避免了路径交叉。在分类树策略下，各路径间搜索互不影响，解决了RRT算法采样点重合导致的路径重合问题。同时，配合绕树和连续选择父节点策略，实现了避障效果，消除了路径迂回，保持了路径质量。此外，本文还引入3次B样条曲线对路径进行平滑处理，进一步减小路径长度和转角数量。
在复杂环境中，树木障碍物极为密集，4种算法的路径耗散和搜索时间差距显著增大。本算法在搜索时间和路径耗散上表现出明显优势（如表2）。当巡检点从3个增加到6个时，PSO、ACO、RRT和BT-RRT算法的搜索时间分别增加了96.28%、102.27%、66.24%和48.86%；从3个增加到9个时，搜索时间分别增加了221.77%、332.42%、184.78%和102.35%。在复杂环境中，本算法对目标点数量增加的适应性更强。此外，当巡检点数量固定时，环境从简单变为复杂，本算法受到的影响最小。
表 2 复杂环境中各算法的搜索时间和路径耗散Table 2. Search time and path dissipation of various algorithms in complex environments算法名称 巡检点数量 搜索时间/s 路径耗散/m PSO 3 173.751 65.443 6 341.034 80.309 9 559.073 91.812 ACO 3 230.439 66.108 6 466.112 95.151 9 996.472 112.652 RRT 3 24.656 65.313 6 40.989 92.656 9 70.215 104.385 BT-RRT 3 12.302 62.772 6 18.313 70.891 9 24.893 78.539 2.3 仿真结果分析
通过绘制曲面图直观展示4种算法在不同环境复杂度和巡检点数量下的搜索时间（如图10）。简单环境复杂度设为1，复杂环境设为2。由图11a、11b可知，PSO和ACO算法受巡检点数量和环境复杂度的影响显著，随着两者的增加，搜索时间急剧上升。这表明传统PSO和ACO算法在复杂环境下的多目标路径规划存在明显缺陷。而由图11c、11d可见，本算法对多目标路径规划进行了改进，受巡检点数量和环境复杂度的影响显著降低。
不考虑路径质量，仅从规划时间来看，本算法优于传统RRT，且更适应林区障碍物环境。本算法通过改变随机采样方式，仅朝向下一个目标点采样，若采样点位于障碍物内，则将其推出障碍物，避免了对空间中其他障碍物的无用采样，从而大幅降低了采样时间。由于障碍物形状未知，本文采用10种固定方向将采样点推出障碍物，虽然可以实现推出，但可能陷入非最优方向。后续可重点研究根据障碍物形状及采样点与障碍物的相对位置来优化推出方向。
在路径耗散方面，本算法相较于其他3种算法显著降低，且随着环境复杂度和巡检点数量的增加，优势愈发明显。本算法在靶心策略下，路径几乎不向其他方向偏折，通过连续选择父节点去除了避障形成的多余转折角，并借助3次B样条曲线优化，进一步减少了路径耗散。图12显示，在不同环境复杂度和巡检点数量下，本算法的路径耗散均低于其他3种算法。例如：在包含9个巡检点的复杂环境中，由表2可得，PSO、ACO和RRT算法的路径耗散分别为91.812、112.652和104.385 m，而本算法的路径耗散仅为78.539 m，相比上述3种算法分别降低了14.46%、30.28%和24.76%。
林区环境极为复杂，本文仅针对静态林区环境进行了避障规划。然而，真实的林区中存在诸多不确定因素，如活动的动物、飞鸟、工作人员等动态障碍物。如何避开这些动态障碍物是林区路径规划的一大难点。将静态障碍物与动态障碍物相结合，在完成全局最优路径规划的基础上，对局部动态障碍物进行实时避障调整，将是本文后续研究的重点。
3. 林区点云真实环境验证
在仿真中，本算法取得了良好结果。为检验其在真实林区巡检中的飞行效果，选取北京市海淀区八家公园内的榆树林区（如图13a）作为测试场地。通过三维激光雷达扫描生成点云地图，该地图与真实林区的复杂情况高度匹配，包括树木的形状、位置、行间距、大小，树枝的状态、长短、粗细，地面起伏程度以及林区相关设施等（如图13b）。随后，在ROS平台下，利用PX4飞控系统搭载3D激光雷达传感器，开展了无人机在林区点云上的模拟巡检飞行。
将PX4飞控系统搭建完成并载入林区点云地图（如图14a），随后搭载3D激光雷达（如图14b），其感知范围为5 m。将检测到的点云进行栅格化建图，用于障碍物识别与路径规划。未检测到的点云区域显示为黑色，表示未知区域。
在模拟巡检飞行中，记录了无人机在不同时刻到达不同巡检点的飞行状态（如图15）。结果表明，本算法能够沿着所求的最优序列安全到达每一个巡检点，避开所有林区障碍物，且路径无迂回和交叉。
4. 结 论
本文针对人工林区无人机巡检任务规划问题，融合改进了快速随机扩展树算法（RRT）和遗传算法（GA），提出了一种多目标路径规划算法。通过引入迭代次数自适应调整GA的交叉和变异概率，引入靶心和绕树策略改进RRT，并采用分类树方法避免路径交叉重合，算法在复杂林区环境中表现出色。仿真验证表明，本算法能够高效遍历所有目标点，求解最优访问序列，并快速生成高质量、无碰撞的连通路径。与粒子群算法（PSO）、蚁群算法（ACO）和RRT算法对比，本算法在不同数量的巡检点（3、6、9个）和不同复杂度环境下均展现出显著优势。研究结论如下。
（1）路径质量方面，本算法规划的路径无交叉重合、迂回或巨大转折现象。
（2）时间消耗方面，本算法用时最短。在复杂环境中，当巡检点从3个增加到9个时，PSO、ACO、RRT和本算法的搜索时间分别增加了221.77%、332.42%、184.78%和102.35%。
（3）路径耗散方面，本算法路径长度最短。在9个巡检点的复杂环境中，PSO、ACO、RRT算法的路径耗散分别为91.812、112.652和104.385 m，而本算法仅为78.539 m，分别降低了14.46%、30.28%和24.76%。
（4）本算法在ROS平台上通过无人机搭载PX4飞控系统和3D激光雷达进行模拟巡检飞行，成功遍历所有巡检点并避开林区障碍，验证了其在林区巡检中的有效性和可行性。
然而，当前研究仅针对静态林区环境，主要集中在固定障碍物（如树木、地形）的避障路径规划。未来研究需重点关注动态林区障碍物的避障策略，例如野生动物的活动、行人穿行等突发情况。这些动态因素不仅增加了路径规划的复杂性，还可能对无人机的安全飞行和巡检任务的连续性带来挑战。此外，随着无人机在林区巡检任务中的应用日益广泛，多机协同巡检的策略也亟待研究。通过多机协同，可以提高巡检效率，覆盖更广泛的区域，同时需要解决无人机之间的通信、任务分配以及协同避障等问题。因此，未来的路径规划研究不仅要考虑单一无人机的动态避障能力，还需探索多机协同作业下的高效路径规划方法，以更好地适应复杂多变的林区环境，同时兼顾生态保护和野生动物安全。
-
![]()
图 2 交叉（a）、变异（b）概率变化图
k2. 调节参数，Pc. 交叉概率；Pm. 变异概率；favg. 当前种群的适应度平均值；f'. 两个交叉对象中适应度较大个体的值；f. 要变异个体的适应度值
Figure 2. Graph of crossover (a) and mutation (b) probability variations
表 1 简单环境中各算法的搜索时间和路径耗散
Table 1 Search time and path dissipation of various algorithms in simple environments
算法名称 巡检点数量 搜索时间/s 路径耗散/m PSO 3 40.565 62.169 6 70.773 80.303 9 110.996 96.200 ACO 3 70.695 68.965 6 108.677 86.732 9 180.632 99.802 RRT 3 7.530 67.778 6 8.239 85.609 9 12.585 98.163 BT-RRT 3 6.735 60.999 6 7.042 75.848 9 8.210 86.960 
下载: 导出CSV
表 2 复杂环境中各算法的搜索时间和路径耗散
Table 2 Search time and path dissipation of various algorithms in complex environments
算法名称 巡检点数量 搜索时间/s 路径耗散/m PSO 3 173.751 65.443 6 341.034 80.309 9 559.073 91.812 ACO 3 230.439 66.108 6 466.112 95.151 9 996.472 112.652 RRT 3 24.656 65.313 6 40.989 92.656 9 70.215 104.385 BT-RRT 3 12.302 62.772 6 18.313 70.891 9 24.893 78.539
下载: 导出CSV
-
[1] 杨兰, 孟凡烨. 林火防控中多旋翼无人机的应用分析[J]. 林业科技情报, 2020, 52(4): 105−107. doi: 10.3969/j.issn.1009-3303.2020.04.035 Yang L, Meng F Y. Application analysis of multi-rotor UAV in forest fire prevention and control[J]. Forestry Science and Technology Information, 2020, 52(4): 105−107. doi: 10.3969/j.issn.1009-3303.2020.04.035
[2] 徐凯男, 朱红伟. 无人机在森林防火中的应用研究[J]. 林业机械与木工设备, 2024, 52(8): 57−60. doi: 10.3969/j.issn.2095-2953.2024.08.010 Xu K N, Zhu H W. Research on the application of UAV in forest fire prevention[J]. Forestry Machinery & Woodworking Equipment, 2024, 52(8): 57−60. doi: 10.3969/j.issn.2095-2953.2024.08.010
[3] Li J, Kang F, Chen C, et al. The improved A* algorithm for quadrotor UAVs under forest obstacle avoidance path planning[J]. Applied Sciences, 2023, 13(7): 4290. doi: 10.3390/app13074290
[4] 马力, 江东晓, 辛明翰, 等. 基于农机智能管理平台的田间燃油配给策略[J]. 农业工程学报, 2024, 40(15): 22−33. Ma L, Jiang D X, Xin M H, et al. Fuel rationing strategy in farmland based on intelligent management platform for agricultural machinery[J]. Transactions of the Chinese Society of Agricultural Engineering, 2024, 40(15): 22−33.
[5] Vonásek V, Pěnička R. Space-filling forest for multi-goal path planning[C]//2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). Zaragoza: IEEE, 2019: 1587-1590.
[6] Sun C. A study of solving traveling salesman problem with genetic algorithm[C]//2020 9th International Conference on Industrial Technology and Management (ICITM). Oxford: IEEE, 2020: 307-311.
[7] Wurll C, Henrich D, Wörn H. Multi-goal path planning for industrial robots[J]. International Conference on Robotics and Application, 1999, 18: 1−7.
[8] Spitz S N, Requicha A A. Multiple-goals path planning for coordinate measuring machines[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings. San Francisco: IEEE, 2000: 2322-2327.
[9] Yang H, Lu X, Zhou X, et al. Expected length of the shortest path of the traveling salesman problem in 3D space[J]. Journal of Advanced Transportation, 2022(1): 4124950.
[10] Yang B, Li W, Wang J, et al. A novel path planning algorithm for warehouse robots based on a two-dimensional grid model[J]. IEEE Access, 2020, 8: 80347−80357. doi: 10.1109/ACCESS.2020.2991076
[11] 陈璐, 魏文红. 基于改进自适应遗传算法的旅行商问题研究[J]. 东莞理工学院学报, 2024, 31(5): 1−8. Chen L, Wei W H. Research on travelling salesman problem based on improved adaptive genetic algorithm[J]. Journal of Dongguan University of Technology, 2024, 31(5): 1−8.
[12] 韦念念, 韩曙光. 基于图卷积和注意力神经网络的旅行商问题新解法[J]. 计算机科学, 2024, 51(增刊1): 222−229. doi: 10.11896/jsjkx.230700222 Wei N N, Han S G. New solution for traveling salesman problem based on graph convolution and attention neural network[J]. Computer Science, 2024, 51(Suppl.1): 222−229. doi: 10.11896/jsjkx.230700222
[13] 刘孟莹, 秦进, 陈双. 求解动态旅行商问题的蚁群优化算法新策略[J]. 计算机仿真, 2024, 41(8): 349−355. doi: 10.3969/j.issn.1006-9348.2024.08.061 Liu M Y, Qing J, Chen S. Novel strategy of ant colony optimization for dynamic traveling salesman problem[J]. Computer Simulation, 2024, 41(8): 349−355. doi: 10.3969/j.issn.1006-9348.2024.08.061
[14] Kuffner J J, La Valle S M. RRT-connect: an efficient approach to single-query path planning[C]//Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings. San Francisco: IEEE, 2000: 995-1001.
[15] Jeong I B, Lee S J, Kim J H. Quick-RRT*: triangular inequality-based implementation of RRT* with improved initial solution and convergence rate[J]. Expert Systems with Applications, 2019, 123: 82−90. doi: 10.1016/j.eswa.2019.01.032
[16] Gammell J D, Srinivasa S S, Barfoot T D. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//2014 IEEE/RSJ international conference on intelligent robots and systems. Chicago: IEEE, 2014: 2997-3004.
[17] Gammell J D, Srinivasa S S, Barfoot T D. Batch informed trees (BIT*): sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs[C]//2015 IEEE international conference on robotics and automation (ICRA). Seattle: IEEE, 2015: 3067-3074.
[18] 吴宇, 胡莘婷. 城市低空环境中多旋翼无人机在线航线规划方法[J]. 控制与决策, 2021, 36(12): 2851−2860. Wu Y, Hu X T. An online route planning method for multi-rotor drone in urban environments[J]. Control and Decision, 2021, 36(12): 2851−2860.
[19] 栾添添, 王皓, 孙明晓, 等. 基于动态变采样区域RRT的无人车路径规划[J]. 控制与决策, 2023, 38(6): 1721−1729. Luan T T, Wang H, Sun M X, et al. Path planning of unmanned vehicle based on dynamic variable sampling area RRT[J]. Control and Decision, 2023, 38(6): 1721−1729.
[20] Kang J G, Lim D W, Choi Y S, et al. Improved RRT-connect algorithm based on triangular inequality for robot path planning[J]. Sensors, 2021, 21(2): 333. doi: 10.3390/s21020333
[21] Wang B, Ju D, Xu F, et al. CAF-RRT*: a 2D path planning algorithm based on circular arc fillet method[J]. IEEE Access, 2022, 10: 127168−127181. doi: 10.1109/ACCESS.2022.3226465
[22] Zhong H, Cong M, Wang M, et al. HB-RRT: a path planning algorithm for mobile robots using halton sequence-based rapidly-exploring random tree[J]. Engineering Applications of Artificial Intelligence, 2024, 133: 1952−1976.
[23] Faigl J. An application of self-organizing map for multirobot multigoal path planning with minmax objective[J]. Computational Intelligence and Neuroscience, 2016(1): 2720630.
[24] Cui X, Wang Y, Yang S, et al. UAV path planning method for data collection of fixed-point equipment in complex forest environment[J]. Frontiers in Neurorobotics, 2022, 16: 1105177. doi: 10.3389/fnbot.2022.1105177
[25] Englot B, Hover F. Multi-goal feasible path planning using ant colony optimization[C]//2011 IEEE International Conference on Robotics and Automation. Shanghai: IEEE, 2011: 2255-2260.
[26] Diaz-Arango G, Vazquez-Leal H, Hernandez-Martinez L, et al. Multiple-target homotopic quasi-complete path planning method for mobile robot using a piecewise linear approach[J]. Sensors, 2020, 20(11): 3265. doi: 10.3390/s20113265
[27] Punnen A P. The traveling salesman problem and its variations[M]. Boston, MA: Springer US, 2007.
[28] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transaction on Systems, Man and Cybernetics, 1994, 24(4): 656−667. doi: 10.1109/21.286385
[29] Zhou B, Gao F, Wang L, et al. Robust and efficient quadrotor trajectory generation for fast autonomous flight[J]. IEEE Robotics and Automation Letters, 2019, 4(4): 3529−3536. doi: 10.1109/LRA.2019.2927938
计量
- 文章访问数: 34
- HTML全文浏览量: 3
- PDF下载量: 11
