??2022:动态多机器人任务分配在不确定性和时间限制下 (Dynamic multi-robot task allocation under uncertainty and temporal constraints)

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

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

@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} } 

??已有$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）物体从外部到达传送带，根据拾取策略或抓手特性，机械臂需要花费不同的时间来拾取；
  3）机械臂的范围是有限的，一个物体在超出范围之前不会被拾取；
  4）未被机械臂拾取的物体将在后续手动拾取；
  5）目标是尽可能多的拾取与放置物体。

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

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

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

  已知任务集合、时间窗口，以及任务完全度不确定性分布，目标是构建一个代理的任务尝试策略树。由于任务的时耗是随机的，任务的第一次可能尝试时间取决于在它之前尝试的任务。我们做了一个简化的近似——代理尽快尝试一项任务，并在窗口结束时观察结果。这种近似通过将任务视为离散事件而不是延续事件以折叠时间维度。
  给定单个机器人$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\leftrightarrow k_2$) 所具有的三个不同的副本 具有不同的输出概率
 
  二叉策略树的叶子包含沿其分支的累积惩罚，例如，每个不成功任务的惩罚为1。然后使用动态规划从叶子将值传递到根。对于一对输出节点，我们将父节点的值 (表示为$V$) 设置为其子节点的期望值：
$$V(\text{parent}):=p\cdot V(\text{Fail})+(1-p)V(\text{Succ}).\text{\hspace{1em}(4)}$$  对于一对决策节点，父节点的值设置为孩子节点的最小值：
V ( parent ) : = min ⁡ { V ( child1 ) , V ( child2 ) } . (5) \tag{5} V(\text{parent}):=\min\{ V(\text{child1}),V(\text{child2}) \}. V(parent):=min{ V(child1),V(child2)}.(5)对应到图3中，有 V ( root ) = min ⁡ { V ( n 1 ↔ k 1 ) , V ( n 1 ↮ k 1 ) } V(\text{root})=\min\{V(n_1\leftrightarrow k_1),V(n_1\nleftrightarrow k_1)\} V(root)=min{ V(n1​↔k1​),V(n1​↮k1​)}。生成的树对策略进行编码，该策略将代理对计划范围内的所有任务的期望惩罚最小化，$V(\text{root})$则是期望惩罚的值。通过跟踪最小值子节点直到第一次尝试节点，以获得分配给代理的下一个任务。