机器人在线“偷懒”怎么办？阿里研究出了这两套算法

阿里妹导读： 随着互联网和电子商务的发展以及全球化的不断加速，中国产业持续升级，人工智能与机器人集群逐步被应用于制造业与物流供应链产业中。机器人集群的主要目的是与人协同合作，将人从沉重的重体力搬运任务中解放出来，专注于更精细的操作当中。由于在工业界的广泛应用与进一步智能化生产的思考，机器人集群调度成为了多智能体系统（Multi-agent System）学术研究中的一个新兴研究方向，其核心问题是如何调度机器人执行合适的任务并规划高效的路径，使得系统整体效率最优。

文末福利：七道典型算法 笔试 模拟题精解。

前言

与传统工业优化不同，多智能体系统中每个机器人互相替代性很强，流程是非线性的，导致系统效率很难直接建模。一般通过调整任务分配与移动路径，优化总任务距离来间接逼近系统效率。但我们在实践中发现，任务距离与系统效率并不强相关。由于成本的限制，机器人数量往往是有限的，当针对任务距离进行优化时，会导致部分作业人员过于繁忙，而部分作业人员无事可做的问题。

因此我们结合了菜鸟柔性自动化实验室在多智能体系统的实践与反思，于论文《Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers》中提出了基于工作站空闲时间的优化模型，关注如何最大化人的能力，从而推动整个系统达到更高的效率。我们对工作站的工作时间进行了离散化切分，模拟了机器人排队与等待的情况，并通过一套统一的网络流模型获得机器人与工作站的分配策略，以及机器人集群的路径规划，提升了系统产能。

论文地址：https://aaai.org/Papers/AAAI/2020GB/AAAI-KouN.3001.pdf

应用场景

基于多智能体集群的自动化技术方案的兴起和发展，促进了现代物流业的发展和全球化，代表着物流与供应链行业未来的一个主要方向。在阿里巴巴旗下菜鸟网络以及其合作伙伴的仓储和分拨中心有着成百上千的机器人在工作，实现包裹高效安全的到达用户手上。

图1. 机器人集群在分拨中心进行包裹分拨

图1是一个机器人分拨中心，几百个机器人在快速的把大量的包裹根据城市分拨，帮助干线物流网络更高效的运输包裹。机器人分拨中心的核心是三部分：工作站（Station），机器人（Agent）以及道口（Sorting Bin）。机器人会自动行驶到工作站领取包裹，通过自动扫码，然后再将包裹运输到对应的目的地道口，此时机器人会将包裹投进道口，从而完成包裹分拨。如何让这几百个机器人高效的运转，使得包裹可以更加快速的到达用户手中。这里要值得思考的是，一般性的会认为让这些机器人总的行驶路线最短就会使得整个分拨中心的效率最高。然而并不是这样，我们会看输入和输出，输入是所有的包裹，输出是各个道口中的包裹。受限于大量的包裹以及有限的机器人，仅仅是去优化路线最短并不能最大产出，这样就会存在部分工作站机器人排队而另一些工作站缺乏机器人的情况，在输入部分就已经限制了整个系统的产能。所以我们的目标是最小化所有工作站的空闲时间，来达到最大化系统产能的目的。下面会介绍如何建模来解决最小化空闲时间的问题。

问题建模

我们将上图机器人分拨中心模式进行抽象成如下图2所示，这样可以方便的引入多智能体路径规划的研究，其中核心三要素分别是橙色的工作站，绿色的机器人以及蓝色的道口。

图2.分拨过程，橙色节点为工作站，绿色节点是机器人，蓝色节点为分拨道口（每个道口对应了一个目的地结合）

要完成最小化工作站空闲时间，其核心是解决两个问题：

1. 每个机器人去哪个工作站接包裹，即任务分配(Task Assignment)问题；

2. 接完包裹后每个机器人按照什么路线运行到目的地道口，每个机器人可以视为一个智能体，即多智能体路径规划(Multi-Agent Path Finding, MAPF)问题。

这两个问题合在一起在学术上定义为TAPF问题。解决单次的任务分配和路径规划问题，我们定义为一个单次的TAPF问题。那么顺理成章的对于上述的自动化分拨中心持续作业的场景，可以抽象成Lifelong TAPF问题。接下来我们给出TAPF的定义。在给定的如下3个条件：

1. 一个全连接的无向图G(V,E)，

2. N个Station： ，

3. M个Agent： ，

TAPF会找到一个分配方案，这个分配方案表示即为每个Agent去哪个Station，同时会为所有的Agents找到没有冲突的路径使得可以更快的到达各自的工作站。

当每个Agent到达其目的地Station点后，Station将需要T的时间将包裹处理到Agent上的时间。因此如果给定一个时间窗口[0, KT)，那么我们可以设定每个工作站的操作时间为K个工作时间片: [0,T), [T,2T),..., [(K-1)T,KT)，且每个Station仅允许Agent的到达时间为kT，其中k=0,1,...,K-1。基于以上，我们认为当一个Agent在kT时刻到达其目的地工作站时，则这个工作站在时间段[kT,(k+1)T)内将会被占用。 

对于Life-Long TPAF问题，那就不是仅仅计算一次任务分配和多智能体路径规划问题。其本质就是不断的计算并更新每个Agent的分配方案和路径，这样对于上述场景中即是，每个机器人在运行过程中都在调整其目的地工作站和运行的路线，最终达到最小化工作站空闲时间最大化分拨中心产能的目的。

目标函数：基于以上定义，我们可以定义：在一个给定时间段内，最小化总的空闲时间，即为在这段时间内所有工作站的空闲时间之和。

示例说明：在后面的章节中，我们将用如下示例来详细解释每一种模型。

图3. 问题示例

• 两个Agent：   于时刻0从A出发，   于时刻1于C出发；

• 两个Station：   位于E点，其位置用表示，   位于F点，其位置用表示；

那么假设给定时间范围是[0,6)，工作站的处理时间T=2，我们可以看到一个最优的TAPF的解决方案是给分配工作站   ，且其路线为；分配到工作站，且其路线为，null表示0时刻不在地图中。这样两个工作站的工作时间段均为[4,6)，得到的目标函数即总的空闲时间为8。

ITO-空闲时间优化

图4. ITO模型，边上标记(cost, capacity)，为简洁起见(cost=0,capacity=1)的边没有标记

为优化空闲时间，如图4所示，我们建立了ITO（Idle Time Optimization）网络流模型。每一条边有两个属性(cost, capacity)，cost代表了每单位流量经过这条边需要付出的代价，capacity代表这条边能承载多少单位的流量。为简洁起见，在图中我们省略(cost=0,capacity=1)的边。

我们对每一个建立了一个对应的蓝色节点，对每个建立一个矩形Station子结构。Station子结构根据时间轴展开成K个离散的时间段，每个时间段[kT,(k+1)T)用节点表示，这样可以方便的考虑每个时间段的工作情况。Agent与Station子结构之间是一个全连通的二分图，表示每个Agent都能被指派到任意一个Station并占用一个对应的工作时间段。

图5. Agent节点与Station子结构的链接

图5解释了Agent节点与Station子结构的链接细节。对于每一组 ，我们可以估算到达的时间，如果这个时间段是[kT,(k+1)T)，那么可以在时间段开始排队，并填补之后任意一个时间段的空缺，排队的特性我们通过与之间的链接实现。

最后，为使得整个系统的空闲时间最少，我们希望找到一个工作站指派使得工作站时间段尽可能被占用。因此我们以Agent节点为流的入口，每个Agent分配一个单位流量，以工作站时间段为出口，每个工作时间段最多流出一个单位流量。这样每个时间段只能被一个Agent独占，每个Agent也只能占用一个时间段。这个网络流模型的最大流解即是使整个系统空闲时间最少的Agent-Station分配。当我们得出分配方案后，再通过MAPF算法求得无冲突的Agent路径，就可以按照该路径来控制调度整个多智能体集群。

图6. 示例的ITO模型

图6是前文示例对应的ITO模型，两个Agent的预测到达时间都是在第3个时间段，粗边是最大流的解，对应匹配为 与 。

PITO-结合路径规划的空闲时间优化

由于ITO将Station分配与路径规划分开考虑，其效果高度依赖于基于到达时间预测的精确程度。为了避免这个依赖，我们基于ITO设计了PITO（Path Finding with ITO），它将ITO与匿名MAPF网络流模型（Anonymous MAPF flow network, Yu and LaValle 2013）相结合，通过一个统一个网络流模型，同时计算得出Station分配与Agent路径。

图7. PITO模型

PITO的构造过程如图7所示由两部分构成。左侧MAPF网络用于计算生成路径信息，右侧ITO网络用于生成Station分配结果。

对于任何一个地图中的点，我们根据时间轴将其扩展到每一时刻t，t时刻的u用一个紫色节点表示。对于每一个，我们创建一个紧随其后的绿色辅助节点。由于与之间只有一条capacity为1的边，任何时刻t最多只会有一个单位的流通过u，从而避免了多个Agent同时到达u而相撞。我们在这里并没有在网络结构中设计避免在边上相撞，而是采用了一个小技巧，如果有两个Agent在一条边上相撞，则令他们在当前点等待，并交换两者的Station分配与后面的路径。由于Agent是匿名的，交换Station分配与后面的路径并不会影响空闲时间，从而达到了简化网络、加速求解的目的。

ITO网络和前一章的构造方式基本相同，我们不再将Agent与Station子结构直接相连，而是采用让Agent通过MAPF直接“走到”Station的方式。每个Station  有其真实位置。对于每个工作时间段[kT,(k+1)T)，我们从辅助节点 连接一条边到对应的工作站时间段，从而允许Agent在到达时可以占用其对应工作时间段。最后我们根据Agent的起始时间与起始位置，将它们连接到对应的节点上。

图8. 示例的PITO模型

图8是前文示例对应的PITO模型，蓝色粗边相连的节点展示了Agent的对应路径以及Station的分配结果。

Lifelong优化

这一章我们讨论如何将ITO与PITO应用到Lifelong的优化中。前面我们讨论了如何利用ITO与PITO求解One-Shot问题的Station分配与路径规划，每个Agent只需要去Station一次。但在现实场景中我们更关心的是一个动态的过程，Agent不断往返工作站与倾倒口。因此在每经过  的一个时间窗口，我们会重新根据场上情况重算为Agent分配Station并规划路径。

但为了让上个时间窗口的结果能够更好的为下一个时间窗口留出优化空间，Agent最好能占用更早工作时间段。我们通过增加惩罚节点P来达到这个目的。如图4和8，我们在ITO与PITO中增加了一个红色惩罚节点P，将它们转化为一个最小费用最大流的问题。P拥有足够大的流量并且跟所有的时间段相连但cost不为0，如果一个工作时间段没有Agent能够占据，就会产生一个从P到该时间段的等同于cost的惩罚。为了让Agent尽可能占据前面的时间段，我们用一个随时间单调递减的函数来表示P到的cost，比如采用线性递减或者指数递减函数。从而当空闲时间相等时，解会倾向于将空闲时间放在后面。

我们将Lifelong版的ITO与PITO（带时间窗口W与惩罚节点P）称为ITO-L与PITO-L。

实验分析

基于以上提出的的ITO-L和PITO-L算法以及我们给出3 种 对比算法，共5 种 算法框架进行Life-Long TAPF的实验对比。5种算法框架分别如下：

1）H(Inf)-L

采用Hungarian算法将所有agents按照总距离最近的方式统一分配到工作站，解决Task Assignment问题，然后采用改进的PBS算法求解MAPF问题；随着系统的运行不断重复实时的计算直至时间窗口结束。

2） H(1)-L

采用Hungarian算法重复计算[M/N]次将所有agents分配到工作站，解决Task Assignment问题；然后采用改进的PBS算法求解MAPF问题，随着系统的运行不断重复实时的计算直至时间窗口结束。

3） H(Q)-L

采用Hungarian算法重复计算[M/(NQ)]次将所有agents分配到工作站，解决Task Assignment问题；然后采用改进的PBS算法求解MAPF问题。可以发现H(1)-L和H(Inf)-L分别对应Q=1和Q=∞，随着系统的运行不断重复实时的计算直至时间窗口结束。

4） ITO-L

采用Primal Dual算法求解Min Cost Max Flow问题，解决Task Assignment问题；然后采用改进的PBS算法求解MAPF问题，随着系统的运行不断重复实时的计算直至时间窗口结束。

5） PITO-L

采用Primal Dual算法求解可直接得到TAPF问题的解，同时解决Task Assignment和MAPF问题，随着系统的运行不断重复实时的计算直至时间窗口结束。

下面将介绍我们采用的两个实验平台。

Agent Simulator

图9. 模拟实验中两个分拨中心的地图

Agent simulator是指在我们随机生成的分拨中心业务模式的地图集合上（如图9所示），其中橙色代表工作站，蓝色表示道口，Agent未标明在上述地图中。采用我们设计的仿真框架来模拟系统的运行，核心参数分别是：

• 工作站处理包裹时间，T = 10;

• 时间窗口范围为[0,600]，即KT = 600，K = 60;

• 每次重复计算的时间间隔30，即W = 30;

• Q = M/N + 5;

Industrial Simulator

图10. 分拨中心场地的2D布局，绿点为Station，灰点为不可达区域，黑点为道口

我们将ITO-L算法和H(Q)-L算法应用到上述应用场景的分拨中心的调度系统中；其中Task Assignment问题分别用对应的算法解决，实际中的路径规划采用centralized A*算法求解以及解决deadlock问题。我们将实际分拨中心的地图抽象抽象成如图10所示。核心参数分别如下：

• T = 4;

• K = 75;

• Q = 15;

数据结果

Agent Simulator的实验结果如下图11与12所示：

图11. 变化Agent数量的空闲时间趋势

图12. 相对H(Inf)-L算法，各算法对于总产能的提升比例

Industrial Simulator的实验结果如图13所示，其中全场分布的绿色方块表示带着包裹的机器人，全场分布的蓝色表示空载的机器人。

图13. Industrial Simulator运行截图，以及ITO-L与H(Q)-L在Industrial Simulator的表现

从以上数据结果我们可以看到：

1）在自测平台上，无论是ITO-L还是PITO-L表现的要比其他算法好，最小化空闲时间带来的产能提升超过10%，且我们知道10%的分拨能力的提升对一个持续运行的业务系统来说已经是比较好的表现。

2）在实际分拨中心的系统仿真中，我们的产能提升也可以达到11%，表明了我们所设计的算法的扩展性和实用性。

结束语

本文是研究任务分配，多智能体路径规划以及两者结合在一起的TAPF问题的一次成功尝试。我们的核心是针对当前物流行业前沿的自动化方案机器人作业模式的研究，分析其核心点Life-Long TAPF问题，首次提出了最小化工作站空闲时间的思想，来优化提高系统的效率。并在此基础上设计了两种算法框架ITO-L和PITO-L来求解Lifelong TAPF问题，达到最小化工作站空闲时间的目的。在实验部分，我们分别采用了Agent Simulator和Industrial Simulator两种仿真平台来验证所设计的两种算法。实验数据表明在两个测试平台上我们所提出的算法在系统产能上均可以有10%以上的提升，而对于一个长期运行的自动化作业系统来说，10%的提升已经是一个不错的表现，可以让大量的包裹更加高效快速的到达用户手中，对保证和提高物流时效、加速物流自动化的发展起到了积极的作用。本文主要表达，针对物流自动化机器人作业模式，我们在优化方向上和算法设计上的一些思考和做的事情。后续我们将继续分析行业问题，设计和改进算法来进一步加速算法应用来提高系统效率。

  福利来了 

算法学习

七道典型笔试算法模拟题精解

含“模拟”、“贪心”、“排序”等常见知识点

例题：Alice给了Bob一个字符串s，Alice想让Bob找出这个字符串中有多少个恰好包含了k个1的子串。请你帮助Bob计算出这些子串的个数是多少？

题解：本题可直接用双层循环扫描数组，找到所有的连续子串，查看每个组合是否拥有指定数量的1。精解将提供三种解题方法，开阔大家的思路。

识别下方二维码，或点击文末“ 阅读原文 ”查看更多算法题及精解：

你可能还喜欢

点击下方图片即可阅读

一套 SQL 搞定数据仓库？Flink有了新尝试

亿级搜索系统的基石，如何保障实时数据质量？

关注 「阿里技术」

把握前沿技术脉搏

戳我，查看算法题精解

。