英语原文共 6 页

基于改进A-Star算法的自动导引车路径规划

摘要：随着自动化物流系统，柔性制造系统（FMS）和无人自动化工厂的发展，自动导引车（AGV）的应用逐渐成为提高企业生产效率和物流自动化的重要手段。AGV系统的开发在降低劳动力成本，改善工作条件，统一信息流和物流方面发挥着重要作用。路径规划一直是AGV控制系统中的关键问题。本文解决了多AGV中的最短时间路径规划和碰撞两个关键问题。提出了一种改进的A-Star（A *）算法，该算法引入了转向因子，并采用改进的A *算法求解边缘去除k最短路径问题。与此同时，提出了一种基于A *算法的动态路径规划方法，该方法能够有效地搜索最短路径并避免碰撞。最后，通过仿真和实验验证了算法的可行性。

第一节 介绍

随着行业的发展，由AGV组成的物流系统越来越受欢迎。但是，在应用中仍有一些问题需要解决。作为最严重的问题之一，AGV路径规划不同于一般的车辆路径问题。它适用于不同的应用和不同的机智。更重要的是，约束，最优解决方案和策略与一般车辆路线不同。

路径规划意味着根据给定的起点和终点在某些环境约束中搜索最优可行路径，参考一个或多个因素，例如最短路径，最短时间，最小成本和其他因素。AGV路径规划中有静态路由和动态路径规划[1]。静态路径规划意味着已在站点之间预先识别路径。路径规划，例如从站点i移动到站点j，AGV只需沿固定路径运行。静态路径规划很简单，但不能适应环境和运输情况的变化。动态编程可以避免基于当前环境的多AGV与实时交通信息之间的冲突，以搜索每个AGV的最佳路径规划。这是AGV路径规划的难点。

在AGV系统的多路径规划中需要解决资源竞争和冲突。研究人员进行了许多研究，不同的应用并提出了许多解决方案策略。LING QIU，WEN JING [2]，带头详细描述了AGV路径规划和调度问题，并总结了AGV路径规划的方法。Broadbent等[3]，考虑冲突和最佳时间为目的，以及使用Dijkstra算法解决单向路由网络规划问题的优先级方法。Kim和Tanchoco [4]给出了一种在双向路径网络上结合Dijkstra算法和时间窗的算法。该算法将路径规划问题转换为计划节点空闲时窗问题。然而，该算法的过程复杂且搜索效率低。为了提高算法的搜索效率，Taghaboni-Dutta和Tanchoco [5]等提出了一种增量规划方法。但是这种方法牺牲了最优路径。Nenad Smolic-Rocak等。[6]讨论了基于算法边缘时间规划规则的若干AGV动态路径规划时间窗。该算法只允许一个AGV占用一侧，因此利用路径相对较低。在中国，Zhifan Luo等人。[7]提出了一种结合模糊控制全局路径规划和局部规划的两阶段路径规划方法，当AGV运行路径减小的同时实现无障碍车辆运行。刘国栋等。[8] [9]提出了一种两阶段路径规划方法。方法第一代AGV在站点离线候选路径集内运行，然后路径候选集中在线选项行使AGV路径。但是，这两种方法无法保证最优解搜索路径。其他学者有基于路径时间窗的研究计划算法[10] [11]。他们将传统的路径规划方法与规划AGV路径的时间窗相结合。还有一些研究人员将时间窗方法与Petri网相结合，以解决更多的AGV路径规划[12] [13]。在某种程度上，这些方法扩大了搜索范围以实现更复杂。

在本文中，我们将介绍路径规划算法，最短时间规划的A *算法和用于设计的AGV系统的多AGV路径规划（图1）。在最短的时间规划中，采用基于改进的A *算法的转弯和边缘去除因素来解决k最短路径问题。在多AGV路径规划中，提出了一种基于A *算法的动态路径规划方法，该方法有效地搜索最短路径并避免碰撞。

图1 AGV-MKS_1概述

查看全部

第二节 问题描述

A.最短时间规划

在AGV路径规划期间，需要解决的问题是选择合理的路径。许多学者将最短路径等同于最合理的路径，而一些研究人员则考虑了路径的平滑性，例如AGV转向的影响[13]。但他们两个都没有给出具体的方法。最合理的AGV路径应该是短的，平滑的等等。

生产工厂的网络图如图2所示。本文将简化装载站，卸载站，处理站与无向连接图G之间的路径.AGV23从物料装运站23到处理站10的最短路径可以是路径23-24-14-15-16-17- 18-19-9-10或路径23-24-14-7-8-9-10。但后者更曲折，转弯次数更多，不利于AGV自动操作控制。在这种情况下，解决最短路径问题的传统算法无法从上述两条路径中选择转向数较少的路径。

当最短路径被另一个AGV或障碍物使用时，AGV需要选择第二个最短路径或第三个最短路径。目前，虽然有很多解决方案可以寻求k倍短路径，但它们更复杂。

图2 环境地图

B.多AGV路径规划

AS AGV系统环境表示基于图论，工作站，交叉口，转折点之间的路径可以简化为无向连通图 G ={ V，E，W}其中V是节点集，E是由节点连接形成的边集，W示两个节点之间的有效长度。

1. AGV运行路径是单通道和双向运行路径，路径宽度只能容纳一个AGV;
2. AGV运行速度恒定且相同;
3. 同时，在包含每个节点的范围内仅允许一个AGV，但是在一个AGV路径上允许多个车辆;
4. 根据实际车辆运动的规则，在AGV之间确定安全距离。如果两个AGV之间的距离小于安全距离，则汽车后部停止，直到检测不到安全距离的障碍物。

第三节 最短的时间规划

A. A *算法的原理

如AGV工作环境图G中所示，di表示从节点vi到起始站点vs的最短路径，dij表示从节点vi到节点vj的最短路径。我们可以得出以下结论：（1）图G中节点vi和节点vj之间的最短距离是vi和vj之间的最短距离，它位于从起始站到目标站vt的最短路径中。（2）第二条最短路径必须经过最近路径的最近节点。第二条最短路径是从起始节点到终点通过最近路径的附近节点之一。

上述结论在[14]中得到证实。本文使用A *算法作为最短路径，首先我们必须排除最短路径，因此检测最短路径的一侧可以排除从起始站点到目标站点vt的最短路径L. 然后使用A *算法可以获得最短路径L.根据结论（1），（2），最短路径之一必须是所需的第二最短路径，通过从起始站点vs连续删除最短路径的边。目标网站。以升序查找所有最短路径长度，选择前k路径请求较短路径并将其存储在AGV系统的路径库中。

B. k次中的最短路径

基于上述方法找到K最短路径的过程如下所示：

1. 在本文中，改进的A *算法用于找到从起始站点到目标站点vt的最短路径。并将其存储在数组路径[n]中。n是最短路径的边数;
2. 整数i和i的定义初始化为1.如果条件满足则确定是否小于等于n，转3），否则转到4）;
3. 删除side lt;path [i-1]，path [i]gt;证明它们之间没有连接。然后再次调用A *算法以找到从起始站点到目标站点vt的最短路径，将结果存储在pathi []中。我等于我脉动1，然后转到2）;
4. 如果n小于k，则pathi []的数据 （i = 1 ... n）在AGV系统的数据库中存储路径和相关长度，按降序排序。如果n大于或等于数据库路径中的AGV系统路径和相应的路径长度被存储; 如果n大于等于k，则根据路径长度选择路径[k-1]的前k-1个最短路径，并在AGV系统的数据库中存储路径[n]的相应长度。

C.模拟

仿真地图模拟了一般生产自动化车间现场，如图1所示。使用VC 6.0程序，设置r的值。根据实际研究应用，r分别设定为0.8,0.4,1。与一般的A *算法和Dijstra算法相比，该改进的A *算法（1,2,5）的路径长度，匝数和搜索节点如表1所示，实验路径如图3所示。

图3 算法仿真结果

表1：模拟比较

可以看出，上述三种方法的路径长度相同，但转折点的数量不同。在本文中，改进的A *路径算法可以搜索AGV控制的最小匝数的最短路径，并且轨道优于前两个。同时，我们可以看出，相对于Dijkstra算法，A *算法的搜索效率大大提高，相对于一般A *算法略有改进。当s接近线的最小长度时，搜索效率达到最低。

分别使用本文算法寻找k次最短路径和相邻点算法的结果来寻找表2所示的文档8的前3倍最短路径，实验路径如图2所示。

表2 三条短路径的结果

两种算法的路径是相同的。近点法的枚举方法算法复杂，效率低。但改进的A *算法，算法简单，搜索效率快。

第四节 多AGV路径规划

A.路径时间模型

针对最短的运行时间而不冲突，AGV路径规划不同于最短路径规划，目标是最短路径。考虑到已经有很多复杂的算法，可以在现有算法的基础上解决最短路径问题。首先，我们应该将路径模型转换为路径时间模型。具体方法如下。

可以在每个节点设置参数。节点集R中的一维AGV登记信息。结构中有三个元素{stime，ltime，no}，分别表示到达时间节点，出发时间节点，AGV标识号。节点i中的注册信息点j可以表示为Rⁱ_j。no, Rⁱ_j。stime，Rⁱ_j。ltime。

当分配给一个AGV的节点时，相应节点上的AGV注册信息指示该节点在该时段内不可用。当AGV离开节点时，删除相应的注册信息和节点释放时间。其他AGV可以通过节点，AGV路径规划相当于规划可用时段内现有时间信息上从起始节点到目标点的最短时间线。

B.时间规划中的A *算法

A *算法是一种启发式搜索算法，它使用启发式函数来评估到目的节点的传输节点的成本。A *算法评估函数可表示为：

其中，g(x)表示从起始点s到当前节点值的最短路径 f(x)表示从当前节点x到目标节点的最短路径的启发式值。以来h^*(x)事先不知道，f(x)是近似值off^*(X)

，f(x)表示如下：

其中， g(x)gt;=g^*(x) ,h(x)lt;=h^*(x)

g(x)和 h(x) 进行以下更改：g(x) 表示AGV输入当前节点x的最早时间值， h(x) 表示目标节点x的当前值以激励节点时间t，表示如下：

其中v代表AGV的平均运行速度。

假设从节点I到节点x没有潜在的冲突，解决方法如下：

AGV第一次访问x时的时间为L_ix = g(i) t_ix,t_ix显示时间AGV通过边lt;i，xgt;，比较R₁^x.stime和L_ix，

如果L_ix t_x lt; R₁^X,t_x表示AGV占用节点x次，然后g(x)=L_ix

否则搜索R^X,T_arr= max { R_J^x.Ltime.L_ix}

找出 T_arr满足的价值

当从节点i到节点x存在冲突时，h(x)可以通过以下策略找到。

C.碰撞检测

通过时间分配解决了AGV节点资源争用的问题，但仍存在AGV边缘资源争用问题。AGV边缘资源争用问题在面临冲突和追赶上进行。当所有AGV以相同的速度运行时，不会发生追赶冲突。因此，没有必要考虑这种冲突。面对冲突如图4所示。节点vi和节点vx的时间轴如图5所示。已经规划了AGV1的程序，而AGV2的程序没有。判断AGV2中是否存在从节点vi到节点vj的冲突的方法如下：

签入注册信息 在R^x

以确定是否存在相同的注册信息AGV标识号（如果有的话）是否存在与x相反的冲突i。

图4面对冲突