随着电子商务的快速发展，其对仓储业提出了更高的要求。中国物资储运协会会长姜浩峰指出，电商对仓储业的需求主要体现在仓储和配送两个方面，要求仓储实现快速响应，准确地入仓、完成货位管理，快速准确分拣[1]。作为智能仓储的重要组成部分，物流机器人主要完成仓储包裹分拣、传输等工作。路径规划是物流机器人导航过程中的一个重要环节，而物流机器人属于移动机器人中的一种，移动机器人的路径规划是指机器人基于环境信息规划出一条从起点到终点的无碰、安全的可行路径，并尽可能地优化路径[2]。机器人路径规划的常用方法有可视图法、人工势场法、A*算法、人工智能算法等。智能仓储环境下的物流机器人路径规划方法主要有A*算法[3]、遗传算法[4]、蚁群算法[5,6]、强化学习算法[7]及算法融合[8,9,10]。其中，文献[4]分别基于人工鱼群算法、遗传算法、A*算法解决仓储系统中多机器人小车路径规划问题，结果表明，在多机器人仓储系统路径规划中，改进A*算法完成所有任务的时间最短，总的路径步数也最少。

A*算法是Dijikstra算法的一个扩展，它利用等代价搜索和启发式搜索来有效地计算最佳优先搜索，使用的时间更少[11]。文献[12]针对仓储物流中移动机器人的多任务调度问题，提出复杂对角线距离算法，改进A*算法的启发函数，实现调度系统中移动机器人的总任务完工时间最短，但规划之后的路径仍存在冗余节点。针对A*算法规划出的移动机器人路径存在折线多、转折次数多、累计转折角度大等问题，研究者们主要提出了平滑路径的解决方案。例如，文献[13]在A*算法的初始路径规划的基础上，遍历路径中的所有节点，删除冗余节点，建立平滑A*模型，以极低的计算时间损失有效地降低移动机器人规划路径的长度、转折次数和转折角度,适用于复杂环境的路径规划。而文献[14]在A*算法的初始路径的基础上，通过划分路径步长、删除冗余路径节点的方法，有效地减小路径长度和转折角度，适合多任务点、高障碍率环境下的移动机器人路径规划。但智能仓储环境与一般机器人的工作环境大不相同，仓储环境中布满货架，物流机器人的可行空间有限，障碍物形状规则，因此，智能仓储环境下的物流机器人的路径规划有别于一般移动机器人。对于智能仓储物流机器人而言，不仅要求规划的路径最短，同时，也要求转折角度小，转折次数少，从而便于物流机器人的运行控制和安全作业。文献[15]在A*算法的基础上进行改进，在代价函数中加入转向代价和路径冲突代价，实现多物流机器人的路径规划，但具体的代价值比较难确定。

综上，针对A*算法规划的路径存在转折点和冗余点过多的问题，现有的研究主要采用删除冗余节点的路径平滑方法，较少考虑智能仓储环境的特殊性。因此，本文首先探索了A*算法中不同启发式距离函数对智能仓储环境下路径规划的适用性；其次，针对A*算法在路径规划中存在较多转折的问题，提出一种适用于智能仓储环境路径规划的L型路径趋势的改进A*算法。

智能仓储系统一般由拣选工作台、货架、物流机器人等组成，对于物流机器人而言，拣选工作台、货架、其他物流机器人等都是障碍物。

为便于研究且不失一般性，本文在智能仓储系统的环境建模时做出以下合理假设：

(1)拣选工作台、货柜等障碍物边界是在实际边界的基础上加一个物流机器人安全距离；

(2)把物流机器人看做是一个质点，暂不考虑其高度，且物流机器人可以在任意方向移动；

(3)在路径规划过程中，仓储环境信息不变。

常用的环境建模方法有几何法、可视图法和栅格法等。栅格法是将环境分割成大小相等的方格单元的一种建模方法，被广泛用于描述二维信息，具有简单有效的特点，因此，本文采用栅格法进行智能仓储环境的建模，同时以经典物流系统———KIVA系统中的仓储布局模式为参考，建立了一个51×16的栅格化智能仓储环境（如图1所示，在实际应用中，可以根据实际需要设定智能仓储环境的规模和货架布局）。其中，紫色矩形为拣选工作台，黑色矩形为货架，青色小方格为障碍物（其他物流机器人等），红色为起始位置，蓝色为目标位置（目标货架），白色为通道。

本文设计基于改进A*算法求解智能仓储环境下，物流机器人从起始位置到目标位置的无碰撞最优路径。

图1 智能仓储环境的模型  下载原图

A*算法由Dijkstra算法演变而来，是一种启发式算法。A*算法通过估价函数引导和决定路径的搜索方向。从起点开始搜索当前位置相邻的8个周围节点，由估价函数表示每个节点的价值，选择价值最低的节点作为下一个扩展节点，循环这一过程直到到达终点停止搜索，从而获得最终的路径规划结果。因为每次搜索都选择价值最低的节点作为扩展节点，因此，最终获得的路径代价是最低的。

A*算法的估价函数f(n)表示如式（1):

其中:f(n)表示从起始位置经过节点n到达终点的估价函数；g(n)表示从起始位置到节点n的实际代价函数；h(n)表示从节点n到终点的估计代价函数。

通常，估计代价函数h(n)可以使用欧几里得距离或曼哈顿距离作为启发函数，因为曼哈顿距离只涉及加、减法，和欧式距离相比较，节约算法的运行时间，提高算法效率。相比于一般移动机器人的工作环境，智能仓储环境中布满货架，曼哈顿距离显然更适用。因此，本文采用曼哈顿距离作为节点间的启发函数，即

其中：（xd,yd）为目标位置的坐标；（xn,yn）是节点n的坐标。

A*算法在搜索路径过程中，需要不断更新两个列表，一个是开启列表，另一个是关闭列表。开启列表存储所有周围的节点。A*算法从开启列表中选择估价值最小的节点作为下一个扩展节点。关闭列表存储所有经过的节点和环境中的障碍物所在节点。

通过A*算法计算，得到智能仓储物流机器人的初始路径规划。

传统A*算法计算的路径类似“锯齿形”路径，存在转折过多，转弯过多的问题。智能仓储环境不同于一般的移动机器人所处的环境，智能仓储环境中障碍物主要是货架、拣选工作台、随机障碍物等，这些障碍物都是规则、有序且相对固定，轮廓近似矩形。与此同时，智能仓储环境中的通道规则且狭窄，可行空间相对有限，因此，“锯齿形”路径主要出现在拣选工作台附近的局部区域。从起始位置S到目标位置T形成的最终路径可以近似看做是L趋势，当各部分路径都和该L趋势一致时，则该路径的转弯节点最少。

本文根据起始位置S与目标位置T的几何关系，构造4种L型路径趋势的标识，分别为L1（实线）、L2（实线）、L3（实线）和L4（实线）。

图2 L型路径趋势的标识示意图  下载原图

路径趋势标识的构建方法。以L1型路径趋势标识为例，起始位置S在目标位置T的左下方，延长S、T所在直线构成直角（D），构建L1型路径趋势标识。同样地，S在T左上方时，构建L2型路径趋势标识；S在T右上方时，构建L3型路径趋势标识；S在T右下方时，构建L4型路径趋势标识。

路径趋势标识的使用方法。在A*算法规划出初始路径之后，依据“尽可能使局部路径与S、T构成的路径趋势一致”的原则，通过路径趋势标识进行优化。具体规则如下：局部路径中，邻近的3个节点（k-1、k、k+1）构成L型链路时，判断其与当前L型路径趋势标识是否匹配（依据：局部链路的L型与S、T构成的路径趋势标识L刚好组成一个回路）；如果匹配，判断局部链路中间节点k的对角节点D（组成回路的对角）是否为障碍物，如果不是障碍物，则将对角节点D替换该节点k。

以L1型路径趋势标识的优化为例。当前，S与T构成L1型路径趋势，初始路径中局部路径k-1、k、k+1三个节点构成的链路（绿色点划线所示），呈现出L型形状，（从S、k-1、k、k+1、T路径出现了锯齿形状，存在3个转弯），因此需要进行优化。现判断D节点是否为障碍物（拣选工作台、货架、其他障碍物等），如果是，则不处理；如果否，则节点k替换成节点D。此时，链路变成S、k-1、D、k+1、T，该链路中，只有1个转弯，从而，减少了转弯的节点，使路径变得平滑。其他L型路径趋势标识的优化方法以此类推。

基于A*算法的智能仓储物流机器人的L型路径优化流程如图3。

本文通过MATLAB2015软件（Math Works公司）对所提出的基于改进A*算法的智能仓储物流机器人的路径规划进行仿真验证。首先设置智能仓储环境，包括仓储边界、货架、拣选工作台、物流机器人初始位置和目标位置、随机障碍物位置等信息。其中，起始位置S的栅格坐标为（5,6），目标位置的栅格坐标为（25,11）。其次，设计A*算法求解从起始位置到目标位置的初始规划路径。

为探索曼哈顿距离与文献[12]提出的复杂对角线距离对智能仓储环境路径规划的适应性，本文分别求解基于以上两种距离公式的A*算法初始路径。结果如图4～5所示。

图3 基于改进A*算法的智能仓储物流机器人的路径规划流程图  下载原图

图4 基于复杂对角线距离A*算法的智能仓储物流机器人的初始路径规划结果  下载原图

图5 基于曼哈顿距离A*算法的智能仓储物流机器人的初始路径规划结果  下载原图

图中灰色表示已访问的栅格，灰白色代表在访问列表中。图4中点实线表示基于文献[12]提出的复杂对角线距离公式获得的A*算法初始路径，图5中点实线表示基于曼哈顿距离公式获得的A*算法初始路径。观察发现，两种距离公式最终规划出的路径一致，均成功避免了与货架等障碍物相碰，并且找到了从起始位置到目标位置的规划路径。

表1 基于不同距离A*算法的智能仓储物流机器人的初始路径规划结果  下载原图

表1 基于不同距离A*算法的智能仓储物流机器人的初始路径规划结果

表1的数据说明，基于文献[12]中的复杂对角线距离公式获得的A*算法初始路径与基于曼哈顿距离获得的A*算法初始路径总长度一致，都是25单位长度，但前者算法运行时间为7.46 s，后者运行时间为7.23 s。这个结果表明，对于智能仓储环境，曼哈顿距离在算法运行时间上更有优势。因此，本文在改进A*算法时采用曼哈顿距离公式。

进一步观察以上两条初始路径，可以发现，A*算法求解的初始路径中有5个转折，路径不够平滑。

在实验中，分别用平滑A*算法和本文提出的L型路径趋势标识对A*算法获得的初始路径进行优化。首先参考文献[13]的平滑A*算法，在A*算法初始规划路径的基础上，遍历所有节点，若某一节点的前一节点与后一节点连线未经过障碍物，则剔除本中间节点，从而减少转折节点和转弯过多的问题。结果如图6所示。

图6 基于平滑A*算法的智能仓储物流机器人的路径规划结果  下载原图

其中o-实线表示采用平滑A*算法获得的从起始位置S到目标货架T的优化路径。

其次，采用本文构造的L型路径趋势标识对A*算法初始路径中的局部路径进行优化，结果如图7所示。

图7 基于L型路径趋势改进A*算法的智能仓储物流机器人的路径规划结果  下载原图

其中*线表示采用L型路径趋势标识优化后的从起始位置S到目标货架T的优化路径。

A*算法改进前后智能仓储物流机器人的路径规划结果比较见表2。

表2 A*算法改进前后智能仓储物流机器人的路径规划结果比较  下载原图

表2 A*算法改进前后智能仓储物流机器人的路径规划结果比较

与A*算法规划的初始路径比较可以发现，平滑A*算法中，路径长度较初始路径减少8.7%；转折节点减少2个，减少率为40%；累计转弯角度减少225°，减少率为50%，即在一定程度上达到了减少路径总长度、转折节点数和累计转弯角度的效果。与A*算法初始路径比较，L型路径趋势改进A*算法，其路径总长度没有减少，但转折节点减少3个，减少率为60%；累计转弯角度减少270°，减少率为60%。L型路径趋势改进A*算法减少转弯节点率较平滑A*算法高20%,L型路径趋势改进A*算法减少转弯角度率较平滑A*算法高10%，对于布满货架、可行空间有限的智能仓储系统环境而言，相较于路径总长度的减少，对减少转弯次数和转弯角度的需求更迫切，一方面便于控制物流机器人的转向，另一方面，更有利于作业安全。与此同时，L型路径趋势改进A*算法的运行时间较平滑A*算法运行时间短，在大规模智能仓储环境的路径规划中，算法运行时间短显然更有优势。

本文建立了栅格化的智能仓储环境。采用A*算法求解智能仓储物流机器人的路径规划，获得了一条从起始位置到终点位置的无碰撞安全路径。仿真实验结果表明，与文献[12]提出的复杂对角线距离比较，曼哈顿距离更适用于智能仓储环境的路径规划。针对A*算法求解最优路径时存在转折点过多和转弯角度过大的问题，提出了一种基于起始位置与目标位置构建的L型路径趋势方法对A*算法规划的初始路径进行局部优化。仿真实验表明，L型路径趋势局部优化方法能够以微小的算法运行时间为代价有效地减少A*算法规划路径中的转折次数和累计转弯角度，使物流机器人的路径趋向于总体路径方向，路径更加平滑，有效提高仓储的作业安全和效率。本文研究的是智能仓储环境中物流机器人的全局路径规划问题，将来，可以在此基础上考虑动态障碍物及避碰策略，更加有效地对物流机器人进行协同调度和路径规划。