--------点击屏幕右侧或者屏幕底部“+订阅”，关注我，随时分享机器智能最新行业动态及技术干货----------
前言
与传统工业优化不同，多智能体系统中每个机器人互相替代性很强，流程是非线性的，导致系统效率很难直接建模。一般通过调整任务分配与移动路径，优化总任务距离来间接逼近系统效率。但我们在实践中发现，任务距离与系统效率并不强相关。由于成本的限制，机器人数量往往是有限的，当针对任务距离进行优化时，会导致部分作业人员过于繁忙，而部分作业人员无事可做的问题。
因此我们结合了菜鸟柔性自动化实验室在多智能体系统的实践与反思，于论文《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 分拨过程，橙色节点为工作站，绿色节点是机器人，蓝色节点为分拨道口（每个道口对应了一个目的地结合）
要完成最小化工作站空闲时间，其核心是解决两个问题：
- 每个机器人去哪个工作站接包裹，即任务分配(Task Assignment)问题；
- 接完包裹后每个机器人按照什么路线运行到目的地道口，每个机器人可以视为一个智能体，即多智能体路径规划(Multi-Agent Path Finding, MAPF)问题。
这两个问题合在一起在学术上定义为 TAPF 问题。解决单次的任务分配和路径规划问题，我们定义为一个单次的 TAPF 问题。那么顺理成章的对于上述的自动化分拨中心持续作业的场景，可以抽象成 Lifelong TAPF 问题。接下来我们给出 TAPF 的定义。在给定的如下 3 个条件：
- 一个全连接的无向图 G(V,E)；
- N个Station
； - 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 的表现
从以上数据结果我们可以看到：
- 在自测平台上，无论是 ITO-L 还是 PITO-L 表现的要比其他算法好，最小化空闲时间带来的产能提升超过 10%，且我们知道 10% 的分拨能力的提升对一个持续运行的业务系统来说已经是比较好的表现。
- 在实际分拨中心的系统仿真中，我们的产能提升也可以达到 11%，表明了我们所设计的算法的扩展性和实用性。
结束语
本文是研究任务分配，多智能体路径规划以及两者结合在一起的 TAPF 问题的一次成功尝试。我们的核心是针对当前物流行业前沿的自动化方案机器人作业模式的研究，分析其核心点 Life-Long TAPF 问题，首次提出了最小化工作站空闲时间的思想，来优化提高系统的效率。并在此基础上设计了两种算法框架 ITO-L 和 PITO-L 来求解 Lifelong TAPF 问题，达到最小化工作站空闲时间的目的。在实验部分，我们分别采用了 Agent Simulator 和 Industrial Simulator 两种仿真平台来验证所设计的两种算法。实验数据表明在两个测试平台上我们所提出的算法在系统产能上均可以有 10% 以上的提升，而对于一个长期运行的自动化作业系统来说，10% 的提升已经是一个不错的表现，可以让大量的包裹更加高效快速的到达用户手中，对保证和提高物流时效、加速物流自动化的发展起到了积极的作用。本文主要表达，针对物流自动化机器人作业模式，我们在优化方向上和算法设计上的一些思考和做的事情。后续我们将继续分析行业问题，设计和改进算法来进一步加速算法应用来提高系统效率。
