多AGV路径规划中冲突算法设计与仿真系统实现
发布时间：2021-02-08 04:23
自动引导小车AGV（Automated Guided Vehicle）执行任务时所规划的路径对于仓储仓库、物流分拣和无人自动化工厂等工业场景有着重大意义。近年来,随着物流运输行业的飞速发展和工业自动化的要求日益迫切,自动化仓储系统对物料运输的要求也越来越高,而AGV则是这类自动化仓储系统的重要组成部分。为了提高运输效率,人们开始研究如何在给定的时间内运输尽可能多的货物,这其中AGV彼此之间的冲突碰撞是耗时的关键因素。本文的目标是让场景中所有AGV在完成任务的前提下彼此之间产生的冲突最少。为了解决多AGV高动态与少冲突的问题,主要完成了以下几方面的工作:针对多AGV的静态场景算法研究,本文提出了增强冲突规避的改进启发式寻路算法。在对物流仓储场地布局特性进了调研后,基于栅格网络模型,将仓储场景地图抽象为无向图的形式,并针对静态场景的特点进行了AGV所执行的任务类型的详细描述;基于协作路径规划的思想,提出了改进的启发式搜索方案,使得在路径转弯数、重叠度以及AGV冲突发生数量上得到了显著的改进,大幅降低AGV完成任务所需要的各项指标。针对多AGV的动态场景算法研究,本文创新性地设计并实现了适用...
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
冲突等待次数对比
哈尔滨工业大学工程硕士学位论文图2-2场景中AGV数量不同而形成的不同程度的引导2.3实验与测试在实验的测试上，本文选取了A*算法、CA*以及理论层面不会产生冲突的单向寻路算法作为对比算法。所谓单向寻路算法，就是将整个场景建模为单向图，即车道为单向单车道形式。虽然在实际应用中几乎不会使用，但作为冲突规避最优的方案可以作为本文的冲突对比最优算法。由于上述算法并没有冲突解决方案，为了控制变量，上述算法均使用与改进算法相同的冲突解决策略。同时，场景中设置了执行取货任务和送货任务的AGV各10辆。图2-3冲突等待次数对比图2-4平均完工时间对比实验结果主要从所有AGV因冲突而产生的等待次数、平均完工时间、最大完工时间以及行走总步数这四个角度来进行分析，以此来考察改进算法在预防、降低冲突产生，以及降低任务完成时间上的效果。首先，对于AGV由于冲突而产生的等待次数而言，实验对比结果如图2-3所-16-
哈尔滨工业大学工程硕士学位论文示。从对比图不难发现，由于单向图法在理论层面上是不会产生冲突的，只有在十字路口处才有可能产生冲突，因此单向算法在冲突的规避上效果是最优的，改进算法在冲突的完全避免上是要略弱于这种最优策略。但是改进算法较A*算法与CA*算法而言，冲突的避免能力远远好于二者。其次，对所有AGV完成任务的平均完工时间而言，实验对比结果如图2-4所示。从对比图可以看到，改进算法在平均完工时间上要好于所有对比算法。尽管单向算法能够有效减少冲突，但是在AGV完工所用时间上，单向算法往往会让AGV绕大量的路程去避免冲突，因此在这一点上改进算法要远远好于单向算法。图2-5最大完工时间对比图2-6完成任务总步数对比接着，对于所有AGV完成任务的最大完工时间而言，实验对比结果如图2-5所示。所谓最大完工时间，指的是所有AGV完成任务时间的最大值，是衡量一系列任务完成速度的评价指标。从图中同样可以看出，改进算法在最大完工时间参数上较三个对比算法都要更优。最后，对于所有AGV完成任务所行走的总步数而言，实验对比结果如图2-6所示。在对比中可以看出，改进算法由于为了规避冲突，有时需要进行一定的绕路，因此在行走总步数上可能较A*算法与CA*算法而言稍高，但是较单向算法而言还是更低的。同时从图2-4与图2-5中可以了解到，在时间代价上改进算法还是较优的，从图2-3中也可以看出，改进算法在冲突的规避上较A*算法与CA*算法也相对更优，因此行走总步数上的轻微劣势并不会弱化本文改进算法的先进性。2.4本章小结本章对多AGV在静态预设场景中的面向冲突规划算法进行了设计改进与实-17-
【参考文献】：
期刊论文
[1]多AGV路径规划方法研究[J]. 泰应鹏,邢科新,林叶贵,张文安. 计算机科学. 2017(S2)
[2]中外快递企业分拣效果差距分析及启示——以UPS公司为例[J]. 柯晶琳,姜维军,王庆. 对外经贸实务. 2017(09)
[3]一种基于A*算法的动态多路径规划算法[J]. 刘斌,陈贤富,程政. 微型机与应用. 2016(04)
[4]复杂工况下视觉AGV导航标识带中心线的提取研究[J]. 佘宏杰,赵燕伟,冷龙龙. 计算机测量与控制. 2016(01)
[5]磁导航AGV控制系统的设计与实现[J]. 郑炳坤,赖乙宗,叶峰. 自动化与仪表. 2014(03)
[6]AGV自动调度系统及其与WMS的接口方法[J]. 王丹伟,张胜,吴蔚,孔祥震,于红波. 物流技术与应用. 2013(04)
[7]柔性生产系统配料区多自动导航小车调度优化[J]. 朱琳,范秀敏,何其昌. 计算机集成制造系统. 2012(06)
[8]基于混合区域控制模型的多AGV系统调度研究与实现[J]. 白帅福,唐敦兵,顾文斌,郑堃. 机械与电子. 2012(03)
[9]基于时间窗的自动导引车无碰撞路径规划[J]. 贺丽娜,楼佩煌,钱晓明,刘冉. 计算机集成制造系统. 2010(12)
[10]粒子群算法在生产物流调度中的应用研究[J]. 边培莹,李德信,包宝军,路燕. 计算机工程与应用. 2010(17)
硕士论文
[1]自动化仓储系统AGV调度研究与实现[D]. 焦福明.山东大学 2013
本文编号：3023360
【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校
【文章页数】：62 页
【学位级别】：硕士
【部分图文】：
冲突等待次数对比
哈尔滨工业大学工程硕士学位论文图2-2场景中AGV数量不同而形成的不同程度的引导2.3实验与测试在实验的测试上，本文选取了A*算法、CA*以及理论层面不会产生冲突的单向寻路算法作为对比算法。所谓单向寻路算法，就是将整个场景建模为单向图，即车道为单向单车道形式。虽然在实际应用中几乎不会使用，但作为冲突规避最优的方案可以作为本文的冲突对比最优算法。由于上述算法并没有冲突解决方案，为了控制变量，上述算法均使用与改进算法相同的冲突解决策略。同时，场景中设置了执行取货任务和送货任务的AGV各10辆。图2-3冲突等待次数对比图2-4平均完工时间对比实验结果主要从所有AGV因冲突而产生的等待次数、平均完工时间、最大完工时间以及行走总步数这四个角度来进行分析，以此来考察改进算法在预防、降低冲突产生，以及降低任务完成时间上的效果。首先，对于AGV由于冲突而产生的等待次数而言，实验对比结果如图2-3所-16-
哈尔滨工业大学工程硕士学位论文示。从对比图不难发现，由于单向图法在理论层面上是不会产生冲突的，只有在十字路口处才有可能产生冲突，因此单向算法在冲突的规避上效果是最优的，改进算法在冲突的完全避免上是要略弱于这种最优策略。但是改进算法较A*算法与CA*算法而言，冲突的避免能力远远好于二者。其次，对所有AGV完成任务的平均完工时间而言，实验对比结果如图2-4所示。从对比图可以看到，改进算法在平均完工时间上要好于所有对比算法。尽管单向算法能够有效减少冲突，但是在AGV完工所用时间上，单向算法往往会让AGV绕大量的路程去避免冲突，因此在这一点上改进算法要远远好于单向算法。图2-5最大完工时间对比图2-6完成任务总步数对比接着，对于所有AGV完成任务的最大完工时间而言，实验对比结果如图2-5所示。所谓最大完工时间，指的是所有AGV完成任务时间的最大值，是衡量一系列任务完成速度的评价指标。从图中同样可以看出，改进算法在最大完工时间参数上较三个对比算法都要更优。最后，对于所有AGV完成任务所行走的总步数而言，实验对比结果如图2-6所示。在对比中可以看出，改进算法由于为了规避冲突，有时需要进行一定的绕路，因此在行走总步数上可能较A*算法与CA*算法而言稍高，但是较单向算法而言还是更低的。同时从图2-4与图2-5中可以了解到，在时间代价上改进算法还是较优的，从图2-3中也可以看出，改进算法在冲突的规避上较A*算法与CA*算法也相对更优，因此行走总步数上的轻微劣势并不会弱化本文改进算法的先进性。2.4本章小结本章对多AGV在静态预设场景中的面向冲突规划算法进行了设计改进与实-17-
【参考文献】：
期刊论文
[1]多AGV路径规划方法研究[J]. 泰应鹏,邢科新,林叶贵,张文安. 计算机科学. 2017(S2)
[2]中外快递企业分拣效果差距分析及启示——以UPS公司为例[J]. 柯晶琳,姜维军,王庆. 对外经贸实务. 2017(09)
[3]一种基于A*算法的动态多路径规划算法[J]. 刘斌,陈贤富,程政. 微型机与应用. 2016(04)
[4]复杂工况下视觉AGV导航标识带中心线的提取研究[J]. 佘宏杰,赵燕伟,冷龙龙. 计算机测量与控制. 2016(01)
[5]磁导航AGV控制系统的设计与实现[J]. 郑炳坤,赖乙宗,叶峰. 自动化与仪表. 2014(03)
[6]AGV自动调度系统及其与WMS的接口方法[J]. 王丹伟,张胜,吴蔚,孔祥震,于红波. 物流技术与应用. 2013(04)
[7]柔性生产系统配料区多自动导航小车调度优化[J]. 朱琳,范秀敏,何其昌. 计算机集成制造系统. 2012(06)
[8]基于混合区域控制模型的多AGV系统调度研究与实现[J]. 白帅福,唐敦兵,顾文斌,郑堃. 机械与电子. 2012(03)
[9]基于时间窗的自动导引车无碰撞路径规划[J]. 贺丽娜,楼佩煌,钱晓明,刘冉. 计算机集成制造系统. 2010(12)
[10]粒子群算法在生产物流调度中的应用研究[J]. 边培莹,李德信,包宝军,路燕. 计算机工程与应用. 2010(17)
硕士论文
[1]自动化仓储系统AGV调度研究与实现[D]. 焦福明.山东大学 2013
本文编号：3023360
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3023360.html
