文 / 龚志锋 石 超 闫 丰 陈建银

随着电子商务高速发展，对仓储物流的效率要求越来越高，随之而来的便是以仓储物流机器人（AGV）为代表的自动化浪潮，智能仓储的概念也应运而生，以在提高仓储拣选效率的同时，应对不断上涨的劳动力成本。目前，拣选作业是库内最主要的环节，至少占据50%的库内操作成本，决定着客户的服务体验水平，因此如何利用物流机器人进一步提升拣选作业效率，对仓储物流具有重要意义；而高效的路径规划算法，正是决定物流机器人作业效率的关键因素，是物流机器人能够流畅运行的核心之一。

一、研究背景

A＊算法是一种常用的启发式路径查找和图形遍历算法，其改进自Dijkstra算法，拥有较好的性能与准确度。但是对于AGV而言，最短路径往往并不是最合理的路线，其路线具有更多的影响因素：

1. AGV与机动车一样，一般只能够向前行走，转向需要花费额外的时间，因此路线应尽可能减少转向次数。

2. 多辆AGV同时运行时，其互相之间路线会出现相交与冲突，规划路径时应尽可能避免路线冲突。

3. 当AGV不可避免的出现拥堵时，能够根据当前路况重新规划一条新的路线。

针对以上影响因素，本次研究遵循A＊算法的基本方法，对A＊算法中的的F值计算进行更加深入的探索，使其计算方法更加合理，能够更好地契合AGV的路线规划需要。

二、算法思路

本文最终将算法通过仿真程序实现，考虑到影响AGV行走的各项因素，具体会从A＊算法的F值计算与任务管理两方面着手，二者配合以实现AGV的流畅运行。

1. 代价值计算优化

为了使逻辑思路更加清晰，本文使用结构体来表示每一个节点。

（1）转向代价

原A＊算法中计算F值时，由移动代价与估算成本相加得到，当有多条最短路径时，其只会随机返回一条最短路径，并没有考虑路径的拐弯因素，而现实情况是，AGV需要停止后才能进行原地旋转，会花费额外的时间。对此，本文在计算中加入反映AGV旋转的转向代价，使得到的结果更加偏向于直线行走。

原F值计算公式为：

式中：

F，当前节点的总代价；

G，从起点移动到当前节点的移动代价；

H，当前节点到终点的估算成本，

本文采用曼哈顿距离。

在公式中加入新的变量R，代表AGV的转向代价。如图1所示，共有3条路线，分别为ADE、BDE、CDE，当前研究节点为E，其父节点为D，其中2条路线将会发生旋转，因此对于节点E，关键在于判断从D到E是否会发生旋转。

图1 转向情况

从图1中可以发现，ADE、CDE这两种情况下需要进行旋转，BDE不需要旋转，而A、C这两个节点与E节点的横纵坐标完全不同，B节点与E节点的横坐标相同，由此可以做出推断，一旦当前节点与父节点的父节点坐标完全不一致，则由父节点到达当前节点就需要进行转向，否则不需要且R为0，

因此，新的F值计算公式为：

增加的R，便是转向代价。

（2）路径冲突代价

由于实际生产情况下，通常都会是几十台AGV同时运行，若仍然给每台AGV独立规划路径，则必定会出现不同AGV的路径相互干扰甚至冲突的状况，因此需要在为每台AGV进行规划路径时，考虑已规划路径AGV的影响，引入路径冲突代价D，从而将所有AGV间的相互干扰降至最小。

为了能够更好地判断各条路径间的关系，需要构建一张公共地图，在地图的每个节点上存储当前节点的信息与每条路径对该节点的占用情况，以供AGV规划路径时进行查询。

判断是否会在当前节点产生冲突时，首先查询当前的地图节点，读取当前地图节点所有AGV的占用信息，然后和当前规划路径进行比对，若产生冲突则赋予冲突代价D一个较大的值，否则D为0。进行判断时，首先计算当前规划路径对该地图节点的占用时间区间是否与已规划路径的占用时间区间相交，若时间发生冲突，则进一步判断两条路径的方向是否相向，若相向，则认为路径冲突。

如图2所示，中央的格子为当前计算的地图节点，O为已规划路径离开当前地图节点的方向，A、B、C、D为当前规划路径移动至当前地图节点的可能方向，其中A、C、D方向的情况下，AGV只需等待一小段时间，等前面的车辆离开便可以成功移动，而B方向与已规划路径的离开方向是相向的，可以认为B方向与已规划路径存在冲突。

图2 路径冲突

此外，每当路径规划完毕，便会返回一个终点的路径节点，此时需要根据新路径的信息对地图节点进行更新，以用于后续新路径的规划。

最终，总代价的计算更新为：

增加的D，便是路径冲突代价。

2. 任务管理优化

仿真程序主要由AGV模块与任务管理模块构成，通过定时器触发各主要对象的更新，AGV模块与任务管理模块通过Qt的信号与槽机制进行交互。

路径规划并不能做到万无一失，当现场道路狭窄而AGV数量比较多的时候，发生拥堵的概率仍然会比较高，因此在合理的时机命令被堵住的AGV重新规划线路是十分有必要的。

图3 AGV单次任务循环

表1 AGV任务单次循环

（1）AGV模块

AGV仅有两种状态，空闲与任务，空闲时在原地等待，有任务时行走。

如图3所示，通过定时器触发AGV自身的任务循环，同时需要不断更新AGV对地图的实际占用情况以更好地规划路径。AGV若有任务在身时，便会首先对下一个目标位置进行碰撞检测，若移动至下一节点会发生碰撞则停在原地并发出碰撞信号，任务管理接收信号后便会进行碰撞计数，若连续碰撞多次，则会触发重新规划路线，否则就移动至下一节点并释放上一节点，若AGV处于空闲状态则要发出信号占据当前停留节点。在这一循环中共有3种信号，对应到任务管理模块中便有3个槽进行接收和处理。伪代码如表1所示，可以看出AGV发出的信号都需要任务管理进行处理。

图4 任务管理模块单次循环

图5 输入模块与订单输入信息

同时，AGV需要2个槽用于接收任务管理模块发送的信号，其具体功能为：

槽4，用于处理信号4，此时任务管理模块发布了新的任务坐标与路径，AGV需要进行接收并更改自身的目标与路径，并将AGV状态更改为任务状态。

槽5，用于处理信号5，此时AGV经过了连续多次碰撞检测发现无法继续前进，需要接收来自任务管理模块新规划的路径，并按照新路径的指引继续前进。

（2）任务管理模块

任务管理模块同样拥有自身的任务循环，由定时器触发，同时带有4个用于处理AGV信号的槽。其中，任务管理模块的循环主要逻辑为：遍历所有AGV，对其中处于空闲状态的设备发布新的任务，调用A＊算法算出路径后，将路径通过信号4发送给对应的AGV，具体流程，如图4所示。

任务管理模块用于处理AGV信号的3个槽的具体功能为：

槽1，用于处理信号1，此时AGV处于空闲状态并停留在了原地，此时任务管理模块需要将地图节点中对应节点的agvOccupied属性更改为true，如此在规划路径时便会避开此节点。

图6 动画模块

槽2，用于处理信号2，此时AGV按照路径前往下一节点，因此需要保证AGV即将离开的节点的agvOccupied属性为false，同时将对应AGV的碰撞检测计数清零。

槽3，用于处理信号3，此时AGV经过碰撞检测认为移动至下一个节点会发生碰撞，任务管理模块会进行碰撞计数，若计数达到一定次数，则会触发重新规划路线，并通过信号5将新的路径发送给指定AGV。

在AGV与任务管理模块的循环、信号、槽的相互配合下，便可以实现较为合理的AGV路线重规划，从而降低堵塞概率。

三、仿真实现

为了验证路径规划算法的可行性，本文在Qt Creator中采用C++编程语言建立一个可视化仿真系统，用于模拟在仓储物流中物流机器人的批量路径规划。

图7 规划结果

1. 仿真系统介绍

仿真系统主要由输入模块与动画模块构成，输入模块负责接收用户的参数，动画模块负责将仿真结果实时演示给用户。

（1）输入模块

如图5所示，在输入模块中，用户可以使用Excel软件定制仓位信息与订单信息，仿真程序便可以读取Excel文件，仿真开始后程序可以根据用户的仓位与订单给AGV下达拣货任务。同时，在输入模块中，用户可以自定义AGV与拣货人员的数量从而在观察路径规划算法有效性的同时得到不同人机配比下的拣货效率。

（2）动画模块

如图6所示，动画模块负责将仿真结果实时输出到画面上，让用户能够更直观地了解仿真的情况，观察哪边容易发生拥堵。同时，仿真的地图可以根据需要进行修改，对应的，仓位信息同样需要同步修改。

2. 有效性验证

最后通过人为制定具体的AGV点对点任务以验证算法的有效性，如图7所示，有4个点对点任务，分别指派给4台AGV，任务具体为：A1-A2、B1-B2、C1-C2、D1-D2。

将任务导入程序后观察AGV的实际行动路线。如图7所示，AGV的行动路线基本符合算法的思路，在预计会产生冲突时，采用了绕行的路线。

此外，通过生成较多数量的AGV并派发相对重复的订单，还原AGV产生拥堵的情况，经过测试可以发现，当AGV在原地拥堵超过一定时间后，其便会掉头沿着新的路线继续行走，如图8所示，中间最下方的AGV的目的地为当前巷道的上方，由于前方发生了拥堵，因此其掉头寻找新的路线，说明任务管理模块发挥了作用。

图8 自动规划新路线

四、结论

本文在A＊算法的基础上对物流机器人的拣选路径进行了系统性研究，针对现场实际出现的问题提出了对应的解决方案，并利用C++编写仿真系统对解决方案进行了有效性验证，最终得到如下结论：

1.构建公共的地图占用信息，有助于更加合理地进行AGV路径规划。经过本文的探索可以发现，AGV在预测路况的条件下可以有效避免路径冲突的发生。

2.在A＊算法中加入转弯代价，可以有效避免AGV在规划路径时因随机性导致转弯过多的情况。

3.合理的任务管理机制，可以有效疏通堵塞情况，本文采用了相对较为简单的次数触发机制，配合地图信息的实时更新，使AGV在狭小通道相互妨碍而停滞时能够自动绕路。