随着全球定位系统(Global Positioning System,GPS)智能设备的日益普及和无线移动网络的全面覆盖,人类可以作为移动传感器,参与到各种基于空间位置的任务中,空间众包(Spatial Crowdsourcing,SC)概念应运而生。空间众包领域中的一个重要研究方向是任务分配,即以空间众包平台为基础,将空间众包任务分配给特定的工人,要求工人在任务的时空约束下主动或被动地完成任务。但是由于空间众包的时空限制特性以及工人/任务的随机性,任务分配问题面临着一系列挑战:首先,在空间众包任务分配的目标方面,任务分配的一个重要优化目标是实现全局任务完成数量的最大化,寻求这个目标的最优解被证明是NP难问题,即不存在高效的多项式算法,在实际的空间众包应用中,往往存在大量的在线工人和任务等待分配,如果分配算法运行效率太低的话,任务请求者(即发布任务的用户)或工人会因为等待时间过长而放弃;其次,在任务完成的质量方面,由于空间众包系统中的工人是一个不确定的大众群体,使得工人完成任务的质量无法得到保证,如部分工人可以通过提交不真实的偏好集合来最大化自己的任务分配量,以致提交质量低下甚至虚假的随机数据给平台;再次,在空间众包中,工人必须移动到指定地点完成任务,在这个移动过程中会产生行程,行程成本的大小与空间距离有着密切的关系,同时行程成本也会影响工人的任务奖励,进而影响任务的接受率和完成质量;此外,空间众包中的工人和任务均受到时间和空间的约束,且都具有时空动态特征,如果忽略这些特征而去单纯地在静态假设条件下进行任务分配,往往会影响空间众包服务的用户体验;最后,空间众包中存在某些复杂的任务,这些任务往往无法由一个工人单独完成,而需要多个工人共同协作完成,因此工人必须形成一个稳定的工人组或工人联盟来共同协作完成任务,如何为每个任务分配一个稳定的工人组是此类任务分配问题的重要挑战。本文针对上述空间众包任务分配的问题,进行了深入研究,取得了如下研究成果:1)本工作首次研究了基于树分解的最优任务分配算法,通过设计基于树分解的工人依赖关系消除策略,将工人划分为相互独立(即不存在依赖关系)的工人集合,并将这些独立的工人集合组织成较平衡的搜索树结构,使得搜索树中的兄弟节点之间的工人不存在任务依赖关系,最终采用深度优先算法进行树搜索,从而得到最优任务分配。本论文将上述分配算法应用到基于工人目的地的空间众包任务分配场景中,实验证明,该算法能够在大规模的工人和任务集合下有效地实现任务数量的最大化分配。2)为了改善任务完成质量,本论文研究了基于张量分解的工人偏好计算方法,基于工人和任务的历史数据,求得工人在不同时间段对不同类别任务的偏好值,并根据这些偏好值,设计不同的任务分配策略,为工人分配其感兴趣的任务,实现最优任务分配。大量的基于真实数据的实验验证了上述方法的有效性。3)针对空间众包中工人和任务的时空动态特征,本论文提出了一个基于预测的空间众包任务分配算法框架,该框架包括两部分,其中,预测部分采用不同的学习模型来预测工人和任务未来的时空分布;任务分配部分则设计贪婪算法(以提升任务分配效率)和图分割算法(以实现最优任务分配)。4)本论文发现在空间众包中存在某些复杂的任务,这些任务无法由一个工人单独完成,因此,本论文提出基于工人联盟的空间众包任务分配问题,并设计了基于合约的贪婪算法和基于纳什均衡的算法,以实现一个较高的任务总奖励值。其中,基于合约的贪婪算法主要是通过制定合约来约束工人的行为并贪婪地为任务分配合适的工人联盟;而基于纳什均衡的算法主要是将任务分配问题转化为严格位势博弈,然后采用最佳响应算法和模拟退火策略进行任务分配。