近几年,Amazon Mechanical Turks,oDesk等众包应用快速发展,众包吸引了工业界和学术界的广泛关注.众包通常指一种把过去由专职员工执行的工作任务通过公开的Web平台以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式^[1].文献[2-5]对众包的研究现状和挑战进行了较好的综述.随着智能手机和移动互联网的兴起,空间众包成为众包发展的新方向.gMission^[6]是在国际上被广泛认可的空间众包平台.在国内,滴滴出行、百度外卖等空间众包平台对人们的生活产生着重要影响.在空间众包的研究中,任务分配问题是其核心问题之一.然而大部分现有任务分配问题研究的假设过强,导致其存在两点不足.

(1) 大部分研究基于静态场景(也称离线场景),即,全部众包任务和众包工人的时空信息在任务分配前已完整获知.但在动态环境(也称在线场景)下,待分配对象一个接一个地动态出现,并在等待一段时间后离开.每个对象出现时,系统需要立即做出以下两种决定之一:将该对象与还未离开的对象进行匹配(即做出任务分配,匹配、分配二词在本文通用),或令该对象继续等待.匹配决定(匹配或等待)一经给出无法更改.因此,现存基于静态场景的研究结果在实际应用中缺乏可行性;

(2) 现有研究均假设空间众包中的任务分配问题仅涉及众包工人和众包任务两类对象:众包工人移动到众包任务指定地点完成任务并获取报酬.然而目前还存在着大量其他类型的空间众包应用,其任务分配不仅涉及众包任务和众包工人,还受到第三方工作地点的影响.下文将详细介绍这类应用.

本文研究一类新型空间众包应用,在这类应用中,任务分配涉及3类对象:众包工人、众包任务和众包工作地点.任务分配后,众包工人和众包任务发布者均需要移动到某第三方工作地点.上述3类对象的任务分配问题在大量O2O应用中广泛存在.下文将以美容美发类O2O应用(如南瓜车)为例进行阐述.南瓜车是具有代表性的O2O理发应用,其也可被视为一个空间众包平台.客人(众包任务发布者)不仅会被分配理发师(众包工人),还将被分配理发店(众包工作地点).在分配完成后,客人和理发师都要到达被分配的理发店,然后由理发师借助理发店的设备给客人理发.这类新型空间众包应用中的任务分配问题需要将3种类型的对象匹配起来.本文将该问题建模成最大化三维匹配^[7]问题,并研究动态场景,即,3种类型的对象都动态出现.优化目标是最大化匹配总效用.

例1:设在众包平台上有4个众包任务t₁~t₄,3个众包工人w₁~w₃和3个众包工作地点p₁~p₃,他们的位置如图 1所示.众包任务和众包工人具有活动范围,如图中圆环所示,表示他们只能被分配该范围内的众包工作地点.众包工人和众包工作地点具有容量,表示其能接受的最大任务数.在本例中,众包工人w₁~w₃分别有容量1,2,1,众包工作地点p₁~p₃分别有容量1,2,2.任务分配的效用定义为众包任务的报酬与众包工人服务质量的乘积.众包工人、众包任务和众包工作地点的详细信息见表 1.在动态环境下,每当一个对象出现时,众包平台可以做出两种决策:(1) 将该对象与已经出现的另外两类对象进行匹配;(2) 等待,即:暂时不进行匹配,而是等待此后出现的对象再与其进行匹配.优化目标是最大化任务分配的总效用.如果对象的出现顺序是w₁,p₁,t₁,t₂,w₂,p₂,p₃,t₃,t₄,w₃,如图 2所示为一种可能的匹配过程.w₁和p₁先出现,由于无法构成匹配,他们进入等待状态.随后t₁出现,如图 2(a)所示,平台可以选择将其与w₁,p₁构成匹配,或令其等待.假设选择做出该匹配,则获得效用20×0.9=18.随后t₂出现,如图 2(b)所示.由于没有对象可与t₂匹配,平台令其等待.可以注意到:如果之前没有做出匹配＜w₁,p₁,t₁＞,则当前可做出匹配＜w₁,p₁,t₂＞,其效用为100×0.9=90.但在实际应用中,对于已经做出的匹配,系统无法更改.随后,w₂,p₂,p₃,t₃,t₄依次出现,如图 2(c)所示,可以选择做出匹配＜t₃,p₂,w₂＞和＜t₄,p₂,w₂＞,也可以选择等待.假设选择使这些对象都等待.最后w₃出现,如图 2(d)所示,并可以构成匹配＜t₃,p₃,w₃＞和＜t₄,p₃,w₃＞.这两个匹配的效用分别为48和72,系统选择做出这两个匹配.最终的匹配结果为M={＜t₁,p₁,w₁＞,＜t₃,p₃,w₃＞,＜t₄,p₃,w₃＞}.匹配的总效用为18+48+72=138.从以上匹配过程中可以看出:在动态环境下,需要在不知道随后出现对象信息的情况下,在当前对象出现时立即做出涉及3类对象的匹配决定,且不能更改.

本文的主要贡献有:

· 首次综合考虑第三方工作地点对任务分配的影响和任务分配的动态性,提出了空间众包环境下的3类对象在线任务分配问题;

· 提出随机阈值算法,并证明了该算法在最差情况下的竞争比;

· 采用在线学习方法将随机阈值算法扩展为自适应随机阈值算法,并证明该算法可逼近随机阈值算法使用不同阈值所能达到的最佳效果;

· 在真实数据和不同分布数据集上进行实验,证明了所提出算法具有很好的近似效果与伸缩性,能够满足实时性要求的时空开销.

本文第1节介绍相关工作.第2节给出问题定义.第3节讨论解决方案,包括一种基于随机阈值选择的在线算法、随机阈值算法和相应的基于在线学习方法的扩展算法、自适应随机阈值算法以及相应的理论分析.第4节给出实验结果及分析.第5节对全文进行总结.

1 相关工作

本节从分配问题与空间众包两个研究方向分别回顾与本文相关的工作,具体总结如下.

1.1 分配问题

根据分配问题(assignment problem)的静态/动态特点将其各类变种研究分为离线匹配问题(又称为静态匹配问题)与在线匹配问题(又称为动态匹配问题),分别进行阐述.

1.1.1 离线匹配问题

(a) 离线二分匹配

离线二分匹配问题长期以来都是组合优化领域中的经典问题.具体而言,是指给定无向图G=(U∪V,ε),U和V是互不相交的节点集合,ε⊆U×V是边集合,一个匹配M是边集ε的子集,使得对于所有U∪V中的节点,M中最多有一条边与其相连.根据二分图中边是否带有权重,又可将离线二分匹配问题分为最大二分匹配(maximum bipartite matching)和最大加权二分匹配(maximum weighted bipartite matching)^[8].上述两问题均在多项式时间内可解,其中,最大二分匹配问题的优化目标是最大化匹配数,针对该问题已经提出大量经典求解算法,其中最具代表的算法如Ford-Fulkerson算法^[8].此外,最大加权二分匹配问题的优化目标是最大化加权二分图匹配的边权加和,针对此问题也已存在众多经典算法,例如Hungarian算法^[8].另外,Burkard等人所撰写的专著^[9]对各类离线二分匹配问题的变种进行了全面完整地介绍.

除通用的离线二分匹配问题,还有一些现存的相关研究特别关注在二维空间下两类对象的匹配问题,此类研究又被称为空间匹配.根据优化目标不同,Wong等人^[10]考虑每个对象对另一种类型对象的偏好,使得所给出的匹配是稳定匹配.余亮豪等人^[11]研究在有容量约束的条件下最小化匹配的距离加和.Long等人^[12]研究最小化最大的匹配距离.注意,这些研究都基于离线情形假设.余亮豪等人^[13]研究连续空间匹配,在初始匹配给出后,在保持匹配稳定性的基础上维护匹配的最优性.Gao等人^[14]研究将资源分配给动态出现的空间事件,即事件在线到达,优化目标是最小化匹配距离的加和.这两项工作所研究问题的优化目标与本文不同.

(b) 离线三维匹配

不同于离线二分匹配问题是多项式时间内可解的,Garey等人^[7]证明了最大三维匹配问题(maximum 3- dimensional matching)是NP难的.进一步地,Kann等人^[15]证明了最大三维匹配问题是MAX SNP-hard^[16].在该问题的近似算法研究方面,Hurkens等人^[17]证明了最大三维匹配问题对任意ε>0是2/3-ε可近似的,Arkin等人^[18]证明了最大加权三维匹配问题对任意ε>0是1/2-ε可近似的.最大三维匹配问题和最大加权三维匹配问题的近似算法基于一种称为局部搜索(local search)的思路:尝试从现有匹配中删除一些边,然后加入与剩余匹配不冲突(即没有公共节点)的边,并判断是否能够获得更好的匹配结果.下面通过一个例子介绍这一思想.

例2:可以由表 1建立如图 3(a)所示的三分图,并定义每条边(连接3个点)的权值为表 1所示的任务报酬与工人服务质量的乘积.例如,边(t₁,p₁,w₁)的权值为20×0.9=18,边(t₂,p₁,w₁)的权值为100×0.9=90.对于容量大于1的对象,采用复制的方式.例如,p₂的容量为2,将其复制为p₂₁和p₂₂.经过复制操作后,得到图 3(b).算法首先依次将相互不冲突的边加入临时结果集.在图 3(b)中,按照自上而下顺序,算法先将边(t₁,p₁,w₁)加入临时结果集.在考虑边(t₂,p₁,w₁)时,由于该边与(t₁,p₁,w₁)冲突,因此不将其加入临时结果集.随后,算法依次将边(t₃,p₂₁,w₂₁)和(t ₃,p₂₂,w₂₂)加入临时结果集,此时,临时结果集如图 3(b)所示绿色部分.然后,算法进行局部搜索:对临时结果集中的每一条边,尝试删除该边,并引入与该边冲突但不与临时结果集中其他边冲突且权值大于被删边的边.算法首先尝试删除(t₁,p₁,w₁),并发现可以将(t₂,p₁,w₁)加入临时结果集.由于(t₂,p₁,w₁)的权值为90,大于(t₁,p₁,w₁)的权值18,算法执行此次替换;类似地,算法继续删除(t₃,p₂₁,w₂₁),引入(t₃,p₃₁,w₃₁);最后删除(t₄,p₂₂,w₂₂),引入(t₄,p₃₂,w₃₂).经过局部搜索后,结果集中的边如图 3(c)中所示红色部分.最后将其转化为原始图,如图 3(d)所示.局部搜索需要更改已经做出的匹配决定,因此并不适用于动态场景.

综上所述,上述离线匹配问题要求匹配执行前必须获得输入对象的全部信息,而不可根据部分二分图或三维图信息进行匹配.因此,上述方法都不适用于文本所讨论的动态在线匹配问题.

1.1.2 在线匹配问题

Hassan等人^[19]研究在线的空间任务分配问题,其优化目标是最大化任务分配数.文献[19]和本文工作有以下区别.

· 首先,本文研究的任务分配问题涉及3类对象:众包任务、众包工人和众包工作地点,并且这3类对象都动态出现;而文献[19]研究匹配众包任务和众包工人这两类对象,并且仅允许一类对象动态出现;

· 其次,本文研究最大化任务分配总收益,而文献[19]研究最大化任务分配的数量;

· 此外,文献[19]的解决方案无法给出竞争比保证,而本文的解决方案给出了竞争比分析.

Ting等人^[20]研究单边在线(一类对象动态出现)最大加权二分匹配问题,并给出了该问题目前最好的竞争比.Tong等人^{[21, 22]}研究双边在线(两类对象动态出现)任务分配问题,分别研究了最大化任务分配总收益和在最大化任务分配数的前提下最小化任务分配总花费.文献[20-22]与本文的区别是,本文研究涉及3类动态出现对象任务分配.

1.2 空间众包

本节介绍空间众包领域的3个主要研究问题,包括任务分配、任务规划和隐私保护.任务分配问题一直是空间众包研究中的核心问题之一,其研究角度为全局优化;任务规划问题则从众包工人的视角出发,最大化工人的收益,是一种局部优化;隐私保护主要研究在任务分配的过程中保护众包工人和众包任务发布者的位置隐私.

1.2.1 任务分配

Kazemi等人^[23]最早提出了空间众包平台上的任务分配问题,研究最大化任务分配数.Kazemi等人^[24]在文献[23]模型的基础上增加了任务完成的正确率约束.To等人^[25]扩展了文献[23]提出的模型,赋予匹配分数,优化目标是最大化匹配的总分数.Cheng等人^[26]研究在任务分配的同时最大化工人的可靠性和空间分布的差异性.She等人^{[27, 28]}研究了在时空冲突约束下的任务分配问题,并分别研究了离线分配与在线分配两种场景.此外,对于复杂类型的空间众包任务,通常非单一众包工人所能解决,而需要一个众包团队协同完成.针对此类问题,Gao等人^[29]研究了top-k最佳众包团队推荐问题.上述工作或研究离线情形,或研究仅涉及两类对象的分配,因此,其解决方案均不适用于本文研究的问题.

1.2.2 任务规划

Deng等人^[30]从单一众包工人的视角研究静态路径规划问题,该问题旨在给定此众包工人出行预算成本的条件,为其规划完成任务的路径,从而最大化其所完成任务的数量.此外,She等人^[31]研究了针对空间众包平台中全部众包工人的静态全局路径规划问题.上述两类研究只针对静态离线场景,Li等人^[32]进而研究了针对单一众包工人的动态在线路径规划问题,该问题在保证众包工人按时到达目的地的前提下,最大化工人完成任务所获得的收益.虽然上述工作也针对动态在线场景,但其仅关注单一众包工人,因此并不适用于本文研究的问题.

1.2.3 隐私保护

To等人^[33]基于差分隐私(differential privacy)给出了一种在保护众包工人隐私的同时提供有效空间众包服务的机制.Pournajaf等人^[34]研究了基于隐蔽位置(cloaked locations)进行任务分配.上述工作研究的问题与本文不同,且关注静态场景,其解决方案不适用于本文研究的问题.

2 问题描述

本节给出形式化问题描述.首先给出问题定义,然后介绍在线算法的评价模型,最后给出离线场景下问题的复杂性分析.

2.1 问题定义

首先介绍3个基本概念,然后给出匹配效用的定义.

定义 1(众包任务). 一个众包任务定义为t=＜l_t,r_t,u_t,b_t,e_t＞,表示任务的位置为欧式空间中的一个点l_t,同意接受的移动范围是以l_t为圆心、以r_t为半径的区域,任务的回报为u_t,任务的出现时间为b_t,截止时间为e_t.

定义 2(众包工人). 一个众包工人定义为w=＜l_w,r_w,c_w.q_w,b_w,e_w＞,表示工人的位置为欧式空间中的一个点l_w,同意接受的移动范围是以l_w为圆心、以r_w为半径的区域,同意接受的最大请求数(即容量)为正整数c_w,工人的服务质量q_w∈(0,1],出现时间为b_w,截止时间为e_w.

定义 3(众包工作地点). 一个众包工作地点定义为p=＜l_p,c_p,b_p,e_p＞,表示众包工作地点的位置为欧式空间中的一个点l_p,并且能够容纳的最大任务数(即容量)为正整数c_p,出现时间为b_p,截止时间为e_p.

参照文献[21],定义众包工人完成众包任务的效用:

定义 4(效用). 众包工人w完成众包任务t的效用定义为U(t,w)=u_t×q_w,即任务回报与工人服务质量的乘积.

最后,定义空间众包环境下的3类对象在线任务分配问题.

定义 5(空间众包环境下的3类对象在线任务分配问题). 给定众包任务集合T、众包工人集合W、众包工作地点集合P和一个效用函数U(·,·),众包任务、众包工人和众包工作地点按照某种顺序一个接一个地出现.求解目标是找到T,W,P的任务分配M⊆T×W×P,最大化任务分配总效用$MaxSun(M)=\sum\nolimits_{t\in T,w\in W}{U(t,w)}$且满足以下约束.

(1) 截止时间约束:当一个众包任务t或一个众包工人w或一个众包工作地点p出现时,可以给出任务分配,并要求众包工人活动时间[b_w,e_w]、众包任务活动时间[b_t,e_t]和众包工作地点活动时间[b_p,e_p]间两两相交;

(2) 不变性约束:任务分配一旦给出,则不能改变;

(3) 容量约束:每个任务t在M中最多出现1次,每个工人w在M中最多出现c_w次,每个众包工作地点p在M中最多出现c_p次;

(4) 空间约束:任务分配＜t,p,w＞需要满足p在以l_t为中心、以r_t为半径的范围内和以l_w为中心、以r_w为半径的范围内.

2.2 评价模型

在线算法研究中,通常使用竞争比评价算法性能.由于本文提出的算法都是随机在线算法,下面介绍随机在线算法的竞争比:

定义 6(竞争比). 设算法A是空间众包环境下的3类对象在线任务分配问题的随机在线算法.对任意的输入T,W,P,U(·,·),设ε[MaxSum(A)]是算法A返回匹配总效用的期望,MaxSum(OPT)是可能获得的最大匹配总效用.如果对于任意的输入都满足ε[MaxSum(A)]≥cMaxSum(OPT),则算法A的竞争比为c.

2.3 问题复杂性

本节分析所研究空间众包环境下的3类对象在线任务分配问题离线版本的复杂性.在离线版本中,3类对象的所有信息在任务分配前已知.将离线版本称为空间众包环境下的3类对象任务分配问题.由于三维匹配问题可以规约到该问题,可证明该问题是NP难问题.

定理 1. 空间众包环境下的3类对象任务分配问题是NP难问题.

证明:考虑空间众包环境下的3类对象任务分配问题的一种特殊情况:众包任务数、众包工人数和众包工作地点数相等,任务回报为1,工人服务质量为1,工人和众包工作地点容量为1.此时,该问题等价于三维匹配问题的优化问题,而三维匹配问题的决策问题已经被证明是NP完全问题^[7].因此,空间众包环境下的3类对象任务分配问题是NP难问题.

综上所述,由于空间众包环境下的3类对象在线任务分配问题的离线版本已经是一个NP难问题,因此,解决空间众包环境下的3类对象在线任务分配问题更加困难.

3 解决方案

首先给出一种解决该问题的基本算法,称为朴素随机算法,并对算法进行了简单讨论;随后给出一种基于随机选择阈值的在线算法,称为随机阈值算法,并给出该算法的竞争比分析;最后,结合在线学习方法扩展随机阈值算法,给出自适应随机阈值算法,并证明该算法效果接近随机阈值算法使用不同阈值所能达到的最佳效果.

3.1 基本算法 3.1.1 算法思想

朴素随机算法思想为随机地进行任务分配.具体地,每当有新对象出现,算法从能通过这一对象做出的任务分配中随机选择一个,加入匹配结果集.

3.1.2 算法伪代码

算法伪代码见表 2.

算法的输入为一个接一个出现的众包任务、众包工人和众包工作地点以及一个效用函数,输出为任务分配结果集M.在算法的执行过程中,首先,在算法的第1行、第2行,每当有新对象v出现,算法将能通过这一对象做出的任务分配加入集合Cand.在算法的第3行、第4行,如果Cand不是空集,则从集合Cand中随机选择一个元素,加入结果集M.算法的第5行返回结果集M.注意:当容量为c_w的众包工人w出现,算法将其看做c_w个容量为1众包工人,并逐一处理.同样地,当容量为c_p的众包工作地点p出现时,算法将其看作c_p个容量为1的众包工作地点,并逐一处理.

复杂性分析:对每个新出现的众包任务t∈T、众包工人w∈W和众包工作地点p∈P,朴素随机算法的时间和空间复杂度分别是O(|P||W|),O(|T||P|)和O(|T||W|).

3.1.3 运行样例

例3:设集合T,W,P中对象信息见表 1.出于简单起见,在例子中忽略截止时间约束.设对象出现顺序为w₁,p₁,t₁,t₂,w₂,p₂,p₃,t₃,t₄,w₃,朴素随机算法运行过程如图 4所示.如图 4(a)所示,最先出现的3个对象是w₁,p₁,t₁,算法将t₁分配给w₁,p₁, 并获得效用U(t₁,w₁)=18.在做出该分配后,w₁,p₁的容量减为0.如图 4(b),随后出现的对象是t₂.由于无法通过t₂做出任务分配,算法使t₂等待.如图 4(c)所示,随后出现的5个对象是w₂,p₂,p₃,t₃,t₄,算法做出任务分配＜t₃,p₂,w₂＞和＜t₄,p₂,w₂＞,并获得效用U(t₃,w₂)=12和U(t₄,w₂)=18.最后出现的对象是w₄,如图 4(d)所示.通过w₄无法做出任务分配,算法结束.最终的任务分配结果为M={＜t₁,p₁,w₁＞,＜t₃,p₂,w₂＞,＜t₄,p₂,w₂＞},总效用为18+12+18=48.

从上述例子可以看出,朴素随机算法给出任务分配结果总效用较低.原因在于:当效用较低任务分配与效用较高任务分配冲突,且效用较低任务分配的相关对象先出现时,算法将损失效用较高的任务分配.

3.2 随机阈值算法 3.2.1 算法思想

在朴素随机算法中,当两个任务分配相互冲突时,先做出的效用较小的分配,可能导致损失随后的效用较大任务分配.针对这一问题,本文扩展Greedy-RT算法^[20],设计了一种基于随机阈值选择的在线算法,称为随机阈值算法.Greedy-RT算法仅适用于两类对象匹配,且仅允许一类对象动态出现.本文将其扩展为适用于匹配3类动态出现的对象.随机阈值算法的主要思想是:首先选择一个效用阈值,在任务分配过程中,仅做出效用大于该阈值的分配.这种策略虽然可能会损失一些效用较小的分配,但在相互冲突的分配中能够选取较大者,从而规避最差情况.在随机阈值算法中,对于每个出现的众包工人w,将其看做c_w个同时出现且容量为1的众包工人.类似地,对于每个出现的众包工作地点p,将其看做c_p个同时出现且容量为1的众包工作地点.

3.2.2 算法伪代码

算法执行过程见表 3.

算法的输入为一个接一个出现的众包任务、众包工人和众包工作地点以及一个效用函数,输出为任务分配结果集M.在算法的执行过程中,在第1行、第2行,随机阈值算法根据任务分配全过程中可能获得的最大效用U_max,随机选择一个阈值(e^k),U_max可以通过历史记录学习得到.在算法的第3行~第6行,当一个新对象v出现时,算法从所有能通过v做出且效用不小于所选阈值的任务分配中任意选择一个,加入结果集M.算法的第7行返回结果集M.

复杂性分析:对每个新出现的众包任务t∈T、众包工人w∈W和众包工作地点p∈P,朴素随机算法的时间和空间复杂度分别是O(|P||W|),O(|T||P|)和O(|T||W|).

3.2.3 运行样例

例4:设集合T,W,P中元素信息见表 1.出于简单起见,在例子中忽略截止时间约束.由于U_max=100,θ=[ln(U_max+1) ]=5,k将从0,1,2,3,4中随机取值.假设取k=4,则阈值为e⁴≈20.1.设对象出现顺序w₁,p₁,t₁,t₂,w₂,p₂,p₃,t₃,t₄,w₃.随机阈值算法运行过程如图 5所示.在图 5(a)中,最先出现的3个对象是w₁,p₁,t₁,可以通过他们做出任务分配.但由于该分配效用U(t₁,w₁)=18<e³,算法不做出该分配.随后出现对象是t₂,如图 5(b)所示.通过t₂可以做出分配＜t₂,p₁,w₁＞,该分配效用U(t₂,w₁)=90≥e³,算法做出该分配.随后出现的5个对象是w₂,p₂,p₃,t₃,t₄,如图 5(c)所示,可做出分配＜t₃,p₂,w₂＞和＜t₄,p₂,w₂＞.由于U(t₃,w₂)=12<e³,U(t₄,w₂)=18<e³,算法不做出任务分配.最后出现的对象是w₃,如图 5(d)所示.通过w₃可做出分配＜t₃,p₃,w₃＞和＜t₄,p₃,w₃＞.由于U(t₃,w₃)=48≥ε³,U(t₄,w₃)=72≥e³,算法将这两个分配加入结果集M.最终分配为M={＜t₂,p₁,w₁＞,＜t₃,p₃,w₃＞,＜t₄,p₃,w₃＞},总效用为90+48+72=210.由于该算法是随机算法,其期望总效用为(48+48+48+210+162) /5=103.2.

与朴素随机算法给出结果相比,可以发现随机阈值算法给出了效用更高的分配结果.原因在于,随机阈值算法能从冲突的任务分配中选择效用较高者.但该算法存在的问题是:选择不同阈值时,算法获得的总效用差异较大,算法表现不稳定.

3.2.4 理论分析

定理 2. 随机阈值算法的竞争比是p_min/3e,其中,p_min=min{p₀,p₁,…,p_q-1}.

证明:设在离线场景下算法的输入对应的三分图是G.设${{G}_{[{{e}^{i}},{{e}^{i+1}})}}$是G的子图,该子图中所有连接3类点的边的效用都在区间[eⁱ,eⁱ⁺¹)内.设$OP{{T}_{[{{e}^{i}},{{e}^{i+1}})}}$和${{M}_{[{{e}^{i}},{{e}^{i+1}})}}$分别为在图${{G}_{[{{e}^{i}},{{e}^{i+1}})}}$上的最优匹配结果和随机阈值算法的匹配结果.对$OP{{T}_{[{{e}^{i}},{{e}^{i+1}})}}$中任意一条连接3类点的边,其所连接的3个点至少有一个在${{M}_{[{{e}^{i}},{{e}^{i+1}})}}$被某条边连接.因此,$|{{M}_{[{{e}^{i}},{{e}^{i+1}})}}|\ge |OP{{T}_{[{{e}^{i}},{{e}^{i+1}})}}|/3$.因此,

$\begin{align} & E[MaxSum(M)]=\sum\nolimits_{i=0}^{\theta -1}{{{p}_{i}}MaxSum({{M}_{[{{e}^{i}},\infty )}})} \\ & \text{ }\ge {{p}_{\min }}\sum\nolimits_{i=0}^{\theta -1}{MaxSum({{M}_{[{{e}^{i}},{{e}^{i+1}})}})} \\ & \text{ }\ge {{p}_{\min }}\sum\nolimits_{i=0}^{\theta -1}{{{e}^{i}}|{{M}_{[{{e}^{i}},{{e}^{i+1}})}}|} \\ & \text{ }\ge {{p}_{\min }}\sum\nolimits_{i=0}^{\theta -1}{{{e}^{i}}|OP{{T}_{[{{e}^{i}},{{e}^{i+1}})}}|}/3 \\ & \text{ }\ge \frac{{{p}_{\min }}}{3e}\sum\nolimits_{i=0}^{\theta -1}{MaxSum(OP{{T}_{[{{e}^{i}},{{e}^{i+1}})}})} \\ & \text{ }\ge \frac{{{p}_{\min }}}{3e}MaxSum(OPT). \\ \end{align}$

因此,随机阈值算法的竞争比为

$CR=\frac{{{p}_{\min }}}{3e}.$

3.3 自适应随机阈值算法

随机阈值算法性能受k值影响较大.为对其进行优化,本节介绍结合Randomized Weighted Majority算法^{[35, 36]}的自适应随机阈值算法.Blum等人^[37]使用Randomized Weighted Majority算法解决了一种具有内部状态的专家问题.本文使用文献[37]的证明框架,证明了自适应算法效果接近随机阈值算法的最佳效果.

3.3.1 基本思想

自适应随机阈值算法本质上采用了一种在线学习的策略.在随机阈值算法中,使用不同阈值将导致不同的匹配结果,具有不同的总效用.自适应随机阈值算法在算法运行过程中动态调整选择不同k值的概率p_k,增加效果较好k值被选择的概率,以提高算法的性能.

3.3.2 算法伪代码

自适应随机阈值算法伪代码见表 4.

算法的输入为一个接一个出现的众包任务、众包工人和众包工作地点以及一个效用函数,输出为任务分配

结果集M.在算法的执行过程中,第1行,设k的每个可能取0,1,…,θ-1权重为w_i=1,并设$W=\sum\nolimits_{i}{{{w}_{i}}}$,p_i=w_i/W,即:在还没有任何对象出现前,k将从0,1,…,θ-1中均匀随机选取.在算法的第2行、第3行,每当有新对象v出现,依照p_k随机选取k值.当使用新选取k值完成任务分配后,算法使用公式${{w}_{k}}={{w}_{k}}{{(1+\delta )}^{{{u}_{k}}/{{U}_{\max }}}}$更新w_k,并相应地更新W和p_k.符号u_k表示如果一直使用e^k作为阈值,随机阈值算法通过对象v获得的效用.

复杂性分析:对每个新出现的众包任务t∈T、众包工人w∈W和众包工作地点p∈P,朴素随机算法的时间和空间复杂度分别是O([ln(U_max+1) ]|P||W|),O([ln(U_max+1) ]|T||P|)和O([ln(U_max+1) ]|T||W|).

3.3.3 理论分析

定理 3. 设d=εU_max/2D.D是变化k值导致的损失上界(变化k值可能导致一直使用某一k值时的分配由于冲突无法给出),且满足D≥U_max,则自适应随机阈值算法的总效用至少是

$OPT(1-\varepsilon )-\frac{2D}{\varepsilon }\ln (\theta ),$

其中,OPT是选取不同的k值时随机阈值算法给出任务分配总效用的最大值.

证明:设算法当前的权重为w₀,w₁,…,w_θ-1,使用不同k值的效用为u₀,u₁,…,u_θ-1.更新后的权重为

${{{w}'}_{0}},{{{w}'}_{1}},...,{{{w}'}_{\theta -1}},$

其中,${{w}_{k}}={{w}_{k}}{{(1+\delta )}^{{{u}_{k}}/{{U}_{\max }}}}$.设$W=\sum\nolimits_{i}{{{w}_{i}}},{W}'=\sum\nolimits_{i}{{{{{w}'}}_{i}}},{{p}_{i}}={{w}_{i}}/W,{{{p}'}_{i}}={{{w}'}_{i}}/{W}'.$

当某个对象v出现时,算法通过分配v获得效用的期望为$\sum\nolimits_{i}{{{p}_{i}}{{u}_{i}}}$,将其称为E_v.从概率分布p_i转移到概率分布${{{p}'}_{i}}$的损失最多为

$D\sum\nolimits_{i:{{{{p}'}}_{i}}>{{p}_{i}}}{({{{{p}'}}_{i}}-{{p}_{i}})}\le \frac{D}{W}\sum\nolimits_{i:{{{{p}'}}_{i}}>{{p}_{i}}}{({{{{w}'}}_{i}}-{{w}_{i}})}\le \frac{D}{W}({W}'-W)=D\left( \frac{{{W}'}}{W}-1 \right)$

由于对任意x≤1,有(1+α)^x≤1+xα,则有:

${W}'\le \sum\nolimits_{i}{{{w}_{i}}\left( 1+\frac{\delta {{u}_{i}}}{{{U}_{\max }}} \right)}=W\sum\nolimits_{i}{{{p}_{i}}\left( 1+\frac{\delta {{u}_{i}}}{{{U}_{\max }}} \right)}=W\left( 1+\frac{\delta }{{{U}_{\max }}}{{E}_{v}} \right)$

因此,

$D\left( \frac{{{W}'}}{W}-1 \right)\le D\frac{\delta }{{{U}_{\max }}}{{E}_{v}}$

因此,算法从对象v获得的效用至少为

${{E}_{v}}\left( 1-\frac{D\delta }{{{U}_{\max }}} \right).$

设W_f是算法结束时的总权重,则有:

${{(1+\delta )}^{OPT/{{U}_{\max }}}}\le {{W}_{f}}\le \theta \prod\limits_{v}{\left( 1+\frac{\delta }{{{U}_{\max }}}{{E}_{v}} \right)}$

对任意的x∈[0,1],ln(1+x)∈[x-x²/2,x],则有:

$\frac{OPT}{{{U}_{\max }}}(\delta -{{\delta }^{2}}/2)\le \frac{OPT}{{{U}_{\max }}}\ln (1+\delta )\le \ln \theta +\sum\nolimits_{v}{\ln \left( 1+\frac{\delta }{{{U}_{\max }}}{{E}_{v}} \right)}\le \ln \theta +\frac{\delta }{{{U}_{\max }}}\sum\nolimits_{v}{{{E}_{v}}}.$

因此,

$\sum\nolimits_{v}{{{E}_{v}}}\ge OPT\left( 1-\frac{\delta }{2} \right)-\frac{{{U}_{\max }}}{\delta }\ln \theta $

因此,算法的总效用为

$G\ge OPT\left( 1-\frac{\delta }{2} \right)\left( 1-\frac{\varepsilon }{2} \right)-\left( 1-\frac{\varepsilon }{2} \right)\frac{2D}{\varepsilon }\ln \theta \ge OPT(1-\varepsilon )-\frac{2D}{\varepsilon }\ln \theta .$

4 实验分析 4.1 实验设置

实验环境:处理器为2.5GHz Inter(R) Core(TM) i7-4710MQ,内存为8GB,操作系统为Windows 10,编程语言为C++.

通过在真实数据和具有不同分布数据上进行实验,验证算法的运行效果.实验数据的参数设置见表 5,加黑的值为具有多种取值参数的默认值.

自适应随机阈值算法显然优于随机阈值算法,因此在实验中比较朴素随机算法(实验图中为Random)和自适应随机阈值算法(实验图中为Adaptive RT).人造数据依据表 5生成,最大效用U_max设置为100.在实际应用中,最大效用可以通过历史记录估计得到.在自适应随机阈值算法中,设δ=0.01.真实数据从空间众包平台gMission上收集得到.

4.2 实验结果 4.2.1 改变分布

在这组实验中,改变任务报酬分布情况,其他参数使用表 5中的默认值.当任务的报酬服从正态分布时,改变均值的实验结果如图 6(a)所示.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着均值的增加,两种算法返回结果的效用都增加,这是由于整体上任务的回报在增加.另一方面,随着均值的增加,两种算法总效用的差距在变大.可能的原因是:当均值增加,越来越多任务的回报集中在一个较大值附近,而自适应随机阈值算法在运行的过程中会过滤掉效用较小的边,从而增加了选择效用较大边的机会;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.原因是,自适应随机阈值算法需要维护每种单一阈值的运行历史.注意:虽然自适应随机阈值算法运行时间较长,但处理每个对象所消耗的时间是毫秒级,因此可以满足实时性的要求.

当任务的报酬服从正态分布时,改变标准差的实验结果如图 6(b)所示.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着标准差的增加,两种算法返回结果的效用有所波动但变化不大,这是由于任务报酬的均值不变;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

当任务的报酬服从幂率分布时,改变幂率分布Shape参数的实验结果如图 6(c)所示.注意:本文调整了幂率分布的集中方向,使得当参数变大时,分布向较大值集中.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着Shape参数的增加,两种算法返回结果的效用都在增大,这是由于任务的报酬越来越向U_max集中;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

4.2.2 改变数量

在这组实验中,改变任务分配对象的数量,其他参数使用表 5中的默认值.改变对象数量的实验结果如图 7所示.注意:为了验证所提出算法的可扩展性,在图 7(a)中增加了|T|分别取15k,20k,25k,30k和35k的实验结果.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着对象数量的增加,自适应随机阈值算法和朴素随机算法返回结果的效用都在增大,这是由于可达成的任务分配数增加;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

值得注意的是:在图 7(a)中,随着对象数量的增加,时间消耗的增加速度快于任务分配对象数量的增加速度.其原因在于:单位时间内到达对象的数量增加,导致在对每个对象进行分配决策时需要考虑更多的对象.但即使在数据量较大的情况下,每个对象的平均处理时间依然能够满足实时性的要求.

4.2.3 改变半径

在这组实验中,改变任务的半径,其他参数使用表 5中的默认值.改变任务半径的实验结果如图 8所示.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着任务半径的增加,两种算法返回结果的效用都在增大,这是由于可达成的任务分配数增加;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

4.2.4 改变容量

改变众包工作地点容量的实验结果如图 9所示.

可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法.随着众包工作地点容量的增加,两种算法返回结果的效用先较快增长,后缓慢增长.这是由于随着容量增加,可达成的任务分配数增加,导致分配总效用增加.但当容量增长到一定程度,任务分配数趋于饱和,总效用只有少量的增长;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

4.2.5 改变服务质量均值

在这组实验中,改变工人服务质量(服从正态分布)的均值,其他参数使用表 5中的默认值.改变服务质量均值的实验结果如图 10所示.

从图中可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法,且差距变化不大.随着服务质量均值的增加,两种算法返回结果的效用都增加,这是由于服务质量的增加导致了分配效用的增加;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

4.2.6 真实数据

使用空间众包平台gMission上收集到的数据进行实验.在gMission平台上指定了300个工作地点,设置了3 000个任务,并收集了前3 000个工人的数据.工人和任务的范围设置为1000m~3000m不等.实验结果如图 11所示.

从图中可以看出:

· 在效用方面,自适应随机阈值算法始终优于朴素随机算法;

· 在时间和空间消耗方面,自适应随机阈值算法的运行时间要长于朴素随机算法的运行时间,内存消耗要略高于朴素随机算法.

上述结果显示,所提出算法具有较好的实际应用价值.

4.3 实验总结

通过在真实数据和不同分布数据集上进行实验,发现自适应随机阈值算法在所有情况下都优于朴素随机算法.自适应随机阈值算法的时间消耗相比朴素随机算法较长,但其处理单个对象的时间消耗完全能够满足真实应用的实时性要求.在空间消耗方面,自适应随机阈值算法的内存消耗略高于朴素随机算法.

5 结 论

本文研究了空间众包中的一类新型动态任务分配问题,称为3类对象在线任务分配问题.由于在大量现存的空间众包应用中,众包工人与众包任务发布者均需要移动到某第三方工作地点来完成任务,因此本文聚焦于基于3类对象的在线任务分配问题.由于该问题所对应的离线问题为经典的难解问题——三维匹配问题,因此本文设计了一种在线算法——随机阈值算法,并给出了该算法在最差情况下的竞争比分析.此外,为了进一步优化随机阈值算法,本文采用在线学习方法将随机阈值算法扩展为自适应随机阈值算法,并证明此优化算法的效果接近随机阈值算法使用不同阈值所能达到的最佳效果.最终,本文通过在真是数据和大量不同分布数据集上的实验,证明了所提出算法不但具有很好的近似效果与伸缩性,而且拥有能够满足实时性要求的时空开销.