仓储物流机器人批量拣选路径规划仿真

陈 文

(福建船政交通职业学院，福建 福州 350007)

1 研究背景

经济的发展，带动人们的生活水平不断提高，电子商务的发展突飞猛进。物流领域的工作环境多变、工作量、复杂性有所提高，传统的工作模式并不能满足物流发展的需要。这种情况下，将移动机器人引入到物流的仓储空间中，可以有效代替人工搬运的问题，提高工作效率，减轻劳动强度，降低维修成本，并且对仓储空间的布局有规划作用。机器人的有效应用解决了物流企业不少问题，并且缓解了工作者高强度的工作压力。但实际操作中，大量的工作仅仅依靠一个或两个机器人并不能完全实现，因此机器人集群的作用就体现出来了，机器人集群的设计能够解决更加复杂的问题，完成更加复杂的工作。仓储物流机器人系统的研究比较广泛，包括机器人导航与定位、系统地图的构建，机器人任务的调度、路径的拣选与规划。本文主要针对仓储物流机器人的路径拣选问题进行了研究与实验。机器人路径拣选的研究的前提是系统给出特定的指令和要求，从环境中获取信息和机器人本身的状态，在此基础上，通过特定的方法实现从目标起点到目标终点最佳路径的规划和选择。

机器人集群在仓储空间的定位有很多方式，二维码、GPS、蓝牙等。机器人集群与中心控制系统之间的通信可以通过无线网络来实现。而对于机器人路径规划需要注意的问题有：首先，当订单到达之后，按照什么标准来调度机器人；其次，如何有效拣选及避免机器人在仓储环境中路径规划问题及碰撞问题；最后，在固定的空间中，既定任务数量，如何最优化的配置机器人数量及路线。

2 仓储空间结构与物流任务分析

设计前期建立一个自动化的物流仓储空间的模型，设计的过程中需要考虑的问题有货物摆放的位置、进货口、出货口仓储内部空间道路的情况，每一个仓储区域分别由纵向与横向街道围起来的区域，每个区域有2排摆放货物的位置。在整个仓储空间中，如果出现机器人集群共同工作的情况，需要解决碰撞冲突的问题。逐渐简化机器人运行规则，提高机器人安全运行标准，设定货物运输方向和道路方向。仓储物流空间模型的建立，需要根据物流任务提出要求，从仓储空间的某一个货物架的位置M1到出货口或入货口位置M2，待到完成任务后，返回某一个货架位置M3，等待下一次任务，具体流程如图1所示。

图1 任务流程建立

物流任务的建立可以分为三个步骤：第一个和第三个步骤可以通过任务的分配调度来进行优化，减少浪费的时间；第二个步骤需要采用路径规划的方法对路径进行优化，具体流程如图2所示。

图2 物流任务的流程图

3 批量拣选路径规划算法

3.1 批量拣选路径规划数学模型

在任务流程建立的基础上，忽略精确路径的规划，可以将批量拣选路径的规划问题分为两种：第一，机器人起点在出口，这种问题是TSP问题；第二，机器人的起点不在出口，在其他位置，可以将这种情况看做是起点终点固定的ST-TSP问题。TSP问题可以通过式(1)来进行描述，求一条最优的路径L={n1，n2，n3......，nk}

(1)

其中Pα是一组K个路径点的排列，Pα是对路径的一个置换，d(nαi,nαt+1)是两点之间曼哈顿的距离。而对于TS-TSP来讲，传统的TSP问题的解决方式并不适合，需要对算法进行改变。将H作为机器人的起点，D为机器人的终点，具体计算最优路径的方式为式(2)：L={H，n1，n2，n3......nk，D}

(2)

公式中的Pα为去除H、D中间的K个路径点次寻的重新排列，d(H,nα1)为H到一个分拣区域的距离，d(D,nαk)为D到另外分拣点的距离。TSP与TS-TSP的算法模型是不同的，但是两种模型之间也有一定的联系，TSP各节点之间是相通的，而TS-TSP是需要除去起点和终点，中间的节点是相通的，并且两种模式都要求历遍所有的节点，两者都可以利用遗传算法来计算。TSP利用遗传算法计算时，需要将路径中所有的路径点作为种群的个体，TS-TSP则是将中间节点作为种群个体。

3.2 对A*算法改进的具体步骤

A*算法是在静态路网中求最短路径值。而机器人拣选路径则完全可以依靠A*算法。在A*算法路径的规划中，物流机器人的规划问题可以表示为数学中的一个集合{space，rob，S,E,H}.其中space是整个仓储空间，也就是移动机器人工作的空间，其中也可以包括多个或单个障碍物，ROB表示移动机器人，S表示起始点，T表示终点，H代表A*算法中的函数。

1.环境建模。本文利用栅格法来进行地图建模，栅格法就是利用AGV的工作环境进行单元分割，分割出大小相等的格子，栅格法可以将环境信息、顺序信息表达在网格中。分割出的大小相等的网格不会发生变化，并且机器人整个运动的过程不会发生改变。将机器人的环境信息进行离散化，机器人整个工作的轨迹可以划分为单个的运动，然后将其组合起来。每一个离散运动都会保存在分割的格子上，利用栅格法规划和计算最短路径，并且要有效规避障碍物。

2.A*算法的具体流程。A*算法是最有效的直接搜索的方法，并且操作原理比较简单，对两个集合进行定义，一个是OPEN表，另一个CLOSE表，以下简称O表和C表。O表保存准备考察的节点，C表保存已经考察过的节点。A*算法开始，O表中包含一个起点元素，C表仅包含一个障碍物的节点。A*算法的流程是从O表中选取一个节点N(k)，并检验是否为目标节点。如果K为目标节点，则路径规划结束，并且做出结论。如果K不是目标节点，节点K则会被保存到C表中，并从O表中删除。并通过扩展节点的方法考察K节点周围的8个节点，判断是否为目标节点，此种方法，以此类推，具体的操作流程如下。

1)设置物流机器人运动的起点S与目标点E，并且做好障碍物的分布工作；

2)做好A*算法的O表和C表，将两个表的值进行初始化，保证为(null)；

3)将S与E赋值给O表，并将障碍节点赋值给C表；

4)使用评价函数F(k)进行评估当前节点，如果K值为目标点，则路径规划结束，如果K值不是目标点，删除该K值，进行下一步；

5)对K节点周围的8个节点进行扩展，将8个节点中值最小的作为路径规划的下一个点；

6)对O表进行查看，是否为空，如果为空，则说明起点到目标节点的所有数值都考察过，得出路径规划数据，若不是空，则重复A*算法，再次进行规划。

3.3 特殊规则下A*算法的路径规划

在对仓储空间结构设计时，一般路径规划方法采用模糊算法，人工势场，神经网络，A*算法等方法。其中比较常用的则是A*算法， A*比较简单通用，并且能够保证用最快的速度寻找最优的路径。一般情况下，仓储空间的道路设计为单向行驶，A*算法会受到该种规则的约束，因此在特殊规则下，必须对A*算法进行改正。A*算法的基本流程是从起点开始计算，根据实际计算情况来扩展节点，直到完成拣选工作，计算出目标点。因此，对于评价函数的选择非常重要，如式(3)

f(k)=g(k)+h(k)

(3)

其中f(k)代表从起始状态经过节点K到目标状态的预估代价。g(k)代表在整个状态空间中，从起始状态到状态K的实际代价。h(k)代表状态空间中从状态K到目标节点最佳路径的预估代价。仓储空间环境中所有通行的道路均为单行道路，在整个线路节点扩展中，方向和顺序是固定的。

图3 节点扩展方式

如图3所示：沿着纵向道路H1从节点M1开始扩展，依次为M2、M3、M4、M5、M6、M7。其中M2 M3 M5 M6是顺序扩展的固定流程，主要在于M4和M6的节点是否会向P1和P3转动，因此为了简化算法，可以将以网格为单位的扩展，转化成以道路为单位的节点扩展路径。

图4 沿道路扩展节点

如图4所示：沿纵向道路H1从节点M1开始扩展，依次是M1、M2、M3。横向道路是P1、P2、P3，以道路为节点的扩展方式，减少扩展次数，提高工作效率，节省时间。道路在仓储空间中，不一定是路径的起点或终点，一般货架的存放空间才是起点或终点，这就是特殊情况，需要加入特殊的扩展方法，特殊扩展分为三种形式。当节点是货架的起点，可扩展的节点有相邻道路的位置，如图5所示，黄色格子为货架M1，灰色格子是可以扩展的后续节点，节点P即为H1，节点Q代表横向道路P2，当节点为道路时，则可扩展所有道路交叉节点的所有道路。

图5 货物架子空间为节点

无论是道路节点或是货架为节点，f(k)评价函数都需要根据实际情况作出调整，除了基本的曼哈顿路径，还需要根据道路的方向与实际情况作出相应的转变。

3.4 A*算法中加入时序的路径规划

假设可以对每一个时刻的机器人的具体位置进行监控，就可以避免在路径规划过程中可能会发生的冲突。因此在算法中可以加入一个地图，可以记录每一个时刻机器人运动的轨迹，并将机器人运动轨迹记录下来，形成一个三维地图，地图中包括运行方向、运行时间，地图可以作为线路拣选的参考。在基于A*算法的基础上，加入时间轨迹，可以将路径代价替换为时间代价。同时需要充分考虑到运动过程中涉及到的碰撞问题，将碰撞问题加入到时间代价中。因此在路径规划和拣选中，需要考虑延时问题，避免规划出的路径产生冲突问题。

仓储道路具有一定的特殊性，其方向为单向。规划的先后顺序并不能保证运行的有限顺序。后规划的路径A插入到先规划的任务B的前方，那么B只能选择等待，这样的问题出现就会导致实际规划情况与原计划不符。遇到这种情况，任务仍需要按照原规划的路径来完成。可能在时间上不能与原计划保持一致。但如果继续根据已经发生偏差的路径来完成任务，即使任务能够完成，误差则会积累的更多。因此一旦是按照非规划的路径来完成任务，则需要及时修改地图，保证地图与实际情况相符合。

3.5 机器人碰撞预防分析

仓储机器人在运动的过程中，发生碰撞的问题是不可避免的。如何有效地解决碰撞的问题，也是路径拣选过程中需要注意的情况。避免可能发生的碰撞，需要设立独占点。在特定的时刻，特定的位置，只能由一个机器人来完成工作。同一时刻进入的工作机器人必须选择等待。在实际工作的系统中，机器人都会通过传感器来完成定位与导航的工作，在检测到机器人之间的距离小于警戒值，要作出刹车指令，防止出现碰撞情况，影响工作效率，提高工作成本。

4 仿真实验验证与分析

通过有效的仿真实验可以验证选择的路径拣选算法是否有效，进一步研究机器人数量、路径、效率三种之间的关系。

4.1 任务设定和实验设定

必须保证仿真实验的真实性与客观性，避免受到任务本身性质的影响。采用随机的算法来布置任务，货架与机器人的位置与数量都是随机产生。任务的编号与入货口、出货口符合要求，随机分布。设置任务数量2000，随机调取20组任务，机器人数量分别设定为10、20、30、40、50、60、70、80、90、100共10种情况。每种情况通过2种算法拣选合适路径完成20组任务，一共进行200次实验。

4.2 实验结果分析

在进行200次的实验中，任务顺利完成，验证了仓储物流机器人路径规划的可行性与有效性。表1显示，利用方差分析机器人数量、路径规划算法对物流任务的影响，其中包括里程、时间及碰撞冲突。机器人数量的配置对运行的里程、时间及碰撞发生次数都有明显的影响。而两种路径拣选算法在里程和时间上没有明显的差别，但在碰撞冲突方面的差别比较明显。

表1 仿真实验结果

根据计算图6总结了不同数量配置的机器人集群在两种路径规划算法下的2000个任务所运行总里程的10个实验平均值。通过呈现的数据可以看出，随着机器人数量的不断增加，机器人工作总里程也逐渐降低，而增加的机器人为系统提供了更灵活的工作方式，在工作中可以选择货架与目标地、机器人距离比较接近的完成任务。

图6 两种算法路径规划对比分析

图7 运动中机器人数量与碰撞次数分析

通过图6、图7的分析可以很直观的看出，两种规划方法的约束下，A*的算法的各项数值比较接近，加入时序路径规划算法，会降低工作中碰撞的次数。但如果是仓储空间中，单行道路的设定，时序算法并不能完全避免碰撞问题的出现。

5 结束语

本文针对仓储物流机器人在仓储空间的路径规划问题进行分析和研究，根据A*算法，建立一个灵活的仓储空间，根据任务建立的特点，建立合适的任务流程和算法模型，根据A*的基本算法，有针对性地进行修改算法，建立特殊规则的A*算法和时序的A*算法。这种方法能够解决批量路径拣选的问题，为机器人更好的工作，提供高效的技术支持。