[4] ( 1) 1 (1) ( ) () (2) () (3) (a) (b) 2 [5][6] (1) (2) (1) (i) (ii) (2) 7% 8% [7] 2 [8] [9] [10] Reddy [11] Kazemi [5] [12] [6] Kazem

Size: px

Start display at page:

Download "[4] ( 1) 1 (1) ( ) () (2) () (3) (a) (b) 2 [5][6] (1) (2) (1) (i) (ii) (2) 7% 8% [7] 2 [8] [9] [10] Reddy [11] Kazemi [5] [12] [6] Kazem"

らむはらしない
5 years ago
Views:

1 Task Assignment by Referring to Worker s Temporal Constraint in Mobile Crowdsourcing Mayumi HADANO Makoto NAKATSUJI Hiroyuki TODA Yoshimasa KOIKE 2 7% This paper focuses on task assignments to workers in mobile crowdsoucing systems. The current method of assigning tasks to workers creates a directed graph that represents the relationships between workers and tasks, and it finds the best set of worker-task pairs by solving a min-cost max flow problem on it. It, however, does not assign tasks so well since it considers only workers who are ready to work at the time of optimization, whereas in reality workers tend to change their activities over time. To tackle with this problem, we propose a new method that incorporates two new ideas: (1) it creates a time-extended worker-task graph that expresses the relationships between workers and tasks over a time period by referring to workers schedules; (2) it handles information on workers that changes over time and finds the best set of worker-task-time triples by using the time-extended worker-task graph. We evaluated our method by using real-world visiting logs. The results show that our method increases the rate of assigned tasks by more than 6% compared with another state-of-the-art assignment method. NTT hadano.mayumi@lab.ntt.co.jp NTT nakatuji@nttr.co.jp NTT toda.hiroyuki@lab.ntt.co.jp NTT koike.y@lab.ntt.co.jp リクエスタ (1) タスク発 { } (3) データ納品ワーカ提案システム (2) タスク割当て 1: [1] Twitter [2] [3]

2 [4] ( 1) 1 (1) ( ) () (2) () (3) (a) (b) 2 [5][6] (1) (2) (1) (i) (ii) (2) 7% 8% [7] 2 [8] [9] [10] Reddy [11] Kazemi [5] [12] [6] Kazemi [5] Chen [13] 1 [14][15] Chen 1 Amazon Mechanical Turk( mturk/) ( 2

2: 3. 3. 1 1 () t i T T t i (x i, y i ) d i t i d i (x i, y i ) 2 t 1 t 6 6 2 () w j W W w j (x j, y j ) R j maxt j R j maxt j 2 w 1 w 3 3 R j maxt j 3 () G(V, E) V E e( E) f (e) f (e) c(e) (1) V W +

3 2: () t i T T t i (x i, y i ) d i t i d i (x i, y i ) 2 t 1 t () w j W W w j (x j, y j ) R j maxt j R j maxt j 2 w 1 w 3 3 R j maxt j 3 () G(V, E) V E e( E) f (e) f (e) c(e) (1) V W + T + 2 w j W v j t i T v W +i v src v sink (2) E W + T + m v src W W T v sink T w j w j R j m (3) v src w j f w j maxt j v 1 v 3 v 4 v 9 3: (1) (2) 2 (1) (2) 4 ( ) w j R j t i w j t i w j v src v sink [16] [16][17] G = (V, E) e E f (e) > 0 f (e) > 0 v δ + v v δ v max f (e) (1) e δ + v src 0 f (e) f (e) ( e E) (2) f (e) f (e) = 0 ( v V\{v src, v sink }) (3) e δ + v e δ v (2) (3) 5 ( ) (2)(3) f max v src v sink 3

4 ϕ k, φ t i, T(ϕ k ) w j, W(ϕ k ) W(φ) R j (ϕ k ) maxt j CP f max c min MT P T 1: ϕ k ϕ k ϕ k w j f max min f (e)c(e) (4) e E (2) (3) (5) e δ + v src f (e) = f max (5) 2 4. (1) (2) 1 φ R j ϕ k T(ϕ k ) W(φ) ϕ k w j (ϕ k )( W(ϕ k )) R j (ϕ k ) maxt j W(φ) T(ϕ k ) T (1) (2) タスクワーカ (1) 最大タスク割当て計算 (2) 最小コスト割当て計算 (3) 割当て時刻計算 4: 出 ( タスク, ワーカ, 時刻 ) 三つ組 (3) 3 (1) W(φ) T(ϕ k ) CT f max 1 (2) (1) CT f max P MT (3) (2) P T (1) (3) 4. 2 W(φ) T(ϕ k ) CT f max [5] ϕ 1 t 1 t 2 ϕ 1 w 1 ϕ 2 w 2 w 1 w 2 t 1 t 2 {(t 1, w 1,ϕ 1 ),(t 1, w 1,ϕ 2 ), (t 1, w 2,ϕ 2 ),(t 2, w 1, ϕ 1 ),(t 2, w 1, ϕ 2 ),(t 2, w 2, ϕ 2 )} 4

5 従来手法提案手法 5: 4. 3 CT f max P MT t i w j φ cand a(t i, w j (ϕ k )) ϕ k w j t i t i w j c i j c i j = min (a(t i, w j (ϕ k )) + ϕ k ) (6) ϕ k φ cand (t i, a(w j (ϕ k )) + ϕ k ) ϕ k w j t i (6) 1 5 (t 1, w 1 ) φ cand {ϕ 1, ϕ 2 } (t 1, w 1 ) min (5 + 1, 5 + 2) = 6 (t 2, w 1 ) min (5 + 1, 2 + 2) = 4 (t 1, w 2 ) min (3 + 2) = 5 (t 2, w 2 ) min (2 + 2) = CT P T (6) Algorithm 1 Algorithm 1 Require: W(φ), T(ϕ k ), φ. Ensure: T. 1: // (1) 2: for each w j (ϕ k ) in W(φ) do 3: for each t i in T(ϕ k ) do 4: if t i can be done by w j (ϕ k ) then 5: candidate triple CT (t i, w j, ϕ k ) 6: end if 7: end for 8: end for 9: f max MaxFlow(CT ) 10: // (2) 11: for each (t i, w j ) in CT do 12: c min ComputeLeastCost(t i, w j, φ) 13: cost triple MT (t i, w j, c min ) 14: end for 15: minimum cost pair P MinCostFlow(MT, f max ) 16: // (3) 17: for each (t i, w j ) in P do 18: ϕ opt ComputeTime(CT ) 19: min. cost triple T (t i, w j, ϕ opt ) 20: end for 5. 1 (1) (2) 2 (1) (2) Gowalla 1 (Gowalla ) ID ID web (100 ) (200 ) (200 ) ( ) 5. 2 [5] [18][12] (1) (2)

6 合割カーワ [%] 仕事開始時刻 6: [%] 0.25 合割カーワ連続仕事可能時間 7: ( ) [100, 200, 300, 400, 500] [3, 4, 5, 6] 10 [1, 2, 3, 4, 5] 3 Gowalla web ϕ k W(ϕ k ) Gowalla ( 6) ( 7) R j 2: [%] [km/h] : (min) Kazemi CTimeOpt (2) v ϕ rest w j R j (v ϕ rest )/2 [100, 200, 300, 400, 500] Kazemi: [5] 1 () CTimeOpt: ( ) FTimeOpt: CTimeOpt 8 CTimeOpt Kazemi 9 10 CTimeOpt CTimeOpt 99.0% Kazemi 92.3% 6.7% CTimeOpt CTimeOpt FTimeOpt CTimeOpt 9 24 CTimeOpt Kazemi CTimeOpt Kazemi 6

数クスタ数クスタ時刻 8: 時刻合割クスタ了完合割クスタ了完タスク数ワーカ数 10: 合割クスタ了完合割クスタ了完タスク数 /10 分ワーカ数 9: ( ) Kazemi CTimeOpt 2 Kazemi

Okazaki, and Y. Matsuo, Earthquake shakes twitter users: Real-time event detection by social sensors, in Proc.

Sumiya, Measuring geographical regularities of crowd behaviors for twitter-based geo-social event detection, in

Shahabi, Geocrowd: Enabling query answering with spatial crowdsourcing, in Proc. SIGSPATIAL 12, 2012, pp. 189 198.

To, Maximum complex task assignment: Towards tasks correlation in spatial crowdsourcing, in Proc.

7 数クスタ数クスタ時刻 8: 時刻合割クスタ了完合割クスタ了完タスク数ワーカ数 10: 合割クスタ了完合割クスタ了完タスク数 /10 分ワーカ数 9: ( ) Kazemi CTimeOpt 2 Kazemi CTimeOpt 3 2 5% 8% CTimeOpt CTimeOpt ( 11) : 7% 8% [ ] [1],, [2] T. Sakaki, M. Okazaki, and Y. Matsuo, Earthquake shakes twitter users: Real-time event detection by social sensors, in Proc. WWW 10, 2010, pp [3] R. Lee and K. Sumiya, Measuring geographical regularities of crowd behaviors for twitter-based geo-social event detection, in Proc. LBSN 10, 2010, pp [4] J. Howe, The rise of crowdsourcing, Wired, [5] L. Kazemi and C. Shahabi, Geocrowd: Enabling query answering with spatial crowdsourcing, in Proc. SIGSPATIAL 12, 2012, pp [6] H. Dang, T. Nguyen, and H. To, Maximum complex task assignment: Towards tasks correlation in spatial crowdsourcing, in Proc. iiwas 13, 2013, p. 77. [7] D. Namiot, Geofence services, International Journal of Open Information Technologies, vol. 1, no. 9, pp , [8] M. C. Yuen, I. King, and K. S. Leung, Taskrec: A task recommendation framework in crowdsourcing systems, Neural Processing Letters, pp. 1 16,

8 [9] P. Donmez, J. G. Carbonell, and J. Schneider, Efficiently learning the accuracy of labeling sources for selective sampling, in Proc. KDD 09, 2009, pp [10] C.-J. H. and J. W. V., Online task assignment in crowdsourcing markets, in Proc. AAAI 12, 2012, pp [11] S. Reddy, D. Estrin, and M. Srivastava, Recruitment framework for participatory sensing data collections, in Pervasive Computing, 2010, pp [12] L. Kazemi, C. Shahabi, and L. Chen, Geotrucrowd: Trustworthy query answering with spatial crowdsourcing, in Proc. SIGSPATIAL 13, 2013, pp [13] C. Chen, S. F. Cheng, A. Gunawan, A. Misra, K. Dasgupta, and D. Chander, Traccs: Trajectory-aware coordinated urban crowd-sourcing, in Proc. HCOMP 14, 2014, pp [14] D. Ashbrook and T. Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, vol. 7, no. 5, pp , [15] A. Noulas, S. Scellato, N. Lathia, and C. Mascolo, Mining user mobility features for next place prediction in location-based services. in Proc. ICDM, 2012, pp [16] L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Canadian journal of Mathematics, vol. 8, no. 3, pp , [17] Y. Dinitz, Dinitz algorithm: The original version and even s version, in Theoretical Computer Science. Springer, 2006, pp [18] D. Deng, C. Shahabi, and U. Demiryurek, Maximizing the number of worker s self-selected tasks in spatial crowdsourcing, in Proc. SIGSPATIAL 13, 2013, pp Mayumi HADANO Makoto NAKATSUJIi NTT 2010 Hiroyuki TODA NTT ( ) ACM Yoshimasa KOIKE NTT

FIT2014( 第 13 回情報科学技術フォーラム ) RD-002 Web SNS Yuanyuan Wang Gouki Yasui Yuji Hosokawa Yukiko Kawai Toyokazu Akiyama Kazutoshi Sumiya 1. Twitter 1 Facebo

FIT2014( 第 13 回情報科学技術フォーラム ) RD-002 Web SNS Yuanyuan Wang Gouki Yasui Yuji Hosokawa Yukiko Kawai Toyokazu Akiyama Kazutoshi Sumiya 1. Twitter 1 Facebo RD-002 Web SNS Yuanyuan Wang Gouki Yasui Yuji Hosokawa Yukiko Kawai Toyokazu Akiyama Kazutoshi Sumiya 1. Twitter 1 Facebook 2 SNS SNS SNS Twitter SNS [1] SNS [2] Twitter Web Web Web Web SNS Web Web 2 Web