基于改进A 星算法对自动导引小车路径规划研究*

王永成，杨明漾，张国辉

（郑州航空工业管理学院管理工程学院，郑州 450046）

0 引言

自动导引小车（Automatic Guided Vehicle）路径规划是AGV 作用在实际生产生活中的重要基础。有动态障碍物的路径规划是当前典型的路径规划问题，主要以最短路径和最短时间等为评价标准，从选定的起始点到目标点找出一条无碰撞的安全路径，路径规划问题可以称为避碰规划问题。AGV工作地图可以分为两种：静态地图和动态地图，本文主要研究动态地图中AGV 路径规划问题。

AGV 路径规划问题是一种约束优化问题，有许多专家学者在研究AGV 路径规划算法问题，使用的算法有概率路线图法（Probabilistic Roadmap，PRM）［1］、Dijkstra 算法［2］、A 星算法［3］、强化学习算法（Reinforcement Learning，RL）［4］、蚁群算法（Ant Colony Algorithm，ACA）［5］、遗传算法（Genetic Algorithms，GA）［6］、神经网络算法［7］、狼群算法（Wolf Colony Algorithm，WCA）［8］、粒子群算法（Particle Swarm Optimization，PSO）［9］、人工势场算法［10］、模糊逻辑算法［11］等。文献［12-19］也作了相关研究。

A 星算法是一种基于启发式的路径规划算法，也是静态环境中寻找最短路径最有效的直接搜索方法之一，相较于其他传统算法，具有更快的运算速度。

n 是路径上的一个节点，f（n）是从第n 个节点到终点的估计代价，g（n）是从第n 个节点到终点的实际代价，h（n）是从第n 个节点到终点的最佳路径的估计代价。在此算法中，估计代价h（n）越好，则运算速度与规划出的路径则最优，一般选用曼哈顿距离或欧几里得距离为估计代价。A 星算法是一种成熟且最有效的路径规划直接搜索方法，但A 星算法估计代价选取不好时，会出现运算时间长或路径不最优的问题。

1 基于改进A 星算法的AGV 路径动态规划

1.1 AGV 工作地图建模改进

路径规划地图建模中包含的元素主要有：AGV本身、静态障碍物以及动态移动障碍物。传统建模方式为：在程序中输入地图矩阵，地图中每一个栅格对应二维矩阵中的一个数据，1 为障碍物，0 为无障碍空间。对地图进行建模，进一步改进的建模方式为：输入障碍物的顶点坐标，以顶点坐标围成的封闭图形作为障碍物。

在栅格数较多且地图复杂的情况时，使用这两种建模方式极为复杂，假设地图大小为n×n，传统建模方式需要输入n2个数据，而后一种改进方式也需要输入极多的数据。在实际应用中，这样的建模方式不能准确地表示出实际地图的情况，且极为复杂，针对这个问题，本文对地图建模进行了改进，使算法能够直接且准确识别输入的照片，便于实际应用时工作地图模型的建立。图像处理的思路为：先将图片进行灰度化处理，再对其进行图像均衡化，对图像进行增强，然后使用大津阈值法统计整个图像的直方图特性，实现全局阈值T 的自动选取，将其进行二值化分割，最终得到输入图片的数字特征矩阵。大津阈值法如图1 所示。

图1 大津阈值法流程

在图像均衡化时，使用累积分布函数，对灰度化后的图片进行均衡化，其映射方法如下：

其中，n 是图像中像素的总数，nk是第k 灰度级个数，L 是图像中灰度级总数。

通过对照片图像处理设计，使得程序可以直接识别所在打开路径文件夹里的任意格式图片，黑色部分自动识别为障碍物，白色部分识别为可行路径，大量减少地图建模时间，在实际应用时可随时改变地图，便于对不同AGV 工作地图进行路径规划。在程序中设置3 个常用地图map1、map2、map3，利于常用地图的切换。

动态地图则是在静态地图的基础上增加动态障碍物，以模拟在地图中运动的人或物。本文在A星算法程序的基础上加以改进，在地图建模处理中增加动态障碍物的设计。程序以增加3 个动态障碍物为例，分别将障碍物设置为随机移动障碍物、横向随机移动障碍物、竖向随机移动障碍物分别仿真人和机器的运动。随机移动障碍物的运动路径为上、下、左、右、左上、左下、右上、右下、原地停止；横向移动障碍物的运动路径为左、右、原地不动；竖向随机障碍物的运动路径为上、下、原地不动；障碍物运动方向等概率出现。

1.2 接收地图固定缩放处理

在利用A 星算法求解路径规划问题时，地图的大小直接影响着算法的运算速度，由于路径规划问题对地图精确度的要求较低，所以对所有地图进行缩放处理，增加算法运算速度，提升系统效率以快速得到最优路径。

在本文中，对缩放比例进行设计，以达到在不影响地图精确度的前提下使算法运行速度更快。用地图栅格均分整个地图，栅格数越多，精确度越高。在这里用栅格个数作为精确度，由于AGV 路径规划对精确度要求并不苛刻，所以本文对比了10×10、50×50、100×100、150×150、200×200、1 000×1 000 的栅格数地图，算法运算速度如表1 所示。路径规划精确度分别如图2 所示。

图2 各个栅格数地图路径规划精确度

表1 不同地图尺寸运算速度对比

通过对比发现，100×100、150×150、200×200较为精确，1 000×1 000 最为精确，10×10、50×50精确度很低，从时间上来讲，随着栅格数的增加而增加，且增加越来越快。综合来讲100×100 与150×150 较好，但考虑到在时间可接受的前提下尽量精确，固本文采用150×150 固定大小，此时，A 星算法求解最短路径运算时间约为0.900 876 s，运算时间受初始点与目标点距离及障碍物复杂程度影响上下浮动。

此时，

n 为地图栅格尺寸，c 为地图实际尺寸。

1.3 拉直路径消除多余拐点

由于A 星算法的启发式函数，使A 星算法搜索具有方向感，能够减少大量计算，但在某些特定情况下，这个明确的方向感会导致多余拐角的产生，如图3 所示。

图3 方向感导致的多余拐点

使用曼哈顿距离作为A 星算法的估计代价h（x），是用于解决路径规划问题的常用方法，且较为准确，但由于搜索的方向感会产生多余拐角。为了减少多余拐角使路径更短，对A 星算法进行路径规划改进。

先进行静态路径规划，在规划好的路线上利用二阶导数检测路径拐点，再从起点开始每隔一个拐点依连接，判断连线上是否存在障碍物。若存在，则保留原路径；若不存在，则删除原路径保留连线，直到判断到终点为止，消除多余拐点流程图如图4 所示。

图4 消除多余拐点流程图

改进前后对比，如图5 所示。

图5 改进前（上）与改进后（下）对比

1.4 路径平滑处理

本文在AGV 路径平滑处理时，利用三次样条插值法及充气函数分别对无障碍路径区域及地图障碍物边沿路径进行平滑处理。

三次样条插值法原理是在已规划的路径上选取相隔n 个单位的样本点，舍弃这些样本点之间的规划点，再用平滑的圆弧连接这些样本点，形成光滑路径。三次样条插值法平滑路径，如图6 所示。

图6 3 次样条插值法平滑路径

在本文中，记路径总点数为P，相隔点数n 的计算公式如下（约定［］为去四舍五入符号）：

在实际AGV 运行环境中，由于AGV 装载货物，可能导致无碰撞尺寸会变得更大，利用算法规划出的路径可能会导致碰撞，不一定是AGV 可通行路径。所以对路径平滑进行更进一步的处理，先对地图进行膨胀，得出规划路径，求出路径规划后，再将膨胀地图变为原地图，这样求出的规划路径与障碍物就将保持一定距离，增加路径的可通行性，如图7 所示。

图7 原始地图与膨胀地图

对平滑处理前后路径进行对比，发现平滑处理后的路径明显优于处理前的规划路径，如图8所示。

图8 平滑处理前后路径

1.5 局部动态地图路径规划

在局部动态环境中，引入D 星算法思想，寻求局部有障碍物时的路径。D 星算法与A 星算法类似，但运算是从目标点开始进行反向搜索，直到搜索到机器人当前位置。在D 星算法中，主要运用两个函数：Process-State 函数和Modify-Cost 函数，前者用于从目标点到当前位置的路径搜索；后者用于改变A 星算法中的估价函数h（n），当遇到动态障碍物时，Modify-Cost 函数将实时改变估价函数h（n），从而使机器人规避动态障碍物，得到可通行路径。

与A 星算法相比，D 星算法搜索是由搜索点向临接点发散的，无A 星算法的方向感，且搜索方向是由目标点到当前点，可有效搜寻避障路径。局部动态规划流程如图9 所示。其中，初始点为AGV 出发的点，目标点为AGV 所要到达的点，当前点为AGV 此时运动到的点，搜索点为此时动态路径规划搜索的点。

图9 局部动态规划流程图

在动态环境中，对AGV 尺寸、动态障碍物尺寸及AGV 小车圆心到动态障碍物圆心之间的距离安全程度划分的设计如下。

AGV 小车半径：2 栅格，动态障碍物半径：1 栅格。

AGV 小车到障碍物执行不同命令的距离设计：5 栅格：暂时停车等待，5-15 栅格：重新规划路径，15-25 栅格：减速行驶，25 栅格以上：正常行驶。

2 AGV 复杂环境路径规划仿真实验及结果分析

2.1 改进A 星算法仿真开发

为了验证改进算法的可行性与有效性，并使问题求解过程形象化和与视化，我们对改进A 星算法进行仿真开发，开发出基于改进A 星算法的AGV小车动态路径规划仿真平台，用户可以上传自己的地图来进行路径规划。

为了使动态规划时更好地显示AGV 小车的避撞路径规划，对AGV 小车进行设计，在仿真环境中，创建了一个半径为0.2 m 的红色圆圈作为机器人，并设置了3 个半圆作为探测障碍物的激光。蓝色的圆圈是危险区域，如果一个物体出现在这个区域，机器人将暂停等待；绿色的圆圈是安全区域，如果一个物体出现在这个区域，机器人会重新规划路径；黄色的圆圈是感知距离区域，如果一个物体出现在这个区域，机器人就会减速，如图10 所示。

图10 不同情况下机器人性能

该平台主要分为3 大部分：静态地图路径规划、动态地图路径规划、AGV 小车命令显示窗口。静态地图路径规划部分包含地图选择、地图显示、起始点和目标点设定、操作命令4 个小模块。动态地图路径规划部分包含动态地图路径显示、随机移动障碍物设定、横向移动障碍物设定、竖向移动障碍物设定、操作命令5 个小模块，命令显示窗口部分可实时显示所有执行的命令及AGV 小车的实时状态，如下页图11 所示。

图11 仿真平台

2.2 改进A 星算法MATLAB 仿真结果

在本文中，分别对3 种地图进行AGV 路径规划仿真实验：静态趣味迷宫地图、复杂不规则地图、车间模拟地图，如图12 所示。分别验证改进A 星算法在静态地图、动态地图和实际运用中的可行性和高效性。

图12 3 种仿真地图

分别对地图1～地图3 进行静态路径规划实验，如图13～第136 页图15 所示。

图13 地图1：静态路径规划仿真

图14 地图2：静态路径规划仿真

图15 地图3：静态路径规划仿真

通过3 种地图静态规划仿真结果，验证了改进的有效性。改进A 星算法的图像处理可以直接接收输入的图片，无需进行地图建模，可直接在程序中输出150×150 地图；静态规划输出路径更加平滑且远离静态障碍物。

在动态规划部分，首先要进行地图的静态规划，选用地图2 的静态规划，得到静态规划路径后，对静态规划后的路径进行平坦化处理，在静态规划平坦化处理后的地图上分别设置随即动态障碍物、水平动态障碍物、竖直动态障碍物。为了模拟实际环境中的复杂情况，验证动态规划的有效性，在此加大了动态路径规划的难度，将动态障碍物全部设置到原路径上，且处于通道较窄的位置，以得到实时改进路径，动态障碍物设置如图16 所示，动态路径规划如下页图17 所示。

图16 动态障碍物设置

图17 动态路径规划

动态规划与静态规划路径对比如下页图18 所示，粉红色粗线为原规划路径，蓝色细线为动态规划实际路线。

图18 动态规划与静态规划路线对比

动态规划仿真结果验证了改进A 星算法具有在动态地图中搜索路径的能力，且可根据障碍物的位置实时改进路径，规避动态障碍物。

MATLAB 仿真实验验证了改进A 星算法的有效性。

2.3 仿真结果对比分析

通过MATLAB 仿真结果，验证了改进A 星算法静态规划与动态规划的有效性，接下来通过改进A星算法与其他几个常用算法的仿真结果对比，验证改进A 星算法的优越性。

在求解路径规划问题中，规划路径优劣的主要指标有3 个：路径长度、平滑程度、求解速度。路径长度是主要指标，也是优化路径的根本问题，平滑程度影响实际应用中AGV 运行快慢及安全程度，求解速度则是影响实际应用时系统能否迅速做出应对策略。所以，在此对改进A 星算法、改进遗传算法、改进蚁群算法、改进粒子群算法从路径长度、运算时间及平滑程度3 方面进行对比，平滑程度可以用弯折数和锐角弯折个数来表现。4 种算法的路径规划仿真效果如下页图19 所示，4 种算法运算速度及平滑程度如下页表2 所示。

表2 4 种算法运算速度及弯折数对比

图19 改进A 星算法与其他3 种算法路径规划对比

将4 种算法的各种指标进行打分，1 分为最差，4 分为最优，并根据指标重要程度进行加权综合评分，其中，路径长度权重为0.5，运算速度与弯折数权重都为0.2，锐角弯折数权重为0.1，得出评分如表3 所示。

表3 4 种算法综合评分

通过MATLAB 仿真对比，验证了改进A 星算法得出的规划路径更短更平滑，且运算速度较快，优于其他3 种改进算法。

3 结论

本文通过对当前较为普遍的路径规划算法进行对比，采用了较为成熟的A 星算法，并且通过自动识别图片、固化地图栅格数、拉直路径消除多余拐点，使用3 次样条插值法和地图膨胀函数对路径进行平滑处理、结合D 星算法思想处理动态规划等对A 星算法进行改进，应用MATLAB GUI 开发工具进行了仿真平台的开发，通过仿真实验结果及与其他算法的对比，验证了改进A 星算法的可行性与优越性。

与其他算法相比，自动识别图片可减少大量的地图建模时间，可以直接识别Auto CAD、Viso 等绘图工具绘制的图片，在实际应用中操作简单省时。固化地图栅格数则在不影响算法精度的前提下，大量减少算法时间，提高了路径规划的时效性，在实际应用中更加高效。拉直路径消除多余拐点减少了路径的弯折数且使路径更短。通过3 次样条插值法和地图膨胀函数对路径进行平滑处理，可以得到更加光滑的路径，在实际AGV 运行时，减少了大量弯折，使AGV 运行速度更快且更加安全。在传统A 星算法的基础上引入D 星算法，使算法可以实时规划AGV 路径，在遇到障碍物时可以做到有效避障，使此程序适应的场合更广，能够适应更复杂的情况，在实际应用中具有很大意义。

相对于当前流行的智能算法而言，本文所用的改进A 星算法在路径长度、运算速度、弯折数3 方面都较优，但在系统鲁棒性及与其他算法相结合方面还需深入研究。