论文部分内容阅读
摘 要：AGV作为提供辅料运送链的关键设备，在物流自动化系统中具有重要的地位，对提高物流作业效率起到了巨大的作用，因此也逐渐得到了广泛的应用。本文通过对AGV系统的研究了提出了适用于单AGV和多AGV系统的调度算法。
关键词：AGV；AGV调度算法
1.AGV系统地图建模
实际应用当中，AGV的工作路径随着不同工厂的环境条件和规划可能各不相同。
图1.1中AGV轨道模型，图中圆圈内的数字代表该位置的站点号，直有向线代表直线轨道，弯曲的有向线代表半圆轨道，线上的数值代表其长度或者半圆的半径。图1.1所示显然为一个有向赋权图，记为G（V，E），V为图中所有站点的集合，显然非空，E为任意站点Vi到另一站点Vj的边的集合。
2.AGV调度问题研究
2.1单个AGV路径规划算法
单个AGV的调度问题可以简化为AGV的路径规划问题，即等价为求最短路径问题。
Dijkstra算法是一种用于计算有向图中一个节点到其他所有节点最短路径的典型图形搜索算法。其时间复杂度O（V2+E）～O（VlgV+E）取决于是否采用最小优先级队列。
实现的具体方法，即当不用队列而用数组实现时为O（V2），用二叉最小堆来实现时为：
O（（V+E）lgV），用Fibonacci堆来实现时为：
O（VlgV+E）。采用Fibonacci堆使算法的运行时间性能相比于O（V2）虽然有一些提高，但是编程时由于其常数较大，多数时候会发现其实际运行速度并没有明显的提高，并没有多大的效率优势。算法具体步骤为：
1）分组初始化，集合S中只有源节点v0，T由除V外的剩余节点组成。根据图的信息初始化各个节点的邻接关系和权值。
2）从T中选取与v0有邻接关系且权值最小的顶点Tp，把Tp又加入到S中（v0到Tp的最短路径值即为其权值大小，最短路径为v0→Tp）。
3）以Tp为中间节点，考察T中与Tp邻接的节点。如果从源节点v0经过Tp到T中节点的距离比不经过Tp时距离短，则修改T中已比较过的顶点的路径值为经过Tp的路径。
4）判断T是否为空，或者源顶点到目的顶点的最短路径是否已经找到，若没有则
重新返回步骤2再次寻找。否则，推出循环，算法结束。
2.2 多个AGV路径规划算法
协调各个AGV之间能够无碰撞地高效完成其工厂里的作业任务，是多AGV调度系统的主要任务。相向冲突、站点冲突、拐角冲突、赶超冲突是多AGV运行过程中常见的几种基本冲突。多AGV的任务调度问题的典型的有效方法有以下几种：
（1）基于时间窗的AGV无碰撞路径规划
针对每段路径引入时间窗来指示该路段在某段时间是否已经被AGV占用，根据接受任务的优先级依次分配空闲的AGV，并利用算法选择最优路径，并产生各路径的时间窗。
（2）混合区域控制模型调度方法
通过对AGV的工作空间进行按不同的区域建模，AGV作业于不同区域内，且一个区域中最多只有一台AGV位于其中。
（3）线段网络控制调度算法通过把AGV小车的路线分为可进行控制的若干条路段，当小车将要或已经在一个路段上行驶时，AGV调度系统将这个路段及其终点分配给该AGV，当AGV行驶离开此路段的起始点一定距离后，系统又将该路段释放。
（4）两阶段控制调度算法
将AGV的调度控制系统分为离线路径表的生成和在线交通控制两个模块，其中离线路径表生成模块根据路径网路模型离线生成各结点间的所有路径，而在线交通控制模块根据下达的任务和工作中AGV的运行信息利用路径库中的路径表生成无冲突的最佳路径。
两阶段控制算法，利用已知信息先离线生成路径库，能很好的减少在线阶段的运行负担，提高系统实时性，且分阶段的控制方法使得实现和优化改进更简单。但是该算法生成的不是各结点的k条最优路径，当某个路段堵塞时，又要附加约束条件在线重新生成最优路径，使得效率反而更差。因此提出离线阶段对每个顶点生成k条最短路径集，以改进两阶段控制算法。
3 AGV调度算法算法分析与实现
（1）流程分析
假设AGV任务离线批量下发，本系统基于改进的两阶段控制算法的流程图设计如图3.1所示。正如图3.1所示，路径规划工作大部分静态工作如最优路径的生成等由调度系统离线阶段完成，而系统在线阶段主要负责动态的状态监控和资源的管理以及进行突发情况处理。突发情况下如果下位机可以采用一般的等待策略解决，则调度系统只负责路径资源时间窗的更新即可；若发现等待超时，即视为不能解决，则需以当前站点为起点重新为该任务进行路径规划。
在任务下发后，AGV开始执行任务，AGV执行任务过程中的避障策略算法如图图3.2所示。AGV根据调度系统对任务的路径规划，从起点开始不断检测障碍物和冲突以确定是否进行下一步。当遇到冲突时，首先自行进行等待处理，若调度系统发现等到时间过长而超时会对任务进行重新路径规划并发送任务的更新命令，AGV接收到该命令后会终止当前流程重新任务的执行。同时，AGV会定时不断的向监控调度系统更新AGV自身的状态信息，供调度系统决策使用。
结论
本文基于AGV運行环境的地图建模和系统简化，针对提出对单AGV系统采用经典的Dijkstra算法解决单AGV的路径的规划，最后完成了针对多AGV系统的算法程序上的流程图设计。
参考文献
[1] 朱大奇，颜明重.移动机器人路径规划技术研究概述[J].控制与决策.2010.7，25（7）：962-967.
关键词：AGV；AGV调度算法
1.AGV系统地图建模
实际应用当中，AGV的工作路径随着不同工厂的环境条件和规划可能各不相同。
图1.1中AGV轨道模型，图中圆圈内的数字代表该位置的站点号，直有向线代表直线轨道，弯曲的有向线代表半圆轨道，线上的数值代表其长度或者半圆的半径。图1.1所示显然为一个有向赋权图，记为G（V，E），V为图中所有站点的集合，显然非空，E为任意站点Vi到另一站点Vj的边的集合。
2.AGV调度问题研究
2.1单个AGV路径规划算法
单个AGV的调度问题可以简化为AGV的路径规划问题，即等价为求最短路径问题。
Dijkstra算法是一种用于计算有向图中一个节点到其他所有节点最短路径的典型图形搜索算法。其时间复杂度O（V2+E）～O（VlgV+E）取决于是否采用最小优先级队列。
实现的具体方法，即当不用队列而用数组实现时为O（V2），用二叉最小堆来实现时为：
O（（V+E）lgV），用Fibonacci堆来实现时为：
O（VlgV+E）。采用Fibonacci堆使算法的运行时间性能相比于O（V2）虽然有一些提高，但是编程时由于其常数较大，多数时候会发现其实际运行速度并没有明显的提高，并没有多大的效率优势。算法具体步骤为：
1）分组初始化，集合S中只有源节点v0，T由除V外的剩余节点组成。根据图的信息初始化各个节点的邻接关系和权值。
2）从T中选取与v0有邻接关系且权值最小的顶点Tp，把Tp又加入到S中（v0到Tp的最短路径值即为其权值大小，最短路径为v0→Tp）。
3）以Tp为中间节点，考察T中与Tp邻接的节点。如果从源节点v0经过Tp到T中节点的距离比不经过Tp时距离短，则修改T中已比较过的顶点的路径值为经过Tp的路径。
4）判断T是否为空，或者源顶点到目的顶点的最短路径是否已经找到，若没有则
重新返回步骤2再次寻找。否则，推出循环，算法结束。
2.2 多个AGV路径规划算法
协调各个AGV之间能够无碰撞地高效完成其工厂里的作业任务，是多AGV调度系统的主要任务。相向冲突、站点冲突、拐角冲突、赶超冲突是多AGV运行过程中常见的几种基本冲突。多AGV的任务调度问题的典型的有效方法有以下几种：
（1）基于时间窗的AGV无碰撞路径规划
针对每段路径引入时间窗来指示该路段在某段时间是否已经被AGV占用，根据接受任务的优先级依次分配空闲的AGV，并利用算法选择最优路径，并产生各路径的时间窗。
（2）混合区域控制模型调度方法
通过对AGV的工作空间进行按不同的区域建模，AGV作业于不同区域内，且一个区域中最多只有一台AGV位于其中。
（3）线段网络控制调度算法通过把AGV小车的路线分为可进行控制的若干条路段，当小车将要或已经在一个路段上行驶时，AGV调度系统将这个路段及其终点分配给该AGV，当AGV行驶离开此路段的起始点一定距离后，系统又将该路段释放。
（4）两阶段控制调度算法
将AGV的调度控制系统分为离线路径表的生成和在线交通控制两个模块，其中离线路径表生成模块根据路径网路模型离线生成各结点间的所有路径，而在线交通控制模块根据下达的任务和工作中AGV的运行信息利用路径库中的路径表生成无冲突的最佳路径。
两阶段控制算法，利用已知信息先离线生成路径库，能很好的减少在线阶段的运行负担，提高系统实时性，且分阶段的控制方法使得实现和优化改进更简单。但是该算法生成的不是各结点的k条最优路径，当某个路段堵塞时，又要附加约束条件在线重新生成最优路径，使得效率反而更差。因此提出离线阶段对每个顶点生成k条最短路径集，以改进两阶段控制算法。
3 AGV调度算法算法分析与实现
（1）流程分析
假设AGV任务离线批量下发，本系统基于改进的两阶段控制算法的流程图设计如图3.1所示。正如图3.1所示，路径规划工作大部分静态工作如最优路径的生成等由调度系统离线阶段完成，而系统在线阶段主要负责动态的状态监控和资源的管理以及进行突发情况处理。突发情况下如果下位机可以采用一般的等待策略解决，则调度系统只负责路径资源时间窗的更新即可；若发现等待超时，即视为不能解决，则需以当前站点为起点重新为该任务进行路径规划。
在任务下发后，AGV开始执行任务，AGV执行任务过程中的避障策略算法如图图3.2所示。AGV根据调度系统对任务的路径规划，从起点开始不断检测障碍物和冲突以确定是否进行下一步。当遇到冲突时，首先自行进行等待处理，若调度系统发现等到时间过长而超时会对任务进行重新路径规划并发送任务的更新命令，AGV接收到该命令后会终止当前流程重新任务的执行。同时，AGV会定时不断的向监控调度系统更新AGV自身的状态信息，供调度系统决策使用。
结论
本文基于AGV運行环境的地图建模和系统简化，针对提出对单AGV系统采用经典的Dijkstra算法解决单AGV的路径的规划，最后完成了针对多AGV系统的算法程序上的流程图设计。
参考文献
[1] 朱大奇，颜明重.移动机器人路径规划技术研究概述[J].控制与决策.2010.7，25（7）：962-967.