无人仓自动搬运系统策略研究—动态任务分配

黄 颖，李 蔷

（1.江苏科技大学张家港校区，江苏 张家港 215600；2.上海大学 管理学院，上海 200444）

1 研究的问题与现状

1.1 无人仓发展趋势

根据eMarketer 数据，2017年全球网络零售交易额较2016年增长24.8%，占全球零售总额的比重进一步提升，网络零售已成全球零售市场的强劲拉动力[1]。电商行业的高速发展，使得物流需求结构不断改善，且在提升运营效率、降低物流成本、提高用户体验等方面对市场提出了更高的要求，无人仓储系统得到了广泛的关注。该系统通过自动化手段，实现货物从入库存储到分拣出库全流程的智能化和无人化，满足系统柔性扩张的要求。

1.2 大规模机器人的使用

机器人的发展经历了萌芽期、产业孕育期、快速发展期，现今已经处于智能应用阶段（如图1所示）。随着感知、控制等技术的升级和人工智能技术在机器人领域的应用，工业机器人成为全球范围内第一大应用市场。从2012年亚马逊收购kiva 机器人到2017年菜鸟建立并投入运行大规模机器人仓群、京东建立完全无人仓，近年来机器人仓库已经从过去的单点小规模使用走向了大规模使用。

工业自动化体系的应用，也经历了从单点应用到集群化应用的发展过程。越来越多的企业意识到，与工业生产的点状作业相比，物流体系更需要实现在面上以及立体空间内的作业。通过分布式、并行化的机器人系统可以实现自动化的物流过程，取代传统作业中人的单调重复劳动。

相较于单点智能，群体智能具有以下优势：

（1）群体智能基于经验与数据共享，去除单点智能模式“中心”的概念，使数据更开放和自由，决策准确率更高且整体数据成本更低；

（2）群体智能在信息交互的过程中可以更好的完成全局行为的优化，实现1+1＞2的效果；

（3）对于较为复杂的任务和环境，设计多异构/异能机器人相互协作远比设计一个多能力机器人要容易，且成本更低；

（4）大规模使用简单机器人比单点使用复杂机器人的成本更低，灵活性更高；

（5）群体智能拥有更为完整的数据链条记录，有利于上下游协同决策，提高整体响应速度；

（6）多机器人可以平行作业且具有冗余性，系统柔性更好、容错率更高、鲁棒性更强；

（7）多机器人系统模块化设计更易扩展、执行更高效，在时间、功能、布局分布上更灵活。

群体智能较之单点智能，其智慧化程度更高，系统柔性更好，能够实现个体与整体更好的良性迭代，并利用规模优势实现更低的总成本。

图1 机器人发展历程

1.3 目前多机器人任务分配的方法简述

多机器人任务分配问题可以视作调度问题，通过合理的任务分配方案使得资源获得有效的配置以达到提高效率、降低成本等目的。目前针对该问题使用的方法主要有：基于市场机制的任务分配方法、群体智能方法、基于线性规划的方法、基于行为的任务分配方法等。随着人工智能的不断发展，一些研究也将智能优化算法借鉴到了多机器人分配中，如利用SOM（自组织神经网络算法）的子分类映射原理寻找最适合目标任务的机器人等。

1.3.1 基于市场机制的任务分配方法。基于市场机制的任务分配方法源于经济学中的拍卖模型，其中较为经典的是R.Smith[2]在1980年提出的通过招标、投标、竞标进而合同建立的合同网协议的分配方法。该方法具有适用性好、可弹性扩张的优势，但是对于通信能力的要求较高[3]，不太适用于较大规模的多机器人，通常用于任务和机器人状态可知的中小型环境中分布式问题的求解。在该思想下有集中式和分布式两种应用。集中式任务分配是利用中央处理器进行任务拍卖和任务分配，分布式任务分配则是指自利的AMR（Automatic Mobile Robot）直接参与虚拟市场。集中式任务分配算法设计难度较低，但通信和计算集中，容易造成信息堵塞，对于较大规模的多机器人任务分配处理能力受限，且中央节点作为系统核心，对其稳定性的要求非常高，整体系统的鲁棒性较差，因此仅适用于规模较小的系统。分布式任务分配具有应对动态环境的能力，通信负荷均衡，且系统可以并行处理问题，鲁棒性较高，数据处理能力更强。在实际运用中，该任务分配方法又分为单目标拍卖、组合目标拍卖、单层拍卖、任务树拍卖等[4-12]。针对该任务分配的结果，高梓豪[13]强调任务分配完成的不可更改性以确保通讯的效率。

1.3.2 基于群体智能的方法。基于群体智能的方法是利用社会性的昆虫模拟出的算法，该方式中合作的个体呈现分布式的特点，具有较强扩张性和鲁棒性。由于该方式中的通讯方式属于非个体直接通讯，因此其扩充任务池所带来的通讯增量并不大。最经典的算法有阈值法、蚁群算法等[14-16]。该方法在多机器人系统环境未知时可以发挥良好的效用。

1.3.3 基于线性规划的方法。基于线性规划的任务分配方法是将任务分配的问题看作0-1 线性规划问题[17]，常用的有单纯型法和匈牙利法。该方法通过矩阵运算，以最小化执行代价为目标进行任务分配，一些算法虽然可以找到最优解[18-20]，但因为其高集中式的特性，该算法扩展性差且效率不高，仅适用于单机器人单任务问题的解决方案。

1.3.4 基于行为的任务分配。基于行为的任务分配方法是将效益最高的机器人与任务相配对，每次匹配后将其从待分配任务列表中删除，进行下一组配对[21]。典型的算法代表有ALLIANCE[22]、Broadcast of Local Eligibility（BLE）[23]等。该分配方法实时性、容错性、鲁棒性都存在优势，但求得局部最优解的可能性较大。

各任务分配方法的优劣势对比见表1。

表1 任务分配方法对比

根据以上分析，基于市场机制的任务分配方法在已知仓库环境的前提下可以发挥较优的效用，但仍可能存在计算复杂、通信量大等问题。为解决此问题，进一步提高仓库拣选效率并降低任务完成所需的系统代价，本文提出了一种多层次的适用于无人仓自动搬运系统的分布式合同网动态任务分配策略。

该动态任务分配策略由任务分配方式和任务执行保护机制组成，其中任务分配方式包含单任务分配和可组合任务分配，执行保护机制包括延误触发和合同不可更改两部分，如图2所示。

图2 动态任务分配策略框架

2 动态任务分配策略的原理

2.1 参数设置

2.1.1 任务参数。目标货架位置（若该货架正在拣货，则该参数为对应的机器人编号，否则为坐标）、目标货物编号、目标拣选台、目标货物拣选数量、货架回归位置。

2.1.2 AMR 参数。设置任务执行表TEL（Task Execute List）、任务队列表TQL（Task Queue List）；任务执行表状态TES（Task Execute Status），任务队列表状态TQS（Task Queue Status）；正在执行任务的终点位置TEEL（Task Execute End Location）。

2.1.3 任务看板设置。任务看板内任务数量为1，包含信息有：任务起点位置TSL（Task Start Location）、任务终点位置TEL（Task End Location）、任务商品数量TQ(Target Quantity)、竞标位置范围BLR（Bidding Location Range）、竞标池BP（Bidding Pool）。当任务看板为空时，推入新任务信息并发送任务到达提醒。

2.2 任务分类

本文所提出的任务分配策略中将任务分为单任务和可组合任务两种。若任务的目标货架（非目标货物）存在于机器人的任务列表中，则该任务可以和任务列表中的任务进行组合，称为可组合任务，否则称为单任务，如图3所示。

图3 任务分类

2.3 任务分配逻辑

任务分配应用分布式模型，即AMR 自主参与虚拟市场的竞标。若待分配任务为可组合任务，将其与已分配任务相组合可以增强作业的连续性，减少货架的出入库次数，进而提高作业效率和资源利用率，因此对于可组合任务，拥有相关任务的机器人拥有最高的竞标值，此时直接接收任务并创建合同可以提高响应速度，减少不必要的通讯。对于单任务而言，机器人的竞标值排序未知，因此需要自主竞标，在市场竞标模式中，竞标评价函数Bi由完成当前任务预计耗费时间tm1与到达任务货架所需时间tm2组成，即Bi=tm1+tm2。其中：

C是拥堵系数，由目标区域内碰撞频率决定。

当前AMR应用路径引导方式主要是利用路径节点（二维码等）和自由路径引导（激光SLAM等），本文讨论路径节点引导下的行进模式（网格地图），即利用两目标间的曼哈顿距离作为行走距离。

综上，动态任务分配的流程如图4所示。

2.4 组合任务执行逻辑

若待分配任务i是可组合任务，假设任务i是（目标货架i，目标货物m，目标拣选台k,目标数量n1），其对应已分配但未完成状态的任务j 是（目标货架i,目标货物q，目标拣选台 l，目标数量 n2）,则任务j 将扩充为（目标货架i,目标货物q，目标拣选台l，目标数量n2；目标货架i，目标货物m，目标拣选台k,目标数量n1）。组合任务在执行时遵循子任务队列顺序（子任务队列顺序默认进入顺序，紧急任务置顶），如图5所示。

图4 动态任务分配流程

图5 可组合任务分配逻辑

2.5 灵活响应拣选台

由于组合任务中同一货架响应多个拣选台，所以当因拣选台的处理能力不同（基于拣选站台内操作人员的效率、工作状态等差异）而导致AMR当前执行的子任务需在拣选队列中排队时间预计高于临界值时，触发灵活响应拣货台机制。即读取下一子任务预计排队时间，若符合要求，终止原子任务，开始新子任务。若子任务列表所有任务均不符合要求，继续执行当前任务。灵活响应拣选台机制可以降低部分拣选台前等待队伍较长而部分拣选台前无货可拣的不均衡状态出现的概率，提高整体拣选效率和仓库出库效率，减少机器人的无效等待时间，如图6所示。

图6 灵活响应拣货台流程

2.6 合同不可更改

合同自任务进入任务执行表起开始履行，此时合同除特殊情况（如机器人故障等）不可更改，即使在该机器人还未到达目标货架点时存在其他机器人距离任务点更近的情况，也不会再分配给其他机器人，以防止机器人任务执行过程中终止重新获取任务所产生的空载运动，避免资源浪费，也避免重复运算所造成的内存和计算能力的浪费。

2.7 延误触发逻辑

在本文描述的基于市场的分配机制中，在建立任务合同后任务进入任务队列表等待，该等待时间可能因为可组合任务在任务执行表中的插入、任务执行堵塞（在拣选队列等待时间增长）、机器故障等原因导致过长，影响出货效率。因此为保护订单完成的效率，处于任务队列表的任务仍可能被重新分配，且为避免占用内存和计算能力的浪费，设置延误触发点D（最长等待执行时间）。当到达延误触发点D时，AMR发送信息给中央处理器，使该任务回归任务池。若AMR 处于机器故障（短时间内无法自我修复）等无法执行任务状态时，立即将任务执行表和任务队列表内所有任务信息发送给中央处理器，将任务回归任务池。

3 动态任务分配与静态任务分配的比较

3.1 订单处理效率

传统静态任务分配下，AMR 需完成搬运指定货架到拣货台拣选完成并将指定货架卸载到存储位置才被释放，成为可用资源，即此时AMR的订单行处理能力为1。而动态任务分配方式下，AMR的任务接收量增大，搬运指定货架到拣选台拣选完成即完成单任务循环，有效减少货架的出入库次数和无效行走，当所载货架可以满足多个拣选台需求时，作业连续性增强，订单处理速度提高。同时，可接收多个任务的特性使得AMR 在执行任务时依然属于可用资源，因此同等数量的AMR 运行时，动态任务分配模式中可响应任务的资源数量高于静态任务分配，提高了订单响应速度。

3.2 灵活性

传统静态任务分配下，AMR 完全被动接收中央处理器指令，系统灵活性差，当遇到机器故障等情况时，无法及时对任务进行处理，进而影响整体出库效率。而动态任务分配模式下，AMR 具有一定的自主能力，通过与中央处理器的信息交互，提高异常情况的响应速度与处理速度。同时，动态任务分配模式下延误触发的机制，使得任务具有一定的灵活性，提高资源配置的合理性，提高拣货效率。

3.3 数据处理量

传统静态任务分配下，数据处理完全集中在中央处理器上，一次只能处理一条任务，其内存要求较高，数据处理量较大，任务处理速度不高，无法满足实时化任务调度的要求。而在动态任务分配下，中央处理器将计算过程和资源属性数据分散到AMR上，降低了数据处理量，提高了数据处理速度，在同等数据处理能力下，单位时间内可以处理更多的任务，且在增减AMR时，无需更新资源池内的属性等数据，二者对比见表2。

表2 动静态任务分配模式对比

4 总结与展望

随着提高运营效率、降低物流成本等市场要求的提高，仓储系统的柔性需求日益增加。本文所描述的自动搬运系统的动态任务分配策略通过集中式和分布式资源调度相结合的模式，提高了系统的智能化水平和灵活程度，对于无人仓自动搬运系统柔性的提升提供了一定的帮助。对于已提出的动态任务分配模式下，AMR 的需求数量与仓库规模及订单数量之间的关系等问题在未来需要进一步的研究。