Learning Periodic Human Behaviour Models from Sparse Data for Crowdsourcing Aid Delivery in Developing Countries

James McInerney, Alex Rogers, Nicholas R. Jennings

Abstract

In many developing nations, traditional road-based aid delivery to rural areas is prohibitively expensive and slow. This paper presents a novel approach to "last-mile" delivery by crowdsourcing the task to local citizens, leveraging their existing daily routines. By modeling periodic human mobility from sparse cell tower data using a Bayesian non-parametric framework and optimizing delivery chains via a Markov Decision Process (MDP), the researchers achieve significant improvements in both prediction accuracy and delivery efficiency.

Introduction

Half the population in many developing countries resides in rural areas where infrastructure is poor. Delivering essential goods like medicine or school supplies often relies on expensive international logistics or ad-hoc social schemes involving outsiders. This research explores whether the natural, pre-existing movements of the local population can be harnessed as a reliable transportation infrastructure.

Two primary technical challenges exist: data sparsity and optimization complexity. Mobility data in these regions typically comes from cell towers, providing only a few "pings" per day per user. Furthermore, routing packages through a chain of individuals with uncertain schedules is a computationally hard problem.

Methodology

The Mobility Model

To address data sparsity, the researchers developed a Dirichlet Process Mixture Model (DPMM). Unlike traditional models that require predefined locations, the DPMM automatically infers the number of significant locations (e.g., home, work) an individual visits. The model assumes human behavior is periodic (daily and weekly) and uses a Bayesian framework to create a smooth probability distribution of a person's location over time, effectively filling in the gaps between sparse data points.

Plate notation of the proposed Bayesian non-parametric model for learning periodic human mobility from sparse data.

The Routing Model

The delivery problem is formulated as a Markov Decision Process (MDP). While such problems are often intractable due to unbounded delays, the authors prove that assuming periodic behavior makes the state space linear and solvable. The system identifies the optimal "courier" for each hop—the person whose routine most reliably aligns with the required exchange point and time.

Datasets

The study utilizes the Orange "Data for Development" (D4D) dataset, containing anonymized cell tower records for 50,000 individuals in the Ivory Coast over two weeks. This dataset reflects real-world conditions where connectivity is discrete and sparse.

Results

Prediction Accuracy

The Bayesian model significantly outperformed state-of-the-art Variable-order Markov Models (VMM). As shown in the log-likelihood comparison, the proposed approach provides a more robust fit for the sparse mobility data, leading to a 25% improvement in predicting held-out location data.

Log-likelihood comparison of the proposed approach against baseline mobility models.

Delivery Speed and Feasibility

Simulations of 10,000 journeys to rural destinations revealed that MDP-optimized routes were 81.3% faster than naive shortest-path approaches, reducing average delivery times from 161 days to just 30 days. Furthermore, the study found that a pool of only 3,500 participants could provide 80% geographical coverage of the Ivory Coast, with most delivery chains requiring only 2 to 4 people.

Discussion and Future Work

While the technical optimization is promising, several real-world hurdles remain. The current model assumes a high degree of trust and willingness to participate. Future work should integrate "trust costs" and incentive structures into the MDP. Additionally, the model's reliance on long-term periodicity means it does not yet account for real-time disruptions like illness or infrastructure failure.

Summary updated

BibTeX
@inproceedings{mcinerney2013learning,
  author = {James McInerney and Alex Rogers and Nicholas R. Jennings},
  title = {{Learning Periodic Human Behaviour Models from Sparse Data for Crowdsourcing Aid Delivery in Developing Countries}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
}
Figure