论文阅读 (55)：Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints

1 引入

1.1 题目

  2022：不确定性和时间约束下的动态多机器人任务分配 (Dynamic multi-robot task allocation under uncertainty and temporal constraints)

1.2 概述

  考虑在时间约束和任务完成不确定性下将任务动态分配给多个代理的问题。任务目标是最小化操作结束时不成功任务的数量。提出了一种多机器人分配算法，该算法将不确定性和多智能体协调下的顺序决策中的计算难题解耦，并通过层次方式解决。下层使用带有树搜索的动态规划计算单个代理的策略，上层解决单个计划中的冲突以获得有效的多代理分配。所提出的随机基于冲突的分配 (Stochastic conflict-based allocation, SCoBA) 将在合理假设下完成且期望最优。在实践中，SCoBA的高效计算可以满足在线交错规划与执行。
  验证数据集包括城市中多臂传送带拾取与放置，以及多无人机交付调度。结果展示在任务成功率上，SCoBA始终优于许多基线方法，并表现出相较于Oracle的强大竞争能力。它可以随着任务和代理的数量而很好扩展。

1.3 代码

  Julia：https://github.com/sisl/SCoBA.jl

1.4 Bib

@article{
    Choudhury:2022:231247,
author		=	{
    Shushman Choudhury and Jayesh K Gupta and Mykel J Kochenderfer and Dorsa Sadigh and Jeannette Bohg},
title		=	{
    Dynamic multi-robot task allocation under uncertainty and temporal constraints},
journal		=	{
    Autonomous Robots},
volume		=	{
    46},
number		=	{
    1},
pages		=	{
    231--247},
year		=	{
    2022},
doi			=	{
    10.1007/s10514-021-10022-9}
}

2 问题声明

  已有$N$个代理与$K$个任务，分别记为$[N]$和$[K]$。问题限定在$T$个时间步长中，对于每一个代理$n\in [N]$和任务$k\in [K]$，其服务的时间窗口 (Time window) 为$W_{nk}=(t_{nk}^l,t_{nk}^u)$，其中$l$和$u$分别表示$n$能够处理$k$的时间下限与上限。如果代理成功执行任务，则可能会有额外的停机时间 (Downtime)，例如机械臂将物体转移到垃圾箱的时间。我们将任务持续时间不确定性 (Task duration uncertainty) 定义为：
$${\tau }_{nk}(t)=\text{Prob}[n在时间步长t内完成k].\text{\hspace{1em}(1)}$$我们假设这种累积分布的知识是问题声明的一部分，尤其是不确定性下的任务调度，同时假设特定模型是领域相关的。$W$和$\tau$共同揭示了任务完成率的上届：
$$\text{Prob}[n完成k]\le {\tau }_{nk}(t_{nk}^u-t_{nk}^l).\text{\hspace{1em}(2)}$$对于所有的不成功任务，系统将受到${\sum }_{k}J(k)$单位的惩罚。一个代理一次只能处理一个任务。
  我们寻求一种最小化累计惩罚的分配策略$\pi$，其是一个代理到任务及其相应处理时间的映射，即$\pi :[N]\to [K]\times [T]$。由于任务的完成率是不确定的，简单的单次分配显然不够。当然，未来任务的处理时间依赖于早期任务的完成度。最终，我们的优化问题如下：
$$\begin{array}{ll}\underset{\pi \in \Pi }{\mathrm{argmin}}& \mathbb{E}\left[{\sum }_{k\in [K]}1[k]\cdot J(k)\mid \pi \right]\\ \text{ s.t. }& t\in W_{nk}\forall (k,t)\in \pi (n)\end{array}\text{\hspace{1em}(3)}$$其中$1[k]=1$表示任务$k$未完成，$\Pi$是所有可能分配策略的集合，以及约束是将任务限制在一个合理的时间内完成。余下部分中，将假设$J(k)=1$，即所有任务同等重要的无加权惩罚。
  上述离散时间滚动界限公式是相当普遍和有用的。这是因为我们关注上层分配而不是下层任务执行，这需要避免连续时间表示的额外复杂度。基础任务通常涉及时间受限的轨迹规划，为此有完善的模型和方法。此外，我们可以适当地交错计划和执行，并在新任务出现时重新计算分配策略。

2.1 示意

  描述两种不同的机器人设置来实例化我们的公式。首先，考虑沿着传送带分布的机械臂，如图2，有以下限制：
  1）每个机械臂都有一个自己的收集箱，用于收集从传送带上拾取的物体；
  2）物体从外部到达传送带，根据拾取策略或抓手特性，机械臂需要花费不同的时间来拾取；
  3）机械臂的范围是有限的，一个物体在超出范围之前不会被拾取；
  4）未被机械臂拾取的物体将在后续手动拾取；
  5）目标是尽可能多的拾取与放置物体。

  图2：$N=3$，$K=5$的机械臂拾取示意：传送带为单位长度，每个机械臂的工作空间跨越为0.3个单位，虚线表示限制范围。给定传送带速度，任何机械臂-物体对的时间窗口$\le 5$秒。

 
  然后，考虑在城市中进行包裹递送的多无人机调度：
  1）交付任务是通过客户请求的外部流程产生的；
  2）根据飞行条件，无人机从产品仓库到包裹递送地点需要不同的时间；
  3）请求同样有时间窗口，无人机必须等到用户的时间窗口开始，再将产品交付给客户，并且延迟交付会受到惩罚；
  4）在确定的时间范围内，目标是最小化延迟交付的数量。

2.2 挑战

  以下将加大问题的求解复杂度：
  1）基于多机器人任务分配的归类，我们的问题归属于ST-SR-TA，即单个机器人在延续时间内处理单个任务。ST-SR-TA问题是NP难调度问题的一种，特别是资源约束的多代理调度；
  2）任务执行时间的不确定性进一步加大求解难度；
  3）时间窗口要求算法考虑时空任务关系，从而使分配更加困难；
  4）新任务流入需要我们的方法能够有效地交错规划与执行，例如，在新任务到达时重新调度。

3 层级多机器人任务分配

  算法挑战包括不确定性下的顺序规划以及多代理协调。对于大型设置，联合多智能体规划问题在计算上是令人望而却步的，已有的方法则通常使用近似规划、近似优化，或者简单启发式方法。与此对应，所提出的ScoBA使用两层层次结构来处理该问题：
  1）下层独立确定每个代理的最佳任务顺序而忽略其他代理；
  2）上层解决跨代理任务分配中的潜在冲突，以获得有效的多机器人分配；
  3）两个层级间在线交错规划与执行，并利用协调图来进行稀疏代理交互。

3.1 下层：单一代理策略

  已知任务集合、时间窗口，以及任务完全度不确定性分布，目标是构建一个代理的任务尝试策略树。由于任务的时耗是随机的，任务的第一次可能尝试时间取决于在它之前尝试的任务。我们做了一个简化的近似——代理尽快尝试一项任务，并在窗口结束时观察结果。这种近似通过将任务视为离散事件而不是延续事件以折叠时间维度。
  给定单个机器人$n_1$和三个任务$k_1,k_2,k_3$，策略树的搜索过程如图3：
  1）按照起始时间窗口升序排序任务；
  2）沿着时间轴扫面，并在每一个事件节点更新树。事件节点包括窗口的起始，或者任务完成后的终了时间；
  3）对于起始窗口，引入成为尝试或者放弃的决策节点；
  4）对于结束窗口或者终了时间，引入表示成功或者失败的输出节点，其输出概率取决于任务尝试的最小可行开始时间。

  图3：下层SCoBA为单个代理生成有效任务的策略树。具体而言，通过沿时间轴扫描并在任务时间窗口的开始或结束时分支。在窗口开始时，两个新的决策节点 (椭圆) 被引入：尝试 ( \leftrightarrow ) 或者放弃 ($\nleftrightarrow$)。在窗口结束时或者终了时间后，输出节点 (圆角矩形) 描述成功或者失败。在树生成之后，动态规划将值从叶子传播到根。概率值$p=0.03$、$p^{\prime }=0.1$，以及$p^{\prime \prime }=0.9$只是说明同一个尝试节点 ($n_1{k}_2$) 所具有的三个不同的副本 具有不同的输出概率
 
  二叉策略树的叶子包含沿其分支的累积惩罚，例如，每个不成功任务的惩罚为1。然后使用动态规划从叶子将值传递到根。对于一对输出节点，我们将父节点的值 (表示为$V$) 设置为其子节点的期望值：
$$V(\text{parent}):=p\cdot V(\text{Fail})+(1-p)V(\text{Succ}).\text{\hspace{1em}(4)}$$  对于一对决策节点，父节点的值设置为孩子节点的最小值：
$$V(\text{parent}):=\min \{V(\text{child1}),V(\text{child2})\}.\text{\hspace{1em}(5)}$$对应到图3中，有$V(\text{root})=\min \{V(n_1{k}_1),V(n_1\nleftrightarrow k_1)\}$。生成的树对策略进行编码，该策略将代理对计划范围内的所有任务的期望惩罚最小化，$V(\text{root})$则是期望惩罚的值。通过跟踪最小值子节点直到第一次尝试节点，以获得分配给代理的下一个任务。

3.2 上层：多代理协调

  策略树为单个代理确定近似最优的任务尝试序列。对于多个代理，其树的搜寻是独立的，这将可能出现冲突。而由于我们的目标函数依赖于所有代理，因此直接打破关系可能会产生很差的全局分配。多智能体寻路算法面临类似的挑战，必须解决最短路径之间的智能体冲突。基于冲突的搜索是解决这个问题的有效策略，其将单代理路径规划和路径间冲突解耦，在实践中被证明是有效的，且不失最优性。
  我们利用基于冲突搜索中代理间冲突解决方法，上层SCoBA将搜索从下层获得的单个代理的解决方案之间的冲突，进而生成的二叉约束树，如图4。两个代理$n_1$和$n_2$如果在交叠的时间窗口内分配了同样的任务$k$，它们就是冲突的，即$(k,t_1)\in \pi (n_1)$、$(k,t_2)\in \pi (n_2)$，且$t_2\in W_{n_1,k}$或$t_1\in W_{n_2,k}$。代理的约束是对该代理的树搜索排除在考虑范围之外的任务。约束树的每一个节点包括：
  1）约束的集合，即每个代理需要忽略的任务；
  2）考虑所有约束的多代理分配；
  3）分配的代价。
  于SCoBA而言，分配代价是每个代理的期望惩罚之和，期望惩罚是当前代理策略树根节点的值。分配成本作为约束树上最优优先搜索的标准，将一直持续到找到一个无冲突的分配。

  图4：存在分配冲突的约束树节点生成两个子节点，在冲突代理 ($n_1$和$n_3$) 和任务 ($k_1$) 上具有相应的约束。约束树上的最佳优先搜索返回具有无冲突分配的第一个高层节点

3.3 随机基于冲突的分配 (SCoBA)

  算法1展示了使用搜索树作为PLANTREE子程序的SCoBA算法。
  行2–6：初始化约束树为空，为每个单独的代理运行PLANTREE的分配；
  行9–14：扩展高级节点时，检查相应分配的有效性。如果没有冲突，则返回此分配作为解决方案；否则，对于两个或多个代理之间的每次冲突，均添加新的子节点，其中对所涉及的代理施加约束。子约束树节点继承其父节点约束，并为特定代理添加一个约束。

  考虑图4中的简单说明性示例。根节点有代理$n_1$和$n_3$都分配给任务$k_1$。此冲突产生两个约束，一个由两个子节点中的每一个继承。第一个约束将$k_1$从重新计算的策略树搜索中排除$n_1$。第二个约束对$n_3$的作用相同。对于每个新的非根节点，下层树搜索仅在为其添加约束的代理上重新运行 (行18)。生成的两个子节点都是无冲突的，但分配成本较低的左侧子节点的值为$2.6$，其作为解决方案返回。
  我们的问题设置是在线的和随机的。然而，在一些简化的假设下，我们可以建立SCoBA的最优性和完整性属性。

命题1：
  如果：
  1）没有新任务在线添加；
  2）树搜索全局执行；
  3）任务完成度由终了时间窗口决定，那么SCoBA具有期望最优，即SCoBA可以在全局时间之前最小化未完成任务数量的期望。

命题2：
  在命题1的基础上，SCoBA是完整的，即如果一个合法的分配存在，SCoBA将返回它。

  为满足最优性，我们使用顺序决策中的现有结果来表明SCoBA的下层程序，即策略树生成，以使得对于单个代理的期望是最优的。 然后证明了SCoBA的上层多智能体协调满足继承基于冲突的搜索的多智能体最优性充分条件。展示了SCoBA的上层约束树如何具有有限数量的节点。因此，如果存在，系统的最佳优先搜索将找到有效的解决方案。

3.3.1 交错计划和执行

  为了解决新任务，我们将计划和执行在线交错。对于单代理策略树搜索，根据计算要求截断搜索范围。在实现中运行扫描，直到第一个任务的时间窗口在它之前的所有任务的终了时间之后开始。对于多智能体协调，再次基于实时计算约束设置了上层冲突数量的阈值。如果超过阈值，返回当前的上层解决方案。对于分配给同一任务的代理，将随机打破联系，并保留未分配的代理以在下一个时间步长分配给新任务。

3.3.2 协调图

  SCoBA适用于任意代理配置和代理间约束，进一步使用来自多智能体决策的协调图 (CG) 来提高效率。在CG中，每个节点代表一个代理，每条边编码代理之间的潜在定向依赖关系，这样只有连接的代理需要协调动作，或在我们的例子中分配。问题协调图的选择取决于领域，例如，在传送带的例子中，手臂沿着传送带排列，它们的工作空间是互斥的，因此协调图是从第一个手臂到最后一个手臂的有向链。
  CG结构影响了SCoBA的上层多智能体协调阶段。两个代理之间没有边意味着它们的可能任务集不相交，即它们不会有冲突的分配。因此，在实践中，SCoBA不需要考虑所有代理之间的依赖关系。如果CG是定向的，如在传送带中，我们将沿着CG的拓扑排序运行树搜索代理。对于任何代理，排除已分配给其前任的任务。通过构造，最终将获得无冲突的分配 (在上层约束树中不会生成任何子节点)。如果CG是无向的，如在多无人机交付领域，这种拓扑排序是不可行的，冲突可能是不可避免的。但是，如果CG有多个连通组件，那么不同组件中的节点不能相互冲突，因此可以在每个组件上并行运行SCoBA。