文档介绍：2017-1-23 1自动导引车路径规划作者: 崔晨群班级: 工物 121 学号: 201210222013 2017-1-23 2 一、自动导引车(Automated Guided Vehicle ,简称 AG V)路径规划问题的提出 AGV 的效率对仓储系统的运作效率有重要的影响,而 AGV 系统的效率很大程度上取决于对路径的导引,即 AGV 运送路径的优劣严重影响 AGV 的效率,间接制约着仓储系统的自动化程度及企业的生产效率。对于单 AGV 而言,路径规划相对比较简单, 即从出发点到目标点的最短路径。对于多 AGV 自动化仓储系统路径规划,要考虑到避免系统的冲突、碰撞,这就不得不涉及到路径规划。因此研究自动化仓储系统 AGV 路径规划问题就变得十分必要。 2017-1-23 3 二、固定路径导引 AGV 路径规划 AGV 路径规划 1)局部路径规划局部路径规划要解决的是根据具体环境模型找出一条连接两个不同目标点最佳路径。利用 Floyd 算法能较好地解决 AGV 局部路径规划。 2)全局路径规划全局路径规划负责根据局部路径规划的结果,为当前任务中所需运送的所有物品安排一个最优运送次序,即一条最佳的全局路径。 AGV 的全局路径规划可以转化为 TSP 问题,然后用模拟退火算法( SA 算法)通过模拟固体退火过程,采用 Metropolis 接受准则,可以在多项式时间取得问题的近似解。 2017-1-23 4 二、固定路径导引 AGV 路径规划 AGV 路径规划单台 AGV 不能从整体上提高自动化仓储效率的要求,因此多 AGV 路径规划问题成为研究的热点。多 AGV 的应用首先要解决的是避碰问题, 即在完成任务的前提下,避免与其他正在工作的 AGV 发生碰撞问题。 1 )而引起碰撞的主要原因有: (1)线路交叉; (2)多个 AGV 的线路冲突; (3) AGV 本身出现故障;( 4)运输线路超负荷运行。 2 )多 AGV 的碰撞类型有如图四种,根据碰撞类型提出两种主要解决方案: (1)延时等待:主要解决 b、c碰撞类型。(2)局部调整路径:主要解决第一类碰撞类型。 2017-1-23 5 二、固定路径导引 AGV 路径规划 3)多 AGV 路径规划所用方法: 基于 CPN 的 AGV 控制系统建模与求解方法: : AGV 等待任务 :AGV 向目标工位移动 : AGV 处于冲突检测中: AGV 处于冲突中 :AGV 处于执行解决冲突方案的状态:新任务:检测冲突:无冲突:发现冲突:解决冲突:执行解决方案:任务结束 CPN 较好的描述了 AGVS 系统地运行情况,为解决多 AGV 路径规划问题提供很好的分析工具和理论指导,有效地解决了多 AGV 小车路径规划问题。 1P 2P 3P 4P 5P 1t 2t 3t 4t 5t 6t 7t 2017-1-23 6 三、自由路径导引 AGV 路径规划在固定路径环境中, AGV 只能完成一些简单的任务。随着作业任务的复杂化,要求 AGV 能实现自由路径行走方式。下面将应用一种新的方法——模拟退火-人工势场法,并介绍基于该方法的路径规划系统的设计。人工势场法的基本思想是构造目标位姿引力场和周围障碍物斥力场共同作用的人工势场, 搜索势函数的下降方向来寻找无碰路径。人工势场法最主要的弊端是在到达目标位置前陷入局部最小点而无法达到目标位置。通过将模拟退火算法和人工势场法结合,利用模拟退火算法求解全局极小点。模拟退火-人公势场法的流程如右图 2017-1-23 7 三、自由路径导引 AGV 路径规划用 Visual C++ 为工具开发了基于 SA-APE 的 AGV 路径规划原型系统,该系统实现了单 AGV 无碰撞路径的自动生成,下图为复杂环境下,算法生成无碰撞路径的仿真实例。 2017-1-23 8 四、 AGV 路径规划实例 Dijkstra 最短路径确定法。下图中的节点 1~5是 AGV 运行路线上的岔口, 6~18 是货物装卸点,6是系统的入口,9、15、16是系统的出口,19是 AGV 停车处。在图(b)中,将 AGV 可能的运行方向用箭头进行了表示。 2017-1-23 9 四、 AGV 路径规划实例 (1) 因为节点 1~5是找出 6~18货物装卸点间最短距离的关键点,故先只考虑系统中的各岔口即节点 l~5间的最短路径。为此, 将相应箭头所表示的距离填人下面的距离矩阵。因节点 1、 3之间无直接连接的箭头,但两者之间可通过 16、18连在一起, 所以 C 1,3=C 1,16 +C 16,18 +C l8,3 =84 。C 3,4=∞表示所连两点间无直接联系,之间的联系要通过岔口节点。由此