何为一个智能的AGV调度系统？
一、概述
1.1 名词介绍
- AGV：Automated Guided Vehicle，自动导引车，是一类轮式移动机器人，沿着地板上的磁条、标记块，或者通过视觉导航或激光导航进行运动。
- 拣选：仓储配送中心的配货人员按订单要求的商品名，规格，型号，数量，将商品从存储的货架或货垛中取出。
- 分拣：拣选作业完成后，将拣选出的商品按照不同的客户，不同的配送路线进行分类，集中等待装车配载，送货作业的流程。
- 运力组：用于完成特定任务的一组运力资源的集合。
- 移库：由于业务需要，将仓内物料移动至同一逻辑区下的另一个位置。
- 容器：用于存放商品的器具，常见容器包括料箱、中转箱、托盘等。
- 托盘搬运AGV：Pallet Shuttle,一种搬运托盘的AGV。
- 料箱机器人：一种可同时搬运多个料箱的机器人。
- 出口：用于存放同一订单或同一目的地对应商品的虚拟格口。
- 叠托：当托盘被捡空后，将多个托盘叠在一起，便于回收及存储。
1.2 概述
本文主要介绍仓内智能机器人任务的分发及执行的相关内容。任务分发，顾名思义，针对当前待执行的一批任务(仓内场景常见任务包括搬运任务及泊车任务），为其分配可用的AGV资源，即仓内不同场景下的任务需求与可用搬运机器人资源的匹配。AGV资源是执行任务的运力资源，因此任务分发又叫做运力分配。一个简单的示例如下图1所示。
一个优秀的任务分发系统，可以充分调动机器人资源，并在运行时间、距离等方面全局或局部最优，从而达到效率最高。本文对现有机器人常见的两大类任务，即搬运任务和泊车任务，进行具体讨论，探讨搬运任务中的任务分配模式和执行策略以及泊车任务中的泊车点选择等内容。
二、背景介绍
随着机器人技术的不断发展、企业数字化和自动化程度的不断提升，越来越多的机器人逐渐进入仓储和生产相关领域各环节作业场景中。虽然机器人形式多样并且应用的作业环节或者作业模式各有不同，但是所执行的基本操作或者所实现的基本功能却有共性，即完成搬运功能并在任务完成后选择合适地点泊车等待后续任务。
机器人搬运任务可以抽象为将需搬运目标(比如托盘、货架、料箱和商品等)从起始点(比如储位、提升机接驳点、上包台和货架拣选处等)搬运至目的点(比如拣选工作站、分拣口和复核打包工作站等)，泊车任务即机器人完成任务后选择合适泊车点等待，从而能够快速响应之后任务，提高作业效率。
三、搬运任务分发
3.1搬运任务分发
当前仓储和生产制造等领域，地面机器人主要实现的核心功能之一就是对物品或者容器的搬运。一条搬运任务的要素主要包括：机器人、搬运目标、起始点、中转点、目的点和行驶路线，其中：
- 机器人：搬运任务的具体执行载体。
- 搬运目标：机器人要搬运的实体，在不同场景下其具体表现形式不唯一。比如，在货到人系统中搬运目标主要是多层货架或者托盘；在分拣场景下主要是待分拨的包裹；而在拣选支持系统中则是人工拣选出的货品。
- 起始点：机器人开始执行任务的所在点，比如泊车点或者工作站等。
- 中转点：搬运任务下必经的关键节点，而非行驶路径上的一般节点。这里的中转点往往是有业务相关的节点。比如，货到人机器人系统下的货架存放点，也就是储位点，机器人从初始点出发前往储位点搬取货架之后送到工作站；在拣选支持机器人系统中则是一系列拣选点，机器人需要经停并拣选或者搬运由人工拣选出的货品。
- 目的点：搬运目标最终需要到达的地方，比如工作站或者分拣隔口等。
- 行驶路径：依据路网连通性和道路拥堵情况等因素规划出的机器人行走路径。
每一条任务包含一个机器人和对应的一个搬运目标，机器人从一个起始点出发，可以经过一个或多个中转点到达一个或多个目的点。对于入库上架和回库任务，在库存系统对货架和储位进行了选择。经过库存系统和订单批处理系统处理，搬运任务中的搬运目标、中转点和目的点均已经确定。
3.2任务约束及优先级
3.2.1 任务约束
搬运任务的任务分发系统分为两层，分别为上层的业务约束定义和底层的核心匹配算法。业务约束涉及大量不同场景，需要满足不同业务要求，较为复杂。
举例说明，在执行任务分发时，待做任务可能是不同类型的，有的任务更紧急，优先级更高，需要先做；有的任务等待成本较高，因此需要为其时刻预留一定的运力，保证当该类任务下发时，可以立即分配运力进行搬运；闲置AGV可能存在不同类型，有的类型的AGV只能执行特定类型的任务。
由于业务要求的复杂性，对业务进行分层、细致的梳理，是对仓内搬运任务进行提效的重点。
3.2.2 任务优先级
不同任务的优先级不同，具体可用以下指标衡量：
- 任务下发/截止时间：在当前非空任务池中，不同任务存在不同的下发时间或截至时间，一般来说优先考虑截止时间，越早优先级越高。
- 任务类型：任务按照类型划分，包含托盘入库、托盘出库、空托回库、叠托移库、料箱入库、料箱出库、物料投送及物料驳接等。
- 排队状况：以料箱机器人入库任务为例，某个工作站可能积压了大量任务需要料箱机器人来搬运，因此该工作站任务的优先级高于其他工作站。
3.2.3优先级评分机制
对于每一个任务，都可以根据其指标属性给出一个综合打分，来评价其优先程度；分数越低，优先级越高。
对于单个指标，限定每个任务对应分数在0-1之间，且可配置。比如配置入库任务分数0.5，出库任务分数0.8，则代表出库任务先于入库任务。
不同指标同样存在优先考虑顺序，一种简单的方法是为不同指标的评分乘以一个具有显著区分度的权重，得到每个任务加权后的综合分数，如下图2所示。
3.2.4 任务依赖
不同任务可能存在任务依赖，例如托盘搬运AGV人工区出库，当前工作站需要在上一个任务完成并移走托盘后，才能执行下一个出库搬运任务。因此出库搬运任务依赖于对应工作站的托盘回库或空托回收任务。因此对于已根据优先级生成的任务队列，对于每一个存在依赖的任务，需要在该任务前插相应依赖任务。
不同任务可能存在任务依赖，例如托盘搬运AGV人工区出库，当前工作站需要在上一个任务完成并移走托盘后，才能执行下一个出库搬运任务。因此出库搬运任务依赖于对应工作站的托盘回库或空托回收任务。因此对于已根据优先级生成的任务队列，对于每一个存在依赖的任务，需要在该任务前插相应依赖任务。
一般来说，不同任务类型存在优先级，或者相互依赖关系，例如托盘搬运AGV区出库托盘拆空后，需要先将空托盘搬走，否则下一个绑定在该站点的入库任务无法执行。而叠托移库任务需要先于空托回库执行，否则叠托占用叠托机，导致空托回库任务无法执行。
3.2.5 运力配比
以托盘搬运AGV区为例，虽然出库任务优先级更高，但如果出库任务较多，可能导致所有AGV全部执行出库搬运任务，造成入库托盘在接驳点积压，因此需预留一定配比的AGV运力只为或优先为入库任务服务。
3.2.6容量限制
由于起始点、目的地或行驶区域的物理容量限制，需要对同一时间到达相应地点的AGV或搬运容器实施容量限制，例如短时间内目的站点可容纳容器数、巷道可驶入AGV数等。该限制条件可根据具体业务场景灵活配置。
3.2.7 AGV约束
可执行任务类型限制划分运力组后，每个AGV只能执行特定类型任务。
AGV优先级划分常见料箱机器人场景，例如同一巷道内的任务优先分给已被分配该巷道任务的AGV，出入库任务优先分配正在前往相应工作站的AGV。
3.3 核心匹配算法
基于任务选车或基于车选任务是两种不同的方式。一般来说，某个任务长期无法执行，比如某辆AGV长期闲置更加严重，因此基于任务选车是一种更合适的方式。
核心匹配算法主要涉及到任务和AGV两个主体部分。一般来说，根据某一时刻机器人可挂载的最多任务数量可以分为两种模式：
- 单一任务模式
在单一任务模式下，机器人一次只能执行一个任务，在完成当前任务后才可以领取执行下一任务。
- 任务队列模式
对于任务队列模式，机器人可以一次分配多个任务，根据场景不同可以按照一定顺序或者同时执行。
根据任务分发模型中的两方(即AGV和搬运任务)数量的多少，可采用多对多轮询模型。
在新任务生成时从多个可选机器人中选择最为合适的一个执行任务。如何从可选机器人中选择最合适的那一个，是整个策略的核心。
一般来说，有如下原则：
- 最近原则
- 最长闲置原则
- 最少空驶时间/距离原则
对于当前待执行任务池（任务间无优先级），依次对每个任务执行以上选取原则，为每个任务匹配一个最优AGV，然后按照成本从低到高选取个数不超过AGV数量与任务数量最大者的配对，作为分配结果。
对于当前可用AGV资源池，依次对每个AGV执行以上选取原则，为每个AGV匹配一个最优任务，然后按照成本从低到高选取个数不超过可用AGV数量与任务数量最大者的配对，作为分配结果。
3.4 搬运成本
一般来说，搬运任务的起终点在下发任务时就已确定，因此某个指定运力执行某个指定搬运任务的成本可以明确地定义。常见的定义方式包括搬运距离、搬运时间。
考虑到仓内AGV的行驶方向一般为二维平面的水平、垂直两个正交方向，常用路径自动规划算法计算，自动计算AGV→任务起点→任务终点的最短路径的完整距离，如下图3所示的曼哈顿距离。
该方法尤其适用于路网中存在单向路的情形。考虑到实时计算成本较高，可将地图中所有完整路径的距离存储下来，直接查询即可。
在考虑路线拥堵的情况下，可根据地图热点信息为每条边定义不同成本。搬运距离和搬运时间可以相互转化。例如对于完整路径内的每一段直线路径，可根据AGV的加速度信息，求出基于速度规划的行驶时间，并为每个转弯行为加入转弯时间。
3.5 任务执行
对于以挂载任务队列或多中转点任务的情形，为使机器人可以执行任务，还需要确定任务涉及的顺序问题。
- 如果存在多个中转点或者目的点，需要确定他们之间到达服务顺序。
- 如果采用任务队列模式，需要确定多任务之间的执行顺序。
确定执行顺序在不同场景下方式不尽相同，主要考虑因素包括任务拆分、距离、加工配合及交通管制等多个因素。
每个机器需要指派一个或多个搬运任务,并且需要确定每个机器人分别需要搬运的货架以及搬运顺序,使得所有机器人总搬运距离最短或者使得所有任务的完成时间最短。
3.6 评价及灵敏度分析
任务分配和执行的策略会依据不同场景不同需求而有所不同，而在同一场景下面对同样的业务需求，通常也会有多种不同的调度策略可供选择，即便同一种策略也会因为不同的内置参数选择而产生不同表现，现实中通常很难完全确定某一单一环节如何影响整体系统生产效率，可用若干用于评价调度策略性能的统计量，其中包括：
- 订单生产效率：—定时间内生产完成订单数量与接受订单数量的比例。
- 响应时间：任务等待机器人执行的时间与机器人空驶时间之和。
- 生产时间：订单在系统中生产的时间。
- 机器人平均利用率：机器人执行任务的时间(包括空驶和满载时间与总时间的比值)。
四、泊车任务调度
当机器人完成前一个任务后，如果没有后续任务也无需进行充电的情况下，通常需要执行泊车任务。
泊车任务是指空闲机器人前往选择的停靠点进行等待直到分配下一任务，停靠点的选择需要考虑距离和其它机器人位置等因素，在不影响其它工作机器人作业的情况下，选择合适的泊车点可以提高机器人系统对新任务的响应速度从而提高整体作业效率。对于AMR/AGV系统，常见的泊车情形包括：
- 前往预先规划的指定停车地点泊车；
- 在规划的路径上巡行直到有新任务指派；
- 在上一任务完成地点等待。
现实场景下，空闲机器人泊车任务调度主要包括首先选择合适的泊车位，在前往泊车点和在泊车点等待的过程中可以随时终止泊车任务去执行新的搬运任务。
生成泊车位的整体选择过程可宏观上分为两个步骤，首先需要确定可选泊车位范围，可能在一些场景下在规划之初已经设计了若干固定的泊车位置，而空闲机器人只能在这些泊车位中选择当前未被其它机器人占用的位置进行泊车；而在另外一些场景下,没有固定的泊车位置，机器人可以选择任何可选位置(不可选位置包括造成路线堵塞的点等)进行泊车。
其次，需要根据距离和其它空闲机器人泊车位置选择本次具体泊车位。其中距离因素考虑尽量选择下一任务可能发生区域的位置从而降低移动距离提高响应速度，同时也需考虑其它空闲机器人泊车位置，平衡各区域机器人分布密度，避免特定区域空闲机器人过多造成资源浪费，而其它区域缺少机器人造成接受任务后响应不及时的情况。
本文部分内容参考合肥壹恒智能 - 智能机器人（AMR）/AGV调度任务分发与执行，特别说明！
