下载掌阅APP，畅读海量书库
立即打开
AGV路径规划是指机器人以某一个或多个衡量指标（如运行成本、耗时、路径长度、路径曲线光滑度）在工作空间内找到一条从起点到终点的可行路径，且该路径必须满足避障原则。因此，AGV路径规划从本质上讲是一种求解多约束条件下的最优解问题 [29] 。
路径规划的分类可从以下方面考虑。
（1）根据目标点数目可将路径规划分为单目标路径规划和多目标路径规划。单目标路径规划也称两点（起点和终点）间路径规划，该规划是比较简单的；多目标路径规划是指规划出的路径需要遍历多个目标点，与旅行商问题（Traveling Salesman Problem，TSP）求解的基本思想类似，因此可将其视为TSP来求解 [30] 。
（2）根据AGV对环境、障碍物信息的感知程度可将路径规划分为全局路径规划和局部路径规划。前者是指AGV对环境信息和障碍物信息完全已知，因此该规划过程是静态的，并且规划出的路径通常是全局最优的；后者是指AGV对部分环境信息未知，需要激光、视觉等传感器实时采集并更新环境信息，在此基础上对其下一步运行方向进行决策，因此该规划过程是连续且动态的，具有很强的实时性 [31] 和鲁棒性。由于局部路径规划无法对全局信息进行处理，因此在利用局部路径规划规划路径时，无法保证规划出的路径是全局最优的。目前，路径规划的通常做法是先利用全局路径规划寻找满足全局最优的运行路径，然后实时监测障碍物位置，并利用局部路径规划实现避障功能。
（3）根据AGV的数量可将路径规划分为单AGV路径规划和多AGV路径规划。单AGV路径规划只需要考虑AGV与障碍物的碰撞关系即可，所以考虑的因素较少，计算量也比较简单；多AGV路径规划不仅要考虑每台AGV与障碍物的碰撞关系，还要考虑各台AGV之间的冲突，更加注重各台AGV之间的信息交互与协同配合，这极大地提高了路径规划问题的难度和复杂度。
路径规划问题的解决需要融合机械、计算机、自动化等多学科、多领域的知识。早在20世纪70年代，人们就开始研究机器人路径规划问题并得到初步解决。路径规划问题的求解离不开优秀算法的支撑，改进的旧算法和新兴算法的出现极大地促进了路径规划技术的发展。按照时间顺序来看，国内外对于求解路径规划问题使用算法的研究可分为三个阶段，即传统算法、智能优化算法和新一代人工智能算法。传统算法主要包括广度优先搜索（Breadth-First Search，BFS）算法、深度优先搜索（Depth-First Search，DFS）算法、A*算法、快速搜索随机树（Rapidly-exploring Random Tree，RRT）算法、人工势场法等。Zuo等学者 [32] 使用DFS算法找出了分区的覆盖顺序，进而提出了一种基于分区的全覆盖路径规划算法，减少了机器人在狭窄区域的转弯次数。程传奇等学者 [33] 优化了A*算法的评价函数，并使用关键点选择策略来精炼路径点，最终与动态窗口法融合，可实现实时动态避障路径规划，且路径曲线更光滑。Zhang等学者 [34] 首先使用A*算法规划出了AGV的初始路径，然后使用关键点选择策略消除冗余节点得到了二次规划的结果，同时计算出了AGV在拐点处的旋转方向和旋转角度，所得二次规划结果的路径长度更短，转弯过程也更优。刘成菊等学者 [35] 使用改进RRT算法设计了一种适用于足球机器人动态避障的路径规划控制器，引入了引力分量，使机器人在生成随机树时变概率地向目标点进行搜索，以提高搜索终点的效率；使用平滑路径处理方式消除冗余节点，从而缩短了路径长度并解决了路径震荡问题，基于该算法设计的控制器应用在NAO机器人上并在RoboCup比赛中取得了佳绩。Yang等学者 [36] 提出了一种改进人工势场法，解决了传统人工势场法在用于路径规划时会出现的障碍物附近目标不可达问题和易陷入局部最优问题，即优化了引力势场和斥力势场，并采取势场填充策略和引入回归搜索来优化路径，在仿真环境下使用提出的改进算法得到一条可避开所有障碍物的较优路径。
在使用传统算法解决路径规划问题时较显著的特征是几乎要在整个搜索空间进行计算和搜索，这无疑会导致计算量十分庞大，进而耗时严重，甚至出现组合爆炸现象，无法找到有效解。另外，传统算法在面对高维复杂环境时也露出了自身的短板。鉴于路径规划问题本质上是一种求最优解问题，因此国内外研究者通常使用智能优化算法来解决该问题。该算法表现出优于传统算法的性能和效果。智能优化算法是一类仿照生物行为的算法的总称，常见的智能优化算法有GA [37] 、蚁群优化（Ant Colony Optimization，ACO）算法 [38] 、粒子群（Particle Swarm Optimization，PSO）算法 [39] 、模拟退火算法（Simulated Annea-ling，SA） [40] 等。Han等学者 [41] 提出了一种可用于多AGV路径规划问题的改进GA，使用三交换交叉启发式算子，产生了更多的优化后代，可以得到更多的局部搜索信息，用改进GA搜索的路径既能保证所有AGV路径长度总和最短，又能保证每台AGV路径长度最短。刘二辉等学者 [42] 使用灰狼优化（Grey Wolf Optimization，GWO）算法改进GA中选择操作的精英选择策略，维持了种群的多样性特征，保证了算法的全局搜索能力；将标准交叉变异操作改进为基于染色体信息熵的自适应交叉变异操作；对染色体中位于障碍物上的基因段进行邻域变异操作，以使规划出的路径避开障碍物。Cheng等学者 [43] 提出了一种改进蚁群算法，用“蚂蚁边缘化”的思想设定蚁群的初始位置，定义了一种新的全局信息素分布规则，使信息素挥发系数自适应变化，并在信息素更新策略中引入模拟退火算法的思想，他们分别对基于无障碍物的TSP和有障碍物的单目标路径规划问题进行了仿真实验，证明了改进蚁群优化算法没有搜索时间长、停滞、收敛速度慢的缺陷。白建龙等学者 [44] 为解决蚁群优化算法易陷入局部最优的问题，改进了信息素的更新方法，将负反馈机制加入蚁群优化算法中，与传统蚁群优化算法中蚂蚁仅在最优的路径上释放正反馈信息素不同，改进算法中蚂蚁也能在较差的路径上释放负反馈信息素，以使后续的蚂蚁避免走较差的路径而更多地走入全新的路径中，从而提高算法的全局搜索能力。杨超杰等学者 [45] 提出了改进粒子群算法，将路径规划的应用场景从二维提升到三维，其创新性在于适应度函数中加入了路径与障碍物间距和路径光滑度指标，采用的自适应惯性权重因子和加速系数调整策略可以提高算法的全局搜索能力，为使算法跳出局部最优，其改进了逻辑混沌映射以实现全局最优粒子的混沌优化。Zhang等学者 [46] 提出了一种基于差分进化的混合多目标基本粒子群算法，优化的目标包含路径的长度、平滑性和安全性，所提出的算法通过改进的差分进化变异策略，将被障碍物阻塞的非可行路径与可行路径相结合，生成最终的可行路径。此外，他们根据路径碰撞度的定义，提出了一种新的具有碰撞约束的帕累托控制算法来选择粒子个体的最佳位置。Hayat等学者 [47] 在仿真环境中设置了圆形障碍物，并使用模拟退火算法来获得机器人在圆形障碍物之间的无碰撞最优路径，为验证算法的有效性，他们将该算法应用于不同工作区域和不同障碍物的环境中，最终得到了十分理想的结果。
智能优化算法的使用已经为路径规划技术带来了重大突破，它能更快、更好地得到一条优化路径，且具有较高的实时性。但传统算法和绝大多数智能优化算法的使用都基于环境信息已知的情况。当机器人面临复杂多变的环境时，上述算法几乎不再适用。目前，人工智能技术正处于快速发展阶段，作为新一代人工智能技术代表的深度学习和强化学习（Reinforcement Learning，RL），其与路径规划之间的联系越来越紧密 [48，49] 。人工智能技术为复杂多变和环境未知情况下的路径规划问题提供了新的求解方向。文献[50]使用激光雷达采集到的数据确定目标点和障碍物的位置信息，并将上述信息用于细化机器人的当前状态，在设计动作集时，张福海等学者考虑了机器人运行的安全性，在计算机器人的回报值时使用了一个连续且分段的函数，因此机器人在做出动作时能够很快得到一个对应的回报，有利于提高算法的训练效率。植入深度学习算法的机器人在实际场景中能够有效地导航到终点。文献[51]将NN算法与 Q -Learning算法相融合，将一种NN规划器用于拟合 Q 表数值，以便提高算法的收敛速度，使机器人能够成功地在放置了静态障碍物和动态障碍物的复杂环境中以理想速度进行导航，此算法中也考虑了避障问题的几何因素，从而确保了生成路径的安全性。王珂等学者 [52] 使用卷积神经网络（Convolutional Neural Network，CNN）算法和异步优势演员评论家（Asynchronous Advantage Actor Critic，A3C）算法实现了机器人动态路径规划。该算法的输入是由RGB-D相机采集的深度图像信息，输出是控制机器人移动状态的运动速度和转向角，使用A3C算法训练能确保输出状态信息的连续性。他们在制定奖惩规则时充分考虑了深度图像的最小值因素，并且为了进一步缩短训练时间，他们在机器人的运动学约束中使用了比例控制算法调整其移动速度，在使用Gazebo建立的仿真环境中进行训练来验证算法的效果。Kamoshida等学者 [53] 提出了一种基于深度强化学习的AGV拣选系统路径规划算法，该算法使用原始的高维地图信息作为输入，以离线更新的方式通过与模拟系统的交互来收集环境信息，与使用的在线样本相比具有更快的收敛速度且更加可靠，所使用的深度神经网络中包含4个隐含层，每层中含有批量归一化函数、整流激活函数和Dropout函数。
上述文献虽然针对不同场景提出了多AGV（或机器人）的路径规划算法，但大多只对单AGV路径规划进行了研究，而在少数学者研究的多AGV物料运输系统中，AGV的数量也仅有3～6台，这相较于工厂实际需求无疑是偏少的，故在多AGV物料运输系统中路径规划的研究需要设置在一个比较复杂的环境中，且包含较多的AGV。此外，多数对于路径规划技术应用实现的研究仅限于理论和仿真阶段，并未真正落地应用。因此，为使AGV更好地服务智能工厂，还需要对路径规划技术的应用实现进行进一步研究。
路径规划技术虽然能使AGV自主规划其最优可行路径，但在多AGV物料运输系统中，如果各AGV单纯地按既定路径运动，而不考虑其他AGV的实时位置，那么很容易出现路径冲突现象，如果AGV不具备感应避障功能，可能会出现AGV碰撞的异常状况，而且AGV自身的故障也会对其他AGV或整个系统的正常运作造成一定程度的影响。为避免上述问题的出现，学者们将调度技术引入多AGV物料运输系统中，部分AGV的实际运行路径需要根据实际调度结果进行实时变更，故路径规划与协同调度之间的联系十分紧密。随着新兴制造模式和定制化生产模式的出现，AGV调度也更多地与作业车间调度结合，成为共融调度，从而使产品的最大完成时间和运输制造成本最优化。由此可见，多AGV协同调度不仅关系到多AGV物料运输系统的有效运作，也关系到车间的制造和生产进度。
多AGV协同调度是指对AGV调度任务进行分配和调整，目的是使多AGV物料运输系统处于高效的运行状态，使资源得以优化配置。根据任务信息的完整与否，多AGV协同调度可分为静态调度和动态调度 [54] 。前者是指在所有AGV的路径都已经确定好的基础上对其进行任务派发，离线调度的实现过程较为简单，但是缺乏灵活性，无法处理突发事件；后者是指在AGV的运行路径上可能会有其他AGV或AGV本身出现故障，因而需要实时调整，在线调度必然会复杂很多，需要的计算能力也应相对提高。多AGV协同调度的目标通常包括最大完工时间最短、总路径长度最短、等待时间最短等，因此多AGV协同调度可以根据优化目标的数目分为单目标调度与多目标调度，但不论如何，多AGV协同调度问题都是一个NP困难问题 [55] ，利用传统算法未必能解决该问题，而利用智能优化算法能解决该问题。虽然多AGV协同调度是多AGV物料运输系统应当具备的一项基本功能，但其仍是十分复杂的。因此，不管在国内还是国外，与多AGV物料运输系统相关的调度技术成了研究的热点和难点之一。
在国内，徐立云等学者 [56] 基于改进文化基因算法实现了多品种柔性生产中AGV的调度任务优化，他们建立的数学模型的约束条件包括AGV搬运能力、机床加工能力和产品加工时间等，优化目标为所有AGV任务完成时间，故个体编码的每个基因位上均有3个数字，分别表示AGV、机床和工件的编号。他们使用了爬山算法以提高算法局部搜索能力，针对1～4台AGV和24种加工任务进行结果分析，并讨论了AGV数量和加工任务方案对调度任务目标函数值的影响。刘二辉等学者 [57] 将改进花授粉算法用于AGV与机器的共融调度，算法中的切换概率会随着迭代次数的变化而变化，并且该算法中引入了优先保护交叉策略和启发式变异算子，将 m 维的 n 个数据点进行中心化处理，根据所得矩阵的最小特征值及其对应的特征向量确定个体变异的方向，从而提高算法的全局搜索能力和局部搜索能力，此外还采用矩阵的形式对染色体的相似度进行计算，若2条染色体过于相似，则进行初始解重构，以提高初始种群的整体分布水平，但不足之处在于，文献中尚未体现对AGV碰撞和避障问题的研究。贺长征等学者 [58] 着重研究了多AGV与机器的集成调度问题，以最小化最大完工时间为优化目标构建了数学模型，将约束条件转换成网络图使工件、机器与AGV之间的约束关系能更加清晰地表示出来，面对路径冲突问题选择调节AGV速度/路径来避免发生碰撞，进而使用改进GA实现了柔性作业的集成调度，改进GA中混合了时间窗法和迪杰斯特拉算法，但在算法模型中并未考虑AGV的故障问题。在国外，Tavakoli等学者 [59] 提出了一种生产过程调度和AGV分配的数学模型。该模型考虑了任意工艺的生产时间、设置时间、装卸行程时间、停车位时间、每个工位的产品卸货时间和装载量。他们通过数值算例对模型进行探讨，并利用GAMS软件进行求解。Fontes等学者 [60] 提出了一种用于求解柔性制造环境下的联合生产运输调度问题的综合求解算法，利用2组链式决策将联合生产运输调度问题转化为一种新的混合整数线性规划问题，2组链式决策分别用于机器和AGV，并且通过机器操作和调度任务的完成时间约束来相互连接。Arani等学者 [61] 考虑了单元形成问题和小区域调度问题，建立了单元化制造系统的综合数学模型，其目标是使最大完工时间与零件小区域内移动距离之和最小，他们将该综合数学模型转化为线性模型求解，并在GAMS.9软件上进行了计算实验，验证了模型的有效性和准确性。