张金越，侯至丞，张 弓，王卫军，杨文林

( 广州中国科学院先进技术研究所机器人与智能装备中心,广州 511458)

0 引言

路径规划是指移动机器人基于某些特定的准则，在环境中存在障碍物的前提下，自主规划一条从起始位置到目标位置的安全、无碰撞的最短路径。随着自主移动机器人的快速发展，路径规划成为了一个热门的研究问题。

现阶段，国内外众多学者已取得了大量关于路径规划的研究成果：马浩浩等[1]对传统遗传算法中的种群初始化、交叉算子以及变异算子进行改进，设计了机器人路径规划算法，有效提高了算法的效率；吴东林等[2]基于人工势场法设计了采摘机器人的动态路径规划系统，具有很好地避障和路径规划的能力；陆皖麟等[3]在A*算法的基础上添加阈值减少了搜索栅格的数量，并结合了Floyd算法去除了多余节点，使得规划的路径短且光滑；刘彩霞[4]提出了一种基于模糊推理的PSO路径规划算法，解决了移动机器人路径规划质量不佳的问题；Jabbarpour M R等[5]针对现有路径规划算法无法降低UGV能耗的问题，将能耗预测模型与蚁群算法相结合，在减少计算时间和迭代次数的同时，规划出低功耗的无碰撞最短路径；Zhang H等[6]为防止RRT算法对配置空间的过度搜索，引入了回归机制，提高了规划的成功率和效率。在上述的路径规划算法中，遗传算法、蚁群算法以及粒子群算法能否规划出最优路径取决于各参数的选取；基于引力与斥力的原理的人工势场法容易陷入受力平衡而出现目标不可达的情况[7]；RRT算法存在搜索效率较低、用时较长的缺陷[8]；而A*算法在编程方式简单的前提下能够有效地搜索到最优解。

对于多AGV的避碰问题，常见的避碰算法包括区域控制方法、时间窗法、交通约束法等[9]。其中，区域控制法容易在物品的传递环节浪费大量时间，降低工作效率；而时间窗法是利用AGV的行进速度预测其经过每一节点的时间，若AGV的速度发生变化，则会降低预测结果的可信度；交通约束法根据日常生活中的交通规则，通过优先级的高低进行减速避让，有效地实现AGV间的避碰。

综上所述，对于单一AGV，A*算法在路径规划的研究工作中一定程度提高了最优路径的搜索效率，但所规划的路径往往拐角数过多[10]，而AGV每次转弯都需要经历加减速的过程，大量的拐角会增加AGV完成路径行走的时间、能耗；而存在多AGV时，交通约束法能够有效地解决AGV间的避碰问题，并且降低系统规划路径时的计算量。

因此，本文将研究采用一种基于交通约束及多元启发函数的A*算法，对传统的A*算法进行优化，引入交通约束，并在原有的启发函数的基础上，添加拐角数的评判指标，构成多元启发函数，在保证规划出最短路径的前提下，实现拐角数最优。

1 环境建模

环境建模即根据工作环境特点建立的抽象化地图，是AGV进行路径规划的先决条件。现阶段常用的环境建模方法包括：栅格法、拓扑法、几何信息法等[11]。

栅格法是将AGV的工作环境划分为多个大小一致的栅格，采用二值信息表示自由空间和障碍物区域。拓扑法[12]是将环境划分为多个具有一定拓扑特征的子空间，根据子空间的连通性构建拓扑网络并进行搜索路径的方法。几何信息法利用环境信息提取出几何特征，再使用这些几何信息进行环境建模。

图1 货架布局示意图

由于本文所依托的项目主要执行货架上货物的搬运任务，货架的布局具体如图1所示，其中，黑色区域为货架，白色区域为自由空间。

出于建模方便、编程易于实现等因素的考虑，本文采用栅格法进行环境建模。按照AGV实际的工作环境，建立一个12×10大小的栅格地图，并根据通行状态将该地图划分为可通行的白色自由区域以及不可通行的黑色障碍物区域。同时为了更好地描述栅格位置，本文采用坐标的形式对栅格进行编号，定义地图左下角的坐标为(1,1)，横坐标从左到右、纵坐标从下到上逐个递增，相邻栅格坐标值相差1。

2 A*算法设计

2.1 交通约束法

交通约束即对AGV的行进过程添加交通规则的约束，使得AGV在某一通道上只能沿特定方向行进。

AGV在正常行进的过程中，常见的会遇态势包括对遇、交叉等，具体如图2所示。

(a)AGV对遇 (b)AGV交叉图2 常见的AGV会遇态势

上述的两种情况，都会对AGV的正常行进产生影响：当两AGV在同一通道对遇时，由于各自下一步指令均为前进，故陷入了死锁的现象；在两AGV出现交叉的局面时，因两者下一节点相同、会出现碰撞的情况，因此也停留在原地不动。

在引入交通约束法后，同一通道上的AGV只能沿着一个方向行进，此时AGV交叉会遇的现象将不复存在；而对于交叉的情况，AGV会根据自身所赋予的优先级大小进行下一步动作：停车避让或者继续前行。

相比于时间窗法，本文所采用的交通约束法的优势在于不用预测每台AGV到达每个节点的时间，无需考虑AGV在工作时受到其他因素干扰而发生速度变化的问题[13]，同时减少了会遇的类型，有效避免了AGV在通道内的碰撞问题，减少了在工作环境中的碰撞几率，具有更强稳定性。

2.2 传统A*算法

A*算法是一种典型的启发式搜索算法，传统的A*算法主要从垂直和水平方向进行搜索：从起始点开始，沿着垂直和水平方向进行搜索点的扩展，通过启发函数f(n)估计扩展点的代价值，同时将扩展点存入open列表中，再将open列表中选取代价值最小的节点作为下一次搜索的起点,并将该点从open列表中移除，重复上述步骤直至找到目标点。

由上述的A*算法的工作原理可知，其成功与否主要取决于启发函数f(n)，启发函数的表达式[14]为：

f(n)=g(n)+h(n)

(1)

式中，g(n)为起始点到当前点n的实际代价，h(n)为当前点n到目标点的估计代价，本文采用曼哈顿距离进行两点间的代价预估：

D=|xn-xg|+|yn-yg|

(2)

式中，xnyn分别为当前点n的横坐标和纵坐标，xgyg分别为目标点g的横坐标和纵坐标。

当前进方向为障碍物或为地图的边缘时，此时该方向的代价为无穷大。

由于传统A*算法所采用的启发函数主要进行距离的评判，因此当出现多个代价相同的节点时，算法将随机选择一个节点作为下一次搜索的起点，这导致了所规划的路径虽长度最短，但拐角数并非最优的问题。

2.3 基于多元启发函数的A*算法

针对上述的问题，本文在原有A*算法的基础上，添加了拐角数的评判指标，构成多元启发函数。当算法中出现多个代价相同的候选节点时，触发拐角数评判机制，对行进至候选节点的路径上的拐角数进行比较。改进后的启发函数表达式如下：

f(n)=g(n)+h(n)+a×N

(3)

(4)

(5)

在改进后的启发函数表达式中，a为拐角数评判机制的触发函数，N为拐角数，m表示在原始启发函数中除n点外的最小代价点。

当存在两个及以上的最小代价点(即g(n)+h(n)=g(m)+h(m))时，式(5)中b=1，根据式(4)可得a=1，此时触发了启发函数中的拐角数评判机制，满足代价最小的点进行式(3)的比较，最终选择f值最小的点作为算法路径选择的下一个节点；当仅存在一个最小代价点时，b≠1，此时a=0，拐角数评判机制未能触发，故该点默认为算法路径选择的下一个节点。

拐角数的统计步骤具体如下：获取当前节点A的坐标(A1,A2)，节点A的父节点B的坐标(B1,B2)，以及节点B的父节点C的坐标(C1,C2)，当A1-B1≠B1-C1且A2-B2≠B2-C2，则说明路径出现了拐角，此时节点A的拐角数=节点B的拐角数+1。

改进后的A*算法具体步骤如下[14]：

(1)设置一个open列表和close列表，并将起始节点放入open列表中；

(2)遍历搜索open列表中存在的节点，根据启发函数确定代价f(n)大小，将f(n)值最小的节点n作为算法路径选择的下一节点，将该节点从open列表中删除并添加到close列表；若存在多个f(n)值最小的节点，则触发拐角数评判机制，选择拐角数最少的点作为下一个节点；

(3)判断节点n是否为目标节点，若为目标节点，则结束算法；否则，则进行下一步；

(4)搜索节点n邻域内所有符合搜索要求的子节点m，计算所有待搜索节点的f(m)值，选择f(m)值最小的节点m作为算法路径选择的下一个节点；

(5)若节点m不在open列表和close列表中，则将其添加到open列表中，并为子节点m添加一个指针指向其父节点n；若节点m在open列表中，则对比之前存储在open列表中的函数值，保留函数值小的数值；若节点在close列表中，则该节点已在当前最优路径上，返回上一步继续对比扩展其他子节点；

(6)循环步骤 (2)～步骤 (6)，但算法寻找到目标节点或open列表为空时，结束算法。

当算法寻到目标节点时，以目标节点为起点，沿着每个方格的父节点移动至起点，即可获取最优路径。算法流程图3所示。

图3 基于多元启发函数的A*算法流程

2.4 基于交通约束及多元启发函数的A*算法

在多AGV系统中，为了使AGV在自主规划路径的前提下，减少AGV间的路径重叠程度，降低AGV间的避碰几率，提高系统的工作效率，本文将交通约束法与改进后的基于多元启发函数A*算法相结合，实现AGV的路径规划。

多AGV系统的运行流程图如图4所示，单台AGV在获取地图信息后，根据地图上各点的交通约束条件，调用基于多元启发函数的A*算法进行路径规划；当AGV的制定的路径遇到其他AGV时，根据两者的优先级进行避让行为。

图4 多AGV系统运行流程图

3 仿真与分析

为了验证改进后的基于交通约束及多元启发函数的A*算法的效果，本文在MATLAB软件上进行算法仿真，其中起始点和目标点的位置是随机生成的。栅格的大小为12×10，代表AGV路径规划区域的大小，黑色的方格代表障碍物的位置。

本文通过实验对传统的A*算法(记为算法1)、基于多元启发函数A*算法(记为算法2)和基于交通约束及多元启发函数的A*算法(记为算法3)所规划的路径进行对比、分析。

实验1：单台AGV的路径规划。起点为(2，11)，目标点为(9，2)，具体的仿真结果如图5所示，图中圆点为起点，方点为目标点。

(a) 算法1 (b) 算法2(c) 算法3

为了更好地验证改进A*算法的优越性，本文将实验1中3种算法在路径长度和拐角数量两项主要指标进行了比较，如表1所示。

表1 三种算法在实验1中的结果比较

通过对仿真图的观察以及对路径长度、拐角数量这两项指标的对比结果的分析可知，算法1虽能够规划出长度最短的路径，但是该路径拐角数多，路径复杂程度较高；而算法2和算法3可在规划出长度最短的路径的同时，尽可能地减少拐角数，以降低路径的复杂程度。

由于在实验1中，无法有效地分辨出算法2和算法3的优劣势，因此，本文再次进行实验，对算法2和算法3进行对比分析。

实验2：多台AGV的路径规划。1号AGV的起点为(9，2)、目标点为(2，11)，2号AGV的起点为(2，11)、目标点为(9，2)，具体的仿真结果如图6所示，其中图6a、图6b分别为算法2和算法3所规划的路径，图中圆点为起点，方点为目标点，1号AGV的路径为黑色，2号AGV的路径为灰色。

(a)算法2(b)算法3 图6 不同算法在实验2的规划路线

通过对仿真图的观察可知，算法2为两台AGV规划的路径存在大量相同的节点，此时两台AGV在行进的过程会产生对遇的局面，进而出现死锁现象；而算法3在交通规则的约束下，为两台AGV规划了无相同的节点的路径，使得两台AGV无避碰、高效地达到目标点。

4 结论

在移动机器人得到广泛应用的时代，路径规划是一个重要的研究领域。本文针对多AGV同时运行容易出现碰撞的情况以及传统A*算法所规划的路径存在拐角数多的问题，在传统A*算法的基础上引入了交通约束条件，并在原有启发函数的基础上，添加了拐角数评判机制，构成多元启发函数。采用栅格法进行环境建模，并在MATLAB实验环境下进行两组的实验，实验结果表明，在多AGV的环境下，相比于传统的A*算法，基于交通约束及多元启发函数的A*算法所规划路径合理，拐角数量优于传统A*算法，且能有效地降低AGV间地碰撞几率，降低AGV完成路径的能耗，增强系统的稳定性，具有一定的应用价值。