基于改进A＊算法的AGV转运机器人路径规划研究

石英托 陈 华 张连新 孙鹏飞 裴 培 李代杨

（中国工程物理研究院机械制造工艺研究所，四川 绵阳 621900）

随着科学技术的发展，智能存储等手段层出不穷，如AGV全向车等实现我国舟山港的无人化，南京晨光集团装配过程中各工位间智能转运等。机器人正逐步替代人工，成为自动化生产与运输领域的生力军。在执行某些转运任务时，需要操作人员完成某些特定工序，与机器人共享工作空间。由于人的误操作、机器人故障等意外，机器人可能会与人发生碰撞，对人员的安全产生威胁。因此如何保证人与机器人的安全交互是AGV机器人广泛应用于自动化运输需首要关注的问题。

机器人路径规划提供了一种解决方案。路径规划包含两个层次，一是避障，控制机器人能自主避开障碍物；二是最优，按照需求规划出路径最短或耗费最少的路径。国内外常用的路径规划算法包括Dijkstra算法[1]、A*算法[2]、动态规划算法[3]、遗传算法[4-5]和人工势场法[6]等。Geetha S等[7]将蚁群算法与遗传算法相结合，在多目标路径规划中得到了很好的效果；王志中等[8]提出了基于改进粒子群算法的机器人路径规划方法，改进算法规划的路径在长度、平滑度和规划时间上均具有优势。相比其他算法，A*算法简单，易实现，便于机器人避碰路径规划，但在障碍较多、环境复杂的情况下计算迭代次数较多，影响其计算的实时性。

本文的研究基于笔者单位在研的某产品高效装配生产线项目，旨在提出一种改进的A*路径规划算法，应用于AGV转运机器人运动控制中，当检测到运动路线上出现障碍物后，能够实时规划运动路径，实现AGV机器人主动避碰，从而在不影响转运效率的前提下，提高AGV机器人应用的安全性。其主体架构为：首先对AGV机器人和运动障碍进行分析，建立机器人运动交互环境模型；随后对传统A*算法进行分析，提出一种改进的A*路径规划算法；接着对改进后的算法进行Matlab仿真验证；最后对文章进行总结。

1 环境建模

图1为某产品高效装配生产线分配了装配、仓储等区域。为节省人力，提高转运效率，不同区域间产品及工装的转运就依靠AGV转运机器人实现。

图1 高效装配生产线示意图

AGV转运机器人上装有导航模块，能够对运动环境进行实时扫描，通过控制器计算与处理，将环境信息转化为计算机可识别的数据，进而建立AGV运动交互环境模型。

基于环境信息的建模方法有很多，常用的有拓扑图法、栅格法和导航网络[9]等。本文采用栅格法进行环境建模，其优势在于：

（1）利用规则长方形包络障碍物来近似建模，虽然扩大了障碍域，所规划的路径并非最短无碰撞路径，但实则增大了安全距离，提高了安全性。

（2）栅格法对随机障碍域的表述准确，不易产生失真等情况，适用于现场复杂环境描述。

（3）栅格法对障碍域的描述相对简化，从而提高路径规划的效率。

AGV机器人在厂区内工作环境相对复杂，运动路径上可能出现杂物、操作人员等。AGV导航模块对这些障碍进行实时扫描与识别，将其外形、位置等信息反馈给主控模块用于构建环境模型。

基于上述分析，得到AGV机器人运动交互环境建模如图2所示。其中1（左）为起点，2（右）为终点，黑色部分包含环境障碍和边界，同视为障碍。

图2 AGV机器人运动交互环境建模

2 路径规划算法研究

2.1 A＊算法原理

A*算法是广泛用于寻路和图遍历的计算机算法，由于其具有较好的性能和准确性，经常被使用在最短路径求解中，是一种启发式搜索算法。其成本估计函数为

式中：f(n)代表从起始节点经由当前节点n到目标节点的成本估计，g(n)代表从初始节点到当前节点n的实际成本，h(n)代表从当前节点n到目标节点的最佳路径的估计成本。

A*算法步骤为：

（1）将起点S加到OPEN表中。

（2）判断OPEN表是否为空，若为空，则算法结束，无法找到路径，否则进入下一步。

（3）从OPEN表中找到f(n)最小的节点N，添加到CLOSE表中，并判断该节点是否为目标节点E，若为目标节点E，算法结束，否则进入下一步。

（4）找到节点N的所有相邻节点Xi（i≤k，k为与节点N相邻的全部节点个数）。若Xi不在OPEN表中也不在CLOSE表中，计算f(Xi)并加入OPEN表中；若Xi在OPEN表中，但是f(Xi)比OPEN表中估计值小，更新OPEN表中的估计值，并按从小到大排序；若Xi在CLOSE表中，则忽略该点。

（5）重复步骤2到步骤4，直到目标点E在CLOSE表中，表明已找到最优路径，或OPEN表为空，算法结束。

在运行此算法之后，目标节点将指向其前导节点，依此类推，直到某个节点的前导是开始节点，就可以得到最短路径序列。

区别于Dijkstra算法，A*算法用了一个启发函数h(n)，使算法利用启发信息朝着某个确定的方向搜索，所以其访问的节点比Dijkstra算法少得多，能快速地导向目标结点，访问到目标节点后算法停止。

2.2 A＊算法不足

A*算法原理简单，使用灵活，因此在现代路径规划领域应用广泛。但通过对其计算过程的分析，可知其存在一定的不足：朝着某个确定的方向搜索，能快速地导向目标结点。h(n)越小，A*算法需要扩展的点越多，运行速度越

（1）启发函数的选取对算法的影响。启发函数可以影响A*算法的运行，使算法利用启发信息慢，此时算法运行效率较低；h(n)选取过大时，算法不一定能找到最佳路径，运行质量较差。

（2）OPEN表对存储空间的占用。当地图较大、路径较为发展时，OPEN表中会保存大量待考察的点，对存储空间大量占用，使算法在表中插入、排序等操作变慢，影响运算效率。

（3）OPEN表中对成本估计f(n)的排序运算。随着算法深入，OPEN表中节点数持续增加，每次迭代运算都要对表中各节点f(n)进行计算和排序，导致运算效率下降。

2.3 A＊算法改进

结合2.2小节对A*算法不足的分析，提出对A*算法进行改进。

2.3.1 启发函数h(n)的选取

在A*算法的估价函数中，节点的g(n)值是实际值，而其h(n)值 是估值，h(n)选择得越合理，那么f(n)的值就越接近真实值，A*算法的效率就会越高。实际计算时常采用曼哈顿距离、对角线距离和欧几里得距离等[10-11]作为启发函数。曼哈顿距离代表标准坐标系上绝对轴距总和；对角线距离相比曼哈顿距离，考虑了沿对角线移动的情况；欧几里得距离特点是“两点一线”，为两点之间的最短距离。图3可以对3种距离进行清晰地表述：

图3 3种距离示意图

图中A为起点，B为终点，黑色实线为各自距离。对比3种距离，曼哈顿距离运算简单，寻径的效率高，但寻径的质量较低；欧几里德距离最短，易求得最短路径，但计算涉及平方和开方运算，求解效率低；对角线距离作为启发函数，在进行估值运算时与最优路径的估值误差不大，同时计算相对简化，因此本文采用对角线距离启发函数。具体计算过程如下：

式中：c表示在地图中水平或竖直移动一步的代价，按对角线移动的代价则为由式（2）～（4）即可计算得到对角线距离的代价估值 。

2.3.2 OPEN表中节点数目优化管理

在A*算法进行路径搜索过程中，每向目标方向扩展一次节点，就要对相邻点f(n)进行计算，并在OPEN表中进行排序，导致算法扩展速度越来越慢。而实际上一些早期加入的和估值很大的节点就因不再需要而成为计算负担。基于此，本文提出对OPEN表中节点数量进行管理与优化。当OPEN表中的节点数达到一定值时，删除最早加入的估值较大的节点，使算法在后续运行过程中，OPEN表中节点数量维持恒定，这样就提高了算法运行后期的计算效率。

对OPEN表中节点数量进行优化管理后，在同样的条件下进行对比发现，运算效率得到了提高，同时扩展的节点并没有减少，因此仍能够得到与原算法相同的路径搜索结果。

3 仿真验证

改进A*算法在路径搜索中的效果需要通过试验进行验证。本文中拟在Matlab环境中进行验证。

仿真试验的软硬件环境如下：

软件：Windows 7旗舰版 64位，Matlab R2015b（x86）；

硬件：CPU Intel Core i5-7500@ 3.40 GHz，内存8 G。

仿真实验采用20×20方格，网格间隔0.2 m的区域进行，建立的环境模型如图2所示。随后分别对无障碍和不同障碍情况下算法的路径规划效果进行仿真验证。仿真结果如图4所示：

图4 不同环境路径规划结果

路径规划结果中，网格变浅灰表示每次迭代运算过程中，该点被加入了OPEN表中，网格变深灰表示该点为浅灰点的相邻待考察点；最终形成的黑色细线路线即为路径搜索结果。

下面对路径搜索效率进行比较，结果如表1所示。通过对仿真试验结果进行分析，可以得出：

表1 路径规划效率比较

（1）改进A*算法与A*算法路径规划结果一致，都能利用启发信息，朝着目标节点方向进行路径搜索，从而快速导向至目标节点，同时都能够规避障碍，规划出合理路线。

（2）在路径规划效率方面。当环境较为简单，运动路线上没有障碍时，所规划的运动路径较为简单，OPEN表中数量较少，算法改进后效率提升不明显；当环境较为复杂，运动路线上出现障碍时，在路径规划迭代运算过程中，OPEN表中数量逐渐增加，算法改进后效率提升较为明显；且当运动路线上障碍越复杂时，算法改进后效率提升更加明显。

4 结语

本文针对提高AGV转运机器人在高效装配生产线项目应用中的安全性，提出了一种改进A*路径规划算法，应用于机器人运动控制中，能够在不影响转运效率的前提下，实现机器人主动避碰。通过仿真试验，得出改进A*算法与A*算法路径规划一致，都能利用启发信息，快速导向至目标节点；算法改进后，路径规划效率得到提升，且当运动路线上障碍越复杂，效率提升越明显。因此，可认为改进A*算法能够规划路线，实现AGV机器人主动避障。