Crowdphysics: Planned and Opportunistic Crowdsourcing for Physical Tasks

Adam Sadilek, John Krumm, Eric Horvitz

Abstract

Research on human computation and crowdsourcing has concentrated on tasks that can be accomplished remotely over the Internet. We introduce a general class of problems we call crowdphysics (CP)—crowdsourcing tasks that require people to collaborate and synchronize both in time and physical space. As an illustrative example, we focus on a crowd-powered delivery service—a specific CP instance where people go about their daily lives, but have the opportunity to carry packages to be delivered to specific locations or individuals. Each package is handed off from person to person based on overlaps in time and space until it is delivered. We formulate CP tasks by reduction to a graph-planning problem, and analyze the performance using a large sample of geotagged tweets as a proxy for people's location. We show that packages can be delivered with remarkable speed and coverage. These results hold for the case when we know people's future locations and also when routing without global knowledge, making only local greedy decisions. To our knowledge, this is the first empirical evidence that dynamic networks of mobile individuals are highly navigable.

Introduction

Traditional crowdsourcing platforms like Amazon Mechanical Turk have revolutionized "intellectual" labor by allowing tasks to be completed remotely. However, many critical real-world challenges—such as logistics, search-and-rescue, or emergency response—require the movement of physical atoms rather than just digital bits. We define this new domain as Crowdphysics (CP): tasks requiring synchronization in both time and physical space.

The core challenge of CP is coordinating a "dynamic mesh" of mobile individuals. Unlike digital crowdsourcing, CP requires participants to be in the same place at the same time to perform a handoff. Furthermore, real-world systems must operate under uncertainty, without an "oracle" that knows every participant's future movements.

Methodology: The Routing Graph

To analyze the feasibility of CP, we modeled human movement as a Routing Graph ($G$). Using geotagged tweets as a proxy for location, we define nodes as a user's location at a specific timestamp. Edges represent either the movement of a single individual between check-ins or a handoff opportunity between two different individuals.

Schematic of spatio-temporal handoffs between users.

A handoff is considered viable if two users are within a distance slack $\delta$ and a time window $\tau$. We evaluated two primary routing strategies: Global Planning, which finds the optimal path assuming perfect future knowledge, and Local Opportunistic Routing, a decentralized "greedy" approach where packages are handed to individuals historically likely to visit the destination.

Key Insights: Reachability and Phase Transitions

Our analysis of millions of tweets across NYC, Seattle, and the continental US revealed several striking properties of physical mobility networks.

The Phase Transition of Permeability

The "reachability" of these networks—the percentage of cell pairs that can successfully exchange a package—is not a linear function of participant flexibility. Instead, we observe a sharp phase transition. As the allowed "digression" (distance slack) or wait time increases slightly, the network "snaps" from being largely disconnected to having near-total coverage.

Reachability as a function of distance and time slack.

Physical Small Worlds and Natural Rhythms

Similar to social networks, physical mobility networks exhibit "small world" properties. Short paths exist between distant locations, often facilitated by long-distance travelers (e.g., people flying between cities). Furthermore, delivery times are heavily influenced by human circadian rhythms, showing strong periodicity at 24-hour and 5-day intervals.

Results

  • High Coverage: In NYC, the system achieved 100% coverage with an 800m distance slack and 90-minute wait. Even in the sparser Seattle area, coverage reached 83%.
  • Local vs. Global: Local greedy routing achieved 58% of the coverage of the global optimum, suggesting that decentralized crowd-delivery is viable even without global coordination.
  • Speed: Coast-to-coast delivery (e.g., NYC to LA) was possible in as little as 5.5 hours by leveraging existing travel patterns of users flying between those cities.

Conclusion and Future Work

This research provides the first empirical evidence that dynamic networks of mobile individuals are highly navigable. While data sparsity in tweets suggests that real-world performance could be even higher, significant hurdles remain regarding participant incentives, trust, and privacy. Future work will focus on developing robust mechanisms to coordinate these "sensor networks of people" for broader humanitarian and logistical applications.

Summary updated

Abstract

Research on human computation and crowdsourcing has concentrated on tasks that can be accomplished remotely over the Internet. We introduce a general class of problems we call crowdphysics (CP)---crowdsourcing tasks that require people to collaborate and synchronize both in time and physical space. As an illustrative example, we focus on a crowd-powered delivery service---a specific CP instance where people go about their daily lives, but have the opportunity to carry packages to be delivered to specific locations or individuals. Each package is handed off from person to person based on overlaps in time and space until it is delivered. We formulate CP tasks by reduction to a graph-planning problem, and analyze the performance using a large sample of geotagged tweets as a proxy for people's location. We show that packages can be delivered with remarkable speed and coverage. These results hold for the case when we know people's future locations and also when routing without global knowledge, making only local greedy decisions. To our knowledge, this is the first empirical evidence that dynamic networks of mobile individuals are highly navigable.
BibTeX
@inproceedings{sadilek2021crowdphysics,
  author = {Adam Sadilek and John Krumm and Eric Horvitz},
  title = {{Crowdphysics: Planned and Opportunistic Crowdsourcing for Physical Tasks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/icwsm.v7i1.14430},
}
Figure