基于平滑A*算法的仓储物流机器人路径规划

冯京伟，陈海霞，刘天鹏

(三江学院 机械与电气工程学院，江苏 南京 210012)

0 引言

电子商务迅猛发展，为仓储物流带来了新的需求和挑战。其发货单位小型化，品种多、批量小、批次多、周期短，传统依靠人工的仓储物流难以适应新的需求，基于移动机器人的自动化仓储技术正在兴起。将自主移动机器人引入仓储空间中，代替人工搬运货物，可以有效地减少工人的劳动强度，降低维护成本，提高运行效率。要实现一个机器人化的自动化仓储环境，关键的问题就是移动机器人的路径规划，使机器人在自动避障的前提下，规划最优路径到达目标点。

1 A*算法路径规划的优势

1.1 常见的路径规划算法

目前，已有多种算法被应用到路径规划中。传统算法主要有图形方法和智能方法，其中图形方法包括路图法、栅格法等；智能方法包括遗传算法、蚁群算法、Dijkstra算法等智能算法及其混合形式也用来解决路径规划问题。在智能算法中，如遗传算法存在编码长度变化范围大，求解效率低，求解规模小等问题[1]。Dijkstra算法直接搜索全局空间而不考虑目标信息，导致路径求解时间长，难以满足快速规划路径的需求[2]。

1.2 平滑A*算法的基本思想和优点

f(p)=g(p)+h(p)

(1)

其中，f(p)是代价函数，g(p)是起点到当前节点p的最短路径值，h(p)是当前节点n到目标的最短路径的启发值。当新的g(p)值大于之前的g(p)，则用新g(p)代替之前的g(p)；而h(p)的替代原则刚好相反，当新的h(p)小于之前的h(p)值才发生替代。应用这样的代价函数策略，是可以找到最短路径的，也就是可采纳的。这种应用这种代价函数的最好优先算法就是A*算法的基本思想。

A*算法规划后的路径存在一些问题，比如很多折线和转折点，不适用于仓储物流机器人的运行特点。为了提升线路质量，深入研究A*算法并进行改善，建立平滑A*算法方法并给出比较结果。仿真结果表明，平滑A*算法进行的路径规划更适用于仓储物流机器人的应用领域。

2 A*算法程序仿真

2.1 设计概述

本设计将仓储物流机器人作为研究对象，实现其路径规划。

2.1.1 建立栅格地图

采用行列划分的矩阵存储方法在地图上建立的栅格，每个方格的坐标信息记录在栅格存储阵列中的第m行、第n列，记为G(m，n)。采用这种“栅格—存储”的映射办法，可以建立起整幅地图。建立栅格后，对模型进行信息的编码。编码格式的基本思想如下：

1——当前栅格有障碍；

0——当前栅格无障碍。

在实际应用中，机器人路径规划为二维结构化空间，假设障碍物的位置和大小已知，并且在机器人运动过程中，障碍物的位置和大小都不发生变化；用尺寸相同的栅格对 机器人二维工作空间进行划分，按照机器人及空间的大小确定栅格数目，栅格大小以机器人可以在其中运动为限[3]。

秉持分布式系统无法同时兼顾一致性、可用性与分区容忍性（CAP）原理[8]，中本聪设计了PoW共识机制。现阶段常见共识算法其中一类为证明类共识，即Proof of X共识方案，是在PoW共识方案之上的变种，将PoW改换为其余证明。PoW算法现阶段依然盛行，使用PoW共识的代表货币比特币依然占据最大市值。

2.1.2 算法流程

当从初始点向目标点移动时，据前述f(p)=g(p)+h(p)，A*算法会权衡g(p)和h(p)的值，每次进行主循环时，它检查f(p)最小的结点p，将在当前的open list中选择f值最小的相邻栅格作为下一个已选定栅格，并将当前已选定栅格作为该相邻栅格的父栅格，移入close list，将父栅格依次连接起来，完成寻路。

2.2 基本A*算法仿真

通过程序来在栅格地图上设置障碍物来模拟仓储空间中的货架，然后进行A*算法路径规划，如图1所示。

图1 障碍物格局

从图1可以看出，利用A*算法自动规划路径的转折较多，如果在实际应用中使用这个程序来控制机器人调度，虽然可以完成任务，但是在机器人每次遇到障碍物需要转弯时，就必须减速到零转弯，然后再启动加速，如果连续遇到多个障碍物，那么机器人的运行时间将会加长；而且不断地启动停止，不仅使机器人的能耗增加，而且对机器人本身的寿命也有所影响，所以必须对机器人的路径进行平滑。

2.3 路径平滑方法

本文研究了多种路径平滑方法，以下两种平滑方法的路径模拟运行仿真如图2所示。

图2 平滑后曲线

(1)利用MATLAB软件自带的函数smooth函数。yy=smooth(y，span，sgolay)，式中yy为平滑后的纵坐标值，y为原纵坐标值，span为移动平均滤波器的窗宽，span为奇数，sgolay为Savitzky-Golay滤波器的窗宽，由span参数指定；横坐标也做相同的处理。

(2)自定义函数SmoothPath。基本思想是对原路径进行分析，设置权重和平滑因子，根据原路径与新路径当前点的差值进行加权，并对路径中上一个点、下一个点与当前点的差值乘平滑因子，在一定的容忍度范围内，自动进行重复计算，得到平滑后的新路径。

3 结语

针对A*路径规划算法在仓储物流机器人应用中的不足，提出了改进的A*路径规划算法，引入平滑路径的处理，不仅优化了路径，且能平滑转折角度，仿真结果验证了算法的有效性。实际应用中平滑A*算法为障碍物随机分布、大规模栅格情况下机器人规划出的路径有转折次数少、转折角度小等优点，能满足工程需求。