BOTP: Balancing Cost and Human Familiarity in Spatial Crowdsourcing

TL;DR

In the world of Spatial Crowdsourcing (SC)—think Uber Eats or Waze—getting a worker to a location is only half the battle. This paper argues that Location Familiarity is the "secret sauce" for task quality. The authors propose the Bi-Objective Task Planning (BOTP) framework, which uses a forgetting-curve model to assign tasks to workers who know the area best, while keeping recruitment costs low.

The Missing Dimension: Why "Where" Matters

Most SC platforms (like TaskRabbit or Didi) treat workers as points on a map. They assume that if Worker A is closer to a task than Worker B, Worker A is the better choice. However, the study identifies a critical oversight: Location Familiarity.

A worker who has visited a neighborhood ten times is faster and more reliable than a newcomer relying solely on GPS. Prior works suffered from two main gaps:

1. Neglecting Human Intuition: They ignored the efficiency gains from spatial memory.
2. Rigid Optimization: They focused on a single goal (minimize distance), failing to see that "cost" and "quality" (familiarity) are often at odds.

Methodology: Modeling Memory and Complexity

The authors quantify familiarity using the Ebbinghaus forgetting curve, which models how human memory of a location decays over time.

1. Familiarity Formula

The familiarity $q_{ij}$ between worker $w_i$ and task $t_j$ is calculated based on how long it has been since their last visit to that specific grid area. If you haven't been there in six months, your familiarity score is near zero.

2. The Algorithmic Duo

Since solving this for hundreds of workers and tasks is NP-hard, the paper introduces two distinct strategies:

• DAC (Divide-and-Conquer): Useful when you have a strict budget ($C_0$). It breaks large regions into smaller sub-problems, solves them greedily, and then merges them back together, adjusting the solution if it exceeds the budget.
• EMOSA (Enhanced Multi-Objective Simulated Annealing): Useful when you want a menu of options. Instead of one answer, it provides a Pareto front—a curve showing the best possible familiarity for every possible budget level.

Figure 1: The EMOSA algorithm uses chromosome-like representations of task sequences and performs crossover/mutation to explore the solution space effectively.

Experimental Showdown

The researchers tested their methods using the Didi Chuxing dataset from Chengdu, involving over 125,000 taxi trajectories.

DAC Results

When compared to a standard cost-constrained greedy approach:

• Familiarity: Improved by 21.5%.
• Completed Tasks: Increased by a staggering 74%.
• Insight: By balancing cost and familiarity during the "merge" phase, DAC avoids the "trap" of picking one very familiar but extremely expensive worker.

EMOSA Results

EMOSA proved that single-objective algorithms are too narrow.

• Versus RCFirst (Recruitment Cost First): EMOSA costs only 8% more but provides 400% higher familiarity.
• Versus LFFirst (Location Familiarity First): EMOSA achieves nearly the same quality but at a 28% lower cost.

Table 1: Improvement of EMOSA over traditional baselines across diverse worker counts.

Conclusion & Future Outlook

This work moves spatial crowdsourcing from a purely geometric problem (distance/time) to a behavioral economic problem. By admitting that human workers are not robots—that they remember and they forget—the SC server can plan tasks that are both cheaper to recruit for and more likely to be completed with high quality.

The Takeaway: Future SC platforms should stop asking "Who is closest?" and start asking "Who knows this street best?" while using Multi-Objective optimization to keep the CFO happy.

Limitations

• The model assumes the "forgetting curve" parameters are the same for all humans, but spatial memory varies significantly between individuals.
• The study is offline; real-world deployment would require adapting these algorithms to handle dynamic task arrivals in milliseconds.