0 引言
自动导引小车（AutomatedGuidedVehide，AGV）作为智能物料运输的主要工具，已经在现代生产系统中广泛使用，AGV的采用带来诸如提高生产率、节约劳动成本、提高能源利用率和增强安全性等优点［1-2］。路径规划是AGV领域的关键性问题，其主要目标是为AGV在包含障碍物的空间中规划出一条从起点到目标点的路径，保证AGV在运动过程中不与障碍物碰撞且以尽可能快的速度到达目标点完成指定任务［3］。AGV的工作空间的环境地图可以是静态的也可以是动态的，静态环境的路径规划问题对算法性能要求比动态规划低，对于动态环境的路径规划问题，由于AGV工作空间中的障碍物实时运动，AGV要规划出可靠路径必须实时获取环境信息，并对规划好的路径进行快速修改［4］，本文着重研究AGV动态路径规划算法设计问题。
AGV路径规划问题可以建模成约束优化问题，已经有很多学者研究AGV路径规划算法的设计问题，路径规划算法分为传统算法和智能算法。传统算法主要有A＊算法［5］、D＊算法［6］、人工势场算法［7］、单元分解法、快速搜索随机树［8］（rapidly-ex-ploringrandomtree，RRT）＊等。路径规划是NP-hard型问题，随着环境地图的复杂性和动态性增加，传统求解算法有求解代价高、容易陷入局部极值和求解效率低等缺陷。为了克服这些缺陷，很多学者广泛研究各种智能优化算法在AGV路径规划领域的应用［9］。智能求解算法主要有遗传算法（GeneticAlgorithm，GA）［10］、花授粉算法（FlowerPollinationAlgorithm，FPA）［11］、灰狼优化算法（GreyWolfOptimization，GWO）［12］、帝国主义竞争算法（imperialistcompetitivealgorithm,ICA）［13］、教—学优化（Teaching–Learning-BasedOptimization，TLBO）算法［14］、粒子群优化（Particleswarmoptimization，PSO）算法［15］等。与传统求解算法相比，智能算法求解路径规划问题有更好的鲁棒性［16］，GA由于其良好的鲁棒性，已经广泛应用于诸多组合优化领域，如云制造服务组合优化［17］、旅行商问题、AGV与加工作业的集成调度问题［18］等。
已经有很多学者开展智能算法求解AGV动态路径规划问题的研究，如文献［19］基于细菌进化算法（BacterialEvolutionaryAlgorithm，BEA）和人工势场（ArtificialPotentialField，APF）算法提出细菌势场（BacterialPotentialField，BPF）算法，用于求解移动机器人静态和动态路径规划问题，该算法利用BEA优化引力和斥力系数，有效避免了传统APF算法容易陷入局部极值的缺点，仿真实验证明了BPF算法求解移动机器人静态和动态路径规划问题的有效性，但其缺点是环境地图以及障碍物运动形式简单。传统的GA求解优化问题时，变异算子是按一定的概率随机生成一个新的基因替换原来的基因，会导致生成更好解的可能性较低，文献［20］提出新的变异算子，具体做法是在要变异的基因邻域确定自由空间中的候选点集，然后从候选点集中随机选择点替换原来的基因进行变异，有助于提高变异生成优质解的可能性。基于改进变异算子提出改进GA并求解移动机器人动态路径规划问题，证明改进策略的有效性，但变异点选择没有启发信息，导致变异生成优质解的概率较低。文献［21］基于爬山算法提出新的变异算子，有效避免传统GA求解路径规划问题容易陷入局部极值的缺陷；改进可视图算法对环境地图进行建模，有效提高了规划出的路径的安全性；为了提高GA的寻优效率，遗传操作之后采用PSO算法更新种群，仿真实验验证了改进GA求解移动机器人动态路径规划问题的有效性；缺点是环境地图简单，障碍物运动形式简单且动态障碍物较少。文献［22］基于PSO提出改进重力搜索算法（Gravitationalsearchalgorithm，GSA），基于改进的GSA求解多移动机器人的路径规划问题，仿真实验和实际实验证明该算法的有效性，缺点是工作空间中的障碍物是静态的。文献［23］基于可视空间法提出改进的初始解生成算法，并提出新的变异算子以避免算法早熟，基于以上改进策略提出改进GA，应用改进GA求解移动机器人静态和动态规划问题，实验证明了改进GA求解静态和动态路径规划问题的有效性，缺点是动态环境中只有一个动态障碍物。文献［24］基于PSO算法和勒让德谱方法（Legendrepseudospectralmethod，LPM）提出粒子群勒让德谱混合算法（PSO－LPM）。PSO－LPM求解动态路径规划问题分为以下两个阶段：第一个阶段利用PSO算法全局搜索能力强的优点进行全局搜索，达到第一阶段的终止条件后进入利用LPM算法搜索的第二阶段，仿真实验证明了PSO－LPM算法求解动态路径规划问题的有效性。文献［25］提出了用于求解AGV静态路径规划问题的改进的GWO和GA，进而设计了路径光滑处理算法以及建立动态路径规划模型，并基于MATLAB GUI开发工具开发出AGV静态和动态路径规划仿真平台，应用改进的GA求解多种环境地图AGV动态路径规划问题证明改进算法的有效性。
基于以上文献，智能算法求解AGV动态路径规划时，变异算子缺少启发式规则，导致变异产生优质解的概率较低，进而导致算法早熟。为此本文提出路径微调算法、路径光滑处理算法以及对每一代的最优解进行退火操作这几种方法以改善上述缺点。路径微调算法考虑相连的路径片段组成的三角形，建立使路径缩短的启发式变异规则，有助于提高变异算子产生较好解的可能性。对每一次迭代种群中的最优解进行路径光滑处理，可有效减少规划出的路径的尖角，进而提高AGV的运行速度。对每一代的最优解进行退火操作，在最优解的邻域进行充分的搜索，有效提高解的质量。为了验证改进遗传算法求解AGV动态路径规划问题，本文设计了两种动态环境地图，并建立AGV沿规划的路径运动的模型，基于MATLABGUI开发工具开发出AGV动态路径规划仿真平台，通过仿真实验证明了本文提出的改进策略的有效性。
暂无评论内容