基于改进A*算法的无人机路径规划研究

Research on UAV Path Planning Based on Improved A* Algorithm

摘要: 针对于标准的A*算法在无人机路径中存在搜索效率低，对动态环境的适应性较差及路径不平滑等问题，本文提出两种改进的A*算法。首先提出二维栅格地图三维化建模方法，通过叠加高度信息并引入颜色表征地形高低，简化三维路径规划问题，使环境模型更直观，便于快速建立仿真模型；其次针对标准A*算法启发式函数权重固定的缺陷，引入动态自适应权重系数ω，根据预估代价与阈值的关系动态调整权重比例进行优化，提出自适应权重A*算法以提升路径求解效率；最后引入B样条曲线平滑的方法，对规划路径进行几何优化以改善平滑度。仿真结果表明，改进后的A*算法能有效解决复杂环境下的路径规划问题，在缩短路径长度、改善路径平滑度、提升搜索效率方面表现显著。

Abstract: Aiming at the problems of low search efficiency, poor adaptability to dynamic environments, and uneven paths of the standard A* algorithm in UAV paths, this paper proposes two improved A* algorithm. Firstly, a three-dimensional modeling method for two-dimensional grid maps is proposed. By overlaying height information and introducing color representation of terrain height, the problem of three-dimensional path planning is simplified, making the environment model more intuitive and facilitating the rapid establishment of simulation models; Secondly, in response to the fixed weight of the heuristic function in the standard A* algorithm, a dynamic adaptive weight coefficient ω is introduced to dynamically adjust the weight ratio based on the relationship between the estimated cost and the threshold for optimization. The adaptive weight A* algorithm is proposed to improve the efficiency of path solving; Finally, the B-spline curve smoothing method is introduced to perform geometric optimization on the planned path to improve smoothness. The simulation results show that the improved A* algorithm can effectively solve path planning problems in complex environments, with significant performance in shortening path length, improving path smoothness, and enhancing search efficiency.

1. 引言

随着无人机相关产业的发展应用，使得民生问题和国防问题得到了更加有力的保障。比如，荒野搜救[1] [2]、农业生产[3] [4]、地形勘探[5] [6]等诸多领域会随着无人机的投入而变得更加有效，无人机应用前景至关重要。兼顾了体积小、灵活、适应能力强等诸多优点，已经随着社会的发展逐步融入了人们的日常生活中，极大地降低了成本，并且作为提高工作效率的有效手段。

路径规划是无人机技术研究领域的热门话题，也是核心技术之一，主要是在某一特定的环境中，能够帮助无人机规划出相对较优或最优路径来有效完成任务，从而使得性能、目标任务的需求以及环境等干扰因素对无人机的影响最小。静态航迹规划和动态航迹规划基于无人机的飞行任务和环境而定义，其中，静态航迹规划是基于环境、障碍、危险等都不再发生变化的前提下，为无人机规划的一条从开始到任务完成的最优路径[7]。然而，危险因素通常会变化，因此，动态路径规划的实用性则更强，同时在处理难度上也更加棘手[8]。

对于无人机路径规划的研究，可追溯到20世纪70年代的美国空军实验室，该实验室的Albert E. Bryson等研究了基于自适应控制理论的航迹规划方法[9]。无人机路径规划的算法主要分为经典算法和智能算法。其中，较为经典的算法当属A*算法，也是当前研究路径规划使用最多的算法之一。国内基于A*算法的无人机三维路径规划研究近年来发展迅速，随着研究的深入发现标准A*算法在无人机路径中存在了一些问题，众多学者提出了不同的改进方法。针对搜索效率低、路径冗余点多的问题，唐嘉宁等人提出了双向搜索与定向搜索结合的双定向机制，减少路径的冗余节点，提高了搜索效率[10]。闫少华等人根据节点与目标点距离自动调整步长，减少无效节点扩展，提升搜索速度。结合欧氏距离、曼哈顿距离和对角线距离，优化路径质量[11]。针对路径平滑度的问题上，张丽丽等人改进的算法扩展搜索节点通过减少路径折角，在保证安全避障的前提下，显著提升了路径搜索效率和平滑度[12]。

针对一些存在的问题，本文从其他角度出发提出新的改进后的A*算法。首先提出二维栅格地图三维化方法，通过叠加高度信息并引入颜色表征地形高低，简化三维路径规划问题；其次针对标准的A*算法启发式函数权重固定的缺陷，引入动态自适应权重系数ω，根据预估代价与阈值的关系动态调整权重比例，提升了算法在复杂三维环境中的搜索效率和路径质量；最后采用B样条曲线对A*算法生成的路径进行几何优化，提升了无人机飞行的实际可行性。

2. 标准A*算法的路径规划

2.1. 环境建模

路径规划的前提是在无人机飞行的环境内建模，合适的三维空间模型是求解无人机路径规划的首要条件和基础，也是最优路径能否高效且准确率高的必要条件。一般情况下，环境模型的简化在一定程度上也使得路径规划的环境复杂度降低，极大的激励寻找到最优路径。

环境建模是仿真实验的基础之一，当前应用范围较广的三维建模方法有三维地图建模法、栅格地图建模法、可视图法、自由空间法等。三维地图建模法是先将三维空间切分成垂直于z轴的n个水平面，再对水平面分成网格。该三维地图建模法被广泛应用于路径规划方法中，且属于较为有效的建模方法[13]。模型中每个小正方体表示一个位置单元，即无人机所在的位置状态，无人机的任意一个位置都有独一无二的坐标来表示，并且无人机在任意一个时刻的一个状态有且只能出现在某一个位置的坐标中。栅格地图建模法的第一步是将地图所在区域划分为大小相等的单元，即正方形或长方形的栅格单元。每个栅格单元表示地图上的其中一部分区域。给每个栅格单元指定属性值，用来表示该单元的状态特征，内含通行信号、所出位置的地形高度、环境状态等特征。

2.2. 基本原理

A*算法是一种相对出现比较早的启发式搜索算法，于上个世纪60年由三位学者共同提出。A*算法是一种广泛应用于图形搜索和路径规划的启发式函数，其包含了三个主要部分：启发式函数、搜索邻域和禁忌表[14]。因此A*算法能够结合起点与终点的信息提供基本的搜索方向，在启发式函数允许的情况下搜索出最佳路径，并且能够结合实际地图情况和自身搜索情况动态调整搜索方向，是一种同时平衡了Dijkstra算法和贪心算法。

2.2.1. 启发式函数

A*算法的启发式函数又称之为评价函数或评估函数，其数学公式为：

$f\left(n\right)=g\left(n\right)+h\left(n\right)$ (1)

其中n代表搜索路径的当前节点，$g\left(n\right)$ 代表起始点到当前点目前行进路径的长度，也称实际代价；$h\left(n\right)$ 是指当前节点n到终点的最优路径的路径长度，也称为预估代价；$f\left(n\right)$ 代表总代价[15]。

栅格地图下距离计算方法通常包含三种：欧几里得距离、切比雪夫距离和曼哈顿距离如图1所示。

Figure 1. Distance diagram of three distance calculation methods

图1. 三种距离计算方法的距离示意图

本文采用的切比雪夫距离计算法，该方法一般应用于A*算法的八邻域方法中，可以计算距离时必须沿着栅格边缘或者对角线进行计算，其计算的距离长度要比曼哈顿距离更短。设当前节点为$\left(x_1,y_1\right)$ ，目标节点为$\left(x_2,y_2\right)$ ，其计算公式如下：

$\text{Distance}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right)$ (2)

2.2.2. 搜索邻域

在进行无人机路径规划时要选择合适的途径点位置和方向，那么如何选择节点和搜索方向不仅需要依靠启发式函数进行判断，搜索邻域就是重要的因素之一。搜索邻域是指A*算法在路径搜索的迭代过程中寻找下一个节点时，确定潜在的搜索节点，一般会基于当前节点拓展到所有相邻的节点[16]。栅格地图下包含常见的三种邻域：四邻域、八邻域和三维邻域，本文采用的八领域搜索邻域法，其方向示意图如图2所示。

Figure 2. Diagram of eight neighborhood search method

图2. 八邻域搜索法示意图

2.2.3. OPEN/CLOSED表

节点选取过程可知，每一次路径搜索迭代都会进行节点选取和途径，为了避免下一次相同节点的重复经过，需要对整个搜索过程进行记录。A*算法引入OPEN表和CLOSED表来记录节点的途径情况，其中OPEN表用于存放A*算法尚未经过的节点，CLOSED表用于记录A*算法已经途径过的节点，A*算法在每一次路径搜索的迭代过程中，首先会迭代OPEN表和CLOSE表来确定哪些节点可以作为节点，再结合搜索邻域方法和选择本次迭代潜在的节点，最后分别计算每个潜在节点的评价函数的值来选择最佳节点[17]。迭代完成后检查OPEN表长度是否为0，若为0则说明A*算法在三维地图下未搜索到路径，则直接退出。

2.3. 模型搭建

借助Matlab仿真软件搭建基于标准A*算法的无人机路径规划仿真模型，步骤如下：

1) 首先导入一个11*11的高度信息矩阵，利用插值法对地图进行细分，在利用网格化对地图进行栅格化处理；

2) 设定无人机在三维地图下的起点为[10, 80]和终点[95, 5]，确定了无人机整体飞行路径的方向，设定了无人机的邻域搜索方向为8邻域搜索方法，初始化OPEN/CLOSE表；

3) 判断是否到达终点，如果没有则分别计算当前节点下8邻域方法确定的潜在节点；若达到终点则输出路径；

4) 根据潜在节点和OPEN/CLOSED表来筛选出可行的途径点，并分别计算每一个途径点的$f\left(n\right)/g\left(n\right)/h\left(n\right)$ 值并更新表中数值；

5) 通过回溯途径点的方式来生成路径，并利用切比雪夫距离计算方法计算路径长度，输出路径长度、仿真时间、搜索节点数和迭代次数等仿真结果；

6) 输出A*算法求解出的路径示意图。

为了避免单一地图的特殊性，程序增加了一个地图选择功能，用户可以自定义地图后并保存mat形式，在仿真时选择导入想要测试的地图。基于标准A*算法的无人机在三维地图下无人机路径规划的流程如图3所示。

Figure 3. Process diagram for solving UAV path planning in 3D map using standard A*

图3. 标准A*求解无人机在三维地图下无人机路径规划的流程图

3. 改进A*算法的路径规划

3.1. 三维地图建模优化

本文在二维0~1栅格地图的基础上对其进一步作出优化，在该地图的基础上加入环境的高度信息，从而得到三维地图，与此同时，引入不同颜色来表示不同的高度，颜色偏黄表示高度越高，颜色偏蓝表示高度越低，从而使得建立的环境模型更加直观，也更加快速的建立仿真模型，将三维的路径规划问题简化，极大的帮助无人机路径规划的最优解的求取。三维栅格地图及其扁平化如图4和图5所示。

3.2. 自适应权重A*算法

A*算法最核心的部分就是启发式函数，启发式函数公式可知启发式函数包含了实际代价函数和预估函数两个部分，并且标准A*算法的启发式函数公式中，实际代价函数和预估函数按照1:1的比例相加，两者之间的权重系数为1 [18]。假设A*算法的启发式函只包含了实际代价函数而去掉预估函数，那么A*算法在路径搜索过程中只考虑了实际代价而不考虑预估代价，A*算法演变成了Dijkstra算法。假设A*算法的启发式函数只包含了预估函数而去掉实际代价函数，那么A*算法演变成了贪婪最佳优先搜索算法。

Figure 4. UAV 3D grid map

图4. 无人机三维栅格地图

Figure 5. Flatten 3D grid map

图5. 拉平后的三维栅格地图

因此需要衡量好实际代价函数和预估函数的比例，是决定了A*算法在路径搜索邻域的求解能力。假预估代价$h\left(n\right)$ 远远小于$g\left(n\right)$ ，那么A*能够求解到最短路径，但是由于$h\left(n\right)$ 的比例权重太小，会导致A*算法需要拓展的点更多，整个路径搜索过程会比较慢。相反假设预估代价$h\left(n\right)$ 远远大于实际代价g(n)，那么A*算法的搜索速度会加快，但相反可能无法求解到全局最优路径。因此本文提出一种自适应启发式函数，即给预估函数增加自适应动态变化的权重系数$\omega$ ，更新后的启发式函数公式如下：

$f\left(n\right)=g\left(n\right)+\omega \ast h\left(n\right)$ (3)

其中，自适应启发式函数主要实现方式是动态调整权重系数，当预估代价$h\left(n\right)$ 的值高于某个阈值时，说明当前节点距离终点较远，那么可以增大权重系数$\omega$ 来使得$\omega \ast h\left(n\right)$ 远远大于实际代价$g\left(n\right)$ ，提高A*算法的搜索速度，减少A*算法在搜索过程中的搜索节点数，提高算法搜索效率。当预估代价$h\left(n\right)$ 的值小于某个阈值时，说明当前节点已经距离终点较近，那么可以减小权重系数$\omega$ 来确保为$\omega \ast h\left(n\right)$ 远远小于实际代价，优先考虑最优路径并且降低搜索速度。具体公式如下：

$\omega ={\omega }_{\min }+\left({\omega }_{\max }-{\omega }_{\min }\right)*\left(\text{Predict Cost}-\text{Threshold}\right)/\left(\text{Predict Cost Max}-\text{Threshold}\right)$ (4)

$\omega ={\omega }_{\min }+\left({\omega }_{\max }-{\omega }_{\min }\right)\ast \text{Predict Cost}./\text{Predict Cost Max}$ (5)

上述公式中预估代价$h\left(n\right)$ 对应的阈值选取，主要取决于三维地图环境和起点终点的位置。根据历史文献中的描述，自适应权重系数的A*算法的路径搜索能力要远远好于单一权值的标准A*算法。自适应优化权重系数的流程图如图6所示。

Figure 6. Process diagram for adaptive optimization of weight coefficients

图6. 自适应优化权重系数的流程图

基于标准A*在三维地图下的路径规划模型，为了进一步验证改进启发式算法即利用权重系数对启发式函数进行优化是否能够优化无人机的路径规划，并进一步研究如何通过对权重系数的调整来实现启发式函数优化的最佳效果，权重系数的最小值和最大值的选取需要结合。

本文拟提出4种最小值和最大值方案：

方案一：$\omega \in \left[0.2,5\right]$

适用于对路径平滑度要求较高的场景，公式表达为：

$\omega =\{\begin{array}{l}0.2+4.8\ast \frac{H_n-H_{\min }}{H_{\max }-H_{\min }}\\ 0.2+0.1\ast \frac{H_n}{H_{\min }}\end{array}$ (6)

方案二：$\omega =\left[0.25,4\right]$

平衡计算效率与路径质量，公式调整为：

$\omega =\min \left(4,\max \left(0.25,\frac{H_n}{\tau }\right)\right)$ (7)

方案三：$\omega =\left[0.4,2.5\right]$

偏向计算效率优先，采用分段线性函数：

$\omega =\{\begin{array}{l}2.5-2.1*\frac{\tau -H_n}{\tau }\\ 0.4+0.6*\frac{H_n}{\tau }\end{array}$ (8)

方案四：$\omega =\left[0.5,2\right]$

极端高效场景，使用指数衰减：

$\omega =2*{\text{e}}^{-\lambda \left(\tau -H_n\right)}$ ，$\lambda =\frac{\ln \left(0.25\right)}{\tau }$ (9)

当预估代价大于阈值时，需要让权值$\omega$ 越接近${\omega }_{\max }$ 值，当预估代价小于阈值时，需要让权值$\omega$ 越小并接近于${\omega }_{\min }$ 值。

因此需要结合不同地图下的预估函数的最大值来选择一个合适的阈值来使得路径最优化。本文选择12、13、14、15这4个整数作为阈值，并进行测试，测试结果如表1所示。

Table 1. Weight and threshold test results table

表1. 权值和阈值测试结果表

权值最小值和最大值	阈值选取
	12		13		14		15
0.2/5	12.5622	7853	12.6082	6293	12.3439	4752	12.3572	3028
0.25/4	12.5644	7960	12.5491	6443	12.3451	4900	12.36	3192
0.4/2.5	12.6158	7728	12.6019	6258	12.398	4890	12.4128	3134
0.5/2	12.8982	6828	12.7448	5808	12.5434	4530	12.564	2815

根据上表的测试结果可知，当权值最小值和最大值分别为0.2和5，阈值为14的时候，当前无人机起点与终点在该地图模型下的路径长度最短，因此选取上述值作为自适应权重A*算法的参数。

3.3. 平滑度优化自适应权重A*算法

由三维栅格地图和距离计算方法可知，在该地图下的无人机路径是通过多个栅格里的节点连线而成，这种无人机的路径普遍比较曲折，曲折的无人机路径在实际应用不切实际，而且曲折路径的长度相对要更长。本文拟采用B样条曲线方法来优化无人机的路径，这是一种通过一组控制点和节点向量来定义曲线的曲线生成方法，具有非常好的灵活性。B样条曲线通过控制点、向量和阶数来定义曲线，其中控制点数量和位置决定了B样条曲线的整体形状，可能不一定经过全部控制点，但是控制点仍然会影响曲线的形状。节点向量是一个非递减的数列，主要用于定义曲线的参数化方程，节点向量会影响曲线的平滑性和连续性。B样条的阶数会决定曲线的光滑性，一般来说阶数越高，曲线的平滑度越好。B样条曲线的数学表达式如下：

$C\left(t\right)={\displaystyle \sum _{i=1}^n{N}_{i,p}}\left(t\right)Q_i$ (10)

公式中的$C\left(t\right)$ 代表曲线在参数$t$ 下的节点，$N_{i,p}\left(t\right)$ 是第$i$ 个控制点的B样条基函数，阶数为$p$ ，$Q_i$ 为控制点。由上述公式可知，B样条曲线法的实现方式更加复杂。

首先通过计算路线中折线之间的夹角来判断路径是否要进行平滑度优化，而判断阈值则是优化平滑度的重要参数之一。如果阈值过小，那么路线平滑度优化的效果不会太明显，如果阈值过大那么优化后的路径可能与障碍物存在相交的风险。因此本文先利用标准A*去迭代测试不同的阈值，阈值测试结果如表2所示。

Table 2. Smoothness threshold test table

表2. 平滑度阈值测试表

阈值	标准A*	平滑度优化A*	路径优化百分比
0.05	12.4836	12.3899	0.75%
0.1	12.4836	12.3226	1.29%
0.2	12.4836	12.1362	2.78%
0.3	12.4836	优化后有交叉	NA

根据上表的仿真结果可知，利用B样条的平滑度优化方法对标准A*求解的路径进行优化，当阈值取0.2时，平滑度优化后的路径长度为12.1362，相比于标准A*而言路径长度减少了2.78%。因此本文拟选择用0.2作为阈值建立平滑度优化模型。

4. 仿真实验结果与分析

4.1. 标准A*算法结果与分析

按照2.3小节建立模型的步骤，在Matlab软件中利用mat文件创建三维地图的高度信息，完成起点和终点的坐标设定后，将该地图导入仿真系统进行测试。

仿真结果可知：标准A*在该三维地图下的路径长度为12.4836 km，路径搜索过程中总计迭代了169次后完成路径求解，整个过程总共搜索974个潜在节点，仿真时间为0.05s。其中仿真时间并不存在绝对参考性，其也和计算设备的性能相关。标准A*算法在三维地图下求解的路径图如图7所示。

Figure 7. Standard A* for solving the shortest path planning map of UAV aerial vehicles on 3D maps

图7. 标准A*求解三维地图下无人机最短路径规划图

4.2. 自适应权重A*算法结果与分析

权值系数的最小值和最大值分别设为0.2和5，阈值为14，设置自适应权重A*算法的参数后，将其导入地图mat文件，设定与标准A*算法相同起点与终点后开始进行仿真。根据仿真结果可知，自适应权重A*算法求解的路径长度为12.3439，有效搜索没点数为4752，迭代次数为1071次，仿真时间为0.12 s，路径长度缩短了大约1.1%。

自适应权重A*的路径规划和与标准A*的路径规划对比图如图8所示，其中蓝线代表的是标准A*算法求解的无人机路径，红线代表改进A*算法后求解的无人机路径。

Figure 8. Comparison of standard A* and adaptive weight A* for solving the shortest path of UAV

图8. 标准A*与自适应权重A*求解无人机最短路径对比图

4.3. 平滑度优化自适应权重A*算法结果与分析

按照3.3小节的参数来设置自适应权重A*算法的参数和平滑度优化的参数后，同样导入地图mat文件，设定与标准A*算法相同起点与终点后开始进行仿真。根据仿真结果可知，平滑度优化后的自适应A*求解无人机路径的长度为11.9909，迭代次数和搜索节点数保持不变。相比于平滑度优化前，优化后的路径长度缩短了大约2.85%，相比于标准A*算法，整体优化后的路径长度缩短了大约3.94%。平滑度优化自适应权重A*以及其与平滑度优化前的路径规划对比图如图9所示，其中蓝线表示平滑度优化前改进A*算法求解的无人机路径，红线代表平滑度优化后改进A*求解的无人机路径。

Figure 9. Comparison of adaptive weight A* for solving the shortest path of UAV before and after smoothness optimization

图9. 平滑度优化前后自适应权重A*求解无人机最短路径对比图

4.4. 结论

本文提出改进的A*算法，通过动态调整启发式函数中实际代价与预估代价的权重系数优化路径求解能力，然后引入B样条曲线对路径进行平滑度优化，以几何优化方式缩减路径长度。仿真结果表明，自适应权重A*算法在路径长度上有显著优化。平滑度优化自适应权重A*算法通过几何手段对路径进行优化，同样有效缩短了路径长度。在经过平滑处理后，路径长度减少的同时，路径的平滑度得到极大改善，有效降低了无人机飞行过程中的能耗与风险。两种改进方法从不同角度对无人机路径规划进行优化，均取得了良好的效果，为无人机在复杂三维环境中的实际应用提供了有力的技术支持。将来的研究可能将本文方法与动态避障技术相结合，构建多源感知融合框架，解决更复杂环境下的无人机安全三维路规划问题。

基金项目

本研究得到国家自然科学基金(62403224)、2024年度辽宁省教育厅研究项目(No. LJ212410154044)、辽宁工业大学博士启动基金(Grant XB2024014)等资助。

NOTES

^*通讯作者。