基于全局引导力的分数阶人工势场的路径规划算法研究

Research on Path Planning Algorithm Based on Fractional-Order Artificial Potential Field with Global Guiding Force

摘要: 本文针对传统A算法在路径规划中存在扩展节点多、搜索时间长、路径转折频繁及易陷入局部最优等问题，提出一种融合全局引导的分数阶人工势场法(APF)的改进A路径规划算法。该算法通过引入分数阶微积分增强势场力的连续性与记忆性，并结合全局路径趋势引导力，动态约束搜索邻域，减少冗余搜索方向。在MATLAB平台上进行仿真实验，结果表明：在30 × 30和50 × 50栅格地图中，改进算法相较于传统A*算法，搜索时间分别减少38.67%和47.31%，扩展节点数降低22.97%和33.46%，路径转折次数减少15.38%和18.18%，路径长度缩短1.94%和2.95%。实验验证了所提算法在复杂环境中具有更高的规划效率和路径质量。

Abstract: To address the issues of excessively expanded nodes, long search time, frequent path turns, and susceptibility to local optima in traditional A* algorithm-based path planning, this paper proposes an improved A* path planning algorithm that integrates globally-guided fractional-order artificial potential field (APF). By introducing fractional calculus to enhance the continuity and memory of potential field forces, and incorporating global path trend guidance to dynamically constrain the search neighborhood, the algorithm effectively reduces redundant search directions. Simulation experiments conducted on the MATLAB platform show that in 30 × 30 and 50 × 50 grid maps, the improved algorithm reduces search time by 38.67% and 47.31%, decreases the number of expanded nodes by 22.97% and 33.46%, and reduces the number of path turns by 15.38% and 18. 18%, and shortens the path length by 1.94% and 2.95%, respectively, compared to the traditional A* algorithm. The results verify that the proposed algorithm achieves higher planning efficiency and path quality in complex environments.

1. 引言

随着科技的进步和社会的不断发展，自主移动机器人在工业、农业、医学、航空航天等许多领域发挥日益重要的作用，广为人知的无人车、无人机和水下机器人等越来越多地进入了人们的生活。在移动机器人相关技术研究中，路径规划是一个重要的环节和组成部分。所谓的路径规划就是指机器人根据各种传感器对周围环境进行感知，自主探索出一条从起点到目标点的无碰撞路径[1]。该路径应满足安全、光滑、高效等一系列要求，并且能够避开沿途的静态和动态障碍物。良好的移动机器人路径规划技术不仅可以节省大量的时间，还可以减少移动机器人的磨损和资本投资[2]。

根据环境信息是否先前已知和规划的范围，路径规划可以分为全局路径规划和局部路径规划[3]。全局路径规划算法被广泛应用于解决在已知的静态环境中的路径规划问题，常见的算法有Dijkstra算法、A*算法、RRT算法、遗传算法、蚁群算法等；局部路径规划算法常被应用在动态的未知或部分已知环境中的路径规划问题，常见的算法有动态窗口法、人工势场法和时间弹性带等[4]。

以上路径规划算法各有优缺点，在全局路径的规划算法中，A*算法使用较为广泛，具有简单且速度相对较快[5]、稳定性较高等优点。但也存在实时性差、扩展节点多、计算量大、路径不平滑、结果不一定为最优解等问题。迟旭等[6]将A*算法原本固定的8个搜索方向改进为5个搜索方向，提高了搜索效率，但是可能错过一些更优节点；彭哲等[7]对评价函数进行优化，虽然搜索效率提升了许多，但搜索出的路径经常不是最优解。

针对A*算法的局限性，本文结合改进分数阶人工势场法优化搜索邻域，减少了搜索邻域的数量，解决了易陷入U型陷阱的问题；改进后的A*算法大幅提高了路径规划效率和质量，进一步加强了A*算法的实用性。

2. 传统A*算法

A*算法在保证搜索最短路径的情况下，通过综合考虑节点到起始点的实际代价和对目标点的估计代价，引入了启发函数的概念，提高路径搜索效率。其实现过程可分为场景建模与路径规划两个部分。

2.1. 场景建模

在A*算法中，场景建模模块扮演着至关重要的角色，它能够将实际场景转化为易于计算机读取的栅格地图，从而为路径规划提供了坚实的基础。场景建模方法有栅格法、拓扑法、可视图法和单元分解法等。与其他建模方法相比，栅格法在操作上更为简单且容易实现，因而被广泛应用于描述机器人环境地图[8]。

2.2. 储存系统组成及流程

在建立地图时，根据实际场景栅格法将环境划分为规则的网格，并在每个网格单元中均存储相应的信息，每一个栅格代表一个节点，这种简单的结构使得栅格法能够更加方便地对相应地图上的区域进行处理与计算。如图1所示，白色栅格表示可通行，黑色栅格对应障碍物。映射标记完成后，就可以开始进行路径规划了。

Figure 1. Grid map

图1. 栅格地图

2.3. 系统的控制要求

A*算法作为Dijkstra算法的扩展，继承了Dijkstra算法的优点，具有完备性和最优性。同时，A*算法又类似于贪婪最佳优先搜索算法，使用启发式函数引导搜索[9]。传统的A*算法常用的节点扩展方式一般为八邻域，利用评价函数来评估当前节点周围的八个节点到目标点的最短距离，并依据这个评估值来选择接下来要搜索的节点，通过综合考虑实际距离和预估距离，最大限度地提高最短路径的寻找速度[10]。利用估价函数对计算空间中每个节点的总代价进行计算。估价函数如式(1)所示：

$F\left(n\right)=G\left(n\right)+H\left(n\right)$ (1)

式中：n为当前节点；G(n)为起点到节点n的实际代价，H(n)为节点n到目标点的启发式预估代价，F(n)为节点n的总代价。启发函数H(n)常见的计算方式有曼哈顿距离、切比雪夫距离和欧氏距离，如图2所示。

Figure 2. Schematic diagram of three types of heuristic function calculation methods

图2. 三种启发函数计算方式示意图

3. 提出基于全局引导的分数阶人工势场A*算法

3.1. 融合势场法优化搜索邻域

当移动机器人在栅格地图上进行搜索时，通常会采用3 × 3邻域搜索方式，即以当前节点为中心，从周围的8个节点中挑选出可供选择的备选节点，然后从中筛选出下一步将进行扩展的节点[11]。受局部路径规划人工势场法的启发，可以将目标点对机器人产生的引力和障碍物对机器人产生的斥力合成一个引导力，根据引导力的方向来确定保留的5个搜索方向和舍弃的3个搜索方向。

3.1.1. 分数阶人工势场法的推广

人工势场法是在移动机器人路径规划避障中广泛应用的方法，基本思想是引入人工势场的概念，将势场分为引力势场和斥力势场[11]，人工势场定义为：

$U=U_{att}+U_{rep}$ (2)

其中引力势场函数定义为：

$U_{att}=\frac{1}{2}K{\Vert R-G_g\Vert }^2$ (3)

式中，$K$ 为引力势场增益系数，${\Vert R-G_g\Vert }^2$ 为机器人到目标点的欧氏距离。机器人所受引力为：

$F_{att}=-\nabla \left(U_{att}\right)=-K\Vert R-G_g\Vert$ (4)

斥力势场函数定义为：

$U_{rep}=\{\begin{array}{ll}\frac{1}{2}q{\left(\frac{1}{d}-\frac{1}{d_0}\right)}^2,\hfill & d\le d_0\hfill \\ 0,\hfill & d>d_0\hfill \end{array}$ (5)

式中，$q$ 为斥力势场增益系数；$d$ 为当前位置与障碍物之间的距离；$d_0$ 为常数，表示障碍物影响距离。机器人所受斥力为：

$F_{req}=-\nabla \left(U_{req}\right)=\{\begin{array}{ll}q\left(\frac{1}{d}-\frac{1}{d_0}\right)\frac{1}{d},\hfill & d\le d_0\hfill \\ 0,\hfill & d>d_0\hfill \end{array}$ (6)

然而，传统整数阶APF仅仅是一种局部瞬时的描述，无法刻画势场力的历史累积效应与机器人的运动惯性。针对这一问题，本文将APF算法在阶次上从整数阶推广至分数阶，分数阶算子具有记忆性和遗传性，能够更精细地描述势场的渐变过程，从而使势场力的变化更加平滑连续，有效克服传统APF的缺陷。

引入了分数阶微积分后的APF算法，引力势场重新定义为：

$U_{att}\left(q\right)=\frac{1}{2}{k}_{att}\cdot \left(D^{\beta }\left[d\left(q,q_{goal}\right)\right]\right)$ (7)

式中，$D^{\beta }$ 表示Caputo型分数阶微分算子；$\beta \left(0<\beta <2\right)$ 为引力场的分数阶阶数；$d\left(q,q_{goal}\right)$ 为当前点到目标点的欧氏距离。机器人所受分数阶引力为该势场的负梯度：

$F_{\text{att}}=-\nabla U_{att}=-k_{att}\cdot D^{\beta }\left[d\left(q,q_{goal}\right)\right]$ (8)

斥力势场为：

$U_{req}=\{\begin{array}{ll}\frac{1}{2}{k}_{att}\cdot {\left(D^{\alpha }\left[\frac{1}{d\left(q,q_{obs}\right)}-\frac{1}{\rho }\right]\right)}^2\hfill & d\left(q,q_{obs}\right)\le \rho \hfill \\ 0\hfill & d\left(q,q_{obs}\right)>\rho \hfill \end{array}$ (9)

式中，$\alpha$ 为斥力场的分数阶阶数；$d\left(q,q_{obs}\right)$ 为当前点到障碍物的距离；$\rho$ 为障碍物影响距离。对应的分数阶斥力为：

$F_{req}=-\nabla U_{req}$ (10)

通过调节分数阶阶数$\left(\beta ,\alpha \right)$ ，可以更精细地控制引力与斥力随距离变化的非线性关系，从而为不同场景下的路径规划提供了更灵活、更强大的参数优化空间，从根本上增强了模型的适应性和鲁棒性。

3.1.2. 提出引入全局路径趋势引导力的APF改进

传统APF算法在面对U型障碍物环境时，引力与斥力可能在非目标点处达到平衡，即$F_{att}+F_{req}=0$ ，导致机器人陷入局部最优点，无法脱身(图3)。

Figure 3. Trapped in local optimum under traditional APF

图3. 传统APF下陷入局部最优

针对这一问题，本文提出了一种结合全局路径趋势信息的优化势场法。我们在改进的APF算法中引入了全局路径趋势引导力，使得机器人不仅受到目标点的引力和障碍物的斥力影响，还能够根据全局路径的方向来调整搜索方向。

改进后的势场法将目标点的引力、障碍物的斥力和全局路径趋势的引导力综合在一起，形成总的引导力F，使得机器人能够沿着更合理的路径前进。具体而言，目标点的引力、障碍物的斥力的计算同上一小节，全局路径的引导力定义其方向为从当前节点指向全局路径参考方向，大小与当前节点偏离全局路径的程度相关计算公式如下：

$F_{glo}=k_g\cdot \frac{P_{goal}-P_{start}}{\Vert P_{goal}-P_{start}\Vert }$ (11)

其中$P_{goal}$ 、$P_{start}$ 分别为目标点位置和起点位置，$k_g$ 为全局引导力增益系数，用于调节全局趋势的影响程度。

此时当前节点受到的合力为：

$F=F_{att}+F_{req}+F_{glo}$ (12)

其中$F_{att}$ 和$F_{req}$ 为传统的引力和斥力势场，$F_{glo}$ 为全局路径趋势引导力。通过综合这些引导力，机器人能够在复杂环境中更有效地找到最优路径，避免了局部最优解的产生(图4)。

Figure 4. Improved APF algorithm avoids local minimum

图4. 改进APF算法避免局部最小

为了证明该改进算法的有效性，我们首先考虑优化后的路径规划算法的收敛性。假设机器人在路径规划过程中不断调整其位置以满足目标点引力、障碍物斥力和全局引导力的作用。我们引入Lyapunov稳定性理论来证明算法的收敛性。

$V\left(P_{current}\right)=\frac{1}{2}{\Vert P_{current}-P_{goal}\Vert }^2$ (13)

对其求导得：

$\dot{V}={\left(P_{current}-P_{goal}\right)}^{\text{T}}\cdot {\dot{P}}_{current}$ (14)

假设机器人运动方向与总引导力方向一致，即：

$P_{current}=\alpha \cdot F$ (15)

代入得：

$\dot{V}=\alpha {\left(P_{current}-P_{goal}\right)}^{\text{T}}\cdot \left(F_{att}+F_{req}+F_{glo}\right)$ (16)

由于$F_{att}$ 指向目标点，$F_{glo}$ 也朝向全局方向，合力方向总体朝向目标点，因此$\dot{V}<0$ ，系统渐近稳定，机器人最终收敛至目标点(图5)。

Figure 5. Lyapunov function convergence

图5. Lyapunov函数收敛

3.1.3 改进APF后的邻域搜索

融合改进APF算法来确定搜索邻域的准确性。如图6所示，利用势场法计算出的F就是当前节点的受到的引导力，再通过引导力的方向选择出下一步要搜索的5个邻域。

Figure 6. Guiding force calculation based on potential field method

图6. 势场法求引导力

为了减小计算量，我们只考虑当前节点的8邻域方向是否有障碍物，设引导力F与n₅方向的夹角为$\alpha$ ，夹角$\alpha$ 与搜索邻域的关系如表1所示。根据图7所示，$\alpha =155˚$ ，所以当前节点需要搜索的邻域是 n₁、n₂、n₃、n₄、n₆。

Table 1. Comparison table of MPC and traditional PID

表1. 搜索方向与夹角α的关系

α	保留的5个方向	舍弃的3个方向
−22.5˚ ≤ α < 22.5˚	n2 n3 n5 n7 n8	n1 n4 n6
22.5˚ ≤ α < 67.5˚	n1 n2 n3 n5 n8	n4 n6 n7
67.5˚ ≤ α < 112.5˚	n1 n2 n3 n4 n5	n6 n7 n8
112.5˚ ≤ α < 157.5˚	n1 n2 n3 n4 n6	n5 n7 n8
157.5˚ ≤ α或α < −157˚	n1 n2 n4 n6 n7	n3 n5 n8
−157.5˚ ≤ α < −112.5˚	n1 n4 n6 n7 n8	n2 n3 n5
−112.5˚ ≤ α < −67.5˚	n4 n5 n6 n7 n8	n1 n2 n3
−67.5˚ ≤ α < −22.5˚	n3 n5 n6 n7 n8	n1 n2 n4

Figure 7. The included angle between guiding force and n5

图7. 引导力与n5的夹角

因此，$\alpha$ 取不同值时对应的保留和舍弃方向如表2所示。

4. 仿真实验与分析

为了验证改进方法的有效性，本文使用MatlabR2022b平台，在30 * 30和50 * 50大小的地图上进行了算法验证。分别对Dijkstra算法、传统A*算法、文献[5]邻域改进方法、文献[6]权重调整方法和本文改进的A*算法进行实验和分析，对比了在两地图下的搜索时间、扩展节点数、转折次数和路径长度。实验数据如表2所示，关键数据的对比图如图8所示。

Table 2. Comparison of experimental data

表2. 实验数据对比

地图	算法	搜索时间(s)	扩展节点数	转折次数	路径长度
30 * 30	Dijkstra算法	13.2259	807	10	47.6985
	传统A*算法	2.5340	209	11	47.6985

续表

	文献[5]算法	2.1729	191	11	47.6985
	文献[6]算法	1.5706	159	14	49.3553
	本文算法	1.5542	161	9	46.7731
50 * 50	Dijkstra算法	40.0258	2228	26	98.7696
	传统A*算法	12.8468	813	26	98.7696
	文献[5]算法	11.5177	736	26	98.7696
	文献[6]算法	7.0954	507	36	111.1960
	本文算法	6.7689	541	22	95.8513

Figure 8. Comparison chart of experimental data

图8. 数据对比图

从实验结果可以看出，相对于另外四种算法，本文改进的A*算法搜索时间、扩展节点数、转折次数、和路径长度均得到有效减少，效果较为理想。与传统A*算法相比，本文改进的A*算法搜索时间分别缩短了38.67%和47.31%，扩展节点数分别减少了22.97%和33.46%，转折次数分别减少了15.38%和18.18%，路径长度分别缩短了1.94%和2.95%，可以看出场景越复杂，地图越大，算法改进的效果会越明显。由此得出实验结论，本文改进后的A*算法，有效提高了算法的搜索效率和路径平滑度，降低了算法运行所需内存和路径长度。

5. 结论

本文针对传统A*算法计算量大、时间长、路径不平滑、结果不一定为最优解等问题，进行分析并提出改进方法。对搜索方向进行改进，结合势场法，考虑当前节点的位置和周围障碍物的分布，减少了搜索邻域的数量；对预估代价函数进行改进，使估价函数自适应调整权重；对搜索线程进行改进，改进传统双向搜索策略，提高计算效率；最后删除冗余节点并利用贝塞尔曲线对路径进行平滑处理。利用MATLAB进行仿真，通过分析数据和实验结果，验证了本文改进的A*算法，在保证路径最短的同时，缩短了路径规划时间，减少了转弯次数，提升了路径平滑度，降低了内存消耗。

NOTES

^*通讯作者。