首发：旷视研究院
作者：郑若辰
导语
“亲，你的618包裹正在派送中，请注意查收”。昨晚才下单的包裹，今天竟然就送到了，你以为给物流插上翅膀的只有飞机和无人仓库吗？其实还有仓库里的智能机器人，它们可都是做数学题的大神呢！本期“技术的真相”将带你了解智能机器人背后的数学奥秘。
概述
本文主要介绍仓内智能机器人任务的分发及执行的相关内容。任务分发，顾名思义，针对当前待执行的一批任务（仓内场景常见任务包括搬运任务及泊车任务），为其分配可用的AGV(Automated Guided Vehicle)资源，即仓内不同场景下的任务需求与可用搬运机器人资源的匹配。AGV资源是执行任务的运力资源，因此任务分发又叫做运力分配。
一个简单的示例如下：
一个好的任务分发系统，可以充分调动机器人资源，并在运行时间、距离等方面全局或局部最优，从而达到效率最高。本文对现有机器人常见的两大类任务，即搬运任务和泊车任务，进行具体讨论，探讨搬运任务中的任务分配模式和执行策略以及泊车任务中的泊车点选择等内容。
背景介绍
随着机器人技术的不断发展、企业数字化和自动化程度的不断提升，越来越多的机器人逐渐进入仓储和生产相关领域各环节作业场景中。
虽然机器人形式多样并且应用的作业环节或者作业模式各有不同，但是所执行的基本操作或者所实现的基本功能却有共性，即完成搬运功能并在任务完成后选择合适地点泊车等待后续任务。机器人搬运任务可以抽象为将需搬运目标(比如托盘、货架、料箱和商品等) 从起始点(比如储位、提升机接驳点、上包台和货架拣选处等) 搬运至目的点(比如拣选工作站、分拣Chute口和复核打包工作站等)，泊车任务即机器人完成任务后选择合适泊车点等待，从而能够快速响应之后任务，提高作业效率。
下面我们将分别讨论机器人的这两种基本任务。
搬运任务分发
搬运任务
当前仓储和生产制造等领域，地面机器人主要实现的核心功能之一就是对物品或者容器的搬运．一条搬运任务的要素主要包括：机器人、搬运目标、起始点、中转点、目的点和行驶路线，其中：
1. 机器人：搬运任务的具体执行载体
2. 搬运目标：机器人要搬运的实体，在不同场景下其具体表现形式不唯一。比如，在货到人系统中搬运目标主要是多层货架或者托盘；在分拣场景下主要是待分拨的包裹；而在拣选支持系统中则是人工拣选出的货品
3. 起始点：机器人开始执行任务的所在点，比如泊车点或者工作站等
4. 中转点：搬运任务下必经的关键节点，而非行驶路径上的一般节点。这里的中转点往往是有业务相关的节点。比如，货到人机器人系统下的货架存放点，也就是储位点，机器人从初始点出发前往储位点搬取货架之后送到工作站；在拣选支持机器人系统中则是一系列拣选点，机器人需要经停并拣选或者搬运由人工拣选出的货品
5. 目的点：搬运目标最终需要到达的地方，比如工作站或者分拣隔口等
6. 行驶路径：依据路网连通性和道路拥堵情况等因素规划出的机器人行走路径
这里我们认为，每一条任务包含一个机器人和对应的一个搬运目标，机器人从一个起始点出发，可以经过一个或多个中转点到达一个或多个目的点。对于入库上架和回库任务，在库存系统对货架和储位进行了选择。经过库存系统和订单批处理系统处理，搬运任务中的搬运目标、中转点和目的点均已经确定。
系统层级
搬运任务的任务分发系统分为两层，分别为上层的业务约束定义和底层的核心匹配算法。
搬运任务分发
业务约束
业务约束涉及大量不同场景，需要满足不同业务要求，较为复杂。
举例说明，在执行任务分发时，待做任务可能是不同类型的，有的任务更紧急，优先级更高，需要先做；有的任务等待成本较高，因此需要为其时刻预留一定份额的运力，保证当该类任务下发时，可以立即分配运力进行搬运；闲置AGV可能存在不同类型，有的类型的AGV只能执行特定类型的任务。
由于业务要求的复杂性，对业务进行分层、细致的梳理，是对仓内搬运任务进行提效的重点。
搬运任务分发
任务约束
任务优先级
不同任务的优先级不同，具体可用以下指标衡量：
1. 任务下发/截止时间：在当前非空任务池中，不同任务存在不同的下发时间或截至时间，一般来说优先考虑截止时间，越早优先级越高；截止时间未知时，考虑下发时间。
2. 任务类型：任务按照类型划分，包含托盘入库、托盘出库、空托回库、叠托移库、阻碍托移库、料箱入库、料箱出库等。
一般来说，不同任务类型优先级满足出库任务>入库任务>理货任务，当然顺序并非绝对，主要依据业务效率要求。
3. 排队状况：以CTU入库任务为例，某个工作站可能积压了大量任务需要CTU来搬运，因此该工作站任务的优先级高于其他工作站。
优先级评分机制
对于每一个任务，都可以根据其指标属性给出一个综合打分，来评价其优先程度；分数越低，优先级越高。
对于单个指标，限定每个任务对应分数在0~1之间，且可配置。例如对于任务类型这一指标，ctu出库任务，ctu入库任务该指标的分数分别为0.5，0.8，则代表出库任务先于入库任务。
任务类型属于类别指标，对于数量（任务对应工作站排队数量）或者时间（任务截止时间）类型的指标，一种方式是根据值来排序，然后由序来拟合一个分数。例如，假设该次任务集合为A,B,C,D,E共5个任务其截止时间按照升序为B,C,A,E,D，那么A,B,C,D,E对应序号为
不同指标同样存在优先考虑顺序，一种简单的方法是为不同指标的评分乘以一个具有显著区分度的权重，得到每个任务加权后的综合分数。
任务依赖
不同任务可能存在任务依赖，例如PS人工区出库，当前工作站需要在上一个任务完成并移走托盘后，才能执行下一个出库搬运任务。因此出库搬运任务依赖于对应工作站的托盘回库或空托回收任务。因此对于已根据优先级生成的任务队列，对于每一个存在依赖的任务，需要在该任务前插相应依赖任务。
一般来说，不同任务类型存在优先级，或者相互依赖关系，例如PS区出库托盘拆空后，需要先将空托盘搬走，否则下一个绑定在该站点的入库任务无法执行。而叠托移库任务需要先于空托回库执行，否则叠托占用叠托机，导致空托回库任务无法执行。
运力配比
以PS区为例，虽然出库任务优先级更高，但如果出库任务较多，可能导致所有AGV全部执行出库搬运任务，造成入库托盘在接驳点积压，因此需预留一定配比的AGV运力只为或优先为入库任务服务。
容量限制
由于起始点、目的地或行驶区域的物理容量限制，需要对同一时间到达相应地点的AGV或搬运容器实施容量限制，例如短时间内目的站点可容纳容器数、巷道可驶入AGV数等。该限制条件可根据具体业务场景灵活配置。
搬运任务分发
AGV约束
可执行任务类型限制
划分运力组后，每个AGV只能执行特定类型任务。
AGV优先级
AGV优先级划分常见CTU场景，例如同一巷道内的任务优先分给已被分配该巷道任务的AGV，出入库任务优先分配正在前往相应工作站的AGV。
搬运任务分发
核心匹配算法
对于核心匹配算法，已经有一套行之有效的实践。本文涉及的所有匹配问题，其主体均为任务和AGV两个部分。
一般来说，根据某一时刻机器人可挂载的最多任务数量是否为一，又可以分为两种模式：单一任务模式和任务队列模式。其中，在单一任务模式下，机器人一次只能领取一个任务，在完成当前任务后才可以领取执行下一任务；对于任务队列模式，机器人可以一次分配多个任务，根据场景不同可以按照一定顺序或者同时执行。
根据单轮指派问题中的两方(即AGV和搬运任务) 数量的多少，又可以分为一对多和多对多模式。
一对多：轮询策略
多对多：MCMF；整数规划
一对多模式
一对多模式主要分为以下两种情况:
1. workcentre initiated：在新任务生成时从多个可选机器人中选择最为合适的一个执行任务
2. Vehicle initiated：当一个机器人空闲后，从多个等待任务中选择一个给该机器人执行
workcentre initiated task assignment problem
在该模式下，如何从可选机器人中选择最合适的那一个，是整个策略的核心。一般来说，有如下原则：
最近原则（Nearest Vehicle rule）
最远原则（Farthest Vehicle rule）
最长闲置原则（Longest Idle Vehicle rule）
对于当前待执行任务池（任务间无优先级），依次对每个任务执行以上选取原则，为每个任务匹配一个最优AGV，然后按照成本从低到高选取个数不超过AGV数量与任务数量最大者的配对，作为分配结果。
Vehicle initiated task assignment problem
在该模式下,每次为当前空闲的车选择一个最合适的任务执行
最少空驶时间/距离原则( Shortest Travel Time/Distance rule)
选择对当前AGV来说空驶时间最短或距离最短的任务其他原则包括最大出库队列原则、FCFS原则等
对于当前可用AGV资源池,依次对每个AGV执行以上选取原则,为每个AGV匹配一个最优任务,然后按照成本从低到高选取个数不超过可用AGV数量与任务数量最大者的配对,作为分配结果。
基于任务选车或基于车选任务,是两种不同的方式。一般来说,某个任务长期无法执行比某辆AGV长期闲置更加严重,因此基于任务选车是一种更合适的方式。
多对多模式
最小费用最大流(MCMF)
根据当前待分配任务集合及AGV集合进行建图：
考虑一个典型的场景,每辆AGV仅可同时执行一个任务,那么每辆AGV到源点的容量均为1. 任务到汇点的各条边容量显然均为1. 如果某个任务能被某个AGV执行,则有从该AGV到该任务的有向边,其容量为1。每条边的成本综合一下几点得出:(1)任务优先级分数(2)AGV优先级分数 (3)搬运成本。
一个典型的网络如下图所示:
通过对以上网络建图方式及增广路的查找方法进行改造，可以得到不同的变种MCMF模型以适应不同的业务场景。
整数规划
建立数学模型,从全局角度出发,一次性为多个任务分配多辆车。以下为一种经典的任务-运力匹配模型:
考虑业务约束下匹配
以上两种模式并无绝对好坏之分,一般来说一堆多模式原理简单,开发维护容易,计算开销较小,但不保证全局最优;多对多模式相对复杂,且计算开销较大,但解的最优性更好。
搬运任务分发
搬运成本
一般来说,搬运任务的起讫点在下发任务时就已确定,因此某个指定运力执行某个指定搬运任务的成本可以明确地定义。常见的定义方式包括搬运距离、搬运时间。
考虑到仓内AGV的行驶方向一般为二维平面的水平、垂直两个正交方向,常见的距离定义方式包括欧式距离或曼哈顿距离,该定义方式较为简单。
另一种更精确的方法为调用路径规划算法( A*等)，计算AGV→任务起点→任务终点的最短路径的完整距离。
该方法尤其适用于路网中存在单向路的情形。考虑到实时计算成本较高,可将地图中所有完整路径的距离存储下来,直接查询即可。在考虑路线拥堵的情况下,可根据地图热点信息为每条边定义不同成本。搬运距离和搬运时间可以相互转化,例如对于完整路径内的每一段直线路径,可根据AGV的加速度信息,求出基于速度规划的行驶时间,并为每个转弯行为加入转弯时间。
搬运任务分发
任务执行
对于以挂载任务队列或多中转点任务的情形,为使机器人可以执行任务,还需要确定任务涉及的顺序问题,具体来说包括:
- 如果存在多个中转点或者目的点,需要确定他们之间到达服务顺序；
- 如果采用任务队列模式,需要确定多任务之间的执行顺序.确定执行顺序在不同场景下方式不尽相同,主要考虑因素包括距离和工作站当时负载情况等。
下面我们通过对一些具体问题场景的讨论来进行阐述。
每个机器需要指派一个或多个搬运任务,并且需要确定每个机器人分别需要搬运的货架以及搬运顺序,使得所有机器人总搬运距离最短或者使得所有任务的完成时间最短。
在这一场景下任务的指派和顺序的确定是通过求解一个变种车辆路径问题(VRP) 同时确定的。而对于上一节介绍的拣选支持机器人系统,确定机器人对拣选点(也就是多个中转点) 的前往顺序可以抽象为一个在仓储路网结构下的经典旅行商问题(Traveling Salesman Problem,TSP) 或其变种问题,通过最小化行驶路径长度确定各个拣选点的到达顺序。
在搬运机器人场景下,可能多个工作站都需求同一个货架上的物品,也就是一条搬运任务有多个目的地的情况。虽然可以通过TSP类方法确定各个工作站的到达顺序从而最小化整体搬运距离,但同时还需要根据工作站当时的任务负载情况进行调整,可以优先前往相对需求急迫或者当前较空闲的工作站,减少工作站的等待,虽然会增加一部分搬运成本但是可以提高整体系统作业效率。
搬运任务分发
评价及灵敏度分析
任务分配和执行的策略会依据不同场景不同需求而有所不同,而在同一场景下面对同样的业务需求,通常也会有多种不同的调度策略可供选择,即便同一种策略也会因为不同的内置参数选择而产生不同表现,现实中通常很难完全确定某一单一环节如何影响整体系统生产效率。
尽管如此,通过对一些特定统计量的分析,我们也可以大致了解策略对系统性能的影响。对于本节所介绍的搬运任务分配和执行,在订单拣选场景例如拣选和拣选支持机器人系统,可用若干用于评价调度策略性能的统计量,其中包括:
1. 订单生产效率:一定时间内生产完成订单数量与接受订单数量的比例
2. 响应时间:任务等待机器人执行的时间与机器人空驶时间之和
3. 生产时间:订单在系统中生产的时间
4. 机器人平均利用率:机器人执行任务的时间(包括空驶和满载时间与总时间的比值)
现实生产系统中还会计算和监控更多统计量用于后续性能分析,其中包括工作站拣选等待时间、机器人平均搬运距离以及搬运任务平均耗时等。对于分拣场景,则会统计包裹投递效率等。
除去上面提及的系统性能表现以外,另一方面我们还需要关注算法策略本身属性。具体来说,随着机器人技术的不断普及和业务场景的不断扩大,系统中机器人数量和待处理的任务量会进一步提升,这会使得调度问题规模变得很大,而同时业务对于系统的响应可能要求很高,在这种场景下,需要算法策略有很好的计算性能。
机器人系统不可避免会出现异常故障,算法策略也需要有足够的鲁棒性可以进行快速调整。另外,对不同时间段内可能的不同调度目标,调度策略也需要有足够的柔性可以满足不同要求。总体而言,需要通过对运营效率、计算性能、鲁棒性和柔性等方面综合对所考虑的任务调度策略进行评价。
泊车任务调度
当机器人完成前一个任务后,如果没有后续任务也无需进行充电的情况下,通常需要执行泊车任务。
泊车任务是指空闲机器人前往选择的停靠点进行等待直到分配下一任务,停靠点的选择需要考虑距离和其它机器人位置等因素,在不影响其它工作机器人作业的情况下,选择合适的泊车点可以提高机器人系统对新任务的响应速度从而提高整体作业效率。
考虑堆垛机立库系统,泊车点包括在出入库工作站处、货架中位点处和在上一任务的完成点处。
对于AGV系统,常见的泊车情形包括:
1. 前往预先规划的指定停车地点泊车;
2. 在规划的路径上巡行直到有新任务指派;
3. 在上一任务完成地点等待。
此外,环工作站环形分布的泊车位选择策略根据各工作站任务发生概率,选择泊车位尽可能降低平均响应时间。环形泊车策略分为静态和动态,其中在静态策略中,泊车位选定后固定不变直到重新计算,而动态策略则在静态策略的基础上进行延伸,泊车位的选择需依据当前所有空闲小车泊车位置并且会动态改变。
现实场景下,空闲机器人泊车任务调度主要包括首先选择合适的泊车位,在前往泊车点和在泊车点等待的过程中可以随时终止泊车任务去执行新的搬运任务。
其中,生成泊车位的整体选择过程大体分成两个部分:首先需要确定可选泊车位范围,可能在一些场景下在规划之初已经设计了若干固定的泊车位置,而空闲机器人只能在这些泊车位中选择当前未被其它机器人占用的位置进行泊车;而在另外一些场景下,没有固定的泊车位置,机器人可以选择任何可选位置(不可选位置包括造成路线堵塞的点等) 进行泊车。
在确定了可选泊车位范围后,第二步需要根据距离和其它空闲机器人泊车位置选择本次具体泊车位。其中距离因素考虑尽量选择下一任务可能发生区域的位置从而降低移动距离提高响应速度,同时也需考虑其它空闲机器人泊车位置,平衡各区域机器人分布密度,避免特定区域空闲机器人过多造成资源浪费,而其它区域缺少机器人造成接受任务后响应不及时的情况。具体到不同类型的机器人在不同场景下的泊车任务调度,需要以提高整体响应速度为目标,考虑前面提到的影响因素,根据特定场景的特点和要求进行选择。
下面通过简要对货到人机器人和分拣机器人的泊车调度讨论来具体阐述前面提出的泊车调度整体流程。
对于货到人机器人系统,通常并不规划固定泊车位而是每次动态选择。泊车位的选择策略会依据不同任务类型而有所变化,例如上一执行完的任务是盘点或者入库任务,当机器人将货架搬运到对应盘点或者入库工作站后,由于盘点和上架完成后货架还需要搬运回库,所以可以选择就地泊车减少后续机器人空驶距离,但是由于盘点和上架任务通常执行时间较长,这期间如果有其它更紧急的任务可以调用该机器人。
另一方面,对于回库任务执行完后的泊车选择则会有所不同。机器人将货架搬运回储位后,通常会选择一个合适泊车点进行泊车。在第一步中首先要确认可选泊车点,道路上泊车会造成拥堵一般不选择,而空储位由于后续可能会有货架回库造成冲突也一般不选择,通常这种情况下一般选择没有机器人占用的货架下储位点。之后第二步中,选择距离其它泊车机器人较远但距离工作站较近的货架下储位进行泊车,这样可以保证空闲机器人分布均衡并且距离后续可能的任务尽可能近,从而提高系统整体响应速度。
对于分拣机器人系统,每个上包台处一般都会规划有固定排队位,并且排队位也有分级,而分拣机器人在完成上一个包裹分拨后需要选择一个上包台的某一个固定排队位进行泊车等待。
在选择排队位时,首先要考虑选择当前等待车数最少的上包台对应的排队位作为可选范围,从而使得各个上包台资源能力均衡,如果各个上包台任务量不同,则可根据任务量多少进行加权选择,之后对应选择该上包台处最高优先级的空闲排队位作为泊车点。
通过上面的介绍,空闲机器人通过确定可选泊车位,依据距离和其它机器人泊车信息选择泊车点,以此保证适合的泊车分布,而合适的机器人泊车分布可以有效提高系统对任务的响应速度提高整体作业效率。
行业名词解释
1. AGV:Automated Guided Vehicle,自动导引车,是一类轮式移动机器人,沿着地板上的磁条、标记块,或者通过视觉导航或激光导航进行运动
2. 拣选:仓储配送中心的配货人员按订单要求的商品名,规格,型号,数量,将商品从存储的货架或货垛中取出
3. 分拣:拣选作业完成后,将拣选出的商品按照不同的客户,不同的配送路线进行分类,集中,等待装车配载,送货作业的流程
4. 运力组:用于完成特定任务的一组运力资源的集合
5. 移库:由于业务需要,将仓内物料移动至同一逻辑区下的另一个位置
6. 容器:用于存放商品的器具,常见容器包括料箱、中转箱、托盘等
7. PS: Pallet Shuttle,一种搬运托盘的AGV
8. CTU:Container Transport Unit,一种可同时搬运多个料箱的AGV
9. Chute口:用于存放同一订单或同一目的地对应商品的格口
10. 叠托:当托盘被捡空后,将多个托盘叠在一起,便于回收及存储
专栏文章推荐
欢迎关注旷视研究院极术社区专栏，定期更新最新旷视研究院成果
加入旷视：career@megvii.com
