基于改进灰狼优化算法的自动导引小车路径规划及其实现原型平台-AGV吧

０引言

科技的快速发展和定制化模式的出现使制造模式从规模经济向更多元化的产品组合方向演变［１］，增加了生产系统生产的产品品类，也使工艺流程更加复杂，由此对制造系统的柔性和制造资源的组织方式提出了更高的要求，作为一种运输物料的智能化工具，自动导引小车（ＡｕｔｏｍａｔｅｄＧｕｉｄｅｄＶｅｈｉｃｌｅ，ＡＧＶ）主要负责工位之间以及物料库和成品库与工位之间的物料转运［２］，已经广泛应用于现代生产系统，其部署不仅能提高生产系统内部物料流的运行效率，还有助于提高生产系统的柔性，因此ＡＧＶ的运行效率对提高整个生产系统的运行效率和柔性至关重要。为了提高整个生产系统的生产效率，从而更及时地响应市场需求的变化，需要考虑ＡＧＶ与车间调度的集成和多ＡＧＶ的协调控制等问题，还需要为每台ＡＧＶ规划出最优路径［３］。ＡＧＶ的路径规划目标是在ＡＧＶ的工作空间中，规划出一条与障碍物无碰撞的、从起点到目标的最优或近似最优路径，优化的指标一般是路径长度、路径安全性［４］等。根据ＡＧＶ工作空间环境地图是否已知，路径规划分为全局路径规划和局部路径规划［５］，本文假定环境地图已知，着重研究ＡＧＶ全局路径规划算法的设计。

ＡＧＶ路径规划属于ＮＰ－ｈａｒｄ问题［６］，设计高效的路径规划算法仍然是很大的挑战，大多数研究着重于智能优化算法。例如，Ｚｈｏｕ等［７］基于粒子群优化（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法提出改进的花授粉算法（ＦｌｏｗｅｒＰｏｌｌｉｎａｔｉｏｎＡｌｇｏｒｉｔｈｍ，ＦＰＡ），并应用改进ＦＰＡ求解路径规划问题；Ｔａｎｇ等［８］为了平衡ＰＳＯ的局部开发和全局搜索能力，提出惯性权重和加速常数的自适应调节策略；为了防止ＰＳＯ陷入局部极值，提出基于差分进化（Ｄｉｆｆｅｒ－ｅｎｔｉａｌＥｖｏｌｕｔｉｏｎ，ＤＥ）算法的改进方法；基于上述改进策略提出应用于ＡＧＶ路径规划的改进ＰＳＯ算法并证明了其收敛性，缺点是没有针对ＡＧＶ路径规划特点设计邻域搜索算子。Ｐａｎ等［９］基于蛙跳算法求解ＡＧＶ路径规划，缺点是环境地图简单对算法性能测试不够充分。Ｌｉａｎｇ等［１０］为了提高人工蜂群算法（ＡｒｔｉｆｉｃｉａｌＢｅｅＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ，ＡＢＣ）的收敛速度采用精英保留策略，为了保证搜索方向的可靠性采用解的共享机制，为了使解的更新利用种群最新信息采用解的即时更新策略，最后提出改进ＡＢＣ并应用于多ＡＧＶ的在线路径规划，缺点是没有结合ＡＧＶ路径规划的特点设计提高算法收敛速度的算子。Ｈｉｄａｌｇｏ－Ｐａｎｉａｇｕａ等［１１］考虑ＡＧＶ路径规划中的路径长度、安全性和路径光滑程度建立多目标规划模型，提出求解该问题的多目标萤火虫算法（ＦｉｒｅｆｌｙＡｌｇｏｒｉｔｈｍ，ＦＡ），并针对路径规划问题提出路径长度调节算子、路径安全性算子和路径光滑程度调节算子，基于多目标ＦＡ求解路径规划问题，证明改进策略的有效性，缺点是未涉及路径片段与障碍物相交的检查算法；Ｐａｋｄｉ等［１２］基于遗传算法求解移动机器人路径规划，为提高所优化路径的光滑程度，采用分段三次Ｈｅｒｍｉｔｅ插值多项式对路径进行光滑处理；为了提高算法求解路径规划时的局部开发能力，将路径片段分类并设计不同的变异算子，最后采用模糊自适应控制器使ＡＧＶ跟踪优化出的路径。缺点是未与其他智能算法对比来证明改进算法的优势。Ｚｈａｎｇ等［１３］针对路径规划的特点提出邻域变异算子来提高算法的局部开发能力，设计了基于可视空间的种群初始化方法来提高初始种群的质量，设计了不可行解修复算子来提高优化过程中可行解的比例，最后将改进ＧＡ用于求解ＡＧＶ动态路径规划问题。Ｌｅｅ等［１４］基于有向无环图提出改进的初始种群生成算法，并基于改进ＧＡ求解ＡＧＶ路径规划问题，结果证明改进策略有效提高了初始种群的质量，进而加快了算法的收敛速度。

ＮｏＦｒｅｅＬｕｎｃｈ理论［１５］指出任何算法都有自身的局限性，因此近几年有很多学者基于一些自然现象启发，竞相提出新的智能优化算法，如灰狼优化（ＧｒｅｙＷｏｌｆＯｐｔｉｍｉｚａｔｉｏｎ，ＧＷＯ）算法［１６］、教—学优化（Ｔｅａｃｈ－Ｌｅａｒｎｉｎｇ－ＢａｓｅｄＯｐｔｉｍｉｚａｔｉｏｎ，ＴＬＢＯ）算法［１７］、ＦＰＡ［１８］、鲸鱼优化算法（ＷｈａｌｅＯｐｔｉｍｉｚａ－ｔｉｏｎＡｌｇｏｒｉｔｈｍ，ＷＯＡ）［１９］、蜻蜓算法（ＤｒａｇｏｎｆｌｙＡｌｇｏｒｉｔｈｍ，ＤＡ）［２０］、蝗虫优化算法（ＧｒａｓｓｈｏｐｐｅｒＯｐｔｉｍｉｓａｔｉｏｎＡｌｇｏｒｉｔｈｍ，ＧＯＡ）［２１］等，并用于解决各类复杂的组合优化问题。ＧＷＯ算法是一种模拟灰狼群围捕猎物行为而得的新型智能优化算法，已经有很多学者应用ＧＷＯ算法求解各种优化问题，例如Ｋｏｍａｋｉ等［２２］应用ＧＷＯ算法求解两阶段装配车间作业调度优化问题，与其他算法对比证明了ＧＷＯ算法跳出局部极小值的概率较高；Ｌｕ等［２３］应用ＧＷＯ算法求解焊接车间的作业调度优化问题；Ｚｈａｎｇ等［２４］基于ＧＷＯ算法求解路径规划问题，并与其他算法对比证明了ＧＷＯ算法规划出的路径更优、效率更高；Ｍｉｒｊａｌｉｌｉ等［２５］基于标准ＧＷＯ算法提出多目标ＧＷＯ算法，拓展了ＧＷＯ算法的应用范围；Ｇｕｐｔａ等［２６］研究了ＧＷＯ算法求解大规模连续优化问题，结果证明ＧＷＯ算法求解大规模优化问题具有较好的性能；Ｌｏｎｇ等［２７］基于精英反向学习策略和混沌映射提出改进ＧＷＯ算法，并用于求解高维优化问题，与其他算法对比证明，改进ＧＷＯ算法能有效平衡全局搜索和局部开发能力；刘二辉等［２８］基于ＧＷＯ算法中的灰狼层级结构关系提出改进的精英保留策略，有效维持了种群的多样性，为了提高算法的局部开发能力提出邻域变异算子，进而提出改进ＧＡ，并用于求解ＡＧＶ路径规划问题，证明了改进ＧＡ求解路径规划的有效性。

基于以上文献，作为一种新型的群智能算法，与ＧＡ，ＰＳＯ等其他智能算法相比，ＧＷＯ算法能更好地平衡全局搜索和局部开发能力，然而该算法在ＡＧＶ路径规划领域研究较少，而且以上文献均未涉及路径片段与障碍物相交判断算法和路径片段避障算子，更缺少带有启发式规则的变异算子，因此本文着重针对ＡＧＶ路径规划的特点研究ＧＷＯ算法的改进策略，并应用改进ＧＷＯ算法求解ＡＧＶ路径规划问题。传统的判断路径片段与障碍物是否相交的方法是，逐次求障碍物的各个边与路径片段的交点，然后判断交点是否在障碍物上，进而确定路径片段是否与障碍物相交。因为计算交点坐标需要进行较多的乘法和除法运算，还需要多次判断，因此效率较低。本文提出的改进算法可以有效减少交点计算次数，从而提高算法的运行效率。传统的种群初始化方法采用完全随机的方法，程序每次运行生成的初始种群质量差异较大，为了提高初始种群的质量，本文提出新的种群初始化方法来有效提高初始解中优质解的比例。传统的变异算子缺少启发式规则，导致变异生成优质解的概率较低，为此本文设计带有启发式规则的邻域变异算子，以提高算法的局部开发能力。此外，与障碍物空间没有交集的路径片段生成效率对算法效率和寻优能力的提高同样至关重要，本文设计了新的避障算子以加快路径片段避开障碍物的速度。为了提高路径规划算法验证的效率，本文基于ＭＡＴＬＡＢＧＵＩ工具开发出了基于ＧＷＯ算法的ＡＧＶ路径规划仿真原型平台。

１ＡＧＶ工作空间描述

为了方便建模与分析，将ＡＧＶ工作空间分为障碍物空间和自由空间，由于本文着重研究ＡＧＶ的路径规划，而ＡＧＶ运动的形式是平面运动，因此定义：ＡＧＶ的工作空间Ｗ是由Ｒ２表示的物理空间，Ｗ的子集障碍物空间记为Ｏｏｂｓ，ＡＧＶ与障碍物无碰撞移动的空间为自由空间Ｃｆｒｅｅ，则Ｏｏｂｓ∪Ｃｆｒｅｅ＝Ｗ。

当进行ＡＧＶ路径规划算法设计时，首先要考虑的是环境地图的表示方法，网格地图因容易实施、对障碍物有较好的表示和对障碍物形状敏感性低等优点［２９－３０］，广泛应用于ＡＧＶ路径规划的环境地图建模，具体方法是将ＡＧＶ的工作空间划分为一定数量的单元格，若单元格属于障碍物空间，则用黑色表示，反之用白色表示，如图１所示。单元格尺寸依据环境地图复杂程度而定，较小的单元格尺寸表示环境地图更精确，有利于提高优化出的路径质量。

２基于改进灰狼优化算法的ＡＧＶ路径规划

２．１ＡＧＶ路径规划模型

为了方便描述，沿用ＧＡ用染色体表示一个解的方法，将ＡＧＶ从出发点到目的地的一条完整路径记为一个染色体（如图２），染色体上第一个基因和最后一个基因分别表示ＡＧＶ运动的起始点和目标点坐标。在自由空间中随机产生ｎ－２个点，满足｛ｐ１，ｐ２，…，ｐｎ｝∈Ｃｆｒｅｅ，这ｎ个点按顺序连接起来构成一个从起始点到目标点的路径。在优化求解过程中，每个染色体的第一个和最后一个基因保持不变［２８］，图１中的黑色实线表示一条包含６个节点的路径。

1. 本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长 QQ2766242327进行删除处理。
2. 本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END