2015年IEEE会议开始
国际信息和自动会议
中国丽江，2015年8月
基于改进的A-Star算法的自动导航车辆路径规划
王春宝，王林，秦剑
第一附属医院
中山大学
广州市新港西路135号510275.P.R.中国
wangchb6@mail.sysu.edu.cn
夏苏，李伟光，吕志江，李孟杰
机械和汽车工程学院
华南理工大学
广州市天河区吴山路188号China.510641
吴正志，段立红，钟秋李美群
和西翠欧
深圳老年医学研究所
深圳市笋岗西路3002号邮编：518037
王玉龙，龙建军，黄美玲
李英红，王秋红
深圳市第二人民医院
深圳市笋岗西路3002号，邮编：518037
摘要:随着自动化物流系统，柔性制造系统（FMS）和无人化自动化工厂的发展，自动导引车（AGV）的应用逐渐变得越来越重要，以提高企业的生产效率和物流自动化程度。 AGV系统的开发在降低劳动力成本，改善工作条件，统一信息流和物流方面发挥着重要作用。路径规划一直是AGV控制系统中的一个关键问题。本文解决了多AGV中最短时间路径规划和碰撞两个关键问题。提出了一种改进的A-Star算法，该算法引入了转弯因素，采用基于改进A *算法的边缘去除算法求解k最短路径问题。同时，提出了一种基于A *算法的动态路径规划方法，该方法有效搜索最短路径并避免碰撞。最后通过仿真和实验验证了该算法的可行性。
关键词：AGV;路径规划; A *算法;改进的A *算法一
- 引言
随着工业的发展，由AGV组成的物流系统越来越受欢迎。但是，应用中仍然存在一些亟待解决的问题。作为最严重的问题之一，AGV路径规划不同于一般的车辆路径问题。它适用于不同的应用程序和不同的机智。更重要的是，约束条件，最优解和策略与一般车辆路线不同。路径规划是指根据给定的起点和终点，在一定的环境约束条件下，以最短路径，最短时间，最小成本等因素为参照的一个或多个因素来寻找最优可行路径。在AGV路径规划中有静态路由和动态路径规划[1]。静态路径规划意味着已经在站点之间预先确定了路线。路径规划，例如从站点i移动到站点j，AGV只需沿着固定路径运行。静态路径规划很简单，但是不能适应环境和运输情况的变化。动态规划可以避免基于当前环境的多AGV与实时交通信息之间的冲突，从而为每个AGV搜索最优路径规划。这是AGV路径规划中的困难。
AGV系统的多路径规划需要解决资源竞争和冲突问题。研究人员进行了许多研究，不同的应用并提出了许多解决策略。凌秋，文静[2]详细介绍了AGV路径规划和调度问题，并总结了AGV路径规划的方法。 Broadbent等[3]，考虑冲突和最佳时间为目的，以及优先采用Dijkstra算法解决单向路网规划问题的方法。 Kim和Tanchoco [4]给出了一种在双向路径网络上结合Dijkstra算法和时间窗的算法。该算法将路径规划问题转换为计划节点空闲时间窗问题。但是，该算法的过程复杂且搜索效率低。为了提高算法的搜索效率，Taghaboni-Dutta和Tanchoco [5]等提出了一种增量规划方法。但是这种方法牺牲了最优路径。 Nenad Smolic-Rocak等人。 [6]边缘时间规划法则讨论了一些AGV动态路径规划时间窗口。该算法只允许一个AGV占用一侧，因此路径利用率较低。在中国，罗志凡等人。 [7]提出了一种将模糊控制全局路径规划和局部规划相结合的两阶段路径规划方法，当AGV运行路径减少时，实现汽车无障碍运行。
这项工作得到了南沙科学研究项目＃2014CX07的部分支持; 广东省产学研一体化项目＃2012B091100311; 深圳市第二人民医院临床医生 - 基础科学家组合基金会。 2015年公共利益研究与能力建设项目，广东省科技厅，＃2014A020221004，＃2014A020215004;国家高技术研究发展计划（863计划）国家基金＃2014AA02090
Guodong Liu et al。 [8] [9]提出了一种两阶段路径规划方法。方法第一代AGV在站点离线候选路径集内行使，然后路径候选集中在线选项行使AGV路径。但是，这两种方法不能保证最佳解决方案的搜索路径。其他学者有基于路径时间窗的研究规划算法[10] [11]。他们将传统的路径规划方法与时间窗口结合起来规划AGV路径。还有一些研究人员合并了时间窗口方法与Petri网解决更多的AGV路径规划[12] [13]。 在一定程度上，这些方法扩大了搜索范围，以实现更复杂。 在本文中，我们将介绍在设计的AGV系统中使用的路径规划算法，最短时间规划的A *算法和多AGV路径规划（图1）。 在最短时间规划中，采用基于改进A *算法的转弯因子和边缘去除来解决k最短路径问题。 在多AGV路径规划中，提出了基于A *算法的动态路径规划方法，该方法有效搜索最短路径并避免碰撞。
II. 问题描述
- 最短时间规划在AGV路径规划中，需要解决的问题是选择合理的路径。许多学者将最短路径等同于最合理的路径，而一些研究者考虑了路径的平滑性，如AGV转弯的影响[13]。但他们都没有提供具体的方法。最合理的AGV路径应该是短而平滑的等等。
图1. AGV-MKS_1
生产厂的网络图如图2所示。本文将简化装载站，卸载站，处理站到无向连接图G之间的路径。从材料装运站23到处理站10的AGV23的最短路径可以是路径23-24-14-15-16-17- 18-19-9-10或路径23-24-14-7-8-9-10。但后者更曲折，转弯次数更多，不利于AGV自动运行控制。传统的解决最短路径问题的算法在这种情况下无法从上述两条路径中选择出车道数较少的路径。
当最短路径被另一个AGV或障碍物使用时，AGV需要选择第二短的最短的最短路径。 目前，虽然有多种解决方案寻求缩短k倍的路径[14] [15]，但它们更复杂。
B.多AGV路径规划
AGV系统环境基于图论，可将工作站，交叉点，转折点之间的路径简化为无向连通图G = {V，E，w}，其中V为节点集，E为边集由点连接组成，w表示两个节点之间的有效长度。
引导线
工作场所
货物
图2环境地图
（1）AGV运行路径为单通道和双通道，路径宽度只能容纳一个AGV;
（2）AGV运行速度恒定不变;
（3）同一时间，在每个节点的范围内只允许有一个AGV，但在一个AGV路径上允许有多个车辆;
（4）根据实际车辆运动规则，在AGV之间确定安全距离。 如果两个AGV之间的距离小于安全距离，则汽车后部停止，直到安全距离内没有障碍物为止。
III.最短的时间规划
A. A *算法的原理
如AGV工作环境图G所示，di表示从节点vi到起始站点的最短路径，dij表示从节点vi到节点vj的最短路径。我们可以得出如下结论：（1）图G中节点vi和节点vj之间的最短距离是vi和vj之间的距离，它位于从起始站到目标站vt的最短路径上。 （2）第二条最短路径必须经过最短路径附近的节点。
第二最短路径是从起始节点到终点之间通过最短路径附近的节点之一。上述结论在[14]中得到了证明。本文使用A *算法求最短路径，首先我们必须排除最短路径，因此检测最短路径的一边可以排除从起始站点vs最短路径L目标网站然后使用A *算法可以得到最短路径L.根据结论（1），（2），最短路径之一必须是期望的第二最短路径，通过连续删除起始站点vs到目标网站。找出所有最短路径长度的升序，选择前k个路径要求乘以更短的路径，并将它们存储在AGV系统的路径库中。
B. k次的最短路径
基于上述方法找到K最短路径的过程如下所示：
1）在本文中，改进的A *算法用于查找从起始站点到目标站点的最短路径。并将其存储在数组路径[n]中。 n是最短路径的边数;
2）整数i的定义，并将i初始化为1.确定是否小于等于n，转3）如果条件满足，否则，转到4）;
3）删除side lt;path [i-1]，path [i]gt;证明它们之间没有连接。然后再次调用A *算法以查找从起始站点到目标站点的最短路径，并将结果存储在pathi []中。）;
4）如果n小于k，那么pathi []（i = 1 ... n）的数据按照降序排列，并将路径和相关长度存储在AGV系统的数据库中。如果n大于或等于数据库路径中的AGV系统路径和相应的路径长度被存储;如果n大于等于k，则根据路径长度选择路径i [k-1]的前k-1个最短路径，并将相应长度与路径[n]存储在AGV系统的数据库中。
C.模拟
仿真图模仿一般生产自动化车间现场，如图1所示。使用VC 6.0程序，设置r的值。根据实际研究应用，r分别设为0.8,0.4,1。与一般的A *算法和Dijstra算法相比，该改进的A *算法（1,2,5）的路径长度，匝数和搜索节点如表1所示，实验路径如图3所示。
图3算法仿真结果
|
表1：模拟较 |
|||||
|
算法 |
路径（颜色） |
路径长度 |
转向节点 |
搜索编号的数量 |
|
|
Dijkstra |
黄色 |
45 |
6 |
32 |
|
|
A* 算法 |
黄色 |
45 |
6 |
17 |
|
|
改进的A*算法 |
a=1 |
橙色 |
45 |
2 |
15 |
|
a=2 |
橙色 |
45 |
2 |
14 |
|
|
a=5 |
橙色 |
45 |
2 |
16 |
|
可以看出，上述三种方法的路径长度是相同的，但是转折点的数量是不同的。在本文中，改进的A *路径算法可以搜索AGV控制的匝数最少的最短路径，并且轨道优于前两个。同时可以看出，A *算法的搜索效率相对于Dijkstra算法有较大的提高，相对于一般的A *算法略有提高。 当s接近线的最小长度时，搜索效率达到最低。
分别采用本文算法寻找k次最短路径和邻点算法寻找表2所示文档8的前3次最短路径的结果，实验路径如图2所示。
|
表2 三种短路径的结果 |
|||
|
算法 |
最短 |
第二短 |
第三短 |
|
本文中的方法 |
橙色 |
紫色 |
黄色 |
|
附近点法 |
橙色 |
紫色 |
黄色 |
两种算法的路径是相同的。 近点法的枚举法算法复杂，效率低。 但改进的A *算法，算法简单，搜索效率高。
IV.多AGV路径规划
A.路径时间模型
针对最短运行时间没有冲突，AGV路径规划不同于最短路径规划，其目标是最短路径。考虑到已经有很多复杂的算法，基于现有算法可以解决最短路径问题。首先，我们应该将路径模型转换为路径时间模型。具体方法如下。
参数可以在每个节点上设置。节点集R中的一维AGV注册信息。结构中有三个元素{stime，ltime，no}，分别代表到达时间节点，出发时间节点，AGV标识号。在节点i中的注册信息点j可以用。
当分配给一个AGV的节点时，对应节点上的AGV注册信息指示该节点在此期间不可用。当AGV离开节点时，相应的注册信息和节点释放时间被删除。其他AGV可以通过该节点，AGV路径规划等同于规划在可用时间段内现有时间信息上从起始节点到目标点的最短时间线。
B.时间计划中的A *算法
A *算法是启发式搜索算法，它使用启发式函数来评估传输节点到目的节点的成本。 A *算法评估函数可以表示为：
其中，g（x）表示从起点s到x的当前节点值的最短路径。 h *（x）表示从当前节点x到目标节点的最短路径的启发式值。 由于h *（x）不能预先知道，f（x）是f *（x）的近似值，f（x）表示如下：
其中，g（x）gt;g*(x),
全文共7199字，剩余内容已隐藏，支付完成后下载完整资料
英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16350]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
