文献综述

1 研究背景及意义

随着我国人民经济水平的提高和网络的普及，人们的购买力发生了翻天覆地的变化，尤其加快了物流行业的发展。近几年来，我国物流行业发展迅猛，其贸易总额2017年已超过250万亿元，并且呈逐年上升趋势。统计数字表明，美国工业生产过程中装卸搬运费用占成本的20%~30%，德国物流企业物料搬运费用占营业额的1/3,日本的物流搬运费用占国民生产总值的10.73%,我国生产物流中装卸费用约占加工成本的15.5%。国内外一直都在寻求机械化和智能化的搬运技术和装备，以降低搬运成本和改善物料搬运的效率。随着工业化进程的加快，许多机械化作业可以由自动化设备完成，虽然在前期增加了投入，但就企业发展而言，在一定程度上提高了工作效率，保证了产品质量，减少了人力成本，从而总体降低了生产成本。“机器人换人”必将成为我国广大劳动力密集型企业解决人力不足、降低生产成本的重要方式^[1]。

自动导引小车（AGV：Automated Guided Vehicle）作为一种可移动机器人，集合了外部感知、动态决策、自动执行等智能技术，可快速、高效地实现物料装卸、搬运等作业任务，已经成为柔性制造系统和自动化立体仓库重要的搬运工具之一^[2]。

我国作为世界上最大的发展中国家，拥有着世界上最大的生产制造基地，AGV在烟草、医药、食品、重工等各个行业的智能化发展中占有着重要的地位。在整个自动化仓储物流中，AGV 运输成本占总成本比重较高，仓储任务的精准调度以及 AGV 良好的路径规划策略，对提高物流作业效率、降低运输成本有重要意义。AGV移动路径规划更是自动化搬运系统的重中之重，直接影响了搬运效率和成本，因此，AGV 路径规划问题的研究和应用是非常迫切和重要的。

2 国内外AGV移动路线规划问题的研究现状

一般的，路径规划主要是指规划一条路径，使得机器人可以无碰、安全、少代价的从起点运行至目的地。路径规划问题涉及到环境表达、规划算法、以及路径执行等几个方面。环境表达指如何将AGV 所处现场环境通过有效的数学建模来表达；规划算法主要指利用高效、智能的算法来指导AGV，从而进行有效的路径规划；路径执行是指相关底层控制器来控制 AGV 执行路径规划结果。

在国外，1989年，G.-C.Vosniakos 等^[3]通过仿真对比了同一柔性制造系统中三种不同的 AGV 路径布局，在同一种路径布局中，通过采用不同数量的 AGV、调节 AGV 的速度和调度策略来探究 AGV 系统效率的影响因素，研究结果表明不同的路径布局与其对应的调度策略联系起来，AGV 系统的效率才会整体提高。1990 年，A Takahashi、T Hongo 等^[4]提出一种基于人工势场法的规划方法规划多边形障碍物中凸多边形物体的平移运动，并阐述了一种基于矩量概念可扩展到多个旋转自由度的启发式算法作为车辆的局部避障算法的基础。1994 年，G Geng、GM Geary^[5]提出了一种利用再执行和预定义地图引导 AGV 的路径规划算法，该算法能够在候选路径被阻塞或在先前经验路径被阻塞的情况下生成替代路径。1995 年，JH Lee、BH Lee 等^[6]提出的一种交通控制方案，可将整个任务划分为路径生成和交通控制两个组成部分。路径发生器采用了 K-最短路径搜索算法生成离线路径，并计算每条路径的占用时间，得到交通控制器检查链路占用表和无冲突的最短时间路径。1998 年，S Rajotia、K Shanker 等^[7]找出了基于 Dijkstra 算法的最快路线，并评估了所提出的动态规划策略和静态规划策略的系统性能，结果表明论文所提出的路径规划策略有助于减少阻塞时间、提高系统的吞吐量。1999 年，KH Wu、CH Chen、JM Ko 等^[8]提出了一种基于模糊逻辑控制和势场法的自动导引车路径规划方法，该方法用势场法计算车辆与最接近障碍物之间的斥力和目标产生的吸引力，两种力的合力共同将 AGV 引导到目的地，当意外状况发生时，可通过一种模糊逻辑控制器改变 AGV 的运动方向，生成新的到达目的地的路径。2004 年，TJ Chen、Y Sun 等^[9]提出了一种用于 AGV 系统的最短路径规划和预防冲突动态路径规划方法，通过仿真实验得出此方法可在很大程度上解决多 AGV 系统的路径规划问题。2009 年，YH Cao、LX Wang^[10]提出了一种基于虚拟对象的路径规划方法，通过根据障碍物的位置在线改变AGV 的方向，使其沿最短无障碍路径行驶，仿真验证得出该方法能够有效地规划 AGV 的平滑路径。2011 年，X Tao^[11]提出了一种基于修正势场的路径规划方法，该方法计算量小、更容易满足实时性要求、数学描述相对简单，该方法提高了 AGV 在实际系统中的运行效率和安全性。2012 年，Z Lan^[12]为解决多 AGV 路径规划中死锁等问题，提出了一种动态路径规划算法，该算法主要采用基于连通性算法动态的调整 AGV 运行过程中空间和时间存在的问题，从而实现多 AGV 的运行时间最短为目标的全局路径规划方案。2014 年，L Szeidel^[13]提出在工业生产过程中建立 AGV 路线图，AGV 可通过在线计算路线，使 AGV 路径的覆盖度、连通性和冗余度得以最大化，从而提高 AGV系统的灵活性和运行效率。2016 年，M Lv、T Gao 等^[14]提出了一种 AGV 定位和路径规划方法，通过 RFID 对 AGV 进行实时定位，通过服务器进行远程监控,并提出了一种改进的 A*算法。通过仿真得出改进后的 A*算法比传统的 A*算法具有更高的效率，可大大降低系统计算时间。

在国内，1997 年，钟家桢、王韧等^[15]根据 AGV 工作环境已知、规范、易于描述的特点，提出了一种自主式的 AGV 的模式。该系统旨在提高 AGV独立的能力，使其运行的可靠性和适应性有所增强。2002 年，王会丽^[16]采用实时最小方差预测算法预测移动障碍物下一个时刻的位置信息，再利用静态环境下的 AGV 路径规划方法进行路径规划。张宏远^[17]利用 Petri 网对分布式AGV 进行建模分析，利用 Petri 网的分层递阶控制功能把各 AGV 描述成为具有一定决策能力的智能体。2004 年，吴晓雨^[18]建立了复杂网线道路中多台AGV 路径规划协调系统模型，采用基于优先权的交通规则法，解决系统中出现的几种类型冲突，为每台 AGV 找到一条与其他 AGV 不发生冲突的路径。2006 年，肖本贤、齐东流等^[19]提出了一种基于速度障碍、碰撞危险度概念的动态环境模型，并结合模糊神经网络给出 AGV 的路径规划流程，最后给出在存在静止和运动障碍物的动态环境中 AGV 路径规划仿真结果，验证了论文所提方法的有效性。2009 年，曹有辉、王良曦^[20]提出一种基于虚拟目标的人工势场路径规划方法，通过设计模糊逻辑控制器来预测合力为零的可能性。2014 年，孟娇[^21]提出了一种已知环境地图的情况下的 AGV 动态路径规划方法，并利用混沌序列的随机遍历特性对粒子群算法进行改进，建立离线路径规划表，规划从起始位置到目标位置的最短路径。2016 年，刘维民^[22]提出了一种复合调节冲突解决策略，解决基于速度调节等待时间过长和基于几何路径调节可能陷入一个无法收敛的路径再规划问题。2017 年，房殿军、周涛^[23]在 A-star 算法的基础上加入了时间因子的影响，对 AGV 路径规划算法进行设计，并根据栅格图下 AGV 碰撞的路径特点，系统地分析了 AGV群体的阻塞类型和避障策略，运用算例对智能 AGV 群体的路径规划、动态避障和路径再规划进行了详细分析。