ICDE-2020 论文简析:空间众包中的预测任务分配 : 一种数据驱动的方法 Predictive Task Assignment in ...

• 利用数据驱动的方法预测系统工作人员未来的路线和任务位置，然后根据此预测优化整体任务分配。

目前的任务分配方法只是试图最大化当前的分配（即局部优化而不是全局优化），而不考虑未来的工人/任务。这些任务可能会在未来的时间实例中动态出现。当未来工人/任务先验地为人所知时，任务分配问题可以简化为经典的最大覆盖问题及其变体。

• 因此，时空众包的主要挑战来自于系统中到达的工人/任务的活力，这使得在线场景中获得最佳解决方案是不可行的。

• 为空间众包提供数据驱动的预测空间任务分配(DPSTA)框架的目的是在给定时间内动态出现员工和任务时，优化全局任务分配；
• 根据工人的旅行历史，预测未来的位置和路线，提出了两种新策略；
• 为估计任务的时空分布，设计了有效的图嵌入机制；
• 提出了权衡分配效率和有效性的贪婪和最佳任务分配算法；
• 实验证实，上述解决方案在实时分配空间任务方面是有效的。

在学习模型之前，有几个概念需要理解：

• ① 空间任务 <s.r,s.l,s.e,s.c>：表示是时间s.r发布的任务将在位置s.l并将执行s.e(s.r≤s.e)过期，其中s.l是 2D 空间中的一个点。每个任务s也被标记为s.c类。
• ② 可用工人 w=<w.φ，w.range，w.P>：给出一组时间实例，T={t，t 1，…，t n}(t 是当前时间实例)，一个可用的工人与它的可用时间实例 w.φ { t k，t k 1，…，t g}（?T），可达距离 w.range，以及相应的旅行路线 w.P（w.P由一组时间戳组成)。
• ③ 任务序列 R(Sw)=(S1，S2，…，S|Sw|)：给定一个工作人员 w 和一组分配给她的Sw任务，一个 Sw上述任务序列表示 w 访问 Sw 每个任务的顺序。在任务中 si∈Sw(即完成任务si的时间)处 w 到达时间可计算如下：
• ④基于特定位置的有效任务集 (L-VTS) ：给定时间实例集T和工作人员w的起始位置 w.l，这样得到的任务集 Sw被称为 w 特定位置有效任务集。
• ⑤ 基于特定路线的有效任务集 (R-VTS) ：给定工人 w 时间实例集 T 和路线 w.p，这样得到的任务集 Sw被称为 w 特定位置有效任务集。
• ⑥ 特殊路线最大有效任务集(L/R-MaxVTS）：给出一组时间实例 T，如果超集中，对员工没有一个超集中 w 如果仍然有效，则特定于 Location/Route 有效任务集 Sw它是最大的，被称为最大/特殊路线的最大有效任务集(L/R-MaxVTS)。
• ⑦ 空间任务分配对<worker，VTS>：给出一组时间实例 T={t，t 1，…，t n}，一组在 T 在此期间，可用的员工和任务由一组分配空间任务<worker，VTS>对组成，以<w1,VTS(w1)>、<w2,VTS(w2)> 表示，让 A.S 表示一组任务分配给所有工人，即 A.S=∪w∈WSw，A 表示所有可能的赋值方法。

在理解了这些主要概念之后，让我们来看看作者本文提出的数据驱动预测空间任务分配的框架 “DPSTA ”。DPSTA预测阶段(工人/任务预测)和分配阶段(任务分配)有两个阶段。

• ① 预测工人/任务在未来时间实例中的时空分布。
  • 工人预测：将工作人员的任务执行历史作为顺序数据，使用顺序模式挖掘(SPM)方法挖掘频繁的时间例子，作为工人更有可能完成任务作为她的可用时间。然后，空间时间被引入——递归神经网络(ST-RNN)模型预测每个未来工人的位置，并根据她的旅行历史设计混合模型来预测每个当前/未来工人的潜在路线。
  • 任务预测：设计路径约束深度步行(PC-DeepWalk)算法估计未来任务的数量，然后用核密度估计(KDE)该方法通过将任务视为空间点事件来预测未来时间实例中任务的位置分布。
• ② 第二阶段，根据当前和未来的工人/任务，将任务分配给合适的工人，以实现最大的任务分配。
  • 贪婪任务分配算法(GTA)；
  • 基于精确图划分的分解算法(OTA)。

作者提出的DPSTA如下图所示，空间众包框架包括两个组件(工人/任务预测和任务分配):

在这一部分，作者首先使用频繁的挖掘方法来检测工人的可用时间。然后使用 ST-RNN 模型和混合模型(集成模型匹配策略和时空序列相关性），以找到工人在可用时间内倾向于执行任务的未来位置和路线。

• 时间分布预测：采用频繁模式挖掘算法（SPM）从工人的任务中执行历史Tkw挖掘出更有可能执行任务的频繁时间w.φ（其中可用时间的发生频率超过给定最小支持阈值）。

• 预测空间分布：作者提出了两种预测未来工人空间分布的策略：

  • 位置预测：作者受 STRNN成功发现了模型 POI 受顺序相关性的启发，将其应用于预测每个未来工人在可用时间开始时的位置，并分析工人倾向于从这个位置执行任务。

    ST-RNN如下图所示，该模型的系统结构包括三层：输入层、隐藏层和输出层。

• 路线预测：根据过去对道路网络中工人的旅行情况GPS观测来预测所有工人的潜在路线。然而，模式匹配方法(PMA存在稀疏问题，即现有的历史轨迹远远不能覆盖所有可能的轨迹，这可能不返回预测结果。为了解决这个问题，当遇到无模式匹配时，作者将ST-RNN模型应用到预测过程中。这样可以提高路线预测精度和鲁棒性。 混合模型对于工人路线预测的概述如下图所示： ​ 该模型首先通过特征点路角提取(CP-RCE)方法从大量历史轨迹中提取路角；然后，利用基于这些街角的轨迹映射方法来表示历史轨迹数据和要预测的查询轨迹，从而生成以街角为中心的路线。

  ​ 在路线预测过程中，基于发现频繁运动模式，采用模式匹配方法(PMA)对未来路线进行预测。在获得频繁移动模式后，实现了模式匹配过程，从查询轨迹生成的以道路拐角为中心的路线的候选模式，找到最长的模式作为预测路线。

  ​ 当遇到无模式匹配时，可以使用ST-RNN模型来预测下一个移动的道路角。请注意，作者只是使用工人的最新速度作为她未来的速度，以计算她能够在她可用的时间内旅行的距离。在此距离下，基于混合预测模型的查询路径逐渐增长。

​ 采用平面KDE方法计算空间任务的密度，通过将研究区域划分为不相交和均匀的网格来预测它们的位置。在预测任务的位置之前，需要估计未来时间实例中可能落入每个网格单元的潜在任务（具有不同类型）的数量。作者构建了一个基于空间任务的网络如下图所示，并应用网络嵌入方法通过在未来的时间实例中考虑到每个单元的空间和时间关系来预测任务计数。

• 任务数量预测：通过使用历史数据来预测一组未来时间戳中每个网格的任务数量。

  • ① 基于任务的时空信息构建一个网络，称为基于空间任务的网络G=(V，E)，V包括两种类型的节点（即基于时间单元的节点TC和基于空间任务的节点ST）；E包括两种类型的边（即空间近似边缘SPR和任务相关性边缘TRR），SPR连接两个TC节点，TRR连接TC节点和ST节点。
  • ② 将节点编码为一个路径结构，设计了三种基于空间任务网络的路径来捕获空间信息、任务相关信息和时间信息。
  • ③ 提出了一种路径约束深度步行(PC-DeepWalk)算法，将网络路径嵌入到低维空间中，使网络的原始节点表示为向量。然后，应用λ-长度随机游走方法沿着所提出的路径，以基于空间任务的网络G作为输入，并为每个节点输出多个λ长度随机游走序列，从而获取每个节点的随机游走序列。接着，利用SkipGram模型学习每个节点的表示向量。最后，可以通过回归算法，同时考虑历史数据和其他节点来估计每个单元中的任务数。

• 位置分布预测：使用KDE方法在单元中任务样本的位置上计算潜在任务的发生概率，将概率较高的top-N位置设置为预测任务的位置。

​ 尝试找到所有工人的一个可能有效任务序列的并集，以使分配的任务数量最大化。

• 最大有效任务集生成：

  • 寻找可达任务：由于工人的可达距离和任务的过期时间的约束，每个工作人员只能在给定的时间实例集中完成一小部分任务。因此，我们首先找到每个工人在给定的时间段T中可以达到的任务集（即：工作人员w的特定位置可达任务子集L-RSw 和 工作人员w的路线指定可达任务子集R-RSw）。

  • 查找最大有效任务集：给定了每个工作人员的可达任务集，接下来找到MaxVTS的集合。提出了一种动态规划算法，以集合大小的升序迭代扩展任务集，并在每次迭代中为工作人员找到所有MaxVTS。

    • OPT(Q,sj)：定义为通过在工人可达范围内从w.l开始并以sj.l结束的约束来调度任务Q中的所有任务完成的最大任务数。则有如下定义，

      • δij=1这意味着sj可以在给定的时间周期T={t，t+1，…，t+n}中附加到R’后完成。基于方程5，我们可以得到每个工人的所有MaxVTS；

      • 当Q只包含一个任务si时，问题是简单的，opt({si},si)设置为1。当|Q|>1时，则需要在Q中搜索有效任务集的所有可能性，并找到实现opt(Q,sj)最优值的特定任务集。

      • 举例说明一下，如下图所示为例，工人w2具有2个可达任务{s1、s2}，并且在计算w2的L-MaxVTS时，算法首先计算opt({s1},s1)=1，opt({s2},s2)=1。对于大小从1到2的所有集合，迭代计算opt值和相应的R。例如，opt({s1,s2}，s2)=1，因为遵循任务序列(s1,s2)，只有s2可以完成，但opt({s1,s2}，s1)=2，是因为通过沿着路线(s1,s2)，s2和s1都可以完成。用同样的方法可以得到w2的R-MaxVTS。

• 贪婪的任务分配(GTA)：

  • 一旦获得了每个工人的MaxVTS，一个简单的解决方案就是从未分配的任务中为每个工人分配最大有效任务集，直到所有任务被分配或所有工人都被耗尽为止，这被称为贪婪任务分配算法，因为它不考虑分配任务的总体最佳策略。

• 最优任务分配(OTA)：首先构造一个工人依赖图，通过在这个图上采用图分区方法并在树结构中组织每个子图的工作人员集，将问题分解为多个独立的子问题。然后设计了深度优先搜索算法来寻找最优任务分配。

  • 工人依赖图(WDG)构造：基于工人之间的依赖/独立关系构建，其中两个工人如果没有可到达的任务，并且彼此依赖，则彼此独立。给定一个工人集W和任务集S，设计了一个WDG，G(V，E)，用于编码工人之间的所有依赖关系，其中每个节点v∈V表示工人wv∈W，如果两个工人wu和wv相互依赖，则u和v之间存在每个边e(u，v)和E。
  • 图分区：应用了一种基于图简化(GR)的方法，通过划分WDG图来分解工人的依赖关系。具体来说，degree-kGR是通过删除度不超过k的顶点，将一个图减少到另一个顶点较少的简单图中，以找到节点集X。

  如下图所示，举例WDG的简化过程： 该过程从通过删除顶点w1及其边的degree-2还原开始。顶点w1和它的邻居被推入堆栈。随后，顶点w2、w3和w5分别被移除，遵循与w1相同的原理。最后，剩下一个三角形，可以找到图的组并输出为图划分的节点：X={ {w1，w2，w3}，{w2，w3，w4}，{w3，w4，w5}，{w4，w5，w7}，{w4，w6，w7}},如下图(b)所示。 接着，根据图划分的性质，如果两个节点不共享相同的顶点，则属于这两个节点的工人相互独立，划分独立是为了可以独立地解决每个兄弟节点上的最优分配子问题。所以通过递归树构造(RTC)算法构造一个平衡树，如上图©所示。

  最后，将工人依赖图转换为树结构后，可以应用深度优先搜索过程计算树节点中每个工人的合适有效任务集，以找到最优分配。

Twitter-Foursquare(TF)数据集和gMission(GM)数据集

• 不同实验方法的性能对比：

• 工人预测方法的性能比较（基于定位预测）：

• 工人预测方法的性能比较（基于路线预测）：

• 任务预测方法的性能比较（训练集大小的影响）：

• 任务分配方法的性能比较（任务数量的影响）：

• 本篇论文作者主要提出了一种新的数据驱动框架，称为数据驱动预测空间任务分配(DPSTA)，通过动态考虑当前和未来进入空间众包系统的工人/任务，将任务分配给工人。同时，提出了不同的策略来预测未来工人和任务的时空分布。然后，设计了一种贪婪算法来有效地分配任务，并设计了一种基于图分区的分解算法来寻找全局最优任务分配。
• 这篇文章亮点我认为是：作者提出的框架从工人预测、任务预测和任务分配角度去分析、解决时空众包中的任务分配问题，在三种角度上分别将较新的方法应用于众包问题上，得到一种新的解决思路。对于这篇论文中的“数据驱动”一词，阅读下来觉得这个指的是workers和tasks的历史执行数据，通过对历史数据的挖掘进行预测，从而获取我们需要的数据。
• 这篇论文阅读下来主要是沿着作者的叙述思路读下来会觉得写的还方便作者理解的，这篇论文的工作量也挺大的，觉得是篇挺有意思的论文，之前一直没有读就是觉得可能会很难理解的，害。。。，接下来要继续多读多写吖。

• 作者讲解视频地址：https://www.youtube.com/watch?v=rwdRobkjPps
• 作者原文（有积分的支持一下吖，没有的也可以私信我邮箱）：https://download.csdn.net/download/Fama_Q/15503380
• 论文中文翻译版：https://download.csdn.net/download/Fama_Q/15503470