高密集度AGV快递包裹分拣系统的路径规划①

贺学成,吕淑静,吕 岳

(华东师范大学 上海市多维度信息处理重点实验室,上海 200062)

1 引言

随着电子商务的迅猛发展,快递包裹数量的急剧增加,传统的人工分拣已不能满足要求,交叉带分拣机等自动分拣系统虽然分拣效率较高,但占地面积大,一次性投入成本高,而且一旦建成就不可改变,柔性和灵活性差,能耗高.自动引导小车(AGV)高度的灵活性和低能耗可较好的适应现代物流“多品种、小批量、相对集中”的特点[1].因此基于AGV 的快递包裹分拣系统成为智能物流近年来的热点之一,其研究具有重要的实用价值.

早期的AGV 运行时只能单向行驶,因而适用环境受到局限,主要应用于仓储、制造、港口码头、机场等领域完成物料搬运.在这些行业中,AGV 的应用大多表现出工作独立,固定轨道,行驶速度慢以及密集度低等特点[2,3].随着AGV 技术的发展和成熟,AGV 的运用也越来越广泛,在物流领域,轻小型的AGV 被用于快递分拣近几年成为自动化分拣的热点.不同于传统的AGV 应用场景,在快递分拣系统中,为了满足分拣效率的要求,通常会设几个甚至十几个上包点,同时进行任务分发,这就要求增加场地中AGV 的数量以便及时处理这些任务.在固定大小的场地中,AGV 数量的增加会使得场地内AGV 密集度增加,这就使得基于AGV 的快递包裹分拣场地中AGV 数量较多、密集度较高.

我们定义密集度为可行走区域内单位面积内AGV 小车的数量.在实际系统中,通常密集度超过0.05 辆/单位面积,就可称为高密集度,低于或者等于0.05 辆/单位面积称为低密集度.基于AGV 的快递包裹分拣是比较典型的高密集度AGV 应用场景.

传统的路径搜索算法根据对环境信息掌握的程度分为两种[4]：基于传感器信息的局部路径规划和基于环境先验信息的全局路径规划.局部路径规划主要方法有人工势场法[5]、蚁群优化算法[6]、粒子群算法[7]、A*算法[8]等.全局路径规划主要方法有可视图法[9]、自由空间法[10]、栅格法[11]等.人工势场法容易产生死锁,适应能力较差,不能够满足AGV 动态环境中实时规划路径的要求.粒子群算法容易陷入局部极值点,而且若参数选择不当,会导致寻优过程中粒子的多样性迅速消失,造成算法“早熟收敛”.蚁群优化算法计算量大、收敛速度慢、求解所需时间较长,不适合实时规划.自由空间法和可视图法建立拓扑网络的过程相当复杂.最重要的是这些路径规划算法都仅考虑了AGV 自身因素,忽略了其他AGV 移动对其产生的影响,在高密集度、AGV 可自由行走的情况下,容易造成拥堵.通常情况下,AGV 密集度越高,场地的利用率也就越高,分拣效率也就越高,但是场地中AGV 的密集度增加到一定程度后,会导致拥挤,甚至堵塞,使得分拣效率下降.针对这种情况本文提出CAA*(Congestion-Avoidable A*)算法,算法以动态环境模型为基础,对各个节点拥堵情况进行预测,在路径规划时规避潜在的拥挤节点,避免拥堵情况的发生.为了验证本文算法避免拥堵的有效性,本文分别使用CAA*算法和A*算法进行了一系列仿真实验.实验表明,本文算法在高密集度AGV 场景下确实能避免拥堵,增加场地AGV 的密集度,提高场地的分拣效率.

2 动态环境模型

路径规划包含两个方面,一是建立环境模型,即对AGV 工作空间(环境信息)进行有效表达,是AGV 导航定位的基础[12].二是进行路径搜索,即寻找从起点到终点符合条件约束的路径.以往的路径规划中环境模型往往是静态的,一旦确定,就不可更改,AGV 仅考虑自身因素,忽略了其他AGV 移动对其产生的影响,在高密集的场景下,AGV 可能相互拥挤,造成堵塞,降低整个系统的效率.因此,本文采用栅格法建立动态环境模型,栅格节点引入动态属性,AGV 在进行路径规划和移动时,其对周围的影响会实时的反映在地图上,其他AGV 在进行路径规划时通过对地图节点拥挤情况的判断,规避拥挤节点和潜在的拥挤节点.

2.1 场地栅格化

常见的建立环境模型的方法可概括为栅格地图法(grid map)[13]、几何特征地图法(geometric feature map)[14]、拓扑地图法(topologic map)[15]三种基本地图表示法.

栅格地图法是目前研究最广泛的方法之一.该方法将机器人的工作空间分解为多个简单的区域,这些区域称为栅格.由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径.栅格地图信息直接与环境区域对应,容易创建和维护,方便AGV 进行定位.本文采用栅格法来建立环境模型.以AGV 小车尺寸为基础确定栅格的大小,将场地映射成一系列规则的网格.

可通行的栅格被称为自由栅格；不可通行的栅格,称为障碍栅格.栅格的节点分为有方向和无方向两种,无方向即可以任意方向行走.有方向又分为八邻域方向和四邻域方向.根据快递包裹分拣AGV 的运动特性,AGV 只能水平和垂直方向行驶,不可斜向行驶,故本文栅格节点采用的是有方向的、四邻域的模型.

2.2 栅格节点的动态属性表示

给每个栅格节点增加一个将要经过该节点的小车信息集合,记为V,集合V中存储二元组＜I,T＞,I代表将要经过该节点的小车编号,T表示将要经过该节点的时间点.因为在实际运行时地面平整度、小车自身硬件、小车路径冲突等因素,所以很难准确的控制和预测AGV 小车到达每个节点的精确时间点,所以这个T是一个理想的估计值,允许一定的误差.

假设当前节点为n,则用Vn表 示节点n的小车信息集合,初始状态Vn为 空集,如果小车i将 要经过节点n,并且距离节点n为j格,根据距离我们可以计算出小车i经过节点n的理想时间ti,然后将二元组vi=＜i,ti＞加入Vn集 合,则Vn={vi} ,其他以此类推.每次小车i向前移动一格,则需将vi的 值更新为vi=＜i,ti-t′＞,t′为小车移动当前栅格所用的时间,如果ti-t′≤0,说明小车i已经过了节点n,则需将vi从Vn集合中移除.

3 可避免拥挤的路径搜索算法

传统的A*算法仅考虑了静态环境信息和当前AGV 的信息,而没有考虑场地中其他AGV 对当前AGV 的影响,规划出来的路径可能造成拥堵,尤其是高密集度AGV 场景中,拥堵严重时可能造成某块区域完全堵塞,使得系统效率急剧下降.本文在A*算法的基础上引入潜在拥挤节点的概念,对可能发生的拥挤情况进行预测,在路径规划过程中绕过拥堵节点或潜在的拥堵节点,避免拥堵.

3.1 A*算法

A*算法是Nilsson NJ[16]在Dijkstra算法基础上提出的,是静态路网中最有效的直接搜索方法之一.A*加入了当前节点到目标结点的估计代价,根据起始点经过当前结点到达目标点的代价决定搜索的方向,大大提高了Dijkstra 算法的效率.定义估价函数为：

其中,n代表当前搜索的节点,G(n)是 起始点到节点n的实际代价,H(n)是从节点n到目标节点的估计代价.路径规划通常使用距离作为代价,所以常用的估计代价有曼哈顿距离、切比雪夫距离、欧几里得距离[17,18]等.

假设当前搜索的节点为n(xn,yn),n的父节点是m(xm,ym)( 搜索到了m节 点,再往下搜索到了n,即称m是n的父节点),终点坐标为(xend,yend),

本文采用曼哈顿距离,所以实际代价：

因为本文采用的栅格节点模型是四邻域方向.所以n和m是 四连通的,故|xn-xm|+|yn-ym|=1,即

估计代价为当前点n到终点的曼哈顿距离：

由式(3)和式(4)可知当前节点n的最终估计函数为：

3.2 CAA*算法

本文提出的CAA*算法在路径规划时通过增加潜在拥挤节点的通行代价,从而避开潜在的拥挤节点,所以算法的关键在于潜在拥挤节点的预测,这需要借助于节点的动态属性集合V,V中记录了要经过当前节点的小车及其经过的时间点,根据集合V中小车经过当前节点的时间信息,可以统计当前节点某一时间范围内小车的数量,当小车数量超过拥挤阈值,就判定当前节点为潜在拥挤节点.集合V中的二元组通过增加、更新、删除三种操作来维持集合中动态属性信息的时效性.

(1)节点动态属性的更新

对于节点动态属性的更新,不是每次更新整个地图所有节点的动态属性,而是只更新节点动态属性有变化的节点,引起节点动态属性变化的原因有两个：一是小车路径变化,小车路径变化之后,小车未来要经过的节点发生改变,从而引起路径上节点的动态属性的变化；二是小车按照规划好的路径移动时,引起小车路径上节点动态属性集合中二元组信息的更新或删除.

1)二元组的增加

① 假设小车i规划出来的路径为(x1,y1),(x2,y2),···,(xi,yi),i代表的是节点编号,则依次计算起点到节点1,节点2,…,节点i的理想时间,记为t1,t2,···,ti；

② 将二元组 ＜i,t1＞,＜i,t2＞,···,＜i,ti＞加入到各个节点的动态属性集合V1,V2,···,Vi中.

2)二元组的更新

① 小车i沿着规划好的路径前进,每经过一个节点,计算其经过当前节点所用的时间,记为t′；

② 对于小车i路径上节点的动态属性集合V中值为＜i,ti＞ 的 二元组,更新为＜i,ti-t′＞.

3)二元组的删除

小车i沿着规划好的路径前进,假设当前经过的节点为n(xn,yn),则把二元组＜i,tn＞从 节点n(xn,yn)的动态属性集合V中删除.

(2)潜在拥挤节点判断

假设当前搜索的节点为n,判断节点n对于当前搜索路径的AGV 是否是潜在拥挤节点的依据是节点n动态属性集合V中符合下面时间约束的AGV 数量是否大于拥挤阈值.

时间约束为：

其中,t为当前搜索路径的AGV 从起始点到达节点n的时间,ti为 其他已经规划好路径的AGV 经过节点n的时间,ti的 值可查询节点n的 动态属性集合V,e代表统计小车数量的时间范围.

记V中满足上述约束条件的小车数量为Vcount.

对于节点n,如果Vcount＞P(P节点的拥堵阈值),则说明节点n将在经过时间t后发生拥挤,即节点n是潜在拥挤节点,当前搜索路径的小车应该规避节点n；如果Vcount≤P,则说明节点n不是潜在的拥挤节点,当前搜索路径的小车可以从节点n通过.

(3)估计代价计算

假设小车i的 起点为(xstart,ystart),终点为(xend,yend),

则对节点n(xn,yn)的 估计代价H(n)为：

其中,λ 表示节点n是 否会发生拥挤,λ =1,表示将会发生拥堵或已经拥堵,λ =0,表示不会发生拥堵.b是代价系数,表示发生拥堵时经过节点n的代价.

则最终节点n的代价函数为：

(4)CAA*算法具体流程

算法具体的搜索过程如下：

1)初始化,创建开启列表(open 表)和关闭列表(close 表),开启列表存储的是待搜索的候选节点,关闭列表存储的是已经搜索过的节点.

2)把起点加入open 表中.

3)检查open 表,假如为空,则转到步骤7).假如不为空,则执行步骤4).

4)选择open 表中代价最小的点作为当前点,检查当前点是否是终点,假如是则转到步骤5),否则将当前点的子节点加入open 表中,其中子节点需满足以下约束：① 子节点可达；② 子节点不在open 表中；③ 子节点不在close 表中(子节点没有被搜索过).并记录子节点的父节点为当前点,最后将当前点加入close 表中.转到步骤3).

5)将终点加入path 表中,并沿着父节点移动,将其加入path 表中,得到的就是最短路径,将path 表反向输出即得到了最终的最短路径.

6)计算当前小车理想状态下经过各节点的时间,组成二元组,加入到路径上的各个节点的动态属性集合V中.

7)结束搜索.

(5)性能分析

本文算法是在A*的基础上改进而来的,和A*一样,都是一种启发式的Dijkstra 算法,大大减少搜索的栅格节点数量,从而减少了搜索时间,当然,代价是有可能搜索到的路径不是最优解,是次优解,但是在AGV 快递分拣这种不要求最优解的场景,次优解也是可以接受的.

本文算法和A*算法的时间性能大致相当,是毫秒级的,并且算法稳定,满足实时路径规划的要求.

4 实验结果及分析

4.1 实验设计

结合某实际场地的设计,仿真实验的场地大小栅格化后为91 格×62 格.整个场地共有34 个上包点(左边16 个,右边18 个),中间是投放口,共270 个.任务的起点是上包点,终点是投放口,小车到达终点后,将货物倒下,则当前任务完成,然后回到某一个上包点等待下一个任务.

实验中任务的终点(投放口)是随机生成的,每次实验A*算法和CAA*使用相同的随机种子,生成伪随机数列,保证了实验生成的任务序列是一样的.

节点的拥挤阈值P定义为某一时间范围内(文中e的值)通过该节点而不引起堵塞的最大小车数量.节点的拥挤阈值除了和时间范围的大小有关外,还和该节点及其周围节点的设计、经过该节点和周围节点的小车的运动速度等因素有关,所以节点的实际拥挤阈值是很难准确计算出来的,但是,根据这些因素可以大致的估计出拥挤阈值的范围.为了确定最佳拥挤阈值,本文使用不同的拥挤阈值P进行实验,实验中的e取固定值,为AGV 小车走过4 个节点距离所用的时间.结合拥挤阈值的定义可以看出,P的值必定不会太大(如果e取值大一点,相应的P也会大一点),所以实验中P的值从0 开始取,然后每间隔4 进行一次实验.

为了确定算法能提高场地AGV 密集度和系统分拣效率,使用CAA*算法和A*算法进行仿真实验,每次增加25 辆AGV 小车,然后统计整个场地的分拣效率.

4.2 结果与分析

实验结果如图1所示,横坐标为密集度(辆/栅格),纵坐标为分拣效率(件/时).A*算法其实是CAA*在拥挤阈值P设置为正无穷时的特例,因为当拥挤阈值P设为正无穷时,Vcount≤P是永远成立的,即节点永远不是潜在的拥挤节点.从图中可以看出,在低密集度(密集度＜0.05)的情况下,拥挤阈值P设置的越大,分拣效率越高,这是因为低密集度时发生堵塞的可能性低,在不堵塞的情况下,小车绕行会导致效率有一定程度的下降；在高密集度(密集度＞0.05)的情况下,发生堵塞的可能性高,规避堵塞节点带来的效率提升大于绕行带来的效率下降.

图1 不同拥挤阈值和AGV 密集度下的分拣效率

表1是CAA*不同拥挤阈值下与A*峰值性能对比,可以看到,当拥挤阈值P设置为4 时,分拣效率最高,相比A*算法,场地AGV 密集度提升了28.57%,峰值分拣效率提升24.29%.

由上述分析可知,本文提出的CAA*算法在高密集度的情况下能有效减少拥堵,提高场地的峰值分拣量和场地AGV 密集度.

表1 CAA*不同拥挤阈值下与A*峰值性能对比

5 总结与展望

本文着眼于快递包裹分拣系统的路径规划,提出了一种能进行拥挤预测的CAA*路径规划算法,解决在高密集度和较大规模的AGV 场景中AGV 相互拥挤而导致的效率下降问题.该算法在传统A*路径搜索算法的基础上,引入潜在拥挤节点的概念,对栅格节点进行动态属性表示,建立动态地图模型,对节点未来的拥挤情况进行预测,以规避潜在拥挤节点.本文在实际场地上进行仿真,通过实验可以看出,本文算法在高密集度、AGV 数量较多的情况下确实可以有效的避免拥挤,提升场地AGV 密集度和分拣效率.本文算法仿真峰值分拣效率比A*提升了24.29%,AGV 密集度提升了28.57%.

本文算法也存在一些不足,从实验结果可以看到,在同一个场地,当密集度较低时,本文算法CAA*比A*分拣效率要低,这是由于潜在拥挤节点预测有偏差导致的,潜在拥挤节点预测有所偏差主要有以下两个方面的原因,一是本文对潜在拥挤节点预测结果的粒度分得较粗,预测的结果只有是和否；二是采用的是全局拥挤阈值,实际上不同地图节点会发生拥堵的阈值应该是不同的.因此,下一步的工作,我将从这两个方面入手,一是可以尝试将预测结果用概率表示,代表拥挤的程度,对预测结果的粒度进行细分；二是使用局部动态拥挤阈值,使得节点设置的拥挤阈值更接近实际的拥挤阈值.