基于改进A*的物流机器人路径规划算法

Path Planning Algorithm for Logistics Robots Based on Improved A*

摘要: 针对物流机器人路径规划中使用的传统A*搜索算法存在的搜索时间长、效率低等问题，本文提出了一种改进的A*搜索算法。该算法引入动态目标重定向方法解决双向A*搜索算法搜索区域不重合问题，根据障碍物信息和搜索方向动态调整搜索范围，将全局八邻域修改为动态n邻域，有效提高了搜索效率。实验结果表明，改进算法在随机地图中的平均搜索区域减少60.64%，平均搜索时间缩短28.88%；在模拟物流仓库地图中，平均搜索区域减少59.96%，平均搜索时间缩短40.50%，该算法可以有效提高移动物流机器人的路径规划效率。

Abstract: Aiming at the problems of long search time and low efficiency of the traditional A* search algorithm used in the path planning of logistics robots, this paper proposes an improved A* search algorithm. The algorithm introduces a dynamic target redirection method to solve the problem that the search area of the bidirectional A* search algorithm is not coincident. According to the obstacle information and the search direction, the search range is dynamically adjusted, and the global eight neighborhood is modified into a dynamic n neighborhood, which effectively improves the search efficiency. The experimental results show that the average search area of the improved algorithm in random maps is reduced by 60.64%, and the average search time is reduced by 28.88%; in the simulated logistics warehouse map, the average search area is reduced by 59.96%, and the average search time is reduced by 40.50%. This algorithm can effectively improve the path-planning efficiency of mobile logistics robots.

1. 引言

近年来，随着物流行业快速发展，物流行业对智慧化物流的推崇和追求、人工成本的不断增加，移动物流机器人成为很多企业降本增效的重要手段。机器人在运动过程中必须规避规则摆放的货架、零散的货物及其他移动物流机器人，这就对物流机器人行驶路径提出了更高的要求[1]。路径规划研究一方面有利于促进物流机器人的智能化发展，另一方面可以降低物流行业运送成本，提高运送效率。

目前，机器人路径规划涉及多种算法，包括A*搜索算法、双向A*搜索算法[2]等启发式搜索算法，粒子群算法、灰狼算法等智能算法[3]-[8]。近年来，深度强化学习算法[9]、基于Cornish-Fisher展开法的最优可靠路径搜索算法[10]等算法也被提出。其中，A*搜索算法[11]因其良好的启发性和快速高效等特点，在机器人路径搜索中被广泛应用。针对A*搜索算法的局限性，研究人员通过优化扩展策略、改进启发函数、后端轨迹优化等方式提升其规划效率与搜索质量[12]。蒋承杰等通过引入环境障碍率动态调整启发函数权重，提高搜索效率[13]。辛煜、Xiang Dan等[14] [15]通过优化扩展策略以提高路径质量。张志远等[16]通过预先获取局部障碍率与双向父节点变更，提高路径质量与搜索性能。

综合上述分析，提升物流机器人在进行路径规划时的搜索效率，降低其搜索时间与计算损耗至关重要。本文针对物流系统中的物流仓储环境，提出基于A*搜索算法的改进与优化。在栅格化地图的基础上针对原有路径，在双向搜索中引入动态目标重定方法，以前向路径与反向路径的最低代价点作为搜索重定目标。同时，采用了动态n邻域搜索策略，根据当前迭代点与重定目标点的相对位置及周围障碍物的情况，动态选择搜索范围。最后利用Python 3.8在随机地图与模拟物流仓库地图中与A*搜索算法和双向A*搜索算法进行对比验证。

2. 问题建模

2.1. 栅格地图搭建

机器人路径规划时，对环境建模的方法主要有栅格地图法、拓扑地图法、代价地图法等。栅格地图法建模相较于拓扑地图法、代价地图法更直观灵活，本文基于栅格法分别建立32 × 32、64 × 64大小的随机地图与模拟物流仓库地图，考虑到物流系统中AGV的大小，地图分辨率统一设置为2.5 m。图1表示一个5 × 5大小的栅格地图，使用$Q=\left\{\left(0,0\right),\left(0,1\right),\cdots ,\left(4,4\right)\right\}$ 表示栅格图坐标集，地图横轴为X轴，纵轴为Y轴，左下角为坐标原点$\left(0,0\right)$ 。地图分为两类区域，黑色区域表示障碍物区域，白色区域表示无障碍物区域。

Figure 1. Grid map

图1. 栅格地图

2.2. A*搜索算法

A*搜索算法是一种经典的启发式图搜索算法，兼具高效性与可行性。其代价函数如下：

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

其中，$F\left(n\right)$ 为节点n的总代价，$g\left(n\right)$ 表示从起始节点到节点n的实际代价，$h\left(n\right)$ 为从节点n到目标节点的启发式估计，常见估计方法包括欧式距离估计、曼哈顿距离估计和切比雪夫距离估计，具体形式分别表示为：

$h\left(n\right)=\sqrt{{\left(x_n-x_g\right)}^2+{\left(y_n-y_g\right)}^2}$ (2)

$h\left(n\right)=\left|x_n-x_g\right|+\left|y_n-y_g\right|$ (3)

$h\left(n\right)=\max \left(\begin{array}{cc}\left|x_n-x_g\right|& \left|y_n-y_g\right|\end{array}\right)$ (4)

式中，$\left(x_n,y_n\right)$ 为当前节点的坐标，$\left(x_g,y_g\right)$ 为目标点的坐标，本文采用欧式距离估计。

A*算法的算法流程如图2所示，搜索区域转换成二维数组，栅格的中心被定义为节点n，二维方格定义为可行域(OPENLIST)或不可行域(CLOSE LIST)。$F\left(n\right)$ 评估OPEN LIST中的每个节点的代价值并确定节点的顺序。OPEN LIST用于记录已计算代价值但并未展开的节点，CLOSE LIST用于储存已展开的节点通过循环判断待检测节点的总代价值来选择下一个节点。

本文采用如图1所示的栅格地图构建地图模型，A*搜索算法示意图如图3所示，坐标为机器人运动起点，标记为蓝色；坐标为机器人运动终点，标记为绿色；灰色栅格为A*搜索算法的全部搜索节点。

Figure 2. A* search algorithm flowchart

图2. A*搜索算法流程

Figure 3. Schematic diagram of A* search algorithm

图3. A*搜索算法示意图

3. 改进算法

3.1. 双向A*搜索算法

传统A*搜索算法以起点为开始节点，朝目标点搜索靠近，仅需要建立一个OPEN集，双向A*搜索算法则分别以起点、终点为开始节点，一条路径朝终点靠近，一条路径朝起点靠近，即起点与终点二者互为起点，也互为终点。需要建立前后两个OPEN集。双向A*搜索算法的代价函数由前向代价函数与后向代价函数构成，具体可表示为：

$F_f\left(n\right)=G_f\left(n\right)+H_f\left(n\right)$ (5)

$F_b\left(n\right)=G_b\left(n\right)+H_b\left(n\right)$ (6)

$F\left(n\right)=F_f\left(n\right)+F_b\left(n\right)$ (7)

其中，$F_f\left(n\right)$ 表示前向搜索中从起始节点到节点n的估计总代价，$F_b\left(n\right)$ 表示反向搜索中从节点n到目标节点的估计总代价；$G_f\left(n\right)$ 代表从起始节点到节点n的实际代价，$G_b\left(n\right)$ 代表从目标节点到节点n的实际代价；$H_f\left(n\right)$ 代表从节点n到目标节点的启发式估计代价，$H_b\left(n\right)$ 代表从节点n到起始节点的启发式估计代价，$F\left(n\right)$ 表示总代价函数。

相较于A*搜索算法，双向A*搜索算法最大的优点在于，在大空间内，双向搜索可大大减少搜索空间、提高搜索效率。但双向A*搜索算法仅仅是将A*搜索算法由一维扩充为二维，其前向开放集与后向开放集之间不存在信息交换。理想情况下，两个搜索前沿会在某个节点相遇，从而构成一条从起点到终点的路径。但有时可能会出现两个搜索前沿不相交直至前向搜索包含终点或后向搜索包含起点的情况，即

$U_0\cap U_1=\left\{Start,End\right\}$ (8)

相当于对起点与终点分别进行了一次完整的A*搜索，搜索节点数增加、搜索效率较A*搜索算法也更低。

Figure 4. Schematic diagram of bidirectional A* search algorithm

图4. 双向A*搜索算法示意图

如图4所示，前向与反向搜索呈现出两片不存在交集的搜索区域，最终前向搜索完成一次A*搜索，形成路径解结束双向搜索。此时双向A*搜索算法得出的路径与A*搜索算法得出的路径相似，但搜索区域接近于A*搜索算法的2倍。

3.2. 动态目标重定

针对上述出现的双向搜索区域不相交而导致搜索节点过多、搜索效率下降的问题，本文引入动态目标重定方法，通过动态调整前向搜索和反向搜索的目标点来改变单向搜索方向，从而有效控制双向A*搜索的方向，减少双向A*搜索算法的搜索节点，缩短搜索花费时间。

引入动态目标重定方法后，在双向搜索过程中，定义某个时间前向搜索开放集为$F_b\left(n\right)$ ，后向搜索开放集为$F_f\left(n\right)$ ，则前向搜索目标点与后向搜索目标点为：

$n_{fore}=\arg {\min }_{n\in U_1\left(t\right)}{F}_b\left(n\right)$ (9)

$n_{back}=\arg {\min }_{n\in U_0\left(t\right)}{F}_f\left(n\right)$ (10)

其中，$n_{fore}$ 为前向搜索目标点，$n_{back}$ 为后向搜索目标点。随着算法迭代，后向搜索结果驱动前向搜索，使前向搜索主动向反向搜索前沿靠近；同时后向搜索又被前向搜索驱动，反向搜索同样也向前向搜索前沿靠近，最终在中心汇合，形成一条较优解路径。

引入动态目标重定方法后路径规划结果如图5所示。与图4相比，引入动态目标重定方法解决了双向搜索区域无交集的问题，使得双向A*搜索算法的搜索节点得到明显减少，搜索时间缩短。但由于双向A*搜索算法与A*搜索算法搜索策略都使用八邻域搜索，始终有部分节点对路径生成影响较小，存在搜索节点冗余问题。

Figure 5. Schematic diagram of bidirectional A* algorithm for dynamic target redefinition

图5. 动态目标重定双向A*算法示意图

3.3. 动态n邻域

在A*搜索算法与双向A*搜索算法中，节点通常采用八邻域进行扩展搜索，八邻域扩展搜索范围可用坐标集表示为：

$E_n=\left\{\begin{array}{c}\left(x_n\pm 1,y_n\right),\\ \left(x_n,y_n\pm 1\right),\\ \left(x_n\pm 1,y_n\pm 1\right)\end{array}\right\}$ (11)

如图6所示，灰色区域为父节点(PARENT)即当前节点，白色区域为子节点(CHILD)即当前节点的邻节点，子节点的坐标值是父节点的相对坐标。

Figure 6. Schematic diagram of eight neighborhood search

图6. 八邻域搜索示意图

采用八邻域搜索策略既可以保证搜索路径的安全性，也可以确保搜索方向全面，但缺点是当存在较大搜索空间时，采用八邻域搜索策略会造成搜索冗余。

针对扩展搜索策略优化问题，研究人员提出的方向分为扩展增加与扩展减少，其中虞立斌、吴飞龙等[17] [18]通过优化搜索策略减少搜索区域提升搜索效率；崔宝侠等[19]则通过增加搜索邻域进而增加更多的搜索方向。本文针对此类问题对搜索策略进行改进，提出动态n邻域搜索策略。动态n邻域搜索策略以八邻域搜索为基础，定义障碍物集合

$O=\left\{\begin{array}{cccc}ob{s}_1& ob{s}_2& \cdots & ob{s}_n\end{array}\right\}$ (12)

所有可搜索节点为：

$S=\left\{\begin{array}{c}\left(x_n\pm 1,y_n\right),\\ \left(x_n,y_n\pm 1\right),\\ \left(x_n\pm 1,y_n\pm 1\right)\end{array}\right\}$ (13)

定义节点n与目标节点E相对位置为：

$\left\{\begin{array}{c}\Delta x=x_E-x_n\\ \Delta y=y_E-y_n\end{array}\right\}$ (14)

根据相对位置关系，引入

$\left\{\begin{array}{c}{\Delta }_x=\mathrm{sgn}\left(\Delta x\right)\\ {\Delta }_y=\mathrm{sgn}\left(\Delta y\right)\end{array}\right\}$ (15)

初始化优先搜索方向集合

$P=\left\{\begin{array}{c}\left(x_n+{\Delta }_x,y_n\right),\\ \left(x_n,y_n+{\Delta }_y\right),\\ \left(x_n+{\Delta }_x,y_n+{\Delta }_y\right)\end{array}\right\}$ (16)

其中，$\mathrm{sgn}\left(\Delta x\right)$ 为符号函数，取值分别为−1、0、1。

定义拓展搜索集，当搜索方向不存在障碍物或障碍物对搜索不影响时，

$\left\{\begin{array}{c}P\cap O=\varnothing \\ U_{et}=\varnothing \end{array}\right\}$ (17)

搜索方向存在障碍物且影响搜索时，搜索区域扩展到八邻域，此时搜索节点集合为：

$\left\{\begin{array}{c}P\cap O\ne \varnothing \\ U_{et}=S\setminus P\end{array}\right\}$ (18)

动态n邻域搜索节点集合

$N\left(n,E\right)=\left\{p\in P|p\notin O\right\}\cup \left\{s\in U_{et}|s\notin O\right\}$ (19)

4. 仿真验证

本文在Python 3.8中进行对比实验，设立两组对比实验，第一组实验对比A*搜索算法、双向A*搜索算法与本文中改进A*搜索算法规划路径的各项数据；第二组实验将改进A*搜索算法与A*搜索算法中采用其他邻域搜索方式的算法规划路径的各项数据进行对比，通过两组对比实验验证改进双向A*搜索算法的优越性。本次实验仿真栅格图大小为32 × 32与64 × 64，分为随机地图与物流地图，模拟地图障碍物由随机数根据地图大小进行取点，模拟物流地图设置区域型长条障碍模拟货架与服务台，并随机布置障碍物模拟货物掉落；给定同一起点和目标点，规划起点位于左下角(蓝色方块)，目标点位于右上角(绿色方块)，重复10次实验。

Figure 7. Group 1: Comparison diagram of random map results under 32 × 32 size

图7. 对比组一：32 × 32大小下随机地图结果对比图

第一组仿真实验结果如图7~10所示，依次为32 × 32大小下随机地图结果对比图、32 × 32大小下模拟物流仓库地图结果对比图、64 × 64大小下随机地图结果对比图、64 × 64大小下模拟物流仓库地图结果对比图。各个算法在不同栅格图中的路径规划数据如表1所示，数据为十次实验数据均值。

Figure 8. Group 1: Comparison diagram of simulated logistics warehouse map results under 32 × 32 size

图8. 对比组一：32 × 32大小下模拟物流仓库地图结果对比图

Figure 9. Group 1: Comparison diagram of random map results under 64 × 64 size

图9. 对比组一：64 × 64大小下随机地图结果对比图

Figure 10. Group 1: Comparison diagram of simulated logistics warehouse map results under 64 × 64 size

图10. 对比组一：64 × 64大小下模拟物流仓库地图结果对比图

Table 1. Path planning data of various algorithms in different raster graphs

表1. 各个算法在不同栅格图中的路径规划数据

栅格地图大小	栅格地图类型	算法	路径平均节点个数	平均搜索节点个数	平均花费时间
32 × 32	随机地图	A*搜索算法	48.6	166.5	0.098563
		双向A*搜索算法	49.2	150.7	0.056849
		改进A*搜索算法	52.6	55.9	0.048425
	模拟物流仓库地图	A*搜索算法	52.3	159.2	0.088782
		双向A*搜索算法	51.9	182.1	0.099689
		改进A*搜索算法	56.4	48.4	0.058425
64 × 64	随机地图	A*搜索算法	108.6	411.6	0.256984
		双向A*搜索算法	109.1	376.5	0.233257
		改进A*搜索算法	116.7	172.0	0.183580
	模拟物流仓库地图	A*搜索算法	118.5	352.4	0.236657
		双向A*搜索算法	117.2	323.8	0.238794
		改进A*搜索算法	126.5	152.7	0.207458

第二组实验如图11、图12所示。

Figure 11. Group 2: Comparison diagram of simulated logistics warehouse map results under 32 × 32 size

图11. 对比组二：32 × 32大小下模拟物流仓库地图结果对比图

Figure 12. Group 2: Comparison diagram of simulated logistics warehouse map results under 64 × 64 size

图12. 对比组二：64 × 64大小下模拟物流仓库地图结果对比图

Table 2. Path planning data in different grid graphs using different neighborhood expansion methods

表2. 采用不同邻域扩展方法在不同栅格图中的路径规划数据

栅格地图大小	邻域类型	路径平均节点个数	平均搜索节点个数	平均花费时间
32 × 32	四邻域	62.7	127.6	0.076895
	双向十二邻域	48.9	182.1	0.087929
	动态双向n邻域	56.4	48.4	0.058425
64 × 64	四邻域	136.1	1068.6	0.446657
	双向十二邻域	109.7	732.9	0.238794
	动态双向n邻域	126.5	152.7	0.207458

在实验中，通过对比组一的四组实验，改进A*搜索算法在随机地图与结构化物流仓库地图中均表现稳定，算法对不规则障碍物(零散货物)和规则障碍物(货架)均具有适应性。通过对比图9中的(b)、(c)，可明显观察到引入动态目标重定后，改进A*搜索算法在控制双向路径汇合方面得到明显改善；对比图7~12中的(a)、(b)、(c)，观察到引入动态n邻域搜索策略后，改进A*搜索算法的搜索节点数明显减少，搜索效率显著提高。

从表1、表2的数据中可以分析得出，在给定障碍物地图环境下，无论是随机地图还是模拟物流仓库地图，在不同地图尺寸下，相较于其他四种搜索算法，改进A*搜索算法在有双向信息方向提供指引、动态选择邻域范围的前提下，搜索节点数与搜索花费时间均有不同程度的优化，搜索节点个数平均减少60.12%，搜索时间平均缩短36.63%。

但由于大量减少搜索节点导致搜索信息部分缺失，搜索路径较其他四种搜索算法均有不同程度加长，(平均增加8%~10%)无法保证搜索路径最短，在物流场景下，快速搜索响应较严格最优路径更具实际意义。

5. 结论

本文针对物流机器人路径规划中存在的搜索时间长、效率低等问题，提出了一种改进的A*搜索算法，该算法引入动态目标重定向方法与动态n邻域搜索策略相结合。实验证明，改进A*搜索算法大幅减少搜索节点，缩短搜索花费时间，适合部署在嵌入式设备中，具有较强的实用性。但在减少搜索节点后对全局的实时感知能力减弱，无法保证路径的最优，动态n邻域搜索策略进一步优化后，有望继续提升机器人自主移动工作效率。

基金项目

2023年省级大学生创新创业训练计划项目(s202310407080)。

NOTES

^*通讯作者。