Existing Research Early research directly models the task assignment problem through the classical offline bipartite matching"problem, which tries to maximize the total number of the assignment Worker Task (1,8) w r2(3,6) r1(2,5 f4(65) 4 7(5,3.5) Ws(8,2) Edge: a worker can 6(4,1)W4(6,1) arrive at the location 012345678X of a task before the deadline of the task Kazemi et aL. Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework In TASA 2015
⚫ Early research directly models the task assignment problem through the classical “offline bipartite matching” problem, which tries to maximize the total number of the assignment Existing Research L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015. Worker Task Edge: a worker can arrive at the location of a task before the deadline of the task. 6
Existing Research Early research directly models the task assignment problem through the classical offline bipartite matching " problem, which tries to maximize the total number of the assignment Task w2(1.8)w3(37) Worker r366,7) Cannot handle real-time scenarios where workers and tasks will dynamically appear Ws(8,2) Edge: a worker can 6(4,1)W4(6,1) arrive at the location 012345678X of a task before the deadline of the task Kazemi et aL. Geocrowd: enabling query answering with spatial crowdsourcing In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework In TASA 2015
⚫ Early research directly models the task assignment problem through the classical “offline bipartite matching” problem, which tries to maximize the total number of the assignment Existing Research L. Kazemi et al. Geocrowd: enabling query answering with spatial crowdsourcing. In GIS 2012. H. To et al. A server-assigned spatial crowdsourcing framework. In TASA 2015. Worker Task Edge: a worker can arrive at the location of a task before the deadline of the task. Cannot handle real-time scenarios where workers and tasks will dynamically appear ! 7
Existing Research Recent research uses "online bipartite matching'"' to model the real-time task assignment problem When a task/worker appears, the task assignment is performed immediately and irrevocably A rigorous assumption: once a worker appears on the platform, the worker can only wait in place tlil a task is assigned to him/her Y Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. In ICDE2016
⚫ Recent research uses “online bipartite matching” to model the real-time task assignment problem ⚫ When a task/worker appears, the task assignment is performed immediately and irrevocably Existing Research Y. Tong et al. Online Mobile Micro-Task Allocation in Spatial Crowdsourcing. In ICDE2016. A rigorous assumption: once a worker appears on the platform, the worker can only wait in place tlil a task is assigned to him/her 8
9 Existing Research: An Example 9:009:009:019:019:029:039:039:039:049:059:069:079:08 w1 T 12 W3 w4 15 w7 75 5 Wi(1, 6) Each taxi can move one unit distance per minute 012345678X Dr= 2min and dw=10min
1 2 3 4 5 1 2 3 4 5 0 X Y 6 7 8 6 7 8 Existing Research: An Example 𝒘𝟏(𝟏,𝟔) 𝒘𝟏 𝑫𝒓 = 𝟐min and 𝑫𝒘 = 𝟏𝟎min Each taxi can move one unit distance per minute 9
Existing Research: An Example 9:009:0019:019:019:029:039:039:039:049:059:069:079:08 w1 T1 12 W3 w4 15 w7 75 Deadline constraint: If a taxi is in the n16 dotted circle, it can arrive at the position r1(25) of the passenger before her/his deadline 012345678X Dr= 2min and dw=10min
1 2 3 4 5 1 2 3 4 5 0 X Y 6 7 8 6 7 8 Existing Research: An Example 𝒘𝟏(𝟏,𝟔) 𝒘𝟏 𝒓𝟏(𝟐, 𝟓) 𝒓𝟏 Deadline constraint: If a taxi is in the dotted circle, it can arrive at the position of the passenger before her/his deadline 𝑫𝒓 = 𝟐min and 𝑫𝒘 = 𝟏𝟎min 10