基于A*算法的配送中心“货到人”拣选法AGV路径规划研究

张洪涛，苏凯凯，何震，林雪成，郭曼曼

（1.大连海事大学，辽宁 大连 116026；2.天津科技大学 天津 300457；3.大禹节水（天津）有限公司，天津 301739）

传统仓库系统主要依靠人工进行存储和拣选作业，需要员工手动查找物品，这种方式效率低下，很容易出现错误，导致服务水平低，且需要较多人力资源投入，增加了企业的人力成本。多台自动导引车协同人工拣选能够大幅提高作业效率，李腾[1]将AGV的运行阶段根据路段特征和交通情况进行划分，如直行、左转和右转等。在A* 算法中，引入一个转弯惩罚值，减少转弯的次数，从而达到更快的行驶速度和更高的效率。根据AGV 当前遇到的障碍物的等待时间，设置其避障的优先级，从而避免避障过程中的效率问题。在多AGV 路径规划中，A* 算法是一种重要的算法，多位学者对A* 算法进行了创新性研究，例如刘恒麟[2]改进后的A* 算法相较传统A* 算法在同样的路径成本下，转弯的次数减少了17%；并行化CBS 算法比传统CBS 算法路径规划运算时间降低了33.9%。廖凯文[3]采用拓扑-栅格法来建立地图模型，可以提高路径规划的效率和精度，即将拓扑图栅格化，并根据机器人的占空比将栅格化后的地图进行二值化处理。这一步操作可以将整个地图进行分解，将其变成一个一个的栅格单元。当多台AGV 从同一起始位置规划路径时，侯正[4]将OPEN 表分为公有OPEN 表和私有OPEN 表，其中公有OPEN 表存储了所有AGV 扩展节点和路径，提出了离线多AGV 路径规划算法即DC-CBS 算法。陈梦夏[5]发现DC-CBS 规划出的路径代价总和接近最优解，并且在较大或较小的规模中运行时间都比CBS 算法短。郭超[6]针对多AGV 协同作业场景中的无冲突路径规划问题，采用基于冲突搜索的两层路径规划架构来解决。对AGV 与环境进行建模，确定AGV 的启动和目标位置，并将地图栅格化表示为矩阵。其次，利用搜索算法来规划AGV 的路径。即采用两层搜索的方式，结合A* 算法和冲突搜索算法，可以有效规划AGV 在仓库内的路径，避免冲突并实现高效的物品搬运。

一、问题描述

本文所研究的“货到人”拣选系统主要流程如图1 所示[7]。针对某时间段的用户订单，根据订单需求、货架库存及补货需求生成拣货和上货任务指令，然后将所对应货架的搬运任务分配至AGV，由AGV沿算法规划的路线完成搬运拣选任务。以AGV 完成所有订单拣选任务的行驶路径最短为目标，研究“货到人”拣选系统下的AGV 路径规划。为简化模型，本文不考虑系统如何分析订单，通过设置货架优先级代表货架的重要程度，融合至AGV 的分配策略，从全局视角对AGV 进行路径规划。

图2 为货物存储分拣中心平面规划图，最下侧为AGV 充电区，AGV 无作业安排或者非工作时间可在此完成充电和停放。此模型安排3 辆AGV 小车完成各项作业，设定整个工作区域为64×64 个单位，AGV 每秒可以运行3 个单位。

规划图中间部分为存储区，每个特制货架有四层，货物放置于四层货位上，每个货位仅存放一种商品，一个货架可以放置四种货物。

规划图最左侧为上货区，将补货需求输入控制系统中，对需要补货的货架赋予更高的优先级，派遣AGV 至优先级高的货架下，AGV 将货架顶起，利用A* 算法进行路径规划，使货架到达上货区指定位置，完成上货作业。上货工作平台共三个，每个上货平台有操作员进行上货作业，将货物补货到相应位置。规划图最右侧为拣选区，有六个打包台，并配备六名拣选员，完成订单所需的拣选作业与打包作业，两个打包台为一组，共三组。

基于货架优先级，设计AGV 货架搬运任务分配方式，该方式考虑了订单拣选需求和商品补货需求，并根据货架的重要程度设置了优先级。对于订单拣选需求，将货架上具有更多所需商品种类和数量的货架赋予较高的优先级。通过优先搬运需求率更高的货架，可以尽早满足多订单者的商品需求，减少货架搬运次数，从而实现订单更快出库。对于商品补货需求，货架的优先级指的是货架中空货位的数量，可优先选取空货位更多的货架进行补货，加快补货速度。

二、地图选择以及冲突类型

（一）栅格地图法

栅格地图法将环境划分为多个栅格单元，如一个正方形或一个六边形。然后，使用传感器例如激光雷达、摄像头等，获取环境中的障碍物和地形信息，并将其映射到相应的栅格单元中，形成一张栅格地图。栅格地图法保存环境的静态信息，例如墙壁、障碍物等。由于栅格的尺寸可以调整，这种方法能够在不同的场景中应用。栅格地图法还可以使用快速的碰撞检测算法，让机器人在避免碰撞的同时进行导航，如图3 所示。

栅格地图法是一种简单且高效的方法，常用于工业机器人、无人机和移动机器人的环境感知与导航任务。本文的研究场景为存储拣选仓库，每个货架上都有上货和取货任务，需要准确地描述仓库中的障碍物信息和实际距离成比例的关系，地图构建的方法应具有普适性和扩展性。

（二）多AGV路径规划冲突类型

在多AGV 系统中，路径规划冲突通常是指两个或多个AGV 尝试占用相同的区域。相向冲突如图4所示[8]，当两个AGV 相向而行时，在狭窄的路径或交叉路口相遇，就会发生相向冲突。这种情况下，需要在路径规划时合理安排AGV 的运动方向或在交叉路口设置信号灯等手段避免冲突。

当一个AGV 追赶另一个AGV 并试图占用它正在占用的位置时，就会发生追及冲突。这种情况下，需要在路径规划中考虑AGV 速度、加速度等因素避免冲突，追及冲突示意图，如图5 所示[9]。

在多AGV 系统中，路口冲突是指在AGV 通过路口时，由于路口通道的容量限制或者不恰当的路径规划，导致多辆AGV 在同一路口等待进入通道或目标位置，甚至可能发生相撞的情况，路口冲突如图6 所示[10]。

三、多AGV路径规划

（一）多AGV路径规划模型建立

多AGV 路径规划问题较为复杂，随着作业场地的动态变化，路径规划也会随之动态调整。本文所考虑的场景是货物存储分拣中心仓库，利用AGV 配合人工完成对货物的拣选工作。本仓库内有3 台AGV 运载车，每台AGV 分别被派发了不同的运输与搬运任务，系统程序为每台AGV 各自规划互不碰撞的最优路径，但是由于作业场地的限制，搬运任务实施过程中必然有重合的路径。多AGV 路线规划可以建立数学模型来进行求解，其前提假设如下：

1.假设多台AGV 在同一时间只能处理一项任务，同一任务只能由一台AGV 执行；

2.每栅格点同一时刻只允许一台AGV 占用，当某栅格在某一时刻有AGV 通过时，其他AGV 在该栅格的通行状态为不可通过；

3.在规划期间，系统的整体状态不会发生改变，例如场地上的所有AGV 数量不会增加或减少，任务也不会跳出等；

4.AGV 运输车在结束本次移动任务后，才可接受系统调度的下一个移动指令；

5.每个AGV 车辆都具有相同的速度、最大负载、最大行驶距离和最大运行时间；

6.每个任务都有一个起点和终点，AGV 可以在两个节点之间完成任务。

（二）基于A*算法规划多AGV无碰撞最优路径

A* 算法通过评估从起点到目标点的代价函数，来引导搜索过程，以便尽可能快地找到从起点到目标点的最短路径。A* 算法的输入是在给定空间中的一个起始状态和一个目标状态，算法的输出是一个状态转移序列，表示AGV 的移动路径。当输入一个起始状态和终点状态后，A* 算法从起点开始向四周扩张节点，如图7 所示[11]，同时避开障碍物，每次扩张到列表中具有最小值的节点，直至扩张到目标节点为止，函数将记录的扩张节点顺序作为结果返回。

在计算代价时，A* 算法通常结合两个指标：节点到起点的代价和节点到目标点的估计代价。对于估计代价，A* 算法使用启发式函数，需要满足两个条件：一是启发式函数的返回值不超过节点到目标点的实际代价；二是启发式函数越小越好。一般来讲，A* 算法利用估计代价一般通过下列评估函数计算：

其中，n 为当前节点，g（n）表示从起点到当前节点的实际代价，h（n）表示从当前节点到目标点的估计代价，f（n）表示从起点到当前节点再加上从当前节点到目标点的总代价，优先考虑估计代价更小的节点，能保证找到的路径是最优解，如表1 所示[12]。

表1 符号定义表

将会用到的符号内涵为[13]：n 为栅格地图中的一个节点，n.x 为节点n 的横坐标，n.y 为节点n 的纵坐标，goal.x 表示目标节点的横坐标，goal.y 表示目标节点的纵坐标。欧几里得距离的算法是：

欧几里得距离通常用来计算在平面直角坐标系中两点间的距离，即两点之间的直线距离。本文算法选用欧几里得距离为h（n）的计算方式。A* 算法的具体流程，如图8 所示[14]：

（三）MATLAB实验仿真

1.入库作业

AGV 在没有作业任务时在充电区等候指令并完成充电。系统根据实时监测从而获得货架上的货物量，将缺货的货架赋予更高的优先级，并基于A*算法，将AGV 分配至优先级较高的货架处，利用AGV 自带的顶升装置把需要补货的货架顶起，搬运各个货架区域的货架至指定的上货平台，由上货平台的操作员完成上货作业。之后将货架再搬运至由来的位置，完成上货的全过程。图9 所示为路径规划仿真演示：用圆点代表AGV 小车，为简化模型，不考虑AGV 小车转弯减速等情况，假设AGV 小车匀速行驶，设置AGV 小车的平均时速为3 个单位每秒，并用不同线形不同颜色来表示不同的AGV 路径。

2.出货作业

布局图中一共有三个拣选平台，每个拣选平台分别为两个打包平台服务，本物流配送中心可为六个打包台服务。系统将三个分拣平台汇集的36 个订单进行分析，根据订单需求，匹配尽可能满足订单需求的货架。AGV 在充电区等候指令，系统将每个需要搬运的货架分配至距离货架最近的AGV。AGV 接到指令后，基于A* 算法进行寻路，将指定货架搬运至相应的拣选工作台。在路径规划中要实现避障并满足配送时间最短的要求。

分拣时的作业方式为人工播种式拣选，每个拣选平台都有两位拣选员完成对12 个订单的货物进行拣货。一个拣选平台为两个打包台服务，共用一个AGV 配送货架进行拣货。播种式拣选提高了拣选的效率，减少了AGV 移动距离，达到了降本增效的目的。图10 为出库作业时AGV 路径规划模拟结果。

图1 分拣系统的工作流程图

图2 货物存储分拣中心规划图

图3 栅格地图法图

图4 相向冲突示意图

图5 追及冲突示意图

图6 路口冲突示意图

图7 AGV八向移动图

图8 A*算法流程图

图9 入库路径规划仿真模拟图

图10 出库路径规划仿真模拟图

四、结论

物流是支持电子商务发展的核心基础行业，因此高速发展的电子商务也推动了物流行业进入新的阶段。许多企业都在对物流分拣中心场地进行扩张和无人化、智能化升级，引进多AGV 系统是目前最普遍最有效的实现方式。本文分析了AGV 作为搬运货物主要运输工具的优势以及AGV 配合人工拣选的优势，考虑了多AGV 路径规划时的路径冲突，使用A* 算法规划路径。采用栅格法建立地图模型，建立以各AGV 路径最短为目标的数学模型，提出了适用于自动化仓库环境的AGV 路径规划算法。