1.

INTRODUCTION

In recent years, with the widespread use of smartphones with geographic information sensors, wireless and mobile networks, traditional crowdsourcing has undergone tremendous changes. A new type of crowdsourcing, the emergence of spatial crowdsourcing, has attracted widespread attention from academia and industry. The spatial crowdsourcing system is composed of task requesters, crowdsourcing platforms (such as Amazon Mechanical Turk), and workers. The task requester publishes tasks with geographic location and time requirements to the crowdsourcing platform, and the crowdsourcing platform makes reasonable assignments based on the location of workers and tasks. The worker needs to move to the designated position of the task to complete it, and the worker will be paid accordingly after the task is completed. The completion of crowdsourcing tasks is inseparable from the good collaboration between the task requester, the crowdsourcing platform, and the workers.

Task assignment is one of the key research issues in spatial crowdsourcing. The quality of the task assignment method not only determines the quantity and quality of tasks completed but also determines the interests of the crowdsourcing platform and workers. Spatial tasks can be classified into simple and complex tasks. For simple tasks (e.g., street view of Google Maps) can be performed by a single worker alone with the help of equipment, but for complex tasks (e.g., interior decoration), multiple workers with specialized skills are required to collaborate. From the perspective of professional skills, the skills of the workers assigned by the platform should include one or more of the skills required for the task, so that the selected workers can participate in the task, which can effectively avoid the waste of worker resources. At the same time, the skill set of the assigned worker should include all the skills required by the task, to ensure the completion of the task. Secondly, the intimacy between workers is one of the important factors that affect whether workers can collaborate well. High intimacy will make them communicate and collaborate smoothly, and good communication can achieve the effect of one plus one more than two, reducing team communication costs while completing the assigned tasks with high quality.

The previous research on task assignment only considered the collaboration between workers^1-2 or the assignment of skills^3-4 alone and did not consider the collaborative assignment of workers based on multiple skills. Therefore, we cannot use the existing methods to solve the problem of multi-skill cooperative assignment. To solve the above proposed problem, this paper proposes a cost-based greedy approach. Under the constraints related to workers and tasks are satisfied, suitable teams of workers are matched for spatial tasks to ensure high-quality completion of tasks while minimizing platform costs.

2.

RELATED WORK

The main job of crowdsourcing platforms is to assign tasks to the right workers, so task assignment has been one of the research hotspots of spatial crowdsourcing. From the existing studies, the task assignment methods of spatial crowdsourcing can be divided into two types, worker selected tasks (WST) and server assigned tasks (SAT). Although these two assignment approaches address different problem scenarios, most research works have maximized the number of tasks assigned^5-6, maximizing the system revenue^3,7, or minimizing the platform cost⁸ as the main optimization objectives. For WST, reference⁹ allows workers to browse and choose which tasks to participate in according to their wishes. Reference¹⁰ finds a time scheduling table for workers given a set of workers and tasks such that the number of completed tasks is maximized. This way of assigning tasks can protect workers’ privacy to a certain extent while making it possible to improve workers’ motivation, but it can result in certain tasks in remote locations not being selected by workers for a long time.

For SAT, reference⁶ proposed a task assignment method based on time preference. With the aid of historical data and context matrix, it calculates the preferences of different types of workers in different periods. Give priority to workers who are more interested in tasks to maximize the number of tasks assigned; A task assignment approach based on platform profit is proposed in reference⁷, which first establishes a task pricing model and then uses a tree decomposition algorithm for task assignment to maximize system revenue. Reference¹¹ is the first to consider task location as a factor that affects task assignment. It studies the online task assignment of three types of objects in a spatial crowdsourcing environment and proposes a random-threshold-based algorithm for task assignment.

In addition, if the task assigned is complex and difficult, multiple workers with specialized skills are required to work together to complete it. A multi-skill-oriented task assignment approach is proposed in reference³, where workers who satisfy time and spatial constraints will be assigned to spatial tasks with time constraints using greedy algorithms, partitioning algorithms, and adaptive algorithms based on cost models, making the flexible budget maximized, i.e., maximizing the number of tasks completed while minimizing the cost of worker movement. The study only considers the multi-skills of workers and ignores the collaborative relationship between workers. Reference² proposed a heuristic task framework FCC-SA, which uses feedback from workers and requesters to accurately assess worker skills and intimacy, and then allocate workers to collaborative tasks to maximize the number of tasks assigned. The study considers the collaboration between workers, but for the skills of workers, only single skills rather than multiple skills are considered. Reference¹ only considers the collaborative relationship between workers when assigning tasks, ignoring the skill requirements of workers.

3.

PROBLEM DEFINITION

Definition 1 (skills set): Let D = {d₁ d₂, …, d_n} is a skill set that contains different к skills, and skills can be painting walls, repairing roofs, replacing pipes, etc. Each worker has at least one skill, while multiple skills are required for the completion of each task.

Definition 2 (multi-skilled workers set): Let W_φ={w₁,w₂,…,w_n} is workers set that contains n multi-skilled workers at timestamp φ. For each worker w_i ∈ W_φ, has a skills set D_i(⊆ D), is located at a location l_i (φ) at timestamp φ, can move with speed v_i, has a maximum moving distance r_i, and has the intimacy a_ik with worker w_k.

The platform will maintain the intimacy matrix. Firstly, the platform can initialize the intimacy matrix according to the social relationship α between workers, α is calculated using simple social attributes, such as region, age, gender, and more complex features, and normalized to a decimal of 0 to 1. Then, as the number of task assignment rounds increases, we can dynamically update the intimacy matrix, as shown in equation (1).

where |T_k| represents the number of tasks completed by worker w_i, |T_k| represents the number of tasks completed by worker w_k, and |T_i ∩ T_j| represents the number of tasks completed by worker w_i and worker w_k.

The intimacy between workers determines the smoothness of communication between workers. Therefore, this paper converts intimacy into the cost of communication. The higher the intimacy, the lower the cost of communication. The cost of communication is calculated as shown in equation (2).

where W_j represents the set of workers assigned to the task t_j, and K_I is a constant and represents the hourly call subsidy.

Definition 3 (Complex spatial tasks): Let T_φ = {t₁,t₂,…,t_m} is tasks set that that contains m complex spatial tasks at timestamp φ. For each task t_j ∈ T_φ, needs a skill set for its completion, is located at a location l_j at timestamp φ, and has a deadline e_j and a budget B_j.

Definition 4 (valid worker-task pairs): At the timestamp φ, given workers set W_φ and tasks set T_φ, a valid worker-task pair ⟨w_i, t_j⟩. is constructed by worker w_i and task t_j while satisfying constraints on distance, time, skill, travel cost, etc.

Constraint 1 (distance constraint): This paper uses Euclidean distance as distance function. The distance between the current location l_i (φ) of worker w_i and the location l_j of task t_j is not greater than the maximum moving distance r_i of worker w_i, that is dist (l_i(φ), l_j) ≤ r_i.

Constraint 2 (time constraint): The worker w_i need to arrive at the task location l_j before deadline e_j to perform the task, that is dist (l_i(φ), l_j) · v^–1 ≤ e_j – φ.

Constraint 3 (travel cost constraint): The worker w_i need to physically move to the location l_j of task t_j and the travel cost c_ij of worker w_i is not greater than the budget B_j of task t_j, that is c_ij = K_c ‧ dist(l_i,l_j) ≤ B_j, where K_C is a constant, representing the subsidy per kilometer.

Constraint 4 (skills constraint): The assigned worker w_i needs to provide the required skills for the task t_j that is D_i ∩ D_j ≠ Ø.

An assignment instance I refers to a set of valid worker-task pairs.

Definition 5 (MSC-CS problem): At timestamp φ, given workers set W_φ and tasks set T_φ, The MSC-CS problem is to assign the currently available workers to the spatial tasks and minimize platform total cost S(T):

where C(W_j) represents the travel cost of task t_j and I(W_j) is the communication cost of the task t_j defined by equation (2).

4.

TASK ASSIGNMENT METHOD

4.1

The total cost increase

Firstly, this paper defines the increase of the total cost. At timestamp φ, when a new worker w_i is assigned to the task t_j, the increase of total cost is calculated as shown in equation (5).

where W_j is the set of workers assigned to the task t_j (including w_i), and ∆I(W_j) is the change in communication cost of the task t_j after worker w_i is assigned.

4.2

Task priority calculation

If an assignment conflict is encountered during task assignment, this paper adopts the strategy of assigning the higher priority first. The priority is calculated as shown in equation (7).

where β represents the weight of task benefit and task urgency.

4.3

Cost-based greedy approach

In this section, we propose a cost-based greedy approach, as shown in Algorithm 1.

Algorithm 1 Cost-based greedy approach

At timestamp φ, this paper first retrieves all available workers and tasks (lines 2), then for each worker w_i a range query is executed using spatial indexing methods (e.g., R-Tree) to determine which tasks are reachable by the worker w_i. The time constraint, travel cost constraint, and skill constraint are further used to determine which tasks that worker w_i. can participate in, while constructing a valid worker-task pair about worker w_i. Finally, all valid worker-task pairs at the current timestamp φ can be obtained (line 3). Lines 4 to 18 are iteratively select the worker-task pair ⟨w_i,t_j⟩ with the smallest increase in total cost, if only one pair is found, add it directly to the assignment instance Ι_φ. If several pairs are found, select pairs with the highest priority of conflicting tasks, add them to the assignment instance Ι_φ, and then remove worker w_i from the current workers set W_φ(lines 5 to 13). If the skills set of the workers set W_j and the skills set required by the task t_j satisfy D_j ⊆ U_wi∈Wj D_i, then task t_j can be removed from the current tasks set T_φ(lines 14 to 16). Finally, the task assignment instance Ι_φ is returned (line 18) and the selected worker w_i is notified to perform the corresponding task t_j.

5.

EXPERIMENTAL STUDY

5.2

Result analysis

As shown in Figures 1 and 2, for the platform cost, the increase of the number of workers or the distance workers can move will lead to the increase of the workers available for tasks, and eventually, the number of completed tasks will also increase while the corresponding total platform cost will increase, after, due to the limitation of the number of tasks or the movement speed of workers, the number of completed tasks will stabilize, and the total cost of the platform will also stabilize. Therefore, the curves of the three methods increase first and then flatten. The random method does not consider anything when assigning, so its total platform cost is the highest, Top_1 Greedy considers both costs and benefits when assigning, so its total platform cost is second, Cost-based Greedy selects the worker-task pair with the lowest total cost increase in each round, so it has the lowest total cost of the platform. For the running time, when performing task assignments, the number of workers available for tasks increases will also lead to an increase in system overhead, so the running time of all three algorithms shows an increasing trend. The random method is the simplest and it has the least running time. Cost-based Greedy only needs to calculate the travel cost and communication cost of the workers when assigning, so its running time is secondly, Top_1 Greedy needs to perform additional calculation and comparison of the profit ratio when assigning, and its running time is the highest.

Figure 1.

The impact of the number of workers on total cost and running time.

Figure 2.

The impact of the moving distance of workers on total cost and running time.

According to the above experimental results, by changing the two parameters, the method in this paper generally performs better than the other two methods in terms of total platform cost, and the overall performance is stable. Because this paper is a static offline scenario, the time complexity of the method is not high, so in terms of running time, the method of this paper can meet the requirements.

6.

SUMMARY AND OUTLOOK

For the multi-skill collaboration-based task assignment problem, whose optimization objective is to minimize the total platform cost, this paper transforms the intimacy between workers into the communication cost. Based on the travel and communication costs, a cost-based greedy approach is proposed to iteratively select the worker task pair that minimizes the total cost growth and matches the task with the right team of workers to minimize the total cost of the platform. Finally, the method proposed in this paper is validated on a synthetic dataset. The next step of the study will no longer be limited to the local optimum of the current timestamp but will be to achieve the global optimum of a period by accurate prediction.