论文部分内容阅读
摘 要：本文通过对AGV路径规划现状和路径规划算法的学习研究，在对AGV工作环境建模的基础上，采用Dijkstra算法对多AGV的路径进行规划并结合实际情况提出优化方法，把Dijkstra算法和时间窗方法相结合以解决多AGV避撞问题，从而实现多AGV路径规划，并提出路径优化策略。
关键词：智能引导小车;AGV;路径规划;算法设计
1 车间简介
HD公司现为一家从事煤炭行业专业机械设备生产和维修的的公司，公司建有机械零部件加工、钢铁铸造、机电设备制造、产品储存车间等生产车间，公司主要营业范围是机械、电器设备及配件的设计、制造、维修和销售。本文选择某产品储存车间为研究对象，综合利用Dijkstra算法和时间窗方法研究多AGV（智能引导小车）路径实现的问题，为了计算方便，省去了仓库无关部分，如图1为仓库平面示意图，仓库有12个货架。
2 多AGV路径模型设定
现假设该仓库加入多台AGV小车以实现自动化物流运输，在地图模型中加入AGV停车区域和铺设好的小车工作路径，用绿色阴影部分代表小车的停车区域，蓝色线段代表铺设的小车作业路径。根据所建立的路径信息，为计算方便，现在人为加入节点信息并为每一段路径入权值（权值大小依据长度值，横向相邻两节点权值为2，纵向相邻两节点权值为3）如图2所示。
3 时间窗方法
在利用时间窗方法解决多AGV路径规划问题前，首先做出如下假设：
（1）在实际作业中忽略了AGV在转弯速度变化，所有AGV运行的速度为固定值。
（2）图中路径任意两相邻节点可相互到达。
（3）AGV在装卸货物操作的时间为固定值。
（4）当发生冲突时，保证优先级Pi高的AGV小车任务的执行，调整优先级低的AGV小车任务。针对优先级高低的界定，本论文依据AGV小车接受任务的时间先后顺序划分任务优先级。
基于以上假设，因为AGV速度和装卸时间为固定值，因此AGV之间不存在赶超冲突。现在假设所有AGV均空闲并下达任务，任务1：AGV1去货架4-3执行卸货任务;任务2：AGV2去货架2-1执行卸货任务，现在利用基于Dijkstra算法和时间窗方法计算多AGV路径，算法步骤：
（1）按照发布的m（这里m=2）个任务的时间先后对任务进行优先级排序。根据任务接受时间先后，任务1优先级高于任务2。
（2）选择最高优先级的任务（任务1），并使用Dijkstra算法规划出最短路径，安排AGV1去完成任务并计算出该任务中小车占用的所有路径的进入时间tin 和驶出时间tout，初始化各个路段的时间窗。
（3）选择次优任务（任务2），再次使用Dijkstra算法进行路径规划并安排AGV2区完成任务并计算出该AGV小车所有占用的所有路径的进入时间tin和驶出时间tout，更新各个路段的时间窗表。
（4）按照更新后获得的时间窗表，检验是不是存在碰撞。若不存在碰撞，小车工作路径规划成功;若存在碰撞情况，则该碰撞发生的路段不可用，并根据优先级再次运用Dijkstra算法规划优先级低的任务路径，直到问题得到解决。若路径规划失败，找不到完成任务的路径，则停止对該任务的规划，等待新的任务命令和新的优先级后再执行。
综上即可完成多AGV路径规划，对于任务数量较多情况的算法只需重复上述步骤，但是所得到的时间窗更复杂，可能需要多次使用Dijkstra算法。根据Dijkstra算法得到任务1最短路径为3→7→6→12→18→19，如图4-4红色线段所示，任务2的最短路径为2→6→7→8→9如图3黄色线段所示。
根据图3可知，使用Dijkstra算法对两小车工作路径规划后在路段为6-7出现了两AGV共同占用的现象，该路段可能导致两AGV发生碰撞，画出两条路径的时间窗，其中黄色部分表示任务2时间窗，红色部分表示任务1时间窗，如图4所示。图4中，路段6-7之间两任务时间窗出现了重叠，根据任务1的优先级，调整任务2的路径，根据Dijkstra算法搜索无碰撞次优路径可得任务2路径为2→3→7→8→9，如图5所示。
画出两条路径的时间窗，如图6，可以看到更新后的时间窗不存在堆叠情况，路径优化后得到了无碰撞的路径，路径规划成功。
4 总结
本文运用Dijkstra算法和时间窗方法相结合实现了对多AGV路径的规划，通国对路径规划算法的学习和研究，并结合公司车间的实际情况，运用Dijkstra算法完成了多AGV路径的规划，并提出路径优化策略。
参考文献
[1] 金亚萍.自动导引车关键技术现状及发展趋势[J]. 物流技术与应用，2015，20（11）：96-98.
[2] 石朝侠，洪炳镕，周彤，等.大规模环境下的拓扑地图创建与导航[J].机器人，2007，29（5）：433-438.
[3] 樊征，曹其新，杨扬，等.面向移动机器人的拓扑地图自动生成[J]. 华中科技大学学报：自然科学版，2008（S1）：172-175.
作者简介：曾庆，男（1972.1—），汉族，四川攀枝花人，硕士，讲师，研究方向：智能制造。
潘启宏，男（1995.5—），汉族，四川攀枝花人，本科在读，研究方向：智能制造。
关键词：智能引导小车;AGV;路径规划;算法设计
1 车间简介
HD公司现为一家从事煤炭行业专业机械设备生产和维修的的公司，公司建有机械零部件加工、钢铁铸造、机电设备制造、产品储存车间等生产车间，公司主要营业范围是机械、电器设备及配件的设计、制造、维修和销售。本文选择某产品储存车间为研究对象，综合利用Dijkstra算法和时间窗方法研究多AGV（智能引导小车）路径实现的问题，为了计算方便，省去了仓库无关部分，如图1为仓库平面示意图，仓库有12个货架。
2 多AGV路径模型设定
现假设该仓库加入多台AGV小车以实现自动化物流运输，在地图模型中加入AGV停车区域和铺设好的小车工作路径，用绿色阴影部分代表小车的停车区域，蓝色线段代表铺设的小车作业路径。根据所建立的路径信息，为计算方便，现在人为加入节点信息并为每一段路径入权值（权值大小依据长度值，横向相邻两节点权值为2，纵向相邻两节点权值为3）如图2所示。
3 时间窗方法
在利用时间窗方法解决多AGV路径规划问题前，首先做出如下假设：
（1）在实际作业中忽略了AGV在转弯速度变化，所有AGV运行的速度为固定值。
（2）图中路径任意两相邻节点可相互到达。
（3）AGV在装卸货物操作的时间为固定值。
（4）当发生冲突时，保证优先级Pi高的AGV小车任务的执行，调整优先级低的AGV小车任务。针对优先级高低的界定，本论文依据AGV小车接受任务的时间先后顺序划分任务优先级。
基于以上假设，因为AGV速度和装卸时间为固定值，因此AGV之间不存在赶超冲突。现在假设所有AGV均空闲并下达任务，任务1：AGV1去货架4-3执行卸货任务;任务2：AGV2去货架2-1执行卸货任务，现在利用基于Dijkstra算法和时间窗方法计算多AGV路径，算法步骤：
（1）按照发布的m（这里m=2）个任务的时间先后对任务进行优先级排序。根据任务接受时间先后，任务1优先级高于任务2。
（2）选择最高优先级的任务（任务1），并使用Dijkstra算法规划出最短路径，安排AGV1去完成任务并计算出该任务中小车占用的所有路径的进入时间tin 和驶出时间tout，初始化各个路段的时间窗。
（3）选择次优任务（任务2），再次使用Dijkstra算法进行路径规划并安排AGV2区完成任务并计算出该AGV小车所有占用的所有路径的进入时间tin和驶出时间tout，更新各个路段的时间窗表。
（4）按照更新后获得的时间窗表，检验是不是存在碰撞。若不存在碰撞，小车工作路径规划成功;若存在碰撞情况，则该碰撞发生的路段不可用，并根据优先级再次运用Dijkstra算法规划优先级低的任务路径，直到问题得到解决。若路径规划失败，找不到完成任务的路径，则停止对該任务的规划，等待新的任务命令和新的优先级后再执行。
综上即可完成多AGV路径规划，对于任务数量较多情况的算法只需重复上述步骤，但是所得到的时间窗更复杂，可能需要多次使用Dijkstra算法。根据Dijkstra算法得到任务1最短路径为3→7→6→12→18→19，如图4-4红色线段所示，任务2的最短路径为2→6→7→8→9如图3黄色线段所示。
根据图3可知，使用Dijkstra算法对两小车工作路径规划后在路段为6-7出现了两AGV共同占用的现象，该路段可能导致两AGV发生碰撞，画出两条路径的时间窗，其中黄色部分表示任务2时间窗，红色部分表示任务1时间窗，如图4所示。图4中，路段6-7之间两任务时间窗出现了重叠，根据任务1的优先级，调整任务2的路径，根据Dijkstra算法搜索无碰撞次优路径可得任务2路径为2→3→7→8→9，如图5所示。
画出两条路径的时间窗，如图6，可以看到更新后的时间窗不存在堆叠情况，路径优化后得到了无碰撞的路径，路径规划成功。
4 总结
本文运用Dijkstra算法和时间窗方法相结合实现了对多AGV路径的规划，通国对路径规划算法的学习和研究，并结合公司车间的实际情况，运用Dijkstra算法完成了多AGV路径的规划，并提出路径优化策略。
参考文献
[1] 金亚萍.自动导引车关键技术现状及发展趋势[J]. 物流技术与应用，2015，20（11）：96-98.
[2] 石朝侠，洪炳镕，周彤，等.大规模环境下的拓扑地图创建与导航[J].机器人，2007，29（5）：433-438.
[3] 樊征，曹其新，杨扬，等.面向移动机器人的拓扑地图自动生成[J]. 华中科技大学学报：自然科学版，2008（S1）：172-175.
作者简介：曾庆，男（1972.1—），汉族，四川攀枝花人，硕士，讲师，研究方向：智能制造。
潘启宏，男（1995.5—），汉族，四川攀枝花人，本科在读，研究方向：智能制造。