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

  • 基于改进灰狼优化算法的自动导引小车路径规划及其实现原型平台已关闭评论
  • 208 views
  • A+
所属分类:AGV设计资料
摘要

针对智能优化算法求解自动导引小车路径规划问题效率低且易早熟的缺陷,提出一种用于求解复杂环境下自动导引小车路径规划问题的改进灰狼优化算法。算法引入路径微调算子和邻域变异算子来提高灰狼优化算法的局部开发能力,又引入新的初始解生成算法提高初始种群的质量;采用改进的路径片段与障碍物相交判断算法来提高算法的运行效率,再采用新的避障算子来提高路径片段避开障碍物的效率。基于MATLAB GUI开发工具开发了带有多种智能优化算法的自动导引小车路径规划仿真原型平台,并与单种群遗传算法、多种群遗传算法和改进遗传算法进行对比,验证了改进灰狼优化算法求解自动导引小车路径规划的有效性。

0 引言

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

AGV 路径 规 划 属 于 NP-hard问 题[6],设 计 高效的路径规划算法仍然是很大的挑战,大多数研究着重于智能优化算法。例如,Zhou等[7]基于粒子群优化(ParticleSwarmOptimization,PSO)算法提出改进的花授粉算法(FlowerPollinationAlgorithm,FPA),并 应 用 改 进 FPA 求 解 路 径 规 划 问 题;Tang等[8]为了平衡 PSO 的局部开发和全局搜索能力,提出惯性权重和加速常数的自适应调节策略;为了防止 PSO 陷入局部极值,提出基于差分进化 (Differ-entialEvolution,DE)算 法 的 改 进 方 法;基 于 上 述改进策略 提 出 应 用 于 AGV 路径规划的改进 PSO算法并证明了 其 收 敛 性,缺 点 是 没 有 针 对 AGV 路径规划特点设计邻域搜索算子。Pan等[9]基于蛙跳算法求解 AGV 路 径 规 划,缺点是环境地图简单对算法性能测试不够充分。Liang等[10]为了提高人工蜂群 算 法(ArtificialBeeColonyAlgorithm,ABC)的收敛速度采用精英保留策略,为了保证搜索方向的可靠性采用解的共享机制,为了使解的更新利用种群最新信息采用解的即时更新策略,最后提出改进 ABC并应用于多 AGV 的在线路径规划,缺点是没有结合 AGV 路径规划的特点设计提高算法收敛速度的算子。Hidalgo-Paniagua等[11]考虑 AGV 路径规划中的路径长度、安全性和路径光滑程度建立多目标规划模型,提出求解该问题的多目标萤火虫算法(FireflyAlgorithm,FA),并 针 对 路 径 规 划 问题提出路径长度调节算子、路径安全性算子和路径光滑程度调节算子,基于多 目 标 FA 求 解 路 径 规 划问题,证明改进策略的有效性,缺点是未涉及路径片段与障碍物相 交 的 检 查 算 法;Pakdi等[12]基 于 遗 传算法求解移动机器人路径规划,为提高所优化路径的光滑程度,采用分段三次 Hermite插值多项式对路径进行光滑处理;为了提高算法求解路径规划时的局部开发能力,将路径片段分类并设计不同的变异算子,最后 采 用 模 糊 自 适 应 控 制 器 使 AGV 跟 踪优化出的路径。缺点是未与其他智能算法对比来证明改进算 法 的 优 势。Zhang等[13]针 对 路 径 规 划 的特点提出邻域变异算子来提高算法的局部开发能力,设计了基于可视空间的种群初始化方法来提高初始种群的质量,设计了不可行解修复算子来提高优化过程中可行解的比例,最后将改进 GA 用于求解 AGV 动态路径规划问题。Lee等[14]基于有向无环图提 出 改 进 的 初 始 种 群 生 成 算 法,并 基 于 改 进GA 求解 AGV 路径规划问题,结果证明改进策略有效提高了初始种群的质量,进而加快了算法的收敛速度。

NoFreeLunch理论[15]指出任何算法都有自身的局限性,因此近几年有很多学者基于一些自然现象启发,竞相 提 出 新 的 智 能 优 化 算 法,如 灰 狼 优 化(Grey WolfOptimization,GWO)算 法[16]、教—学优化(Teach-Learning-BasedOptimization,TLBO)算法[17]、FPA[18]、鲸 鱼 优 化 算 法(WhaleOptimiza-tion Algorithm,WOA)[19]、蜻 蜓 算 法 (DragonflyAlgorithm,DA)[20]、蝗 虫 优 化 算 法 (GrasshopperOptimisationAlgorithm,GOA)[21]等,并 用 于 解 决各类复杂的组合优化问题。GWO 算法是一种模拟灰狼群围捕猎物行为而得的新型智能优化算法,已经有很多学者应用 GWO 算法求 解 各 种 优 化 问 题,例如 Komaki等[22]应用 GWO 算法求解两阶段装配车间作 业 调 度 优 化 问 题,与 其 他 算 法 对 比 证 明 了GWO 算法跳出局部极小值的概率较高;Lu等[23]应用 GWO 算法求解焊接车间的作业调度优化问题;Zhang等[24]基于 GWO 算法求解路径规划问题,并与其他算法对比证明了 GWO 算法规划出的路径更优、效率更高;Mirjalili等[25]基于标准 GWO 算法提出多目标 GWO 算法,拓展了 GWO 算法 的 应 用 范围;Gupta等[26]研 究 了 GWO 算法求解大规模连续优化问题,结果证明 GWO 算法求 解 大 规 模 优 化 问题具有 较 好 的 性 能;Long等[27]基 于 精 英 反 向 学 习策略和混沌映射提出改进 GWO 算 法,并 用 于 求 解高维优化问题,与其他算法对比证明,改进 GWO 算法能有 效 平 衡 全 局 搜 索 和 局 部 开 发 能 力;刘 二 辉等[28]基 于 GWO 算法中的灰狼层级结构关系提出改进的精英保留策略,有效维持了种群的多样性,为了提高算法的局部开发能力提出邻域变异算子,进而提出改进 GA,并用于求解 AGV 路径规划问题,证明了改进 GA 求解路径规划的有效性。

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

1 AGV工作空间描述

为了方便建 模 与 分 析,将 AGV 工 作 空 间 分 为障碍物空间 和 自 由 空 间,由 于 本 文 着 重 研 究 AGV的路径规划,而 AGV 运动的形式是平面运动,因此定义:AGV 的 工 作 空 间 W 是 由R2 表 示 的 物 理 空间,W 的子集障碍物空间记为Oobs,AGV 与障碍物无碰撞 移 动 的 空 间 为 自 由 空 间 Cfree,则 Oobs∪Cfree=W。

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

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

2 基于改进灰狼优化算法的 AGV路径规划

2.1 AGV路径规划模型

为了方便描述,沿用 GA 用染色体表示 一 个 解的方法,将 AGV 从 出 发 点 到 目 的 地 的 一 条 完 整 路径记为一个染 色 体(如 图2),染色体上第一个基因和最后一个基因分别表示 AGV 运动的起始点和目标点坐标。在自由空间中随机产生n-2个点,满足{p1,p2,…,pn}∈Cfree,这n个点按顺序连接起来构成一个从起始点到目标点的路径。在优化求解过程中,每个 染 色 体 的 第 一 个 和 最 后 一 个 基 因 保 持 不变[28],图1中的黑色实线表示一条包含6个节点的路径。

恭喜,此资源为免费资源,请先
注意:本站资源多为网络收集,如涉及版权问题请及时与站长联系QQ:2766242327,我们会在第一时间内与您协商解决。如非特殊说明,本站所有资源解压密码均为:agvba.com。
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。