# Scalable Probabilistic Routes

arXiv: https://arxiv.org/abs/2306.10736 · HTML: https://mlsanity.com/paper/2306.10736/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 37 references that are in the map.
- First posted on arXiv 19 Jun 2023.

## Builds on (most cited first, 4 of 4)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models](https://mlsanity.com/paper/1401.3448/) (2014)

## Abstract (arXiv)

Inference and prediction of routes have become of interest over the past decade owing to a dramatic increase in package delivery and ride-sharing services. Given the underlying combinatorial structure and the incorporation of probabilities, route prediction involves techniques from both formal methods and machine learning. One promising approach for predicting routes uses decision diagrams that are augmented with probability values. However, the effectiveness of this approach depends on the size of the compiled decision diagrams. The scalability of the approach is limited owing to its empirical runtime and space complexity. In this work, our contributions are two-fold: first, we introduce a relaxed encoding that uses a linear number of variables with respect to the number of vertices in a road network graph to significantly reduce the size of resultant decision diagrams. Secondly, instead of a stepwise sampling procedure, we propose a single pass sampling-based route prediction. In our evaluations arising from a real-world road network, we demonstrate that the resulting system achieves around twice the quality of suggested routes while being an order of magnitude faster compared to state-of-the-art.