MCSC: Optimizing Throughput, Distance, and Diversity in Multi-Campaign Spatial Crowdsourcing

TL;DR

Spatial Crowdsourcing (SC) is evolving from simple task-matching to complex campaign management. This paper introduces MCSC, the first framework designed to handle multiple simultaneous campaigns while balancing the inherent conflict between high task throughput and low worker travel distance. By integrating worker diversity into the objective function, MCSC ensures that campaigns (like market research) receive high-quality, varied inputs without forcing workers into inefficient, long-distance routes.

Context & Positioning

In the landscape of Spatial Crowdsourcing, early works focused on static matching or simple geometric constraints (bounding circles). However, these methods often missed reachable tasks or ignored the "group utility" of workers assigned to the same campaign. This paper situates itself as a bridge between Mobile Crowd Sensing (MCS) and Vehicle Routing Problems (VRP), providing a robust mathematical framework for platforms like gMission or Amazon Mechanical Turk.

The Core Conflict: Throughput vs. Distance

The authors argue that blindly chasing throughput leads to "detour fatigue." If a worker is forced to travel to an isolated, remote spot, the marginal utility is negative. Many prior systems used hard "bounding circles" to limit distance, but as shown in the paper's examples, this often excludes tasks that could be easily reached via a slightly optimized path.

The MCSC insight is to treat distance and throughput as soft components of a single score: $f(A)=N-{\lambda }_{D}D+{\lambda }_{S}S$ Where:

• N: Total tasks completed.
• D: Total distance traveled.
• S: Worker diversity (sum of pairwise profile dissimilarities).

Methodology: The Two-Step Heuristic

Since the problem is NP-hard (reducible from the Open Vehicle Routing Problem), the authors propose a two-phase solution.

1. Hybrid-benefit based Assignment (HBA)

Instead of just looking at distance, HBA assigns workers to campaigns by estimating the immediate gain in diversity and throughput. It uses a "region-by-region" estimation technique to quickly guess the travel cost without running a full routing algorithm for every possible assignment.

Fig 1: Illustrating the trade-off between throughput and distance (left) and the region-based route estimation (right).

2. Task-Insertion Planning (TIP)

Once a worker is assigned to a campaign, TIP builds their route. Unlike "route-blind" methods, TIP maintains a sequence of visited locations and iteratively inserts new tasks where they cause the minimum increase in distance. This localized optimization ensures that workers follow a logical path rather than a zigzag.

Experimental Insights

The evaluation focused on how different regularization terms (${\lambda }_D,{\lambda }_S$) affect performance.

Fig 2: Performance comparison showing the impact of distance regularization. As we allow for a larger travel radius (increasing 1/λ_D), the system throughput (N) increases significantly.

Key findings include:

• HBA-TIP Superiority: Combining diversity-aware assignment with insertion-based routing consistently yields higher scores than basic greedy approaches.
• Scalability: The heuristics manage to produce results in roughly 10 seconds, making them suitable for near-real-time crowdsourcing platforms.
• Diversity Control: By adjusting ${\lambda }_S$, platforms can prioritize "diverse crowds" for specialized tasks (like diverse feedback for advertisements) or "efficient crowds" for basic data collection.

Critical Analysis & Conclusion

Takeaway

MCSC provides a sophisticated way to manage the "crowd" as a collective asset rather than a set of independent agents. The introduction of campaign-level diversity is a major step forward for high-value spatial tasks.

Limitations

The model assumes worker profiles and locations are known at the start of the time stamp. In highly dynamic environments, a "rolling" or "streaming" version of these heuristics would be necessary to handle workers who join or leave mid-route.

Future Work

The expansion of this work into "Spatiotemporal Crowdsourcing"—where task deadlines and time windows are primary constraints—remains a fertile ground for research, potentially integrating Reinforcement Learning to predict worker movement patterns.