基于改进Dijkstra算法的AGV智能车路径规划

梁彧

基于改进Dijkstra算法的AGV智能车路径规划

梁彧

（武汉理工大学 自动化学院，湖北 武汉 430070）

为了解决传统Dijkstra算法路径搜索范围大、效率低的问题，针对自动导引车（Automated Guided Vehicle，AGV）在部分已知的非结构化静态环境下的路径规划进行研究，提出了一种改进Dijkstra算法。这种算法的改进在于引入了估计函数，通过对路径代价进行估计，可以在缩短响应时间的基础上规划出最短路径，达到在未知环境中为AGV智能车提供无碰撞规划路线的效果，极大地提高了规划效率。通过MATLAB软件进行仿真实验，验证了方法的有效性，可以通过数据展示。

Dijkstra算法；AGV智能车；估计函数；路径规划

1 引言

随着工业生产自动化进程的迅速发展，智能仓储系统、智能物流运输逐渐成为“智能制造”的一个重要组成部分[1]，自动导引车广泛应用于智能仓储物流系统[2]、智能码垛搬运系统[3]。汽车行业是最早开始使用AGV的制造行业，在汽车诞生之初，其型号比较单一，生产制造都是由人工组装完成，福特公司率先使用流水线方式进行大批量生产，是汽车制造行业的一次创新[4]。近年来，AGV小车的无线通信系统、小车平台的升降系统和智能定位系统研究趋于成熟。将AGV运载小车有效运用到物流系统中，可以降低成本，提高工作效率，减少人工分拣失误，实现物流运输的智能化 目标[5]。

路径规划作为智能车研究的关键技术，是研发过程中不可避免的重要环节，即如何在减少碰撞的情况下，高效规划出一条从初始位置到目标位置的最优运动路径。针对不同行业对AGV提出不同的应用需求，研究者提出了许多不同的路径规划算法。在码头集装箱运输中，将遗传算法应用于码头环境，与其他工作场景相比，AGV智能车在复杂码头进行路径规划时会出现拥堵、多载、易碰撞、效率低、耗时长等问题[6]。对于规模过大的问题，遗传算法会出现求解效率低、编码复杂及早熟等问题。而蚁群算法（ACO）具有并行性、正反馈性及良好的扩充性等优点[7]，在解决路径规划、TSP[8]等问题都有成功的应用。但传统的蚁群算法存在运行时间长、搜索效率低的问题。针对以上问题，Dijkstra算法得到发展，该算法遇到动态环境时无需对路径重新规划，能够帮助AGV智能车一次性规划出最优路线。Dijkstra算法因其高实用性至今被学者们在机器人探路、交通路线导航、人工智能、游戏设计等方面广泛应用，对AGV智能车在不同环境下运行具有很强的扩展性和适应性。但是针对环境复杂的大区域地图，Dijkstra算法从起始点开始向周围层层计算扩展，在遍历大量节点后到达目标节点。因此，该算法速度慢、效率低，并且存储量会大大增加，当动态障碍频繁出现后依然需要重新规划。

基于以上问题，本文在Dijkstra算法的基础上引入了启发算法，设计了估价函数，根据传感器获得的实时环境信息，改进Dijkstra算法以高效率产生一条满足AGV智能车非完整性约束的路径，保证所规划局部路径的可行性。能够在保证路径尽可能短的基础上提高AGV智能车路径规划的效率，有效解决了传统Dijkstra算法速度慢且存储量大的问题，满足当今“智能制造”环境中高速、高效的需求。

2 Dijkstra算法原理

2.1 原理简介

Dijkstra算法是解决最短路径问题的经典算法之一，常用于计算从一个节点到其周围所有节点的最短路径，从而帮助AGV智能车在栅格地图上针对非结构化静态环境进行路径规划。该算法的核心思想是以遍历的形式找到图中所有节点的最短路径，从而确立目标点的最短路径。采用从目标节点到起始节点的搜索方式，可以运用于起始点改变的情况。传统的Dijkstra算法在AGV智能车路径规划中从起始源节点o开始，对其周围所有节点的最短路径进行搜索，基本的思路为：在路网模型中每个节点表示为（|），其中为起始源节点o到目标节点m的最短道路权值，为起始源节点o到目标节点m的前一个节点。Dijkstra算法的计算流程如图1所示。

Dijkstra算法的优势在于，当环境中出现新的未知障碍物时，可以快速更新该障碍物周边节点的信息，并将由此而导致不连续的节点重新压入优先列表中进行快速的重新规划。但是在栅格环境下，Dijkstra算法所规划出的路径并不平滑；当AGV智能车处于未知环境中，在距离当前位置较近处出现障碍物的可能性非常大。

图1 Dijkstra算法计算流程图

2.2 栅格地图的建立

AGV智能车运动路径的搜索与规划必须先采集其工作环境信息后进行建模，然后在建立的地图模型上进行路径规划。栅格地图结构简单，空间数据的重叠和组合容易，易于实现算法功能。基于以上优点，本文采用栅格地图进行建模，栅格信息与AGV智能车的工作环境相对应。地图中的节点对应其运行过程中的不同站点，边框代表其实际的运行路径，其中绿色代表起点，黄色代表目标节点，黑色区域为障碍物信息，如图2所示。采用栅格地图建立模型，可以最大限度减少不必要的地图信息，提高计算机对路径规划的处理速度与能力，便于创建与维护。

3 基于改进的Dijkstra算法路径规划

传统的Dijkstra算法需要以遍历的形式搜索到所有节点的最短路径，路径规划速度慢、效率低。针对以上问题，基于Dijkstra算法提出一种启发式搜索算法，这种算法的改进在于引入了估计函数，通过对路径代价进行估计，可以在缩短响应时间的基础上规划出最短路径。

盲目搜索会浪费很多时间和空间，因此在进行路径搜索时会首先选择最有希望的节点，这种搜索称之为“启发式搜索”[9]。改进后的Dijkstra算法核心为估计函数，在估计函数中加入了启发式代价值，使搜索的过程由启发式代价值不断导向至目标状态，可以减少大量计算过程，大大提高算法效率。

估计函数（）表示如下：

（）=（）+（） （1）

式（1）中：（）为从初始状态0经由状态到目标状态的代价估计；（）为由起始状态0到状态的实际代价；（）为从状态到目标状态最佳路径的估计代价。

在路径规划的过程中，需要选择值最小的下一节点作为最优路径中的节点。

算法中（）值由起点开始所经过的距离累加而得，（）值则通过距离预估方法求得，如果是状态坐标是目标状态坐标，则估计代价表示如下：

（）=|1－2|+|1－2| （2）

通常选取当前节点到目标节点的直线距离（欧几里得距离）作为启发式代价，可以表示为：

在（）＜（）的条件下，该算法在遍历所有节点后可以找到最短路径。在估计函数中，（）对算法起主要作用；（）估值越小，算法需要计算的节点就越多，导致算法效率降低，趋近于传统Dijkstra算法；但如果（）估值很大，则会导致（）的作用失效，逐步趋于BFS算法，只追求速度无法获取合理路径。

改进的Dijkstra算法在路径搜索的过程中把起始点o加入open-list，分别往八个方向搜索其连通区域里的子节点，通过式（1）分别计算每个子节点的估计值，再从当前的open-list选取值最小的下一节点n作为最优路径中的节点，加入close-list。接着遍历n的后继节点ns，如果ns是新节点，则加入open-list；如果ns已经位于open-list中，并且当前（ns）的值更小，则更新ns节点并修改parent节点。按以上步骤进行反复更新迭代，直至找到目标节点。最后从目标节点反向追溯其parent节点，从而规划出最优路径。改进Dijkstra算法计算流程如图3所示。

4 仿真实验分析

本文利用MATLAB软件编写了路径规划算法的相关程序，并对改进后算法的有效性进行了仿真验证。

实验设计思路：预先设定AGV智能车的初始节点、目标节点以及障碍物位置，构建10×10栅格地图模型对AGV智能车的运行环境进行模拟，分别使用传统的Dijkstra算法和改进后的Dijkstra算法进行路径规划，最后进行结果比对。

在主程序中设置初始节点为（2，6），目标节点为（9，8），子节点分别从8个方向进行路径搜索，得到的仿真结果如图4、图5所示。

如图4和图5所示，路径规划图中绿色区域为初始节点，黄色区域为目标节点，黑色区域代表障碍物，红色区域代表open-list，蓝色区域代表close-list。通过2次仿真实验进行对比，改进Dijkstra算法得到的路径为7个栅格距离，响应时间为0.098 s，而传统Dijkstra算法规划出的路径为9个栅格距离，响应时间为0.125 s。相较于传统的Dijkstra算法，改进后的Dijkstra算法行程缩短22.2%，响应时间减少21.6%。根据2张路径规划图进行对比分析，可以发现改进后的Dijkstra算法无需遍历图中所有节点，估计函数使搜索的过程由启发式代价值不断导向目标状态，在缩短路径的同时大大提高了路径规划的效率。改进后的算法克服了传统Dijkstra算法需要遍历所有节点的弊端，在保证高效率的条件下达到在未知环境中为AGV智能车提供无碰撞规划路线的效果。

图2 AGV智能车运行环境的栅格地图模型

图3 改进Dijkstra算法计算流程图

图4 传统Dijkstra算法路径规划图

图5 改进Dijkstra算法路径规划图

5 总结与展望

本文主要对部分已知的非结构化静态环境中的AGV小车路径规划方法进行了研究，为满足AGV智能车的实际运行要求，基于Dijkstra算法进行改进，引入了启发算法，设计了估价函数，能够在保证路径尽可能短的基础上提高AGV智能车路径规划的效率，有效地解决了传统Dijkstra算法速度慢且存储量大的问题。经过MATLAB软件的仿真实验，可以验证改进Dijkstra算法优化AGV智能车的规划路径是切实可行的。

［1］唐榆坤，渠水净.AGV在制造业仓储分拣业务中的运用［J］.物流技术与应用，2020，25（7）：127-130.

［2］李鹏涛.基于AGV与RFID的智能仓储系统的应用研究［J］.科技创新与应用，2020（11）：181-183.

［3］吴瑜.智能码垛系统在物流仓储中的应用［J］.电子世界，2020（13）：142-143.

［4］AGV小车在汽车行业自动化生产线上的应用［J］.汽车工艺师，2020（7）：16-18.

［5］吕吟雪，周穆新，王超驹，等.AGV小车在物流运输行业中的应用研究［J］.机电信息，2020（14）：37，39.

［6］宋启松，李少波，柘龙炫，等.基于改进遗传算法的自动导引小车路径规划［J］.组合机床与自动化加工技术，2020（7）：88-92.

［7］葛志远，肖本贤.使用改进蚁群算法的AGV路径规划研究［J］.机械设计与制造，2020（6）：241-244，248.

［8］顾军华，范培培，宋庆增.改进的求解TSP问题文化蚁群优化方法［J］.计算机工程与应用，2010（26）：49-52.

［9］李钊，董霄霄，黄程程，等.基于启发式搜索的浮点表达式设计空间探索方法［J］.计算机应用，2020（9）：2665-2669.

2095－6835（2020）24－0159－03

TP18

A

10.15913/j.cnki.kjycx.2020.24.061

梁彧（2000—），男，本科在读，研究方向为工控与智能机器人。

〔编辑：张思楠〕