车间环境下多AGV路径智能优化研究

唐巧玲 彭全 张燎

摘  要：隨着我国工业技术的高速发展，多自动运输车（Automated Guided Vehicle，AGV）在自主性和节约成本方面受到越来越多的重视。基于多AGV在复杂多变的车间环境中的路径规划问题，提出了改进的A*算法（A-star Algorithm）和DWA算法（Dynamic Window Approach）融合的智能优化算法。首先，利用A*算法规划出从起点到终点的全局路径，然后针对A*算法多冗余的缺点，提出了一种提取关键点的方法，剔除掉全局路径中的冗余节点和多余拐点，保证了对全局路径的改进。其次，通过对全局路径的分段，设置一系列的局部目标点，利用DWA动态窗口法对新增和移动的障碍物进行动态避障的同时不断地到达局部目标点，得到了多AGV从起点到目标点的最优路径，最终实现了对多AGV关于路径长度和安全性方面的改进。

关键词：A*算法  DWA算法  算法融合  路径规划

中图分类号： TP18

Research on the Intelligent Optimization of the  Pathway of Multiple AGVs in the Inter-Vehicle Environment

TANG Qiaoling  PENG Quan  ZHANG Liao

Neijiang Normal University， Neijian， Sichuan Province， 641100 China

Abstract： With the rapid development of industrial technology in China， the automated guided vehicle （AGV） is receiving increasing attention in terms of autonomy and cost saving. This article proposes an intelligent optimization algorithm that integrates the improved A* algorithm （A-star algorithm） and DWA （dynamic window approach） for the path planning problem of multiple AGVs in the complex and variable inter-vehicle environment. Firstly， this article uses the A* algorithm to plan the global path from the starting point to the endpoint， and then， for the shortcoming of the multiple redundancy of the A* algorithm， proposes a method for extracting key points to eliminate the redundant nodes and inflection points of the global path， which ensures the improvement of the global path. Secondly， by segmenting the global path， it sets a series of local target points， and uses the DWA to dynamically avoid newly-added and moving obstacles while continuously reaching the local target points， so as to obtain the optimal path for multiple AGVs from the starting point to the target point， and ultimately achieve the improvement of the path length and safety of multiple AGVs.

Key Words： A-star algorithm; Dynamic window approach; Algorithm fusion; Path planning

AGV（Automated Guided Vehicle）作为自动运输小车，拥有自动寻址系统，使其能通过进行非接触提前路线规划。按照预先规划好的路径独自运动或牵引货物从起始点一直行驶到目标地点，完成货物的自动运输服务。本文提出了一种基于改进的A*算法和DWA算法的融合算法，通过对A*算法的优化和改进，弥补了A*算法平滑性不高的缺陷，再融合了DWA算法，实现了车间环境中多AGV对新增和移动的障碍物动态避障路径规划。

1  多AGV路径规划融合算法

在车间环境中，多AGV最优路径规划问题，就是在其工作环境中对周围环境模型进行搜索，依据某种测评找到一条从起始点到目标点的最优路径，并且此路径能动态避开环境中的障碍物[1-2]。但常用的路径规划算法只考虑单个小车对于障碍物的避碰，没有考虑车辆之间的碰撞，都是静态规划，不能根据实时情况进行路径动态变化，此外现有的路径规划方法只适应于AGV可以在各个方向自由行走的情况，不适用于复杂的车间环境。

本文提出的改进的A*算法和DWA融合算法，充分利用了两种算法的优势，实现了路径平滑度和安全性的改进[3]。首先利用改进的A*算法规划全局静态路径，然后在全局路径中设置多个局部目标点，再利用DWA算法进行局部动态路径规划，使其在最优全局路径的基础上可以实现动态地避让小车和障碍物。

1.1  改进A*全局静态路径规划

在车间环境中，对于传统A*算法所规划路径存在较多冗余节点的缺点，提出了一种关键节点提取法，保留路径必经的关键折点，使改进后的路径长度更短、折点更少[4]。具体步骤如下。

（1）用面积法提取转折点，依次计算路径中相邻三点（p-1、p、p+1）围成的面积，如果面积不为0，则p为转折点，否则p不是转折点。p的初始点为距起点最近的路径节点，直到p为距目标点最近的路径节点，转折点提取结束，将起点和目标点也视为转折点。

（2）进行关键点筛选，在相邻转折点（q-1、q、q+1）中，连接不相邻的两点（q-1、q+1），如果连线经过障碍物区域，则转折点q为关键点，否则为冗余点。q初始点为距起点最近的转折点，直到q为距目标点最近的转折点时，关键点筛选结束。

1.2  DWA局部动态路径规划

DWA算法是通过运动模型和采样的运动信息推算出小车可能的多种运动轨迹，然后通过评价函数选取最优的规划路径。本文将改进的A*算法中提取的关键点设置为局部路径的局部目标点，使其一一到达并最终抵达终点，从而得到一条改进的路径。当多辆AGV将会碰撞时，DWA算法会依次设定AGV的优先级，让优先级高的AGV先通行。为使DWA算法所规划的局部路径更接近全局路径，在预测轨迹评价函数中加入A*算法的代价值函数为全局路径评价子函数[5]，则融合算法的评价函数为：

（1）

式（1）中，heading（v，w）是方位角评价函数，指小车航向与目标之间的角度差；dist（v，w）是小车与最近障碍物之间的距离；velocity（v，w）是轨迹对应的速度大小。P为t时刻通过v和w预测的移动机器人位置坐标；g（P）表示预测位置到起点的距离；h（P）表示预测位置到局部目标点的距离；为全局路径评价函数子函数权重（取值小于α和γ，大于β）。H（v，w）值越小，得分越高。

2  算法测试结果及分析

本文采用MATLAB平台，使用改进的A*算法和DWA算法的融合算法对存在静态以及动态障碍物的车间环境进行多AGV路径规划仿真，实现了智能车间环境中多AGV动态避障路径规划。

2.1  改进的A*全局路径规划

本文采用栅格化的环境模型，模擬了3辆AGV的起点和终点以及动态的障碍物的起点和终点。设AGV1的起点是（19，26），终点是（9，23）；AGV2的起点是（5，8），终点是（11，16）；AGV3的起点是（17，17），终点是（12，27）。然后根据改进的A*算法进行全局路径规划，可以得到3条路径，改进的A*算法路径规划结果如图2所示。

根据改进的A*全局路径规划图可知，AGV1和AGV2的路径发生了交叉，因此AGV1和AGV2在运行过程中可能会发生碰撞，此时就需要运用DWA算法进行动态避障，使AGV1和AGV2在相遇时根据优先级，使最优先的AGV先行，次优先AGV避让，以此来达到多AGV避碰的目的。

2.2  DWA局部路径优化

DWA局部路径优化是将全局路径分成多个局部路径，设置多个局部目标点，避让其余AGV和运动的障碍物，从而到达各个局部目标点，并最终各自到达目的地。

根据本文模拟环境，AGV1和AGV2在路径规划中相遇，AGV3为了躲避向右的移动障碍物，偏向右边规划。然后根据DWA算法设置的优先级AGV1大于AGV2，AGV2停下避让AGV1。如图3所示，经过DWA算法局部规划路径后，分别得到了3条优化的路径[5]。

由图3所示优化后的路径可知，多AGV的路径规划融合算法可以在动态的车间环境中避让小车和障碍物，能够实现多AGV在复杂的车间环境下的路径智能优化。

3  结语

本文针对智能车间环境中使用传统路径规划算法对多AGV路径规划造成的平滑性和灵活性不足、安全性不高等问题，提出了改进的A*算法和DWA算法融合的路径智能优化算法，融合了两种算法的优势，并通过MATLAB平台，模拟了车间中存在的复杂环境，进行了多AGV动态避障路径规划的仿真，实现了多AGV在复杂车间情况下的无碰路径规划。但在A*算法进行全局规划时，有出现重复点的可能性，因此DWA算法进行局部规划追踪时，会出现重复识别，造成错误，未来将针对重复点问题进一步研究。

参考文献

• 岑云飞.面向智能工厂的多AGV调度系统开发[D].西安：西安理工大学，2023.
• 熊焰，刘金库.多移动机器人路径无障碍智能规划算法仿真[J].计算机仿真，2023，40（4）：434-438.
• 陈娇，徐菱，陈佳，等.改进A*和动态窗口法的移动机器人路径规划[J].计算机集成制造系统，2022，28（6）：1650-1658.
• 于洋，杜学历，冯迎宾.融合A*算法和动态窗口法的全局动态路径规划方法[J].沈阳理工大学学报，2020，39（5）：1-7.
• 王彬，聂建军，李海洋，等.优化A*与动态窗口法的移动机器人路径规划[J/OL].计算机集成制造系统：1-17[2023-12-06].http：//kns.cnki.net/kcms/detail/11.5946.TP.20220305.1932.024.html.