基于位置隐私保护的空间众包任务分配方法

针对当前空间众包任务分配中存在用户等待时间长和工人位置隐私保护度低的问题，提出一种面向位置隐私保护的空间众包任务分配方法。利用虚拟生成算法为众包工人提供一个虚拟位置，并发送到空间众包服务器中；为了提高任务分配效率，设计一种基于ε-贪婪算法的自适应批处理机制；根据动态批量大小，采用最大分数分配策略来解决众包平台中动态任务分配问题。该方法不仅减少了工人行进距离和保护了工人的隐私信息，还最大程度地降低了任务等待时间，提升了用户体验。     

一种基于时空位置预测的空间众包任务分配方法

空间众包技术在现实物理世界中有着丰富的应用场景,得到学术界和工业界的广泛关注.任务分配是空间众包的主要研究问题之一,即把工人分配给合适的任务.但是现有的任务分配方法大多假设众包工人和空间任务出现的位置和时间是已知的,忽略了真实的众包平台中众包工人和空间任务的动态变化,由于空间众包平台的强时效性,这种情况下设计的分配方式...     

面向全局优化的时空众包任务分配算法

针对时空众包任务分配研究中未考虑多方参与对象的效益和连续任务分配的全局优化,导致分配效果不佳的问题,提出一种面向三方综合效益全局优化的在线任务分配算法。首先,基于在线随机森林和门控循环单元网络预测出下一时间戳内众包对象（众包任务和工人）的分布情况,进而结合当前时间戳内众包对象的情况构造二分图模型,最后采用带权二分图最优匹配算法完成任务分配。实验结果证明了所提算法在连续任务分配过程中实现了综合效益的全局优化。与贪心算法对比,该算法在任务分配成功率方面提升25.7%,在平均综合效益方面提升32.2%,在工人平均机会成本方面提升37.8%;与随机阈值算法对比,该算法在任务分配成功率方面提升27.4%,在平均综合效益方面提升34.7%,在工人平均机会成本方面40.2%。     

基于预测分析的时空众包在线任务分配

针对时空众包在线任务分配问题,提出任务范围调节算法DMRA与基于预测分析的在线任务分配算法PAMA。DMRA算法以任务位置为中心,根据工人密度动态调整任务的范围。PAMA算法基于历史统计概率,采用贝叶斯分类器预测下一时间戳的对象分布情况,在此基础上,执行带权二分图最优匹配算法以完成任务分配。实验结果表明,将DMRA算法与PAMA算法相结合,能够提升任务分配的总效用,降低工人的差旅成本,任务分配性能优于贪心算法与随机阈值算法。     

基于动态阈值的时空众包在线分配算法

为提升时空众包动态现实场景中任务分配总效用,提出一种基于在线随机森林的动态阈值算法（DTRF）。首先,根据众包平台中工人和任务的历史匹配数据初始化在线随机森林;然后,通过在线随机森林预测每位工人期望的任务回报率作为阈值,按阈值为每个工人选取候选匹配集;最后,从候选匹配集中选取当前效用总和最高的匹配,同时用分配结果更新在线随机森林。实验结果表明,所提算法在提升总效用的同时有效地提高了工人的平均收益。与贪心算法相比,所提算法的任务分配率提升了4.1%,总效用提升了18.2%,工人平均收益提升了11.2%。与随机阈值算法相比,所提算法在任务分配率、总效用、工人平均收益等方面都有较好的提升,且稳定性更好。     

时空众包环境下基于统计预测的自适应阈值算法

针对时空众包环境下任务分配随机性过高且效用值不理想的问题,提出一种基于统计预测的自适应阈值算法。首先,实时统计众包平台中空闲的任务、工人及工作地点的数量以设置阈值;其次,通过历史数据分析将任务与工人的分布分为均衡的两个部分,并用Min-max normalization方法为每个任务匹配一个确定的工人;最后,计算匹配到的工人出现的概率,以验证任务分配的有效性。使用相同真实数据的实验结果证实,与随机阈值算法相比,基于统计预测的自适应阈值算法的效用值提升了7%;与贪心算法相比,其效用值提升了10%。实验结果表明,基于统计预测的自适应阈值算法能够减少任务分配过程中的随机性并提高效用值。     

考虑工人路径的多智能体强化学习空间众包任务分配方法

针对工人和任务进行匹配是空间众包研究的核心问题之一,但已有的方法通常会忽略工人路径对任务分配结果产生的影响.传统的任务分配方法存在计算速度慢、适用范围小和协作效果不突出等问题.对此,从空间众包平台的角度出发研究面向路网的空间众包任务分配问题,以任务完成时间最短为目标,提出考虑工人路径规划的基于多智能体强化学习的QMIX-A*算法,缩短任务的平均完成时间,进而提高用户的满意度.大量的数值仿真研究验证了QMIX-A*的有效性和稳定性,为空间众包服务平台的任务分配与路径优化策略的选择提供决策支持.     

新型时空众包平台中的在线三维稳定匹配问题

近年来,时空众包平台正逐步走入人们的生活,并受到研究者的广泛关注.在时空众包平台中,任务分配是一个核心问题,即在满足时间和空间的条件约束下,如何为不同用户分配合适的工人来进行服务.现有的工作往往将最大化任务匹配个数或效用值之和作为研究目标,这些方法关注全局的解决方案,但是没有考虑用户和工人的偏好来提高他们对于分配的满意程度.此外,现有工作大多只考虑用户和工人两种角色,即工人移动到用户当前位置进行服务.但是,新型时空众包平台的中往往包含用户、工人和工作点三种角色,即为用户和工人分配一个工作点来进行服务.基于以上不足,三维时空稳定分配问题被提出.但是,此问题只关注了静态场景,而时空众包平台往往是在线的,即工人和用户发出的任务都是实时出现的.因此,提出了面向新型时空众包平台的三维在线稳定匹配问题和一种基础算法.通过分析基础算法的不足,结合人工智能的方法提出一种改进算法来解决这个问题.采用大量的真实数据和合成数据集来验证算法的高效性和有效性.     

偏好匹配满意度最大化的众包任务分配

众包任务分配机制对众包任务完成质量起着至关重要的作用,然而现有的分配方法未在稳定性条件下考虑众包用户双边偏好,分配结果的准确性有待提高,并且存在众包用户因不满意当前分配对象而导致众包任务完成质量较低的问题.为此提出一种基于偏好匹配的众包任务分配方法,该方法首先考虑众包任务与工人的双边偏好,根据偏好序计算任务与工人的满意...     

考虑用户时空行为的众包任务推荐方法

当前的时空众包任务推荐方法大都是针对有奖励约束、全职做众包任务的众包工人,忽略了有兴趣偏好、不受奖励约束完成任务的兴趣型众包工人,如何将众包任务推荐给这些兴趣型工人,是亟待解决的问题。针对此情况,提出考虑兴趣型时空众包工人的时空行为规律和兴趣偏好的推荐方法。引入基尼系数,在数据中筛选出兴趣型时空众包工人的数据,利用地理-社会关系模型的聚类方法对众包任务进行聚类,用高斯分析的马尔可夫模型预测众包工人在下一转移时间点可能到达各个地点的概率,把位于众包工人可能到达地点的任务按概率降序推荐给兴趣型工人。实验结果表明,所提方法有效提高了兴趣型时空众包任务的完成率。     

Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning

Spatial crowdsourcing has emerged as a new paradigm for solving problems in the physical world with the help of human workers. A major challenge in spatial crowdsourcing is to assign reliable workers to nearby tasks. The goal of such task assignment process is to maximize the task completion in the face of uncertainty. This process is further complicated when tasks arrivals are dynamic and worker reliability is unknown. Recent research proposals have tried to address the challenge of dynamic task assignment. Yet the majority of the proposals do not consider the dynamism of tasks and workers. They also make the unrealistic assumptions of known deterministic or probabilistic workers’ reliabilities. In this paper, we propose a novel approach for dynamic task assignment in spatial crowdsourcing. The proposed approach combines bi-objective optimization with combinatorial multi-armed bandits. We formulate an online optimization problem to maximize task reliability and minimize travel costs in spatial crowdsourcing. We propose the distance-reliability ratio (DRR) algorithm based on a combinatorial fractional programming approach. The DRR algorithm reduces travel costs by 80% while maximizing reliability when compared to existing algorithms. We extend the DRR algorithm for the scenario when worker reliabilities are unknown. We propose a novel algorithm (DRR-UCB) that uses an interval estimation heuristic to approximate worker reliabilities. Experimental results demonstrate that the DRR-UCB achieves high reliability in the face of uncertainty. The proposed approach is particularly suited for real-life dynamic spatial crowdsourcing scenarios. This approach is generalizable to the similar problems in other areas in expert systems. First, it encompasses online assignment problems when the objective function is a ratio of two linear functions. Second, it considers situations when intelligent and repeated assignment decisions are needed under uncertainty.     

Task assignment for social-oriented crowdsourcing

Crowdsourcing has become an efficient measure to solve machine-hard problems by embracing group wisdom, in which tasks are disseminated and assigned to a group of workers in the way of open competition. The social relationships formed during this process may in turn contribute to the completion of future tasks. In this sense, it is necessary to take social factors into consideration in the research of crowdsourcing. However, there is little work on the interactions between social relationships and crowdsourcing currently. In this paper, we propose to study such interactions in those social-oriented crowdsourcing systems from the perspective of task assignment. A prototype system is built to help users publish, assign, accept, and accomplish location-based crowdsourcing tasks as well as promoting the development and utilization of social relationships during the crowdsourcing. Especially, in order to exploit the potential relationships between crowdsourcing workers and tasks, we propose a “worker-task” accuracy estimation algorithm based on a graph model that joints the factorized matrixes of both the user social networks and the history “worker-task” matrix. With the worker-task accuracy estimation matrix, a group of optimal worker candidates is efficiently chosen for a task, and a greedy task assignment algorithm is proposed to further the matching of worker-task pairs among multiple crowdsourcing tasks so as to maximize the overall accuracy. Compared with the similarity based task assignment algorithm, experimental results show that the average recommendation success rate increased by 3.67%; the average task completion rate increased by 6.17%; the number of new friends added per week increased from 7.4 to 10.5; and the average task acceptance time decreased by 8.5 seconds.     

软件众包工人能力动态度量算法

针对现有软件众包平台对工人能力考虑不足，导致分配给工人的任务完成质量低下的问题，提出了一种软件众包工人能力动态度量算法（ADM），实现工人能力的动态度量。首先，基于静态技能覆盖率，实现工人初始能力的计算；其次，对于工人历史完成的单个任务，综合任务复杂度、任务完成质量及任务开发时效，实现开发能力的计算，并根据时间因子计算随时间衰减的开发能力；然后，根据所有历史完成任务的时间先后顺序，实现能力度量值的动态更新；最后，基于历史任务技能覆盖率，计算工人对于待分配任务的开发能力。实验结果表明，与用户可靠性度量算法相比，所提出的能力动态度量算法具有较好的合理性与有效性，使能力度量吻合度平均值最高达到90.5%，能有效指导任务分配。     

众包系统中基于双向拍卖的诚实多任务分配机制

现有的众包任务分配模型大都假设仅存在一个任务请求者,难以满足存在多个任务请求者的应用场景.因此,该文假设众包系统中存在多个任务请求者,且每个任务请求者或工人在每轮任务分配中可以请求或完成多个任务,并在此基础上设计了适用于众包系统的双向拍卖机制,以激励众包任务被高效地完成.首先,将对多个任务感兴趣的工人抽象为多个虚拟工人,以低报价优先匹配原则,设计了一个高效任务分配机制;根据统一定价原则,为其设计了诚实的定价机制.然后,通过理论分析,证明了所设计的机制可以满足诚实性、个体理性以及收支平衡这3项经济学特性.最后,通过仿真实验结果验证了所设计机制的有效性.     

基于树分解的空间众包最优任务分配算法

随着配备高保真传感器的移动设备的普及以及无线网络资费的迅速下降,空间众包成为一种新型的问题解决框架,被用于将位置相关的任务（如路况报告,食品配送）分配给工人（配备智能设备并愿意完成任务的人）。本文研究空间众包中最优任务分配问题,关键在于设计出将每个任务分配给最合适的工人的任务分配策略,以使得完成的总任务数目最大化,而所有的工人可以在完成所分配的任务后,在预期最晚工作时间之前返回起点。找到全局最优分配是一个棘手的问题,因为该问题不等于单个工人的最佳分配的简单累加。本文注意到,仅有部分工人存在任务依赖,因此本文利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法,该算法可以快速地更新启发函数界限,从而高效的对不可能成为最优解分配方案尽早地剪枝。实验表明,本文所提出的方法是非常有效的,可以很好地解决最优任务分配问题。     

Friendship-aware task planning in mobile crowdsourcing

Recently, crowdsourcing platforms have attracted a number of citizens to perform a variety of location-specific tasks. However, most existing approaches consider the arrangement of a set of tasks for a set of crowd workers, while few consider crowd workers arriving in a dynamic manner. Therefore, how to arrange suitable location-specific tasks to a set of crowd workers such that the crowd workers obtain maximum satisfaction when arriving sequentially represents a challenge. To address the limitation of existing approaches, we first identify a more general and useful model that considers not only the arrangement of a set of tasks to a set of crowd workers, but also all the dynamic arrivals of all crowd workers. Then, we present an effective crowd-task model which is applied to offline and online settings, respectively. To solve the problem in an offline setting, we first observe the characteristics of task planning (CTP) and devise a CTP algorithm to solve the problem. We also propose an effective greedy method and integrated simulated annealing (ISA) techniques to improve the algorithm performance. To solve the problem in an online setting, we develop a greedy algorithm for task planning. Finally, we verify the effectiveness and efficiency of the proposed solutions through extensive experiments using real and synthetic datasets.