PaperlayerView exact revision on arXiv

Source-linked AI summary

Task Assignment on Multi-Skill Oriented Spatial Crowdsourcing

Peng Cheng, Xiang Lian, Lei Chen, Jinsong Han, Jizhong Zhao

arXiv:1510.03149v3cs.DB

TL;DR

The paper studies how to assign multi-skilled workers to complex spatial tasks while satisfying skill, time, distance, and budget constraints. It proves the problem is NP-hard and proposes greedy, g-divide-and-conquer, and adaptive cost-model-based approaches, with experiments demonstrating their efficiency and effectiveness on real and synthetic data.

  • Problem

    Complex spatial tasks require multiple skills, but worker assignment must also satisfy time, distance, and budget constraints while maximizing assignment scores.

  • Method

    The paper formulates MS-SC, proves its NP-hardness by reduction from Set Cover, and develops greedy, g-divide-and-conquer, and cost-model-based adaptive algorithms.

  • Results

    Experiments on real and synthetic datasets show the proposed MS-SC approaches are efficient and effective.

  • Takeaways & Limitations

    MS-SC can be addressed with approximation approaches that retrieve worker-task assignments under skill, time, distance, and budget constraints.

Abstract

from arXiv · show

With the rapid development of mobile devices and crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, the spatial crowdsourcing refers to sending location-based requests to workers, based on their current positions. In this paper, we consider a spatial crowdsourcing scenario, in which each worker has a set of qualified skills, whereas each spatial task (e.g., repairing a house, decorating a room, and performing entertainment shows for a ceremony) is time-constrained, under the budget constraint, and required a set of skills. Under this scenario, we will study an important problem, namely multi-skill spatial crowdsourcing (MS-SC), which finds an optimal worker-and-task assignment strategy, such that skills between workers and tasks match with each other, and workers' benefits are maximized under the budget constraint. We prove that the MS-SC problem is NP-hard and intractable. Therefore, we propose three effective heuristic approaches, including greedy, g-divide-and-conquer and cost-model-based adaptive algorithms to get worker-and-task assignments. Through extensive experiments, we demonstrate the efficiency and effectiveness of our MS-SC processing approaches on both real and synthetic data sets.

I. INTRODUCTION

Multi-skill spatial crowdsourcing assigns workers to complex, location-based tasks whose required skills, timing, distance, and budgets must all be satisfied. The paper formalizes this problem, proves it is NP-hard, and proposes three approximation approaches with experimental evaluation.

  • Motivation: Complex spatial tasks such as house repair require multiple professional skills and cannot be completed through simple sensing or reporting.Examples include repairing roofs and floors, installing pipes and electronics, painting walls, and cleaning rooms.
  • Problem Definition: MS-SC assigns multi-skilled workers to complex tasks so their skills cover task requirements while maximizing assignment profit under time, distance, and budget constraints.Workers must reach task locations before deadlines and remain within permitted moving distances and budgets.
  • Research Gap: Existing spatial-crowdsourcing work did not jointly address multi-skill coverage, time and distance constraints, and assignment scores tied to budgets and salaries.Prior objectives included maximizing completed tasks, worker schedules, or reliability and diversity scores.
  • Complexity: The paper proves MS-SC NP-hard by reducing it from Set Cover, making optimal processing intractable in general.The assignment space can be exponential in the numbers of tasks and workers.
  • Approaches: Three approximation approaches—greedy, g-divide-and-conquer, and cost-model-based adaptive algorithms—compute worker-task assignments under the problem constraints.The approaches are designed to balance assignment quality and computational efficiency.
  • Evaluation: Experiments on real and synthetic datasets evaluate the efficiency and effectiveness of the proposed MS-SC approaches.The paper also presents a general framework for retrieving valid worker-task candidate pairs before applying the assignment algorithms.

C. The Multi-Skill Spatial Crowdsourcing Problem

MS-SC assigns workers to time-constrained spatial tasks while requiring skill coverage, travel feasibility, budget compliance, and maximum assignment score. The problem is NP-hard, so the paper uses heuristic approaches rather than seeking an optimal solution directly.

  • Problem definition: MS-SC forms worker-task assignment pairs in which each worker is assigned to at most one spatial task at a timestamp.The assignment instance set contains pairs ⟨wi, tj⟩ between available workers and tasks.
  • Problem definition: Valid assignments require workers to arrive before deadlines, remain within maximum travel distances, and collectively cover each task’s required skills.For a task tj, its required skill set Yj must be contained in the union of skills held by its assigned workers.
  • Constraints and scoring: Assignments must keep total worker travel costs within task budgets, with travel cost modeled as proportional to worker-task distance.The paper uses cij = Ci · dist(li(p), lj) and assumes Euclidean distance for its distance function.
  • Constraints and scoring: The objective maximizes total assignment score across the time interval, where score sums flexible budgets from completed tasks after traveling costs are paid.The score accounts only for tasks completed by workers who reach locations on time and satisfy the required skills.
  • Computational complexity: MS-SC is NP-hard, with exponentially many possible assignment strategies in the worst case.The hardness proof reduces the Set Cover Problem to MS-SC.
  • Solution approach: Because existing Set Cover approximations do not directly handle multiple spatial tasks and worker-task travel and budget matching, the paper proposes greedy, k-divide-and-conquer, and cost-model-based adaptive heuristics.These approaches are designed to retrieve MS-SC answers efficiently under the problem’s constraints.

III. FRAMEWORK OF SOLVING MS-SC PROBLEMS

The MS-SC framework repeatedly retrieves available tasks and workers, forms valid pairs under skill, time, distance, and budget constraints, and applies assignment algorithms to select worker-task assignments. It uses score increase to guide selection and pruning strategies to reduce unnecessary pair checks.

  • MS-SC Framework: At each timestamp, the framework retrieves available tasks and workers, updates a grid index, obtains valid pairs, and computes an assignment set.Valid pairs satisfy location, skill, time, and budget constraints; selected pairs are used to notify workers.
  • MS-SC Framework: The framework supports greedy, g-divide-and-conquer, and adaptive cost-model-based approaches over the valid worker-task pair set.Each approach produces a good assignment instance set that is a subset of the valid pairs.
  • The Score Increase: The score increase measures the change in flexible assignment score caused by assigning a worker to a task.It combines the budget allocated for newly covered skills with the worker’s traveling cost.
  • Pruning Strategies: Pruning removes dominated workers, workers exceeding remaining task budgets, and tasks that cannot be fully covered within their remaining budgets.These strategies reduce repeated score-increase computations without checking every assignment pair.
  • Pruning Strategies: A task can be pruned when the remaining eligible workers cannot fully cover its required skills or exceed its remaining budget.The task-pruning condition applies to all assignment pairs containing that task.

C. The Greedy Algorithm

MS-SC Greedy iteratively selects the valid worker-task pair with the highest score increase, subject to distance, arrival-time, skill, and budget constraints. It prunes unsuitable pairs during each round and stops when no workers or tasks remain.

  • Greedy Selection: MS-SC Greedy repeatedly assigns the valid worker-task pair with the highest score increase.The selected pair is added to the assignment instance set, and the assigned worker is removed from the available worker set.
  • Valid Pairs: A valid pair requires acceptable distance, arrival before the task deadline, required skills, and traveling cost within the task budget.These four conditions determine the candidate pairs considered by the algorithm.
  • Greedy Selection: During each round, the algorithm prunes dominated and high-wage workers before checking remaining candidates for task-level feasibility.The surviving candidate with the greatest score increase is selected for assignment.
  • Time Complexity: The greedy algorithm has worst-case time complexity O(m · n^2).It considers up to m·n worker-task pairs and performs at most n assignment iterations.

V. THE g-DIVIDE-AND-CONQUER APPROACH

The g-divide-and-conquer approach recursively partitions the MS-SC problem into smaller task groups, solves them, and merges assignments while resolving worker conflicts. A cost model selects the number of groups to balance decomposition and recursive processing.

  • The g-D&C Algorithm: g-D&C addresses greedy local optimality by recursively dividing the MS-SC problem into g subproblems and merging their assignment results.Each subgroup contains ⌈m/g⌉ tasks, and merging resolves assignment conflicts.
  • Problem Decomposition: The decomposition represents valid worker-task pairs as a bipartite graph and partitions task vertices into subproblems with their connected workers.Valid pairs satisfy skill, time, distance, and budget constraints.
  • Problem Decomposition: Each decomposition round selects an anchor task and its nearest tasks, using a sweeping longitude-and-latitude order to form groups of ⌈m/g⌉ tasks.The algorithm repeats this process until it returns all g subproblems.
  • The g-D&C Algorithm: The algorithm estimates the best group count g with a cost model before decomposition, because different group counts can incur different time costs.The cost model is introduced later to guide this choice.
  • The g-D&C Algorithm: Subproblems with more than one task are solved recursively, while single-task subproblems use a greedy set-cover algorithm.The recursive process then merges the resulting assignment sets by reconciling conflicts.

C. Merging Conflict Reconciliation

Merging conflict reconciliation combines assignment sets from subproblems while ensuring that each worker is assigned to at most one spatial task. It resolves conflicts by comparing score reductions from alternative worker replacements.

  • Conflict Identification: Conflict reconciliation prevents two distinct tasks from assigning the same worker when assignment sets are merged.Each worker can be assigned to only one spatial task at a time.
  • Conflict Resolution: The procedure identifies all conflicting workers and processes them greedily in non-decreasing order of their traveling cost in the newly merged assignment set.The conflicting-worker set is updated after each resolution.
  • Conflict Resolution: For each conflict, the algorithm evaluates replacing the worker in either subproblem and computes the resulting assignment-score reductions.It chooses the replacement associated with the lower score reduction.
  • Conflict Resolution: If no replacement worker is available, the procedure may sacrifice the task assigned to the conflicting worker.This provides a fallback when the worker cannot be replaced in the relevant subproblem.
  • Conflict Resolution: After all conflicts are resolved, the current and new assignment sets are merged into the returned assignment instance set.The procedure repeats until no conflicting workers remain.

D. Cost-Model-Based Estimation of the Best Number of Groups

The cost model estimates the best number of groups for g-D&C by combining decomposition, recursive conquering, and merging costs. The algorithm chooses an integer group count near the point where the derivative of total cost changes sign.

  • Total Cost: The total g-D&C cost is the sum of decomposition cost FD, recursive conquering cost FC, and merging cost FM.These three components capture the main processing stages of the approach.
  • Decomposition Cost: FD = m · n + (m · g + m) · logg(m) gives the cost of retrieving valid pairs and decomposing tasks across logg(m) levels.The initial valid-pair retrieval costs O(m·n), while each level contributes O(m · g + m).
  • Recursive Conquering Cost: FC recursively models the cost of conquering subproblems containing x spatial tasks, with the single-task base case solved by the greedy algorithm.The recursive cost is analyzed across levels from 1 to logg(m).
  • Merging Cost: FM = ns · (degw −1) estimates the worst-case cost of resolving conflicts for ns workers with average worker degree degw.Each conflicting worker may require resolution at most degw −1 times.
  • Selecting g: The algorithm differentiates candidate group counts by examining the derivative of total cost and testing integer values of g until the derivative rises above 0.The derivative is described as becoming less negative and then increasing quickly as g grows.

VI. THE COST-MODEL-BASED ADAPTIVE ALGORITHM

The cost-model-based adaptive algorithm chooses between greedy and g-D&C processing, and can stop recursive partitioning when greedy processing is estimated to be cheaper. This adaptively matches the strategy to the estimated cost of the current problem or subproblem.

  • Adaptive Strategy Selection: The adaptive approach decides whether to use greedy or g-D&C processing based on their estimated costs.It estimates costgreedy and costgdc before selecting a strategy.
  • Adaptive Stopping: Unlike g-D&C, the adaptive method can stop partitioning when solving subproblems greedily is cheaper than continuing to divide them.The stopping decision is made during partitioning rounds using the cost model.
  • Adaptive Strategy Selection: If costgreedy < costgdc, the algorithm solves the problem with the greedy method; otherwise, it decomposes the problem and processes subproblems adaptively.The pseudocode then recursively applies the adaptive procedure to subproblems.
  • Adaptive Processing: The algorithm returns one assignment instance set after processing and combining the selected greedy or g-D&C results.The pseudocode processes each subproblem and returns Ip.

A. Algorithm of the Cost-Model-Based Adaptive Approach

The adaptive approach estimates the costs of greedy and g-divide-and-conquer, recursively partitions when appropriate, and merges subproblem assignments. It stops dividing when greedy is estimated to be cheaper.

  • Adaptive decision process: ADAPTIVE compares estimated greedy and g-D&C costs to choose the lower-cost strategy for worker-and-task assignment.It invokes greedy when costgreedy < costgdc; otherwise, it partitions the problem and recursively solves subproblems.
  • Adaptive decision process: The algorithm recursively applies itself to g-D&C subproblems and merges their assignment instance sets into the final result.MS-SC-Reconcile combines assignments returned from the subproblems.
  • Stopping rule: At level k, ADAPTIVE stops dividing when the estimated greedy cost is lower than the remaining g-D&C cost.Otherwise, it continues dividing the original problem into subproblems.
  • Cost model: The greedy cost model accounts for valid-pair computation, worker pruning, score-increase selection, and per-task updates.Its constant factor Cgreedy is inferred from greedy-algorithm cost statistics.
  • Cost model: The decomposition cost is D = m · n + (m · g + m) · k, while g-D&C cost includes decomposition, conquering, and merging costs.The g-D&C cost uses a constant factor Cgdc inferred from time-cost statistics.

VII. EXPERIMENTAL STUDY

Experiments use real Meetup data and synthetic data with controlled worker, task, skill, mobility, cost, and temporal parameters. On real data, ADAPTIVE generally balances assignment quality and runtime between GREEDY and g-D&C.

  • Experimental methodology: The real-data experiments use Meetup users, events, groups, locations, and tags to initialize workers, tasks, and skills.Meetup contains 5,153,886 users, 5,183,840 events, and 97,587 groups.
  • Experimental methodology: Synthetic workers and tasks are generated in a 2D space using Uniform or Skewed location distributions.The Skewed distribution places 90% of workers and tasks in a Gaussian cluster.
  • Experimental methodology: Worker velocities, traveling unit prices, maximum moving distances, and task temporal constraints are generated over specified parameter ranges.Velocities follow a Gaussian distribution, while unit prices and maximum distances follow Uniform distributions.
  • Compared approaches: GREEDY selects the locally highest score increase, g-D&C recursively divides tasks, and ADAPTIVE chooses a stopping level using a cost model.ADAPTIVE trades off the efficiency and accuracy characteristics of GREEDY and g-D&C.
  • Real-data results: As task budgets increase, all assignment scores and running times increase, while g-D&C and ADAPTIVE score higher than GREEDY and RANDOM scores lowest.Larger budgets create more valid workers per task, increasing problem complexity and runtime.
  • Real-data results: As velocity ranges increase, scores initially rise and then plateau, while runtime increases because more valid worker-and-task pairs must be processed.ADAPTIVE takes about 0.5-1.5 seconds and is faster than g-D&C.
  • Real-data results: As traveling unit-price ranges increase, valid worker-and-task pairs and running times decrease; ADAPTIVE is faster than g-D&C but slower than GREEDY.Higher traveling costs reduce the number of affordable worker-task matches.
  • Scope of reported results: The real-data study also tests maximum moving-distance and task-expiration-time ranges, with those additional results placed in Appendix F.The main text omits these results because of space limitations.

C. Experiments on Synthetic Data

On synthetic data, g-D&C generally obtains the highest assignment scores, ADAPTIVE performs similarly while requiring less time, and GREEDY is faster but less accurate. These patterns hold as task and worker counts increase.

  • Effect of task count: For 1K-10K synthetic tasks, g-D&C achieves the highest assignment scores, ADAPTIVE performs similarly, and GREEDY remains better than RANDOM.All proposed approaches achieve higher scores as the number of tasks increases.
  • Effect of task count: As the number of tasks increases, running time increases because more worker-and-task assignment pairs must be processed.ADAPTIVE is slower than GREEDY and faster than g-D&C, matching the intended efficiency-accuracy trade-off.
  • Effect of worker count: As the number of workers increases, the running time of all proposed approaches increases because more workers require processing.ADAPTIVE again costs more time than GREEDY and less than g-D&C.
  • Overall synthetic-data result: ADAPTIVE trades accuracy for efficiency, producing score and runtime between GREEDY and g-D&C on synthetic data.The experiments vary task and worker counts and compare the approaches with RANDOM.
  • Position relative to prior work: The study reports related spatial-crowdsourcing work and emphasizes that MS-SC differs by covering multiple skill sets under budget, time, and distance constraints.The paper states that prior set-cover techniques cannot be directly applied to MS-SC.
  • Paper conclusion: The paper defines MS-SC as assigning time-constrained, multi-skill-required tasks to dynamically moving workers while maximizing assignment score.It proposes greedy, g-D&C, and cost-model-based adaptive approximation approaches and evaluates them on real and synthetic data.

APPENDIX

The appendix material supports the NP-hardness proof and describes pruning conditions used in MS-SC processing. The reduction maps set cover instances to single-task MS-SC instances whose score maximization corresponds to cost minimization.

  • NP-hardness reduction: The NP-hardness reduction creates one MS-SC task whose required skills equal the set-cover universe and whose budget is sufficient to hire workers.Workers inherit set-cover subsets as skills and set-cover costs as traveling costs.
  • NP-hardness reduction: The transformed MS-SC task maximizes budget minus worker costs while requiring the workers’ skills to cover all required skills.Because the budget is constant, maximizing MS-SC score is equivalent to minimizing the selected set-cover cost.
  • NP-hardness reduction: The mapping is bidirectional, so solving the transformed MS-SC instance solves the original set-cover instance.Since set cover is NP-hard, MS-SC is also NP-hard.
  • Worker pruning: A worker-task pair can be pruned when another worker covers at least the same skills and has no higher traveling cost.The dominating worker provides at least as large a score increase.
  • Budget pruning: A worker is excluded when its traveling cost exceeds the task’s remaining budget, because that budget does not increase during later assignment rounds.The same condition supports safely pruning the worker from consideration.
  • Task pruning: A task can be pruned when every subset of remaining workers that covers its skills exceeds the task’s remaining budget.The proof compares the costs of all covering subsets with the remaining budget.
  • Task pruning: Under that condition, the total traveling cost of any covering subset exceeds the remaining budget, so the task cannot be fully covered.This establishes the task-pruning lemma.

E. MS-SC Grid Index

The MS-SC-Grid index organizes workers and tasks into spatial cells with summaries and skill synopses, then prunes cells and pairs that cannot satisfy assignment constraints. On uniform data, it reduces worker-and-task pair retrieval time by up to 79% versus enumerating all pairs.

  • Index Structure: MS-SC-Grid partitions the 2-dimensional data space into square cells and stores worker/task lists, aggregates, and neighboring-cell lists.Each cell maintains records for resident workers and tasks plus statistics used during search.
  • Index Structure: Cell aggregates summarize distances, velocities, deadlines, budgets, and worker and task skill unions for pruning.The maintained statistics include maximum moving distance, maximum velocity, latest arrival deadline, maximum budget, and skill unions.
  • Skill Synopses: Bitmap synopses represent skill sets, enabling bit operations to test containment or intersection efficiently.Separate worker and task bitmaps encode whether each skill is present.
  • Pruning: The index prunes cells when distance, travel time, cost, or skill-overlap conditions make every contained task invalid for a worker.Any one of the four conditions is sufficient to safely discard a cell.
  • Performance: Up to 79%, MS-SC-Grid reduces worker-and-task pair retrieval time on uniform data compared with directly enumerating and checking all possible pairs.The experiment varies m from 500 to 10K with n = 5m.

F. Effects of Moving Distance and Expiration Times

The experiments vary workers’ moving-distance ranges, tasks’ expiration-time ranges, and dataset sizes to compare assignment scores and running times. ADAPTIVE and g-D&C generally achieve stronger assignment scores than GREEDY, while runtime depends on the approach and workload.

  • Moving Distance: ADAPTIVE achieves the highest assignment scores across tested worker moving-distance ranges, while g-D&C outperforms GREEDY.The moving-distance range varies from [0.1, 0.2] to [0.4, 0.5].
  • Moving Distance: GREEDY runs faster than ADAPTIVE, which runs faster than g-D&C; RANDOM is fastest but least effective.This runtime ordering is reported for the moving-distance experiments.
  • Expiration Time: All three approaches maintain good assignment scores as task expiration-time ranges increase, with ADAPTIVE highest and g-D&C above GREEDY.The expiration-time range varies from [0.25, 0.5] to [3, 4].
  • Expiration Time: Increasing the expiration-time range increases the running time of all approaches.The supplied passage attributes this trend to the experimental setting but does not complete the explanation.
  • Number of Tasks: With skewed data and 1K–10K tasks, g-D&C obtains the highest assignment scores, ADAPTIVE performs similarly, and both outperform GREEDY and RANDOM.The passage reports that all approaches achieve higher scores as the number of tasks increases.
  • Number of Workers: With skewed data and 1K–10K workers, all three proposed approaches obtain good assignment scores, which increase as the worker count grows.This experiment varies n from 1K to 10K.
Loading 1510.03149v3…