兼顾启停特性和转角时耗的移动机器人路径规划

兼顾启停特性和转角时耗的移动机器人路径规划

智能移动机器人具有自动化程度高、柔性强、部署时间短等优点，可实现工厂物料及仓库货物的搬运，是智能制造车间的主要运载工具[1-3]。对智能移动机器人系统，如何保证每台机器人高效运行以提高系统运行效率，是当前移动机器人领域的核心问题之一，而移动机器人运行路径的规划与决策是解决该问题的关键因素。

依据适用范围及算法原理，路径规划算法主要包括：传统算法[4-5]、图形搜索算法[6]、智能仿生学算法[7-9]以及其他算法[10]。传统路径规划算法（如模拟退火算法、人工势场法等）具有描述简单、使用灵活、路径平滑安全等特点，但存在计算量大、收敛速度慢、随机性高等缺点[11]。仿生学的发展促使了机器人智能仿生路径规划算法的研究，如蚁群算法、遗传算法易与其他算法相结合，但存在计算繁琐、运行效率不高且易于陷入局部最优等缺点[12]。其他如人工智能领域强化学习等系列算法，在高随机动态障碍物环境下寻路效果好，但其收敛速度慢、空间复杂度高、需进行大量模型训练，应用成本过高[13]。

相较之下，图形搜索算法因其原理简洁、实现方便等优势得到广泛应用[14]。常见算法包括Dijkstra 算法、A算法等。得益于启发式搜索效率高，A算法在移动机器人路径规划领域得到众多学者青睐[15-17]。

总体说来，A*算法具备较好的路径规划效果，但目前研究对移动机器人在真实场景中的运动特性以及其执行时间效率的考量不够充分。如河南工业大学 zhang 等人从移动机器人运动特性以及车辆结构角度分析了运行能耗，提出一种基于节能优化的路径规划算法，但忽略了运动特性对移动机器人任务执行时间的影响，存在任务执行效率低等问题[18]。北京科技大学赵盼等在传统路径规划算法基础上引入了转角约束进行路径规划，但没有考虑转角对任务执行时间的影响[19]。华南理工大学袁洋等[20]针对移动机器人在大场景下存在局部冲突拥堵的问题，提出结合负载均衡的路径规划算法，但缺乏对算法本身规划性能的重视。综上所述，移动机器人在真实运动中的加速、减速运动特性以及转角姿态调整将导致实际运行时间成本高、车辆能耗大甚至无法完成运行任务，这是移动机器人路径规划研究的重点和难点问题之一。通过剖析不同运行情况对移动机器人任务时间规划的影响，并结合车辆转角姿态调整特性建立合理且有效的转角时耗代价函数，避免局部拥堵是解决该问题的关键之处。

为此，本文提出一种兼顾启停特性及转角时耗的最短时间移动机器人路径规划方法，以实现提高移动机器人的任务执行效率，并降低局部拥堵的发生，主要改进如下：1）通过分析实际移动机器人栅格化地图运行微分方程，对其启动、制动过程进行数学建模，进而分类构建了栅格化地图运动代价函数；2）针对移动机器人位姿调整导致任务耗时长的问题，利用地图二维向量坐标分析，建立方位角与位置向量分布关系，构建转角时耗代价函数；3）针对多台移动机器人运行时的场景适应性问题，对非适应性局部拥堵进行算法适配性调整。最后通过测试验证了算法的有效性与优越性。

1 算法描述

1.1 速度启停特性及转角时耗约束构建

A算法是一种常用于静态图的启发式直接搜索算法，其应用特点是通过启发函数来引导搜索方向，被搜索的图的权值不随时间而变化，可直接在地图中进行搜索，无需任何预处理。A算法的核心为其代价函数，每一次搜索都以代价函数为依据进行节点扩展，如下式所示：

$$f(n)=g(n)+h(n) \tag{1}$$

式中，f(n)为实际规划时所使用的实际估计代价，g(n)代表起始顶点到中间顶点n的实际运行代价，h(n)为中间某一顶点n到结束顶点的最小估计代价。

由上述代价函数可知，传统A*算法把简单的几何路径长度作为实际代价，没有考虑移动机器人的直线运动以及姿态调整情况。为此，将移动机器人在栅格化地图中的运动划分为三个阶段：加速、匀速以及减速阶段[18]。加/减速阶段类似，可近似为镜像关系。根据实际路段的长度差异，移动机器人在直线边上的运动可分为有无匀速阶段两种情况，如图 1所示。当实际路段长度大于加速、减速过程所运行的总路程时，移动机器人在该路段上运行包含匀速阶段。当实际路段长度小于加速、减速过程移动机器人所运行的总路程时，由于加速时间过短，其速度还没达到该路段的最大限速就开始减速，故不含匀速阶段。

另一方面，移动机器人在实际运行当中，两条路段间夹角不一致时，为继续在下一个路段直线行驶，机器人需事先调整好运动角度。然而该过程是较为耗时，并且实际运行过程中移动机器人经常发生姿态调整，故需要考虑姿态调整的时间。为此，建立二维地图向量来表征当前移动机器人在某一站点的位姿信息，如图 2 所示：

由图 2 可知，在当前 0 号站点建立二维平面坐标系，连接坐标原点与各个即将可能到达的站点形成地图向量，使用各个向量与 X 轴正方向的夹角即 θ₁、θ₂、θ₃、θ₄ 来表征当前站点可能的姿态方位角，以便进行转角姿态调整代价函数的构建。

1.2 栅格化运动代价函数构建

对于移动机器人在栅格化地图中的运动，由于启停速度特性的存在，会对其通行时间产生影响，故需要对移动机器人在栅格化地图运动时的实际路程运行代价进行分析。为了使移动机器人的加速曲线均匀平滑且更贴合实际，设计了如下迭代表达式(2)来表征移动机器人启动与制动过程中的速度变化关系：

$$v_{af}= av + (1-a)v_{max} \tag{2}$$

式中：v_af表示移动机器人在未来极短一段时间后的速度；v 表示移动机器人在当前时刻的瞬时速度；v_max 表示移动机器人经过当前路段的最大可通行速度a∈[0,1]为加速系数。将该递增表达式连续化得：

$$v+\Delta{t}\frac{dv}{dt}=av+(1-a)v_{max} \tag{3}$$

式中，Δt表示一段很小的时间，在这段极小的时间段内认为移动机器人加速度是恒定的。

为表征移动机器人加速阶段的速度与时间关系，求解上述微分方程并带入初始条件，可知：

$$V=v_{max}-v_{max}e^{-\frac{1-a}{\Delta{t}}t} \tag{4}$$

由上式可知，该加速曲线在加速过程中速度只能逼近所设置的最大速度，而无法真正达到理论上的最大速度，且越靠近最大速度，曲线斜率越小，越接近匀速阶段，曲线越平滑，贴合实际移动机器人运行情况。一般地，当v达到λv_max时即可视为移动机器人完成加速阶段，进入匀速阶段，如表达式(5)所示：

$$\lambda{v_{max}}=v_{max}-v_{max}e^{-\frac{1-a}{\Delta{t}}t_{acc}} \tag{5}$$

式中，t_acc为完成整个加速或减速阶段所需要的加速时间，且0<λ<1 。由表达式可看出，加速时间的求解与最大速度无关，解得加速时间 t_acc 为一常量，如表达式(6)所示：

$$t_{acc}=\frac{\Delta{t}}{1-a}In\frac{1}{1-\lambda} \tag{6}$$

根据所求出的加速时间，通过积分可得到加速或减速阶段在固定加速时间 t_acc 内的加速或减速路程：

$$S=v_{max}t_{acc}+\frac{\Delta{t}}{1-a}v_{max}e^{-\frac{1-a}{\Delta{t}}t_{acc}}-\frac{\Delta{t}}{1-a}v_{max} \tag{7}$$

式中，S为确定最大限行速度的路段的加速或减速路程。

根据实际路段边的具体长度大小，通过分类讨论确定移动机器人在具体路段上的时间消耗。当实际路段边长度d大于等于加速、减速路程之和 2S 时，移动机器人在路段边上存在匀速运动阶段，且匀速运动速度大小为v_max，此时移动机器人在该边上的实际时间花费为：

$$t=2t_{acc}+\frac{d-2s}{v_{max}} \tag{8}$$

当实际路段边长度d小于加速、减速路程之和2S时，此时移动机器人在路段边不存在匀速运动阶段，将d /2代入加速距离公式中解得：

$$ e^{\frac{1-a}{\Delta{t}}t}+t-\frac{\Delta{t}}{1-a}=\frac{d}{2v_{t}} \tag{9}$$

由表达式(9)可知，为求解单个加速或减速过程的时间消耗，所解得的方程是一个超越方程，无法求其解析解，可使用数值分析的方法估计其数值解。估计出误差小于一定范围的t值作为加速、减速时间，故无匀速运动阶段情况的实际时间花费为2t。根据上述分析推导可总结出直线运动时改进 A*算法两个顶点间的实际时间代价如下式所示：

$$g_{1}(i)=\begin{cases}
2t_{acc}+\frac{d_{i}-2s}{v_{max}},d_{i}\geqslant2s \\
2t,t\in{e}^{-\frac{1-a}{\Delta{t}}t}+t-\frac{\Delta{t}}{1-a}=\frac{d_{i}}{2v_{max}},d_{i}<2S
\end{cases} \tag{10} $$

1.3 姿态调整代价函数构建.

车轮姿态调整代价函数构建，关键在于计算当前顶点与待搜索顶点之间的运动方位角以及上一个当前顶点与当前顶点之间的运动方位角之差。对于拓扑路径图中的每个顶点都有唯一二维坐标(x,y) ，通过计算起始点与终止点之间坐标的差值来估算两点之间的运动方位角。故两个顶点之间的运动方位角θ_i的计算表达式为：

$$\theta_{i}=
\begin{cases}
arctan\frac{y_{i}-y_{i-1}}{x_{i}-x_{i-1}},x_{i}-x_{i-1}>0,y_{i}-y_{i-1}\geqslant0 \\
\pi-arctan\frac{y_{i}-y_{i-1}}{\lvert x_{i}-x_{i-1}\rvert},x_{i}-x_{i-1}\leqslant0,y_{i}-y_{i-1}>0 \\
\pi+arctan\frac{\lvert y_{i}-y_{i-1}\rvert}{\lvert x_{i}-x_{i-1}\rvert},x_{i}-x_{i-1}<0,y_{i}-y_{i-1}\leqslant0 \\
2\pi-arctan\frac{\lvert y_{i}-y_{i-1}\rvert}{x_{i}-x_{i-1}},x_{i}-x_{i-1}\geqslant0,y_{i}-y_{i-1}<0
\end{cases} \tag{11}
$$

表达式(11)给出了两点之间方位角的具体计算过程，分别对应于两点之间方位角所在具体象限的不同而进行对应的求解。该角度是一个相对角度，即确定两个顶点中的某一个顶点位于坐标原点，另一个顶点位于坐标轴或四个象限中，计算该点与坐标原点的连线与X轴正方向的夹角作为以坐标原点为起点的两点之间的方位角。

根据以上分析即可归纳出从当前顶点到下一个当前顶点之间的车轮姿态调整实际时间代价为：

$$
g_2(i)=min\lbrace \lvert \theta_i-\theta_{i-1}\rvert ,2\pi- \lvert \theta_i-\theta_{i-1}\rvert \rbrace /v_{rotate}
\tag{12}$$

其中车轮旋转角度取$\lvert \theta_i-\theta_{i-1}\rvert$与$2\pi- \lvert \theta_i-\theta_{i-1}\rvert$间的最小值，移动机器人每次的姿态调整应该小于等于180°，当大于180°时可以通过更换旋转方向而使调整角度小于180°，最后得到需要调整的旋转角度之后除以车轮旋转速度，可以得到车轮姿态调整的实际时间代价。

1.4 启发项均值比例拥塞跟踪调整

宏观基本图[21]（Macroscopic Fundamental Diagram，MFD）用于描述路网交通流宏观变量间的关系模型。体现一定区域内车辆流出量和车辆累积数量的关系。如图 3 所示：

其形状类似于抛物线，当区域车辆累计数达到临界点后，局部路网中的交通流由稳定流变为不稳定流，此时随着累计车辆数的增加，车辆流出率逐渐下降，当累计车辆数达到某一最大值后，道路进入完全拥堵状态，此时无车辆流出。在此基础上的研究表明，产生局部拥堵的最大原因是路网交通流的不均匀分布，即某些路段处于饱和状态而其他有些路段处于车流稀疏的状态[22]。因此避免单个顶点附近产生过大非均衡的车流量是解决拥堵问题的关键。

故针对以上改进存在潜在的大场景适应性不足、易发生局部拥堵的问题，提出算法启发项均值比例拥塞跟踪调整。具体地，当移动机器人规划出的路径每经过一个顶点，便令该顶点的相应标记数值加 1，类似蚂蚁觅食时会在觅食路径上留下信息素，来通知其他蚂蚁能更快地找到食物。这样，在多台移动机器人进行路径规划后，通过统计在路径图上所留下的信息素，形成信息素矩阵，来定量表示路径图局部区域的移动机器人拥堵情况，当某个顶点信息素浓度过高，说明该顶点附近发生拥堵的概率更大。

基于上述分析，进行算法启发项拥塞跟踪调整。传统 A算法启发项h( n)表示其在搜索路径时的方向导航指引，故在此基础上考虑信息素浓度对寻路方向的影响，并对启发项进行相应地修改，适应性调整后的改进 A算法启发函数如下：

$$h(n)=h_1(n)+h_2(n) \tag{13}$$

式中h₁(n)表示传统算法的路径搜索方向指引，其值为两个欧氏距离的比值，分子为当前顶点到终止顶点的欧氏距离，分母为起始顶点到终止顶点的欧氏距离：

$$
h_1(n)=\frac{\sqrt {{(x_e-x_n)}^2 + {(y_e-y_n)}^2}}{\sqrt {{(x_e-x_s)}^2 + {(y_e-y_s)}^2}} \tag{14}
$$

表达式(13)中h₂(n)表示当前待搜索顶点的信息素浓度p_n与其周围邻近 9 个顶点信息素浓度p_i的平均值的比值，表示当前顶点周围局部拥堵情况的反馈指引：

$$h_2(n)=\frac{P_n}{\frac{1}{9}\sum_{i=1}^9 p_i} \tag{15}$$

因算法代价函数的核心实际代价在于g值的计算，h值在算法中作为启发项主要进行搜索方向导航，故本文在这里将h1(n)与h2(n)都实现为比重的形式，令其在1附近小范围波动。防止随着搜索次数的增加，而导致信息素浓度过高，从而使信息素浓度成为算法规划主导因素而导致g值搜索效果失效，而大幅增加移动机器人运行时间。

1.5 改进 A*算法流程

根据以上分析计算，可归纳整理出改进 A*算法对于搜索中间某个待搜索顶点 n 的实际估计代价函数为：

$$ f(n) = h_1(n)+h_2(n)+ \sum_{(i=1)}^n (g_1(i)+g_2(i)) \tag{16}$$

其具体含义是从规划起点经由中间某一顶点 n 到达终止顶点的最小实际估计代价。其中，实际代价由启停时间代价与转角时间代价组成，估计代价为算法启发项，由路径搜索方向指引项与局部拥堵情况反馈指引项组成。

改进 A*算法总体流程如图 4 左图所示，图中openList 与 closeList 为两个点集，前者表示待搜索顶点的集合，后者表示已搜索顶点的集合，每一个顶点都维护了一个 parent 指针表示该顶点的前驱路径点。算法每循环一次，会从 openList 中选 出 代 价 函 数 值 最 小 的 顶 点 作 为 当 前 点curPoint，并根据当前顶点 curPoint 以及具体路径图获取当前点临近可到达顶点的集 sPoints。对于sPoints 中每一个点都是当前顶点可能到达的待搜索节点 target，根据 target 是否已经在 openList算法会有不同的处理流程。若 target 不在 openList中则其没有被搜索过，直接计算代价函数值即可；否则，到达 target 存在多条可能路径，需要根据g 值比较来进行取舍。最后，判断目标顶点endNode 是否在 closeList 中来选择是否继续循环或者结束算法。

改进 A*算法 g 值计算流程如图 4 右图所示，算法在计算旋转实际时间代价 rotateG 时首先需要判断当前顶点 currentNode.parent 是否为空，即判断 currentNode 是否为起始点，若不是起始点则需计算 rotateG，否则 rotateG 为 0。最后将三部分g 值加起来作为 targetNode 的总 g 值返回。

2 实验验证

2.1 改进 A*算法最优时间搜索验证

本小节针对上述所设计的改进 A算法进行仿真实验测试，并与传统 A算法进行移动机器人规划路径时耗比较来说明改进 A*算法的有效性。为了保证仿真实验模拟的随机性，在x- y平面上随机生成了 40 个顶点与相应的边组成测试用拓扑路径图，并设置各边移动机器人所允许通行的最大速度为0.5m/s，所生成的拓扑路径图如图 5 所示，其中顶点 1 位于x- y平面坐标原点，各路径边的长度在图中均有标注，且单位为 m。

2.1.1 改进 A*算法单次最短时间规划验证

为了具体、直观地验证改进 A算法的有效性，首先进行单次路径规划，比较传统 A算法与改进 A*算法的规划路径差异性。

在图 5 所示路径图中，以 7 号顶点作为规划起始顶点，37 号顶点作为规划终点，分别使用传统 A算法与改进 A算法进行路径规划，所得到的路由选择结果如图 5 所示。由图中可明显看出，传统 A算法与改进 A算法路径选择有着明显的差异。其中，蓝色线路为传统 A算法规划路径，红色线路为改进 A算法规划路径。表 1 为两种算法单次规划结果参数对比情况表。

对比项	路径	路径长/m	时间/s
传统 A*	7-14-13-12-11-10-9-8-15-37	43.4	114
改进 A*	7-22-31-40-39-38-37	46.1	109

2.1.2 改进 A*算法多次最短时间规划验证

上述针对传统 A算法与改进 A算法做了单次路径规划的比较，两种算法所规划出的路径存在明显的差异，且改进 A算法规划路径要明显优于传统 A算法。本小节针对图 5 仿真测试拓扑路径图进行多次路径规划来测试验证改进 A*算法的最优时间搜索有效性。

测试中，分别使用传统 A算法与改进 A算法进行了 10 次、20 次、…100 次路径规划，为了增加规划的真实性与随机性，每次规划在路径图上下左右四条出入边上选择任意顶点作为起始顶点，并在剩余三条出入边上随机选择任意顶点作为终止点，统计移动机器人总体运行时间的变化情况如下图 6 所示。

图中，黑色折线表示在规划次数不同情况下，改进 A算法移动机器人总体运行时间变化关系，红色折线则是传统 A算法的总体运行时间变化关系。显然，传统 A算法折线在改进 A算法折线上方，故从整体来看，改进 A算法移动机器人实际运行时间短于传统 A算法。表 2 为两种算法多次规划对比情况。

规划 次数	是否为改 进 A*算法	总体时间/s	单次运行 平均时间 /s	减小比例/%
10	Y N	756 839	75.6 83.9	9.9
20	Y N	1228 1574	61.4 78.7	22.0
30	Y N	1751 2182	58.4 72.7	19.7
40	Y N	2388 2760	59.7 69.0	13.5
50	Y N	3167 3654	63.3 73.1	13.4
60	Y N	3693 4268	61.5 71.1	13.5
70	Y N	4463 4746	63.7 67.8	6.0
80	Y N	4858 5438	60.7 70.0	13.3
90	Y N	5514 6492	61.3 72.1	15.0
100	Y N	6862 7131	68.6 71.3	3.8
总计	Y N	34677 39083	63.0 71.1	11.4

表 2 统计了传统 A算法与改进 A算法在不同规划次数情况下的移动机器人总体运行时间、移动机器人单趟平均运行时间以及运行时间减小比例的对比关系，由表可知对于不同规划次数，改进 A算法移动机器人运行时间都相较传统 A算法有了明显的下降，且传统 A算法的总计移动机器人单次平均运行时间为 71.1s，改进 A算法为 63.0s，下降比例达到 11.4%，说明改进 A*算法规划出的路径对移动机器人整体运行效率有了很大程度的改善。

2.2 改进 A*算法拥塞适应性验证

图 7 为双向多入多出路网模型[23]，其中路网出入端共包含 10 个顶点，且每条路径边长度相等。令起点为地图左上角顶点，终点为地图右下角顶点，分别使用传统 A算法与无启发项调整改进 A算法进行路径规划，规划结果如图 7 所示：

由图 7 可知，在单次路径规划中，传统 A算法由其代价函数启发项的指引，规划路径为图中蓝色路径，而无启发项调整改进 A算法为了减少路程中移动机器人姿态调整的次数，从而降低移动机器人运行时间而选择红色路径。但对于大型智能制造车间系统，每台移动机器人使用无启发项调整改进 A算法进行路径规划，将导致单台车辆的规划路径单一性严重，继而增大局部路网发生区域拥堵的风险，严重时甚至会导致移动机器人运行系统瘫痪[24]。无启发项调整改进 A算法的路由选择策略在到达终止顶点前为尽量将行径路线调整为直线而减少时间消耗，会选择在路网出口边上进行大量的移动，这势必会造成路网出口边处移动机器人流量过大，从而导致拥堵。

随机生成出入口法仿真策略是研究评价路网宏观效率以及安全性能的常用方法[25]，使用图 7所示双向多入多出路网进行改进 A*算法启发项调整前与调整后的仿真实验比较，设置路径图中每条边的长度为 2m，且各边所允许通行的最大速度为 1m/s，仿真实验步骤如下所示：

(1) 初始化总任务数量 sum=5000、信息素矩阵为全 0 矩阵、累计任务执行次数 i=0。
(2) 在路网左右两侧随机生成任务起始位置。
(3) 根据起始侧，在对侧随机生成任务终止位置。
(4) 根据起始位置与终止位置进行单移动机器人路径规划。
(5) 规划结束后更新信息素矩阵，任务执行次数 i 加1，并返回步骤二，直到任务执行次数达到总任务数量后终止实验。

当所有移动机器人完成了路径规划后，根据信息素矩阵的元素分布来观察拥塞分布的规律。使用上述仿真实验流程分别对传统 A算法以及启发项调整前后的改进 A算法进行仿真对比。传统A算法实验测试结果如图 8 所示。改进 A算法启发项调整前实验结果如图 9 所示。

由图 8、图 9 可以看出，改进 A算法在启发项调整前相较于传统 A算法为尽可能减少移动机器人方位调整的次数、降低运行时间，在任务起始位置与终止位置边进行大量的纵向移动，导致任务发生与结束侧附近交通载荷量远高于其他区域，整体图像曲面在两侧凸起严重，类似马鞍状分布。由于交通载荷量高的区域发生局部拥塞的概率更高，故该情况会在出入口处造成移动机器人阻塞等待，严重影响机器人系统的运行效率。

改进 A*算法启发项调整后，实验测试结果如图 10 所示。

由图 10 可看出，改进 A算法在启发项调整后，交通载荷量曲面分布明显平缓，说明算法在调整后所规划路线较为均匀，降低了移动机器人发生局部拥堵的概率。表 3 为传统 A算法以及改进 A*算法调整前后移动机器人运行结果对比：

对比项	传统 A*算法	改进 A*算法调整前	改进 A*算法调整后
信息素矩阵标准差	15.6	361.2	11.3
机器人单趟平均运行时间/s	63.7	49.7	52.2

由表 3 可知，在改进 A算法启发项调整后，信息素矩阵元素标准差下降了 96.9%且低于传统A算法，故算法对局部拥塞情况有了较好的控制，大幅提升了场景适应性。对于单趟移动机器人平均运行时间，算法在调整后增加了 4.9%，并且远低于传统 A算法的单趟平均运行时间，故在引入启发项调整后移动机器人平均运行时间仅有微量的增加，因此改进算法的最优时间搜索性能得到了保障。综上所述，改进 A算法引入启发项均值比例调整后，在保证原算法最优时间搜索效果的情况下能够有效地降低路网局部拥塞情况的发生概率。

进一步地，我们以华中科技大学工程实训中心教学车间为实验环境，选用无轨 AGV 进行智能移动机器人路径规划真实场景测试。如图 11所示，本文实验使用的无轨 AGV 主要任务是从起始点到终止点进行移动从而完成物料的搬运、CNC 机床的上下料等工作。在实际场景中建图、确认站点完成后，以实际站点、路径边等地图信息为输入条件，在无轨 AGV 软件系统的路径规划模块下，调用不同的路径规划算法，完成算法在真实场景下的测试，如图 12 所示。一共进行了四组路径规划测试。其中实验一规划起点为 1 号，终点为 8 号；实验二起点为 16 号，终点为 103号；实验三起点为 103 号，终点为 19 号；实验四起点为 15 号，终点为 106 号。图中传统 A算法规划路径为青蓝色，改进 A算法规划路径为红色，二者规划的重合路径用黑色线条表示。表 4为四组规划实验所规划的路径长度与无轨 AGV运行时间对比结果，由表中可以看出虽然传统 A*算法所选路径几何距离较短，但改进 A算法所规划的路径实际运行时间更短、效率更高，验证了基于改进 A算法且兼顾启停特性和转角时耗的移动机器人路径规划方法的有效性。

实验编号	是否改进	规划路径	路径长 度/m	运行时 间/s
一	N Y	1-101-3-102-4-106-103-5-10-105-104-9-8 1-101-2-20-16-12-11-105-104-9-8	38.1 43.3	73.9 65.8
二	N Y	16-12-11-105-10-5-103 16-20-2-102-4-106-103	28.4 30.2	48.2 39.8
三	N Y	103-5-10-105-11-12-16-17-18-19 103-106-4-102-2-20-16-17-18-19	43.9 45.7	66.1 61.1
四	N Y	15-14-13-12-11-105-10-5-103-106 15-14-13-12-16-20-2-102-4-106	50.3 54.3	87.8 82.4

3 结 论

本文针对移动机器人在真实路段上运行时存在的启动、制动过程以及转向方位调整等影响移动机器人实际运行时间因素的问题，提出了考虑移动机器人启停速度特性及转角时耗的改进 A算法，通过将移动机器人启停速度变化情况以及转向方位调整时长转化为 A算法代价函数的实际代价来进行路由选择，实验证明了所提方法在实际移动机器人路径规划中能显著地降低其运行时间，大大提升了采用该方法规划路径后移动机器人的任务执行效率。在此基础上，分析了启发项调整前改进 A算法在双向多入多出路网模型下潜在的局部拥堵不适应性问题，并通过对改进A算法进行启发项比例均值拥塞跟踪调整，在保证移动机器人单趟平均运行时间仅有微量增加，即保证启停特性与转角时耗最优时间搜索效果的前提下，有效地降低了局部拥堵发生的概率，大大提升了移动机器人系统的运行效率。

参考文献：

[1]姚锡凡, 马南峰, 张存吉, 等. 以人为本的智能制造：演进与展望 [J]. 机械工程学报, 2022: 1-13.
[2]武星, 翟晶晶, 楼佩煌, 等. 考虑任务行程时间的多载量自动导引车系统防死锁任务调度 [J]. 中国机械工程, 2021,32(23): 2840-2849.
[3]周亚勤, 汪俊亮, 吕志军, 等. 密集仓储环境下多AGV/RGV 调 度 方 法 研 究 [J]. 机械工程学报,2021,57(10): 245-256.
[4]ZHANG Ruijin, YANG Zhiyong, JIANG Shan, et al. An inverse planning simulated annealing algorithm with adaptive weight adjustment for LDR pancreatic brachytherapy [J]. International Journal of Computer Assisted Radiology and Surgery, 2022,17(03): 601-608.
[5]ROSTAMI S M H, SANGAIAH A K, WANG Jin. et al. Obstacle avoidance of mobile robots using modifiedartificial potential field algorithm [J]. Journal on Wireless Communications and Networking, 2019,2019(01): 70-88.
[6]王硕, 段蓉凯, 廖与禾. 机器人路径规划中快速扩展随 机 树 算 法 的 改 进 研 究 [J]. 西安交通大学学报,2022,56(07): 1-8.
[7]HAMZHEEI M, FARAHANI R Z, RASHIDI-BAJGAN H. An ant colony-based algorithm for finding the shortest bidirectional path for automated guided vehicles in a block layout [J]. The International Journal of Advanced Manufacturing Technology, 2013,64(01): 399–409.
[8]ZACHARIA P T, XIDIAS E K. AGV routing and motion planning in a flexible manufacturing system using a fuzzy-based genetic algorithm [J]. The International Journal of Advanced Manufacturing Technology, 2020,109(07): 1801–1813.
[9]刘志强, 何丽, 袁亮, 等. 采用改进灰狼算法的移动机器人路径规划 [J]. 西安交通大学学报, 2022,(10):1-11.
[10] GUO Xiaowei, PENG Gongzhuang, MENG Yingying. A modified Q-learning algorithm for robot path planning in a digital twin assembly system [J]. The International Journal of Advanced Manufacturing Technology, 2022,199(05): 3951-3961.
[11] LIU Ye, DU Yanping, DOU Shuihai, et al. Research Summary of Intelligent Optimization Algorithm for Warehouse AGV Path Planning [C]. LISS 2021, 2022: 96-110.
[12] 梁军, 韩冬冬, 盘朝奉, 等. 基于移动机器人的智能 车库关键技术综述 [J]. 机械工程学报, 2022,58(03): 1-20.
[13] 唐恒亮, 唐滋芳, 董晨刚, 等. 基于启发式强化学习的 AGV 路径规划 [J]. 北京工业大学学报, 2021,47(08):895-903.
[14] 王洪斌, 郝策, 张平, 等. 基于 A~算法和人工势场法 的 移 动 机 器 人 路 径 规 划 [J]. 中 国 机 械 工 程 ,2019,30(20): 2489-2496. [15] 赵晓, 王铮, 黄程侃, 等. 基于改进 A算法的移动机器人路径规划 [J]. 机器人, 2018,40(06): 903-910.
[16] 王洪斌, 尹鹏衡, 郑维, 等. 基于改进的 A~算法与动态窗口法的移动机器人路径规划 [J]. 机器人,2020,42(03): 346-353. [17] CHEN Jiaxing, LUO Yi. Dynamic Path Planning for Mobile Robots Based on the Improved A-Star Algorithm [J]. Academic Journal of Computing & Information Science, 2021,4(08): 73-77. [18] ZHANG Zhongwei, WU Lihui, ZHANG Wenqiang, et al. Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop [J]. Computers & Industrial Engineering, 2021,158:107397. [19] 赵盼, 杜兆才, 刘江, 等. 基于改进 RRT算法的超冗余度机器人末端避障路径规划 [J]. 航空制造技术,2022: 1-7.
[20] 袁洋, 叶峰, 赖乙宗, 等. 结合负载均衡与 A*算法的 多 AGV 路径规划 [J]. 计 算 机 工 程 与 应 用 ,2020,56(05): 251-256.
[21] 丁恒, 郭放, 蒋程镔, 等. 多个 MFD 子区边界协调控制方法 [J]. 自动化学报, 2017, 43(4):548-559.
[22] 朱海峰, 刘畅, 温熙华, 等. 均衡流量和饱和度的交通 瓶 颈 控 制 [J]. 控 制 理 论 与 应 用 , 2019,36(05):816-824.
[23] 杨智飞, 苏春, 胡祥涛, 等. 面向智能生产车间的多AGV 系统多目标调度优化 [J]. 东南大学学报(自然科学版), 2019,49(06): 1033-1040.
[24] 余娜娜, 李铁克, 王柏琳. 自动化分拣仓库中多AGV 在线协同调度算法 [J]. 计算机集成制造系统.2021: 1-23.
[25] MA Zian, XIE Jianbo, QI Xiao, et al. Two-Dimensional Simulation of Turning Behavior in Potential Conflict Area of Mixed-Flow Intersections [J]. Computer-Aided Civil and Infrastructure Engineering, 2017,32(05): 412-428.