基于约束的空间众包多阶段任务分配

Multi Stage Task Allocation on Constrained Spatial Crowdsourcing

在人机物融合的背景下,空间众包可被视为一种新型的软件服务.空间众包是针对于物理世界中与地理位置和时间要素相关的众包任务,通常要求参与者真实地移动到指定位置执行相应操作,承担数据收集与感知等任务,并通过移动终端反馈操作结果.任务分配是空间众包中的关键技术,其目的是在满足时空约束条件的前提下选取一个或一组合适的参与者承担任务的执行.在具有空间位置访问权限、线下服务使用权限并考虑参与者可用时间与移动范围约束的空间众包场景中,单个参与者可能无法完成整个任务的执行,转而需要一组参与者进行协同合作后才能完成.针对该需求,本文提出了一种基于约束的空间众包多阶段任务分配方法.该方法的核心算法将首先根据两种不同的优化目标获取对应的任务路径集合,然后针对每一条路径采用从起点和终点双向选取局部最优的方法递归地选择承担阶段性任务的参与者.通过上述步骤,可高效地将任务分解为一组由不同参与者在符合约束条件时能够承担的阶段性子任务,以此提高任务完成的概率.最后,我们使用上述算法分别进行了模拟实验和真实场景实验.模拟实验面向随机生成的参与者数据集,并与基于动态规划取得全局最优解的算法进行对比.实验结果表明本文所提算法相比于对比算法具有更好的计算效率.真实场景实验依赖自主开发的校园空间众包任务平台开展.实验结果表明本文算法能够在真实任务环境下推导得到参与者可接受的子任务分配决策.

In the context of the fusion of the ternary human-machine-thing,spatial crowdsourcing is regarded as a new type of software service.Spatial crowdsourcing works for crowdsourcing tasks which are related to the geographic and temporal elements in the physical world.The involved workers are usually required to move to the specified location to perform the corresponding operations,to undertake tasks such as data collection and perception,and to feedback the operation results through the mobile terminal.Task allocation has been a key technique in the field of spatial crowdsourcing.It aims to select one or a group of suitable workers to undertake the execution of the task while satisfying the constraints of time and space.The existing spatial crowdsourcing research work mostly works for simple tasks,which can usually be undertaken by one worker alone.Even in a multi-tasking scenario,each simple task is basically independent.A single worker may undertake one or more tasks,and the execution of a single simple task does not have to be split and assigned to multiple workers. However,in constrained spatial crowdsourcing,a single worker may not be able to complete the entire task.Constrained spatial crowdsourcing involves location and service authorization,worker available time and worker movement range.Instead,a task in constrained spatial crowdsourcing requires a group of workers to complete the task collaboratively.In response to this demand,we propose a multi-stage task allocation method on constrained spatial crowdsourcing in this paper.The core algorithm of the method will first obtain the path set corresponding to the task according to two different optimization objectives including the minimum execution time and the minimum movement range,and then sort them according to the priority.For each path in the set,the algorithm will recursively select the workers to undertake the phased tasks by means of adopting a method from which the local optimal results are obtained in both directions from the starting point and from the ending point.Once the tasks on the path can be collaboratively completed by one or a group of workers,an allocation decision for the phased task is obtained.Through the above steps,the method efficiently breaks down the task into a set of sub-tasks that can be undertaken by different workers when the constraints are met,thereby increasing the probability of completion of the task.Finally,a simulation experiment and a field experiment were carried out based on the above algorithm.In the simulation experiment,we compare our algorithm with a dynamic programming algorithm which can obtain the global optimal solution based on the same randomly generated data set.The data set includes the workers’ restricted location and service authorization status,movement range and current position coordinate.The experimental results show that our algorithm has better computational efficiency than the comparison algorithm.The field experiment is performed by utilizing a self-developed campus spatial crowdsourcing task platform.The experimental results show that our algorithm can derive sub-task allocation decisions that the workers can accept in real spatial crowdsourcing environment.