摘 要

随着生产物流自动化程度的提高和自动化立体化仓库的发展，AGV(Automated Guided Vehicle)作为物流系统和柔性制造系统中常用的运输工具，得到越来越多的应用。路径规划问题是AGV应用中的最基本也是最重要的问题，对路径规划问题的研究有重要的理论和实践意义。

本文首先介绍AGV路径规划的历史和现状，了解仓库布局的栅格法，设计符合课题的仓库布局，并结合布局与A*算法对AGV路径规划的流程进行分析；对单台AGV路径规划优化技术进行研究，在建立栅格布局的基础之上，对A* 算法进行改进和优化，以实现符合设计要求的单AGV 路径规划，并编程实现；然后针对多台AGVs的路径重叠问题，举例解决各个冲突问题，从而实现多台AGV的避障问题；最后编写了C语言代码，在Visual Studio2013里实现了AGV路径规划算法运行程序。

关键词：AGV；路径规划；A* 算法；Visual Studio2013

Abstract

With the improvement of automation of production logistics and the development of automated three-dimensional warehouses, AGV (Automated Guided Vehicle) has been used more and more as a transportation tool commonly used in logistics systems and flexible manufacturing systems. Path planning problem is the most basic and important issue in the application of AGV. The study of path planning has important theoretical and practical significance.

This article first introduces the history and current status of AGV path planning, understands the grid layout of the warehouse layout, analyzes the flow of AGV path planning, and then studies the single AGV path planning optimization technology based on the establishment of a grid layout. Improve and optimize the A* algorithm to achieve single AGV path planning. Then solve collision problems for multiple AGVs collision-free path planning problems to implement multiple AGV obstacle avoidance problems. Finally, write the C language code. In Visual Studio 2013, a single AGV path planning algorithm was implemented.

Keywords: AGV; path planning; A* algorithm; Visual Studio 2013

目 录

第一章：绪论 1

1.1选题背景 1

1.2 AGV在国内应用及发展趋势 1

1.3 AGVs路径规划研究发展方向 2

1.4路径规划算法概述 2

1.4.1 Dijkstra算法 3

1.4.2 A*算法 3

1.5本文主要研究内容和结构安排 4

1.6本章小结 4

第二章：模型建立与仓库布局设计 5

2.1单目标AGV路径规划模型 5

2.2仓库布局设计及栅格建模 5

2.2.1 布局设计一：单向通道无缓冲区 5

2.2.2 布局设计二：单向通道多缓冲区 6

2.2.3 布局设计三：单向通道合理设计缓冲区 7

2.2.4 布局设计的选取 7

2.3本章小结 8

第三章：基于A*算法的单AGV路径规划 9

3.1使用A*算法实现单AGV路径规划 9

3.1.1基础结构和变量的定义 9

3.1.2算法核心的实现 11

3.2软件实现 14

3.3本章小结 21

第四章：多AGV系统的路径规划 22

4.1多AGV系统的路径规划问题 22

4.1.1问题的由来 22

4.1.2冲突的类型 22

4.1.3解决方法 23

4.2举例实现AGV避障 24

4.2.1 定点冲突的解决 24

4.2.2 相向冲突的解决 27

4.3避障研究结果分析 31

4.4算法不足与改进方向 31

4.5本章小结 31

第五章：环境影响与经济性分析 32

第六章：总结与展望 33

6.1 总结 33

6.2 展望 33

致谢 35

参考文献 34

第一章：绪论

1.1选题背景

随着国内各行各业的迅猛发展，企业的需求和规模在不断扩大，生产所要求的效率不断提高，随之而来的就是，物流装备及其自动化己成为国内各行各业所关注的重点。众所周时，AGV是物流装备及其自动化中的重要的一员，其已经在各大企业中得到广泛的应用，未来会有越来越先进的AGV在市场中应用。

无人配送小车相对于人工配送来说，无人车配送通过规划最优路线来提高配送效率，在方便配送的同时，可以有效地节约人力物力。现如今是无人车配送的初始发展阶段，暂时只执行极速达、精准达等一些最后一公里的配送任务。但是随着社会的发展，大数据时代的进步，无人车配送会逐渐的加入到常规配送任务之中去。并且，不远的将来，大型的无人载货配送车辆也将研发出来，无人车的使用将逐步地解放繁重的人力配送劳动，也将在更多的领域，更广的区域，更高效的去服务人们。

无人配送车也是“智能物流”的一个典型代表。作为短途自主配送机器人，它需要实时动态地进行路径规划，通过各式传感器感知周围地路况信息，避开障碍物，完成配送任务，并且能够达到一定的性能指标，类似时间与距离最短，耗能最小等。路径规划是一个难题，很难得到一个最优的解，在对各个目标进行权衡考虑之后，往往最后得到的是一个协调的折中解。针对于路径规划问题的研究现在已经有了一定的成果，但至今也没有一个非常高效的解决方法和理论。

由此可见AGV（无人配送小车）及其路径规划问题是目前市场急需提高和改善的方向，改善后的AGV及其路径问题给市场带来的收益是非常可观的。

1.2AGV在国内应用及发展趋势

在近二十年的时间里，电子商务也越来越普及，网购逐渐的成为人们的日常生活方式。快递物流行业发生了翻天覆地的变化，但大步前进的同时也承担着巨大压力，传统的快递物流模式已经落后，很难满足现在的生产生活需求。比如说，亚马逊斥巨资收购Kiva systems公司的机器人项目，装备Kiva机器人在他们的智能化仓库当中用于拣货处理。对比之前传统的纯人工拣货，在装备Kiva机器人之后，亚马逊智能化仓库中拣货效率提升了两倍，给亚马逊带来了巨大的经济效益；今年3月份，菜鸟ET实验室联合天猫将无人机运用茶叶运输当中。以往利用人工运输茶叶的时候，由于狮驼峰地势的限制，往返一趟可能需要一个小时左右的时间，利用无人机则只需要2分钟。使得狮驼峰的茶叶能够提前两个小时上市，提高了经济效益。

在近十年的时间里，受益于互联网技术的进步，中国电商行业得以迅猛发展。网购成为人们日常的生活方式，从而使得快递行业有了翻天覆地的变化。从以前的邮政包裹，可能十几天才到达顾客手中，到如今的次日达，甚至于几个小时就能收到几百上千公里空运而来的包裹，这样子的变化是惊人的。在IT架构的发展下，在大数据时代的今天，中国的快递物流行业已是今非昔比。目前，京东的无人机已经在宿迁、西安等地实现了正常运营，单月可完成近千配送任务。京东的无人车配备有多个货舱，同时可以智能的躲避路途中的障碍物。无人车从无人配送站出发，根据既定的路线自动导航行驶，在进行路线规划时，它会优先选择主干道，并根据路况信息等待红绿灯，避让车辆行人。当它行驶到配送点时，会提前向取货人发送信息，收件标识就是取货码，收货人可以在无人车前输入取货码签名签收，完成收货。在完成配送任务后，无人车会返回至配送站。京东无人智慧配送站相对于人工配送来说，无人车配送通过规划最优路线来提高配送效率，在方便配送的同时，可以有效地节约人力物力。现如今是无人车配送的初始发展阶段，暂时只执行极速达、精准达等一些最后一公里的配送任务。但是随着社会的发展，大数据时代的进步，无人车配送会逐渐的加入到常规配送任务之中去。并且，不远的将来，大型的无人载货配送车辆也将研发出来，无人车的使用将逐步地解放繁重的人力配送劳动，也将在更多的领域，更广的区域，更高效的去服务人们。

1.3 AGVs路径规研究发展方向

路径规划的定义是，在一定的环境中具有障碍物的前提下，寻找到一条从起始点到目标点的最优路径。则AGV的路径规划则可以定义为根据给定的起点和终点规划出一条最优的行走路径。

在AGV系统里，路径规划技术是AGV实现技术突破的中的一个非常重要的方面，随着现代科技水平的快速发展，应用于AGV中的各项技术也在同速度的发展，因此就出现了各种的新技术。从研究成果看，有以下趋势：

首先需要不断改善AGV小车路径规划的性能。就AGV小车的的实时性而言，AGV属于自动化装备，智能地进行运行。如果小车没有足够的实时性，没办法及时的检测到障碍，这样就给我们的工作带来了很大的不便。还有安全性和可达性也是很重要的两点，如果AGV的安全性能不达标，即使能规划出最优的路径，也不会投入市场应用，可达性同样重要。智能化对于无人搬运小澈来说，引入智能化的算法，使AGV能够实现自组控制、即使纠正等功能，把这些应用于小车的路径规划中，将会使AGV更加符合实际应用并增加智能化。

就以目前市场上各企业的规模和需求来看，单单一台AGV无法满足这些，所以多台AGV联合系统的路经规划也将成为新的研究热点。

1.4路径规划算法概述

对于最优路径规划问题的研究，国内外的专家学者已经提出了许多种求解算法。包括A*算法、Dijkstra算法等。下面介绍几种主要的算法：

1.4.1 Dijkstra算法

Dijkstra算法是很常用的寻找路径的算法，其通俗说来，迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。

1.4.2 A*算法

A*算法是一种启发式算法可以选择是否不搜索某些节点，也就是给定障碍点，下面结合仓库栅格布局与A*算法进行开展。

A*(A-Star)算法，如公式(1-1)所示：

f(m)=g(m) h(m) (1-1)

其中f（m）表示的是从初始点到目标点估价函数，g（m）表示的是从初始点到节点m的实际距离，而h（m）就是A*算法的核心，也就是节点m到目标点的代价估计。估价函数h（m）的选取决定了能否找到路径的最优解（最短路径），当估算的距离h不大于节点m到目标点的实际距离时，搜索的点数会比较多，效率会比较的低，但能够得到最短路径；而当估算的距离h大于节点m到目标点的实际距离时，搜索的节点数相应的变少，效率会提上来，但不能保证得到最短路径。所以h（m）的值与实际值越接近，选取的h（m）也就越好，算法的效果也就越好。

A*算法实现的步骤如下：

1. 建立两个表sheet1和sheet2，sheet1用来放入已经生成而还没有考察的节点，sheet2用来放入已访问的节点；

（2）将起始点放入sheet1中，sheet2为空；

（3）搜索所有与sheet1中第一个点（此时为起始点）相连接的节点，在其中寻找目标点，如果发现目标点，则搜索完成，如果没有发现，则将所有与该点直接相连的节点放入sheet1中，将起始点放入sheet2中；

（4）将sheet1中的各节点按照估价函数f(n)的值进行排序，选择f(n)值最小的节点（sheet1中第一个点），将其作为下一个扩展结点，将该扩展节点放入sheet2中，重复步骤3、4，直至sheet1中出现目标点。

这样，sheet2中所存储的点就是由A*算法得出的最短路径。在分析完A*算法之后，使用C#算法结合仓库布局实现在给定起点和终点后寻找到最优路径。

A*算法是一种比较流行的启发式搜索方法，对于求解静态路由网络中最短路径有比较好的效果。本文改进A*算法，使得利用其求解能够得到符合要求的满意解。

1.5本文主要研究内容和结构安排

本文研究内容是单巷道立体仓库实现AGV小车的路径规划，主要是基于A*算法实现，采用理论分析为主，仿真运行为辅的方式研究AGV路径规划问题。主要的工作内容如下：

第一部分：介绍选题背景及研究意义，综述国内外基于AGV路径规划的研究现状和发展趋势，并结合课题做出阐述；

第二部分：参考相关文献并设计仓库布局；

第三部分：静态路径规划，即用A*算法实现单AGV路径规划；

第四部分：动态路径避障，即实现AGV解决路径冲突问题；

第五部分：编程并在软件中实现相关设计要求，能够在软件中实现AGV路径优化选择、不碰撞、不死锁。

本文章节安排如下：

第1章阐述课题背景，AGV研究使用现状及未来发展趋势，AGV路径规划研究的历史和现状进行分析，并介绍相关算法，最后明确论文的主要研究内容。

第2章结合本课题，确定研究的路径规划所采用的模型以及设计仓库布局。

第3章使用A*算法结合设计的地图实现单AGV路径规划，并在Visual Studio 2013中编程实现。

第4章针对单目标多AGV路径规划中容易发生交叉碰撞问题进行研究，尽量避免不碰撞、不死锁，并在Visual Studio2013中编程举例实现。

第5章对本课题的研究结果结合实际进行环保性和经济性上的分析。

第6章总结全文，并介绍了本文算法中存在的问题，进而引出下一步的研究目标。

1.6本章小结

本章介绍了本文的选题背景，从AGV小车的使用情况分析到AGV小车的发展趋势，并对AGV路径规划的现状和发展进行了分析，介绍了路径规划的相关算法，引出了可以的研究目的及内容，并对全文的开展进行了安排。

第二章：模型建立与仓库布局设计

2.1单目标AGV路径规划模型

在单目标AGV路径规划的运行模式中，在给定AGV的起点和终点的情况下，运输任务就是在模型里实现从起点到终点的路径规划，目前环境模型建立的方式主要有拓扑图法，栅格法，顶点图像法等。本文采用栅格法进行仓库的建模：

栅格法路径规划是地图建模的一种常用方法，采用栅格对机器人的工作空间进行划分，再利用优化算法对机器人路径优化，是采用智能算法求最优路径的一个经典问题。在栅格法中，我们将自动导引车的工作环境用尺寸相同的正方形划分。用坐标法是将整个工作环境当作坐标系，栅格长度与坐标标度一致，并且每个栅格与其坐标一一映射，更好地描述了仓库的空间环境，如下图2.1.

图2.1 用直角坐标系建立的栅格模型

2.2仓库布局设计及栅格建模

结合本课题是单巷道直达式立体化仓库的路径规划的设计要求，以及第二章提到的栅格布局方法，设计出合理、实用、结合课题的仓库布局以及栅格布局。

在给定仓库大小为10*15个单位的栅格内进行货架、巷道的摆放布局，通过分析其相同面积下的货架数量、巷道可同时运行的AGV数量、与课题的贴合程度以及合理性等选择出最优的仓库布局，结合布局进行下一步的路径规划设计。

2.2.1 布局设计一：单向通道无缓冲区

在10*15个单位栅格内设计单巷道通道布局，具体布局如下：第五行、第十行设计为横向单通道；第二列、第五列、第八列、第十一列、第十四列设计为纵向单通道，不设置缓冲区。其中，货架面积为80个栅格，巷道面积为70个栅格，具体布局如下图2.2。

图2.2 单向通道无缓冲区

2.2.2 布局设计二：单向通道多缓冲区

在10*15个单位栅格内设计单巷道通道布局 以及避障缓冲区，具体布局如下：第五行、第十行设计为横向单通道；第二列、第五列、第八列、第十一列、第十四列设计为纵向单通道，并设置多个缓冲区，缓冲区坐标位置分别为：（3，4）、（3,6）、（4、9）（6,4）、（6,6）、（7,9）、（9,4）、（9,6）、（10,9）、（12,4）、（12,6）、（13,9）。其中，货架面积为68个栅格，巷道面积为82个栅格，具体布局如下图2.3。

图2.3 单向通道多个缓冲区

2.2.3 布局设计三：单向通道合理设计缓冲区

在10*15个单位栅格内设计单巷道通道布局 以及避障缓冲区，具体布局如下：第五行、第十行设计为横向单通道；第二列、第五列、第八列、第十一列、第十四列设计为纵向单通道，并设置缓冲区，缓冲区坐标位置分别为：（4，4）、（4、9）、（7,4）、（7,9）、（9,4）、（9,9）、（（12,4）、（12,9）。其中，货架面积为72个栅格，巷道面积为78个栅格，具体布局如下图2.4。

图2.4 单向通道合理设计缓冲区

2.2.4 布局设计的选取

现对三种结合课题要求设计的仓库栅格布局进行优缺点分析：

方案一为单向通道无缓冲区式的设计，其优点为在实现单通道的基础上实现货架数量最多的摆放，仓库利用率高。其缺点为通道数量一定的情况下，每个通道只能一个方向行驶一辆AGV小车，取货效率低，且难以进行多AGV的冲突避障路径规划优化。

方案二为单向通道设置多个缓冲区式的设计，其优点缓冲区数量多，使得AGV小车在起点和终点确定的情况下可以选择多条路径，在多AGV的运行中可便于避免死锁和碰撞。其缺点为在相同面积的仓库中仓库利用率大大降低，影响仓库的使用率。

方案三为单向通道设置合理数量的缓冲区式的设计，其优点为设置了缓冲区，使得AGV小车在起点和终点确定的情况下可以选择多条路径，在实现多AGV的运行中有方案避免死锁和碰撞，且数量设置合理的情况下保障了货位的数量不会大量减少。其缺点为没有方案二更多地实现多路径和多缓冲区等待。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：