时空众包计算:面向共享经济的一种新型计算范式
2018-12-21

众包(Crowdsourcing)这一概念由JeffHowe于2006年首次提出,其是指通过公开的Web平台将任务分配给非特定的解决方案提供者群体来完成的分布式问题求解模式。众包最著名的典型案例是由美国卡内基梅隆大学Luis von Ahn教授所研发的reCAPTCHA系统,其巧妙地采用网络验证码的形式汇聚亿万网民的智慧,在不知不觉中为纽约时报完成了纸质版报纸的数字化录入工作。随着reCAPTCHA系统的成功,各类众包计算平台如雨后春笋般不断涌现,如早期的百度知道等“问答系统”的兴起,以及近年来Amazon Mechanical Turks(AMT),CrowdFlower,oDesk等各类大型在线工作招募与任务分包管理平台的诞生。该类平台不但带来了新的技术革命,更创造出巨大的市场经济价值。因此,众包技术为当今互联网时代的技术革命带来巨大潜能。正如《人民日报》2014年关于众包的报道所述“众包模式,大势所趋”。  

近年来移动互联网与物联网等技术的飞速发展,使得众包从基于在线Web平台的模式[1]转变为一种新型的计算模式,称为“时空众包(Spatiotemporal Crowdsourcing)”(也称为空间众包或移动众包)。简言之,时空众包是指以时空数据管理平台为基础,将具有时空特性的众包任务分配给非特定的众包参与者群体为核心操作,并要求众包参与者以主动或被动的方式来完成众包任务并满足任务所指定时空约束条件的一种新型众包计算模式。  

图1国内外时空众包应用

 

与此同时,时空众包更是共享经济时代的一种新型计算范式。共享经济最早由美国得克萨斯州立大学社会学教授MarcusFelson和伊利诺伊大学社会学教授JoeL.Spaeth于1978年提出,并在最近几年流行。其主要特点是,个体借助Web平台,交换闲置物品,分享自己的知识、经验,或者向企业、某个创新项目筹集资金等。时空众包通过Web平台整合线下参与者完成各类任务,创造社会经济效益,其应用涉及百姓“衣食住行”的各个领域。人们生活中常用的滴滴出行等实时网约车类应用,和百度外卖等物流派送类应用,都是共享经济时代时空众包计算的典型应用,并取得了巨大成功。如图1所示,各类时空众包应用已遍及百姓“衣食住行”的各个领域,并在人们日常生活中扮演着越来越重要的角色。时空众包所带来的巨大社会经济效益,使其很快引起了学术界的广泛关注。目前对时空众包计算的研究主要关注实时任务分配问题和动态激励机制设计问题,这两个问题分别涉及到时空众包平台的全局优化调控问题和时空众包应用的动力来源问题,因此被认为是时空众包研究的核心。

1.实时任务分配

实时任务分配是指当时空众包任务和参与者动态实时地到达众包平台时,平台根据他们的时空属性和其他相关信息,为每个任务分配适当的参与者。在实际应用中,由于任务和参与者的时间、空间分布具有很强的随机性,平台通常缺少足够的信息来指导任务分配,因此其匹配结果容易落入局部最优,导致复杂时空环境下的实时任务分配往往面临着资源分配不合理以及难以实现全局最优的挑战。

本课题组针对时空众包实时任务分配问题,提出了基于预测的实时任务分配算法。简言之,该方法首先对时空众包任务和参与者数量进行预测,再根据预测结果提前调度众包参与者以优化全局分配效果。具体而言,课题组提出利用“简单模型+复杂特征”的方法预测单位时间和单位空间内的任务数[2]。该方法组合了时间、空间、气象、事件和POI等简单特征。以网约车订单预测为例,图2所示为滴滴出行在北京市网约车订单的空间、POI和气象分布情况,这些特征会不同程度地影响任务的数量和分布情况;同时,某些特征之间还会联合地对任务分布产生影响,例如在特定节日时某个区域的任务可能会显著增多。基于上述观察,课题组提出对简单特征进行组合,并使用基于高维组合特征的线性模型预测任务数,其中模型特征的维度达两亿以上。在北京市和杭州市网约车数据集上的实验证明,该方法的预测效果超过了神经网络(Neural Network)和梯度提升树(GBDT)等复杂模型,能够很好地对任务数量进行预测。图3显示了基于上述方法的预测系统对北京市海淀区网约车订单需求的预测情况。

基于上述成果,课题组继而提出了基于预测的实时任务分配算法[3],算法整体框架如图4所示。该方法基于对任务和参与者的预测进行实时任务分配,以最大化任务完成数。该方法首先将预测空间划分为若干个时间片和若干个空间区域,并对这些区域在不同时间段内的任务和参与者数量进行预测,随后根据预测结果构建二分图进行匹配,以最大化任务完成数。在任务或参与者到来时,即按照之前二分图匹配的结果进行分配。当预测结果与实际情况不相符时,即让任务继续等待或者分配参与者前往指定的区域。经证明,该算法实现了0.47的竞争比,并且在滴滴出行网约车历史数据上的实验表明该算法能够更准确地指导实时任务分配,使得任务完成数提升达40%。

 

图2北京市网约车订单的空间分布,气象分布和POI分布

 

图3网约车订单需求预测系统

图4基于预测的实时任务分配算法框架

2.动态激励机制

另一方面,动态激励机制吸引参与者的加入,为时空众包应用提供动力驱动,因而也是时空众包计算的重要研究内容之一。据此,课题组首次提出了基于全局动态定价的解决方案[4],其旨在帮助平台动态地制定各个空间区域中参与者所提供服务的价格(平台报价),以使得平台期望收益最大化。为了实现该目标,需要解决以下挑战:(1)未知的任务需求:众包任务实时出现,且任务请求者对平台报价的决策(接受或拒绝)在平台确定价格之后才能为系统所知,这导致首先需要估计任务请求者对不同价格的接受概率;(2)众包参与者供给不足:针对时空众包应用中普遍存在的供给不足情况,需要选择合适的框架与算法对问题进行求解;(3)区域间供给依赖:由于不同参与者可覆盖的空间区域不同且存在重叠,某个区域内参与者数量的增加或减少会同时影响本区域以及其他区域的供给状况,这使得问题变得更加复杂。

图5动态定价原型系统

课题组提出了“基础定价+动态调价”的两阶段问题解决框架。其中,第一阶段,即“基础定价”阶段,计算在供给充足假设下的全局最优统一价格,其目的是估计众包市场的价格水平,并为第二阶段“动态调价”做准备。具体而言,当参与者供给充足时,平台的期望收益仅与时空众包市场的收益-价格曲线有关。课题组使用麦尔森价格曲线(MyersonReservePriceCurve)进行建模,并使用随机抽样方法拟合曲线的最大值以求取全局最优统一价格。第二阶段,即“动态调价”阶段,基于时空众包平台中参与者数量(供给)不足的实际情况、区域间供给的依赖关系和第一阶段给出的全局最优统一价格,使用多臂赌博机模型(Multi-armed Bandit Model)对动态激励机制设计问题进行建模,得到具有理论保证的动态定价结果。在人造数据集和真实数据集上的实验表明,课题组提出的算法在动态时空众包环境下能够有效地制定参与者所提供服务的价格。图5为基于上述理论成果实现的动态定价原型系统。

综上所述,课题组近两年来在时空众包计算的任务分配与激励机制问题上取得了上述成果。特别是通过与滴滴出行等共享经济类公司的合作,将课题组的部分研究成果转化到实际应用之中。正如本文开篇所述,时空众包计算正在成为共享经济时代的一种新型计算范式,我们也期望课题组后续相关的研究成果能有机会服务于百姓“衣食住行”的更多应用之中。

童咏昕,计算机学院,副教授,卓越百人,E-mail: yxtong@buaa.edu.cn

参考文献

[1]Yongxin Tong, Lei Chen, Zimu Zhou, H. V. Jagadish, Lidan Shou, Weifeng Lv. SLADE: a smart large-scale task decomposer in crowdsourcing. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2018, DOI: 10.1109/TKDE.2018.2797962.  

[2]Yongxin Tong, Yuqiang Chen, Zimu Zhou, Lei Chen, Jie Wang, Qiang Yang, Jieping Ye, Weifeng Lv. The Simpler the Better: A Unified Approach to Predicting Original Taxi Demands on Large-Scale Online Platforms. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), 2017, 1653-1662. (中国计算机学会推荐A类国际学术会议)

[3]Yongxin Tong, Libin Wang, Zimu Zhou, Bolin Ding, Lei Chen, Jieping Ye, Ke Xu. Flexible Dynamic Task Assignment in Real-Time Spatial Data.InInternational Conference on Very Large Databases (VLDB),2017, 1334-1345. (中国计算机学会推荐A类国际学术会议)

[4]Yongxin Tong, Libin Wang, Zimu Zhou, Lei Chen, Bowen Du, Jieping Ye. Dynamic Pricing in Spatial Crowdsourcing: A Matching-Based Approach. In ACM SIGMOD International Conference on Management of Data (SIGMOD), 2018. (中国计算机学会推荐A类国际学术会议)