AGV 路径规划在智慧工厂中的应用

2023-02-28魏涛

智能计算机与应用 2023年11期

魏涛

（青岛理工大学信息与控制工程学院，山东青岛 266525）

0 引言

引入AGV 后，传统的“人到货”的分拣方式转变为“货到人”的新模式，其优势在于可以通过自动化的方式，实现更高效、更智能的货物分拣生产模式。 AGV 的应用可以满足智慧工厂货物分拣的各种需求，带来了工作效率和精度的双重提升。因此，AGV 在智能制造领域扮演了至关重要的角色，是实现工业自动化不可或缺的关键技术之一。 AGV 对提高产业生产效率、减轻操作人员的负担、降低企业生产成本都具有非常重要的意义。路径规划是智慧工厂生产过程中实现货物运输的必要前提条件。在现代智能制造系统中，通过对AGV 进行路径规划和任务调度，可以实现货物的智能化自动化运输，有效提高生产效率和产能，降低生产成本和风险。因此，深入研究AGV 路径规划算法，优化和应用路径规划策略，对智慧工厂的生产运作具有至关重要的作用。关于AGV 路径规划算法，目前有多种研究方法和实践应用，比如经典的Dijkstra 算法、A∗算法、蚁群算法、遗传算法和模糊逻辑算法等。不同算法适用于不同的场景和问题，需要根据实际情况和需求进行选择和应用。房殿军等学者［1］以电子商务行业仓储需求为基础，提出了自动化立体仓库中AGV 的静态路径规划方法和动态避障决策策略。 Mohammad等学者［2］研究一种高效的2－opt 运算符，在AGV 路径规划过程中用以解决路径重组问题，以此进一步提高路径规划的效率和准确性。在此基础上，还将A∗算法与该运算符相结合，实现了多AGV 线路的规划任务。 Thomas 探究了一种局部搜索算符，并采用了蜂群优化的算法来解决AGV 路径规划任务合理性分配问题［3］。文献［4］利用局部搜索和随机搜索的策略来解决AGV 系统调度和无碰撞路径规划问题。通过分析AGV 系统调度和路径前瞻搜索算法结构，引入一种基于启发式的局部搜索算法来解决AGV 调度问题。文献［5］基于蚁群算法提出AGV 车间任务调度和无碰撞路径集成模型，有效地解决AGV 任务分配和路径规划的问题，提高生产效率和安全性。

本文主要研究的是基于改进的A∗算法在智慧工厂货物分拣系统中AGV 如何进行路径规划。首先，利用栅格法描述AGV 在智慧工厂货物运输过程。其次，为了解决多AGV 在货物运输过程中带来的交通堵塞，通过在多AGV 共同路线上加入惩罚值来改善交通拥堵情况。然后，结合改进的A∗算法针对多AGV 运行线路规划出一条无碰撞路径。最后，通过仿真实验对改进的A∗算法的路径规划效率进行验证，并与其他算法的路径规划效率进行比较。

1 AGV 运行环境建模

研究中，可以把智慧工厂生产车间中AGV 工作环境理想化视为矩形方阵。在环境建模的过程中，有多种常用的方法，其中包括拓扑图法、导航网络法以及栅格法等。以上3 种方法都有其优缺点和适用范围。需要根据实际情况，选取最合适的方法进行建模，以保证建出的环境模型能够符合实际需求。本文采用栅格法来生成环境模型，栅格法环境建模如图1 所示。

图1 栅格法环境建模Fig. 1 Grid based environmental modeling

采用栅格法环境建模，其优点在于：

（1）利用矩阵来近似模拟生产车间的工作环境，可能规划出来AGV 最短无碰撞路径并非最短路径，但可以增大AGV 安全运行距离，提高安全性。

（2）栅格法可对随机障碍域进行准确表达，不容易发生丢失障碍域等情况。

（3）栅格法对障碍域的描述相对简单，从而可以提高AGV 路径规划效率。

2 改进A∗算法的路径规划

2.1 A∗算法

A∗算法是一种启发式搜索算法，通常被用于寻找最短路径。是基于估价函数来指导搜索方向，在保证最优解的前提下，提高搜索效率和速度。其成本估计函数为：

其中，函数f（n）用于估计从起始节点通过任意节点n到目标节点的总成本。这个函数是由当前节点n的实际成本g（n）和当前节点n到目标节点的最优路径估计成本h（n）之和得出的。实际成本g（n）表示起始节点到当前节点n的实际代价。当扩展节点n时，会将其所有邻居节点添加到OPEN表中，并将这些节点的g（n）值设为n的g（n）加上从n到对应节点的实际代价。这样就可以不断更新每个节点的实际成本，直至找到目标节点为止。h（n）表示当前节点n到目标节点的最佳路径的估计成本。通常使用启发式函数来估算，例如曼哈顿距离、欧几里得距离等。启发式函数可以有助于在搜索过程中更好地指导搜索方向，从而更快地找到最优解。

A∗算法思想：A∗算法使用优先级队列来循环扩展最低成本估计节点，并把这个队列称为开集。在每一步执行过程中，从开集中删除f（n）值最低的节点，然后更新它的相邻节点的f（n）和g（n）值，把这些节点添加到优先级队列中。 A∗算法持续执行，直到找到目标节点，或者开集为空为止。最终的路径长度是目标节点的值，该值总是比开集中所有节点的值更低。使用优先级队列可以确保在每一个步骤中按照f（n）值递增的顺序，获取到开集中最低估计成本的节点，并且保证插入新的节点时能够自动维护开集中f（n）值的最低节点。 A∗算法实现步骤详见如下：

（1）定义节点类，包含节点坐标和距离起点的代价g（n）以及到终点的启发式代价估计值h（n）。

（2）初始化起始和终止节点，并将起始节点加入OPEN 表中。

（3）在每个循环中，从OPEN 表中选取f（n）值最小的节点n，将其从OPEN 表中移除，并将其加入CLOSE 表中。

（4）检查节点n是否为终止节点。如果是，则停止搜索并返回从起点到终点的路径。

（5）如果节点n不是终止节点，则对其相邻节点进行以下操作：

①对于每个相邻节点m，计算从起点到该节点的代价g（n）加上从该节点到终点的启发式代价估计值h（m）。计算得到相邻节点m的f（m）值。

②如果相邻节点m已经存在于CLOSE 表中，则跳过该节点，并继续处理下一个节点。

③如果相邻节点m不在OPEN 表中，则将其加入OPEN 表中，并将节点n设置为相邻节点m的父节点，计算相邻节点m的g（m）和h（m）值。

④否则，如果新的g（m）值比原来的小，则更新相邻节点m的g（m）值和父节点，并重新计算f（m）值。

（6）循环执行步骤（3）到步骤（5），直至找到终止节点或者OPEN 表为空。

（7）如果OPEN 表为空、并且未找到终止节点，则无法到达终止节点，搜索失败。

（8）如果找到了终止节点，并且从起点到终点的路径已经确定，则可以将该路径返回。

需要注意的是，在执行步骤（5）时，需要使用优先队列存储OPEN 表中的节点，并总是选取f（n）值最小的节点进行扩展。此外，启发式估价函数的准确性对A∗算法的性能和路径质量有着很大的影响。

2.2 A∗算法的不足

（1）启发式函数不准确时，A∗算法可能找到的不是最优解。 A∗算法的性能高度依赖所使用的启发式函数的准确性，在某些情况下，因为启发式函数不准确，A∗算法会找出次优解或者被卡在一些费时的路径上。

（2）A∗算法可能会陷入局部最优解。在某些情况下，A∗算法可能会受到其所使用的启发式函数的影响，沿着一个看似有趣、但是实际上并不符合题意的方向前进，最终陷入局部最优解。

（3）A∗算法不适用于无向加权图。在无向图中，最短路径搜索的运行过程通常会出现节点被一次又一次地遍历的现象，这将明显增加该算法的复杂度，算法效率也将随之降低。

（4）A∗算法对空间的要求较高。 A∗算法需要维护一个优先队列来存储已经搜索过的节点。如果目标状态太大，可能会出现内存不足，从而导致算法无法运行。

（5）A∗算法的实现较为复杂。在编写A∗算法时，除了需要合理选择启发式函数以外，还需要得到优先队列和开放列表等辅助工具。因此，需要花费一定时间来构建和调试算法。

综上所述，A∗算法虽然在很多情况下表现优异，但也存在一些不足。因此，在具体应用时，需要综合考虑算法的优点和缺点，选择合适的算法并加以改进。

2.3 AGV 碰撞类型

在智慧工厂生产环境中，AGV 在运行过程中难免会出现碰撞情况，下面将介绍一些常见的AGV 碰撞类型。

（1）节点冲突。节点冲突是指整个运行线路中，在某一时刻，有2 个或多个AGV 同时经过某一节点。节点冲突示意如图2 所示。通过设置AGV路径优先级，可以避免发生节点冲突。

图2 节点冲突Fig. 2 Node conflict

（2）赶超冲突。赶超冲突是指2 个AGV 以不同的速度同向行驶。由于后车的速度大于前车的速度，两车的距离越来越近，如果保持这种状态，会导致两车发生追尾。赶超总突示意如图3 所示。

图3 赶超冲突Fig. 3 Catch up and surpass conflict

（3）相遇冲突。相遇冲突也叫做相向冲突。指2 辆正在执行任务的AGV 在同一条线路上相向而行。在同一时间节点，某条路线只能允许有一辆AGV 通过，但如果此时有另外一台AGV 也要通过该条路线，那么这2 台AGV 之间就会迎面发生碰撞。相遇冲突示意如图4 所示。

图4 相遇冲突Fig. 4 Encounter conflict

2.4 A∗算法的改进

基于上述的A∗算法的不足以及AGV 路径碰撞类型，研究中提出对A∗算法的改进。

在A∗算法中，节点的g（n）值是实际值，h（n）值是启发式估计值。选择适当的启发式估计函数能够提高算法的效率和寻找到更优路径。常用的启发式估价函数包括曼哈顿距离、欧几里得距离［6－8］、对角线距离等。对此拟做阐释分述如下。

（1）曼哈顿距离。是根据标准坐标系中的绝对轴距总和来计算节点间的距离，相比于欧几里得距离，其计算简单、效率高，但是在寻找路径的质量上较低。

（2）对角线距离。在估价函数中考虑了沿对角线移动的情况，相对于曼哈顿距离和欧几里得距离，在进行评估值计算时与最优路径的评估值误差较小，因此可以有效提高路径的质量和算法的效率。

（3）欧几里得距离。是计算两点之间最短距离的一种方法，通常被用作启发式函数之一。但是，欧几里得距离计算涉及平方和开方运算，因此在寻找大型图形上的最短路径时，效率较低。

分析可知，选择合适的启发式函数取决于特定应用场景，通常需要平衡最短路径的质量和算法执行效率。在本文中，选择对角线距离作为启发式函数，因为该函数与最优路径的评估值误差较小，且计算相对简单，能够提高路径的质量和算法的效率。改进的启发式函数计算公式如下：

其中，在栅格法地图中，c表示水平或竖直移动一步的代价，而对角线移动的代价为√2c。由式（2）～（4）可计算得到对角线距离的代价估值。

在同样的条件下，经计算对比发现，改进的A∗算法运行效率得到了提高，同时扩展的节点并没有减少，因此仍可得到与原A∗算法相同的路径规划结果。

3 仿真实验

3.1 参数设置

在智慧工厂的模拟实验中，网格的大小为8 m×8 m，工厂的长度和宽度均为800 m。 AGV 数量为100 台，AGV 的运行速度为1 m／s。为了设置适当的x、y参数，需要考虑每个参数的含义和对路径规划的影响。在该实验中，需要使距离越近的节点受到更多的惩罚，从而避免AGV 出现拥堵或者交叉运行的情况。本文利用C＋＋语言开发智慧工厂中多AGV 货物分拣的仿真软件。该软件可以监控AGV运动轨迹，调整AGV 运行速度，通过栅格法建模，可根据系统需求自动设置工厂所要用的AGV 数量。

3.2 AGV 防碰撞分析

由于本次仿真实验所有的AGV 运行速度均为1 m／s，并规定后面的AGV 停止等待前面的AGV 通过后再继续运行。因此本次实验不考虑赶超冲突，只考虑节点冲突。多AGV 防碰撞路径规划涉及到对多辆AGV 路径的规划，可以采用改进的A∗算法和蚁群算法。针对这2 种算法，本文进行了实验比较，结果见表1。

表1 改进的A∗算法与蚁群算法防碰撞对比Tab. 1 Comparison of improved A∗algorithm and ant colony algorithm in collision prevention

从表1 数据结果可以发现，随着AGV 发生碰撞次数的增加，采用蚁群算法和改进的A∗算法的路径规划模拟时间和停止等待时间也会随之增加。使用改进的A∗算法进行多AGV 防碰撞路径规划时，随着防碰撞次数的增加，模拟时间呈线性增长趋势。相比之下，蚁群算法的模拟时间则呈现出指数型增长，这是由于蚁群算法需要进行多次路径搜索和计算，而每次迭代都需要重新计算AGV 的路径、尤其是在交叉口防碰撞时，其迭代次数就与碰撞次数相关，增加了计算复杂度。

本文中采用的改进A∗算法在停止等待时间上稍优于蚁群算法。这是因为改进A∗算法所用的网格节点作为AGV 的停止点，使得在交叉口防碰撞实验时，AGV 停止点与交叉口的距离更近，从而减少了等待时间，加快了AGV 再次启动的时间。相比之下，蚁群算法的路径搜索过程比较复杂，在交叉口防碰撞时，需要较长时间进行路径搜索和计算，导致停止等待时间相对较长。因此，采用改进的A∗算法进行路径规划可以有效缓解交通拥堵问题。

3.3 AGV 分拣效率分析

与传统A∗算法相比，基于改进A∗算法的多AGV 路径规划能够更有效地提高AGV 的路径规划效率，并进一步提升货物分拣系统的运行效率。 A∗算法与改进A∗算法分拣高效率对比见表2。由表2可知，通过改进A∗算法后，每秒平均分拣数（ASP／s）可以明显提高，这得益于在改进的A∗算法中，优化了AGV 路径的选取和优先级的调控，同时还加入了一系列的启发式函数和判定条件来提高搜索效率。这种多AGV 防碰撞路径规划算法的优势在于对分拣系统整体性能的提升，可以更加高效、稳定地实现高速、大规模的货物分拣工作。

表2 A∗算法与改进A∗算法分拣效率对比Tab. 2 Comparison of sorting efficiency between A∗algorithm and improved A∗algorithm

从表2 数据结果可以看出，在货物分拣系统中，无论是传统的A∗算法、还是基于改进的A∗算法，随着时间的增长，分拣速度都会逐渐减缓。然而，基于改进的A∗算法在面对更多的货物时，可以更好地应对系统的需求，从而提高分拣速度，获得了更好的稳定性。这是因为基于改进的A∗算法考虑了交通拥堵和防碰撞，能够规避道路拥堵和车辆碰撞的问题，提高了整个分拣系统的运作效率。因此，基于改进的A∗算法进行多AGV 路径规划可以提高分拣系统的整体效率和生产力。