A Bayesian Nonparametric Approach to Modeling Mobility Patterns

Joshua Mason Joseph, Finale Doshi-Velez, Nicholas Roy

Introduction

Predicting the movement of mobile agents, such as vehicles in an urban environment, is a fundamental challenge for autonomous systems and urban planning. Traditional modeling techniques often struggle with the balance between model complexity and data availability. Parametric models typically require a pre-defined number of behaviors, leading to either underfitting or overfitting. Conversely, grid-based Markov models are often "memoryless," failing to distinguish between different long-term intents when paths intersect or overlap. This paper proposes a Dirichlet Process Gaussian Process (DPGP) mixture model that learns to identify and predict distinct mobility patterns from raw, noisy GPS data without prior knowledge of the number of patterns.

Methodology

The proposed approach leverages two powerful Bayesian tools:

  1. Gaussian Processes (GP): Instead of discretizing space into a grid, the model uses GPs to represent a continuous "velocity field." For any given coordinate, the GP predicts the expected change in position, effectively handling noise and varying-length trajectories.
  2. Dirichlet Process (DP): This nonparametric component serves as a clustering mechanism. It allows the model to automatically discover an appropriate number of mobility patterns. As more data is observed, the DP can instantiate new clusters to represent previously unseen behaviors.

A single trajectory is modeled as a sample from one of $M$ latent mobility patterns, where each pattern is characterized by its own pair of GPs (for x and y velocities). Inference is performed using Gibbs sampling, with a nearest-neighbor approximation to maintain computational efficiency.

Key Insights and Model Behavior

Adaptive Complexity

A core advantage of the Bayesian nonparametric framework is its ability to scale complexity naturally. Rather than fixing the number of possible routes, the model identifies more specific patterns—such as "airport runs" versus "downtown commutes"—as the volume of training data grows.

The number of discovered mobility patterns increases as the model processes more training paths, demonstrating the adaptive complexity of the DPGP approach.

History-Dependent Prediction

Unlike Markovian approaches that only consider the current state, the DPGP model uses a trajectory's entire history to determine its cluster assignment. This is crucial at intersections or shared road segments where multiple distinct paths might overlap. By identifying the underlying "intent" from the start of the journey, the model can disambiguate paths that appear identical in the short term.

Two distinct mobility patterns (red and green) overlap on a shared road segment. The DPGP identifies them as separate intents based on their history, allowing for accurate prediction when they diverge.

Evaluation and Results

The model was evaluated using real-world GPS data from taxis in Boston (the CarTel project). Key findings include:

  • Superior Predictive Likelihood: The DPGP consistently outperformed fine-grained Markov models in assigning higher likelihood to unseen test trajectories.
  • Enhanced Tracking: In simulated tracking tasks, the DPGP-based planner achieved higher cumulative rewards, demonstrating better predictive accuracy in sparse sensor environments.
  • Data Efficiency: The model reached high performance levels with significantly fewer training examples than traditional grid-based methods, which often suffer from "data sparsity" in unvisited cells.

Conclusion and Future Directions

The DPGP mixture model provides a principled, data-driven way to model complex mobility. While it offers significant improvements in accuracy and efficiency, challenges remain regarding computational overhead and the integration of temporal dependencies (e.g., rush hour vs. night traffic). Future work may also involve incorporating formal road network constraints to further refine predictions in dense urban environments.

Summary updated

Abstract

Constructing models of mobile agents can be difficult without domain-specific knowledge. Parametric models flexible enough to capture all mobility patterns that an expert believes are possible are often large, requiring a great deal of training data. In contrast, nonparametric models are extremely flexible and can generalize well with relatively little training data. We propose modeling the mobility patterns of moving agents as a mixture of Gaussian processes (GP) with a Dirichlet process (DP) prior over mixture weights. The GP provides a flexible representation for each individual mobility pattern, while the DP assigns observed trajectories to particular mobility patterns. Both the GPs and the DP adjust the model's complexity based on available data, implicitly avoiding issues of over-fitting or under-fitting. We apply our model to a helicopter-based tracking task, where the mobility patterns of the tracked agents — cars — are learned from real data collected from taxis in the greater Boston area.
BibTeX
@inproceedings{joseph2010bayesian,
  author = {Joshua Mason Joseph and Finale Doshi-Velez and Nicholas Roy},
  title = {{A Bayesian Nonparametric Approach to Modeling Mobility Patterns}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7721},
}
Figure