Scaling Mobile Crowdsourcing: Navigating Trajectory Uncertainty with Stochastic Optimization

TL;DR

Mobile crowdsourcing platforms often struggle with "super agents" who hoard tasks due to better planning. This paper introduces a push-based recommendation system that accounts for the fact that human workers don't follow the exact same route every day. By modeling trajectories as probabilistic distributions and using Lagrangian Relaxation, the authors provide a scalable way to maximize task completion in unpredictable real-world environments.

Problem & Motivation: The Fallacy of the Fixed Route

In the world of mobile crowdsourcing (e.g., store audits, sensor data collection), the "Pull Model" creates an unlevel playing field. A few "super agents" reap the rewards, while average workers go underutilized. While central "Push Model" assignments have been proposed to balance this, they typically assume a deterministic trajectory—the idea that a worker travels from A to B via the exact same path every time.

In reality, traffic, personal errands, and randomness mean that a worker might choose one of several routine paths. If a system assigns a task based on a path the worker doesn't take, that task is lost. The core challenge is: How do we assign tasks to maximize expected utility when we only know the probability of a worker's route?

Methodology: Stochastic Modeling and Decomposition

The authors treat this as a specialized routing problem with time budgets and stochastic constraints.

1. The Stochastic ILP Formulation

The objective is to maximize the expected total rewards. Unlike standard models, the decision variable $y_{ik}$ (assigning task $i$ to agent $k$) is penalized by ${\delta }_{ik}^m$, a binary variable that triggers if task $i$ is assigned but cannot be completed on the realized route $m$.

2. Overcoming Complexity via Lagrangian Relaxation

The resulting Integer Linear Program (ILP) is NP-hard and computationally expensive for standard solvers like CPLEX. To fix this, the authors moved the coupling "task-route" constraints into the objective function (Lagrangian Relaxation). This allows the problem to split into two side-by-side subproblems:

• Assignment Subproblem: Deciding which task goes to which agent.
• Routing Subproblem: Optimizing the visit sequence for each specific agent-route pair.

Figure 1: Conceptual overview of multi-agent coordination in urban environments.

Experiments & Results

The framework was tested using the Singapore transportation network. The study compared the Lagrangian Relaxation (LR) heuristic against a standard ILP solver and a "Deterministic Baseline" (which only plans for the most likely route).

Performance Gains

• Efficiency: For a scenario with 8 agents and 16 tasks, the ILP took nearly 2 hours (6558s), while the LR approach found a near-optimal solution in just 14.8 seconds.
• Robustness: In scenarios where workers had a 10-20% detour budget, the LR approach stayed within 0.4% of the theoretical "Perfect Information" Upper Bound. In contrast, the deterministic approach suffered from a massive performance gap (up to 13.8%), proving that ignoring uncertainty leads to significant missed opportunities.

Table 1: Scalability comparison between ILP and the proposed LR method.

Critical Insight: Why This Matters

The fundamental "Aha!" moment here is the realization that stochastic optimization is more "fair" and "efficient" than deterministic planning. By acknowledging that a worker might take Path B instead of Path A, the system assigns tasks that are robust across multiple possible futures.

Limitations & Future Work

While powerful, the model assumes that the probability distribution of routes (${\beta }_{mk}$) is known. Future iterations could integrate Online Learning to estimate these probabilities in real-time. Furthermore, as the number of possible routes ($M_k$) grows, even the decomposed subproblems may require more advanced heuristic pruning or status-space reduction.

Conclusion

This work provides a critical bridge between theoretical multi-agent planning and the messy, uncertain reality of urban mobility. By leveraging Lagrangian decomposition, the authors proved that we don't have to sacrifice scalability to achieve robustness in mobile crowdsourcing.