Modeling Transportation Routines using Hybrid Dynamic Mixed Networks

Vibhav Gogate, Rina Dechter, Bozhena Bidyuk, Craig Rindt, James MarcaUAI 2005

TL;DR

This paper introduces Hybrid Dynamic Mixed Networks (HDMNs), a novel framework for modeling complex real-life sequential processes that involve both probabilistic and deterministic information. They propose new approximate inference algorithms, IJGP(i)-S and IJGP-RBPF, to handle the computational challenges of HDMNs, demonstrating their effectiveness in predicting individual transportation routines.

What Problem Does This Paper Address?

Modeling real-world sequential phenomena, like human behavior, often requires integrating two types of information: probabilistic uncertainty and deterministic rules or constraints. Traditional Hybrid Dynamic Bayesian Networks (HDBNs) can represent probabilistic relationships but struggle to efficiently incorporate hard constraints, often treating them as probabilistic entities, which can lead to computational inefficiencies. Conversely, constraint networks excel at deterministic reasoning but lack probabilistic modeling capabilities. This paper addresses the need for a unified framework that can seamlessly combine both probabilistic and deterministic information in dynamic environments, specifically for modeling complex sequential behaviors like transportation routines. The authors highlight the practical importance of this for applications like urban planning and personalized traffic assistance, where accurate prediction of travel demand and individual routes is crucial.

Methods

The core contribution is the Hybrid Dynamic Mixed Network (HDMN) framework, which extends Hybrid Dynamic Bayesian Networks (HDBNs) by incorporating explicit discrete constraints. This is achieved by combining a Hybrid Mixed Network (HMN) with a dynamic Bayesian network structure.

To handle the computational complexity of HDMNs, the authors propose two novel approximate inference algorithms:

  • IJGP(i)-S (Iterative Join Graph Propagation - Sequential): An extension of Generalized Belief Propagation (GBP) for HDBNs, adapted for sequential processing in HDMNs. It uses a join-graph structure and message passing, with complexity bounded by an "i-bound" related to the number of discrete variables in cliques.
  • IJGP-RBPF (Iterative Join Graph Propagation - Rao-Blackwellised Particle Filtering): This is the paper's main algorithmic contribution. It integrates IJGP(i) with Rao-Blackwellised Particle Filtering (RBPF). The key idea is to use IJGP(i) to generate a proposal distribution that already incorporates constraints, thereby reducing the rejection rate of samples in the particle filtering process. This algorithm partitions variables into those sampled (R) and those inferred analytically (Z), aiming to improve efficiency in high-dimensional spaces.

Datasets

The paper uses a log of GPS readings collected by one of the authors over a six-month period. This data consists of time, date, location (latitude/longitude), and velocity. The data was preprocessed to identify "goals" (locations where a person spends significant time) and to snap GPS points to road segments using TIGER/Line files from the US Census Bureau. The first three months of data were used for training, and the remaining data for testing.

Key Insights and Ideas

  • Unified Representation: HDMNs provide a powerful way to model real-world phenomena that are inherently a mix of probabilistic uncertainty and deterministic rules, a common scenario in human behavior and complex systems.
  • Constraint-Aware Sampling: The IJGP-RBPF algorithm is a significant advancement for particle filtering in domains with hard constraints. By using a constraint-aware proposal distribution generated by IJGP(i), it effectively reduces sample rejection rates, a major bottleneck in traditional RBPF for such problems.
  • Domain Independence: The framework and algorithms are designed to be domain-independent, allowing for systematic study and easy adaptation to various sequential modeling tasks.
  • Practical Relevance: The application to transportation routines demonstrates the framework's ability to tackle complex, real-world problems with direct implications for urban planning and personalized mobility services.

Key Results

  • Goal Prediction Accuracy: Model-1, which incorporates day-of-week and time-of-day variables, achieved the highest goal prediction accuracy (84%), outperforming Model-2 (77%) and Model-3 (68%).
  • Algorithm Performance: For Model-1, IJGP-RBPF(1,2) and IJGP(2)-S were identified as the best performing learning algorithms. When evaluating inference algorithms on a learned model, IJGP-RBPF generally yielded the best accuracy, while IJGP(2)-S was more cost-effective in terms of time vs. accuracy.
  • Route Prediction Accuracy: Model-1 and Model-2 showed the best route prediction accuracy, characterized by low false positives and false negatives.
  • Computational Efficiency: While exact inference in dynamic networks is often infeasible, the proposed approximate algorithms offer a practical trade-off between accuracy and computational cost. The IJGP-RBPF learning algorithm for Model-1 took up to 5 days of CPU time, which is considered efficient relative to the data collection period.

Limitations and Future Work

  • Restrictions on Dependencies: The paper notes that the current HDMN framework has restrictions on dependencies between discrete and continuous variables.
  • EM Algorithm Efficiency: The authors suggest developing a more efficient EM-algorithm for learning HDMNs.
  • Future Directions: Future work includes relaxing the restrictions on dependencies between discrete and continuous variables and developing more efficient learning algorithms. The authors also suggest exploring other approximate inference techniques and applying the framework to other complex sequential domains.

Summary updated

BibTeX
@inproceedings{gogate2005modeling,
  author = {Vibhav Gogate and Rina Dechter and Bozhena Bidyuk and Craig Rindt and James Marca},
  title = {{Modeling Transportation Routines using Hybrid Dynamic Mixed Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2005},
}
Figure