Scalable Probabilistic Routes

The continuous pursuit of compact representations by the research community has resulted in several decision diagram forms over the years. Some of the decision diagram forms include AOMDD for multi-valued variables, OBDD and SDD for binary variables [5, 11, 24]. Both OBDD and SDD are canonical representations of Boolean formulas given variable ordering for OBDD and Vtree for SDD respectively. OBDD [5] is comprised of internal nodes that correspond to variables and leaf nodes that correspond to $\top$ or $\bot$. Each internal node of OBDD have exactly two child and represents the Shannon decomposition [4] on the variable represented by that internal node. SDDs are comprised of elements and nodes [11]. Elements represent conjunction of a prime and a sub, each of which can either be a terminal SDD or a decomposition SDD. A decomposition SDD is represented by a node with child elements representing the decomposition. A terminal SDD can be a literal, $\top$ or $\bot$. The decompositions of SDDs follow that of the respective Vtree, which is a full binary decision tree of Boolean variables in the formula. In this work, we use the OBDD[$\land$] [20] variant of OBDD, which is shown to be theoretically incomparable but empirically more succinct than SDDs [20].

A related development formulates probabilistic circuits [8], based on sum-product networks [28] and closely related to decision diagrams, as a special class of neural networks known as Einsum networks [27]. In the Einsum network structure, leaf nodes represent different gaussian distributions. By learning from data, Einsum networks are able to represent SPDs as weighted sums and mixtures of gaussian distributions. Einsum networks address scalability by utilizing tensor operations implemented in existing deep learning frameworks such as PyTorch [26]. Our work differs from the Einsum network structure, we require the determinism property for decision diagrams whereas the underlying structure for Einsum network lacks this property. We will introduce the determinism property in the following section.

Various Boolean encodings have been proposed for representing paths within a graph, including Absolute, Compact, and Relative encodings [29]. These encodings capture both the vertices comprising the path and the ordering information of said vertices. However, these encodings necessitate the use of polynomial number of Boolean variables, specifically $|V|^{2}$, $|V|log_{2}|V|$, and $2|V|^{2}$ variables for Absolute, Compact, and Relative encoding respectively. While these encodings accurately represent the space of paths within a graph, they are not efficient and lead to high space and time complexity for downstream routing tasks.

Choi, Shen, and Darwiche demonstrated over a series of papers that the distribution of routes can be conceptualized as a structured probability distribution (SPD) given the underlying combinatorial structure [6, 31, 32]. This approach, referred to as the ‘CSD’ approach in the rest of this paper, builds on top of existing approaches that represents paths using zero-surpressed decision diagrams [19, 17, 18]. The CSD approach utilizes sentential decision diagrams to represent the SPD of paths and employs a stepwise methodology for handling path queries. Specifically, at each step, the next vertex to visit is determined to be the one with the highest probability, given the vertices already visited and the start and destination vertices. While the CSD approach has been influential in its incorporation of probabilistic elements in addressing the routing problem, it is not without limitations. In particular, there are two main limitations (1) there are no guarantees of completion, meaning that even if a path exists between a given start and destination vertex, it may not be returned using the CSD approach [6]. (2) the stepwise routing process necessitates the repeated computation of conditional probabilities, resulting in runtime inefficiencies.

In summary, the limitations of prior works are Boolean encodings that require a high number of variables, lack of routing task completion guarantees, and numerous conditional probability computations.

In this subsection, we will introduce the $\mathsf{PROB}$ (Probabilistic OBDD[$\land$]) decision diagram structure and properties. We adopt the same notations as prior work [37] for consistency.

In this work, we present a novel relaxed encoding that only includes vertex membership and terminal information. Our encoding only requires a linear ($2|V|$) number of Boolean variables, resulting in more succinct decision diagrams and improved runtime performance for downstream tasks. In relation to prior encodings, we observed that the ordering information of vertices can be inferred from the graph given a set of vertices and the terminal vertices, thus enabling us to exclude ordering information in our relaxed encoding. Our relaxed encoding represents an over-approximation of trips in $\mathsf{SimpleTrip}(G)$ for graph $G(V,E)$ using a linear number of Boolean variables with respect to $|V|$. We discuss the over-approximation in later parts of this section.

Our encoding uses two types of Boolean variables, $n$-type and $s$-type variables. Each vertex $v\in V$ in graph $G(V,E)$ has a corresponding $n$-type and $s$-type variable. The $n$-type variable indicates if vertex $v$ is part of a trip and $s$-type variable indicates if $v$ is a terminal vertex of the trip. Our encoding is the conjunction of the five types of clauses over all vertices in graph $G$ as follows.

A simple trip $\pi$ in graph $G$ has at least one terminal vertex and at most two terminal vertices, described by encoding components H1 and H3 respectively. At each terminal vertex $v_{i}$ of $\pi$, there can only be at most 1 adjacent vertex of $v_{i}$ that is also part of $\pi$ and this is encoded by H4. For each vertex $v_{i}$ in $\pi$, at least one of their adjacent vertices is in $\pi$ regardless if $v_{i}$ is a terminal vertex or otherwise, this is captured by H2. Finally, H5 encodes that if a given vertex $v_{i}$ and one of its adjacent vertices are part of $\pi$, then either another neighbour vertex of $v_{i}$ is part of $\pi$ or $v_{i}$ is a terminal vertex.

We refer to our encoding as relaxed encoding because the solution space of constraints over-approximates the space of simple trips in the graph. Notice that while all simple trips correspond to a satisfying assignment of the encoding, they are not the only satisfying assignments. Assignments corresponding to a simple trip $\pi$ with disjoint loop component $\beta$ also satisfy the constraints. The intuition is that $\beta$ introduces no additional terminal vertices, hence H1, H3, and H4 remain satisfied. Since the vertices in $\beta$ always have $n$-type variables of exactly two of its neighbours set to true, H5 and H2 remain satisfied. Thus, a simple trip with a disjoint loop component also corresponds to a satisfying assignment of our encoding.

We introduce algorithm 1, $\mathsf{ProbLearn}$, for updating branch counters of $\mathsf{PROB}$ $\psi$ from assignments. In order to learn branch parameters $\mathsf{\theta_{Hi}}(n)$ and $\mathsf{\theta_{Lo}}(n)$ of decision node $n$, we require a counter for each of its branches, $\mathsf{{Hi}_{\#}}(n)$ and $\mathsf{{Lo}_{\#}}(n)$ respectively. In the learning process, we have a dataset of assignments for Boolean variables in the Boolean formula represented by $\mathsf{PROB}$ $\psi$. For each assignment $\tau$ in the dataset, we perform a top-down traversal of $\psi$ following Algorithm 1. In the traversal, we visit all child branches of conjunction nodes (line 4) and the child branch of decision node $n$ corresponding to the assignment of $\mathsf{Var}(n)$ in $\tau$ (lines 6 to 12), and increment the corresponding counters in the process. Subsequently, the branch parameters for node $n$ are updated according to the following formulas.

While we add 1 to numerator and 2 to denominator as a form of Laplace smoothing [23], other forms of smoothing to account for division by zero is possible. Notice that the learnt branch parameters of node $n$ are in fact approximations of conditional probabilities according to Proposition 1 and Remark 1 as follows.

The ability to conditionally sample trips is critical to handling trip queries for arbitrary start-end vertices, for which a trip is to be sampled conditioned on the given start and end vertices. In this work, we adapted the weighted sampling algorithm using $\mathsf{PROB}$, which was introduced by prior work [37], to support conditional sampling and denote it as $\mathsf{ProbSample}$.

Algorithm 2, $\mathsf{ProbSample}$, performs sampling of satisfying assignments from a $\mathsf{PROB}$ $\psi$ in a bottom-up manner. $\mathsf{ProbSample}$ takes an input $\mathsf{PROB}$ $\psi$ and partial assignment $\tau^{\prime}$ and returns a sampled complete assignment that agrees with $\tau^{\prime}$. The input $\tau^{\prime}$ specifies the terminal vertices for a given trip query by assigning the $s$-type variables. $\mathsf{ProbSample}$ employs two caches $\omega$ and $\gamma$, for partially sampled assignment at each node and joint probabilities during the sampling process. In the process, $\mathsf{ProbSample}$ performs calculations of joint probabilities at each node. In addition, $\mathsf{ProbSample}$ stores the partial samples at each node in $\omega$. The partial sample for a false node would be $\mathsf{Invalid}$ as it means that an assignment is unsatisfiable. On the other hand, the partial sample for a true node is $\emptyset$ which will be incremented with variable assignments during the processing of internal nodes of $\psi$. The partially sampled assignment at every $\land$-node $c$ is the union of the samples of all its child nodes, as the child nodes have mutually disjoint variable sets due to decomposability property. For a decision node $d$, if ${\mathsf{Var}(d)}$ is in $\tau^{\prime}$, the partial sample at $d$ will be the union of the literal in $\tau^{\prime}$ and the partial sample at the corresponding child node (lines 11 to 19) to condition on $\tau^{\prime}$. Otherwise, the partial assignment at $d$ is sampled according to the weighted joint probabilities $l$ and $h$ (lines 21 to 28). Finally, the output of $\mathsf{ProbSample}$ would be the sampled assignment at the root node of $\psi$. To extend $\mathsf{ProbSample}$ to sample $k$ complete assignments, one has to keep $k$ partial assignments in $\omega$ at each node during the sampling process and sample $k$ independent partial assignments at each decision node.

To understand $\mathsf{ProbRoute}$’s ability to learn probabilities from data, we evaluate its ability to produce trips that closely resembles the ground truth. Both $\mathsf{ProbRoute}$ and CSD, which are sampling-based approaches, were evaluated by sampling 20 trips and taking the median match rate for each instance. Recall that the $\varepsilon$-match rate is defined as the proportion of vertices in the ground truth trip that were within $\varepsilon$ meters of euclidean distance from the closest vertex in the proposed trip. In the evaluation, we set the $\varepsilon$ tolerance to be the median edge length of $G_{r}$, which is 64.359 meters, to account for parallel trips. To further emphasize the advantages of probabilistic approaches, we included an off-the-shelf routing library, Pyroutelib3 [36], in the comparison.

In order to conduct a fair comparison, we have adapted the CSD approach to utilize $\mathsf{PROB}$ derived from our relaxed encoding. Our evaluation utilizes this adapted approach to sample a trip on $G_{a}$ in a stepwise manner, where the probability of the next step is conditioned on the previous step and destination. The conditional probabilities are computed in a similar manner to the computations of joint probabilities, which are the $\gamma$ cache values, in the $\mathsf{ProbSample}$. The predicted trip on the road network $G_{r}$ is determined by the shortest trip on the subgraph formed by the sequence of sampled regions. In contrast, $\mathsf{ProbRoute}$ samples a trip on $G_{a}$ in a single pass, and subsequently retrieves the shortest trip on the subgraph of the sampled regions as the predicted trip on $G_{r}$. It is worth noting that for sampling-based approaches, there may be instances where a trip cannot be found on $G_{r}$ due to factors such as a region in $G_{a}$ containing disconnected components. We incorporated a rejection sampling process with a maximum of 400 attempts and 5 minutes to account for such scenarios.

Table 1 shows the match rate statistics of the respective methods. Under $\varepsilon$-Match setting, where $\varepsilon$ is set as the median edge length of $G_{r}$ to account for parallel trips, $\mathsf{ProbRoute}$ has the highest match rate among the three approaches. In addition, $\mathsf{ProbRoute}$ produced perfect matches for more than 25% of instances. $\mathsf{ProbRoute}$ has 0.316 $\varepsilon$-match rate on median, significantly more than 0.172 for CSD and 0.107 for Pyroutelib. The trend is similar for exact matches, where $\varepsilon$ is set to 0 as shown under the ‘Exact Match’ columns in Table 1. In the exact match setting, $\mathsf{ProbRoute}$ achieved a median of 0.310 match rate, almost double that of CSD’s 0.160 median match rate. The evaluation results also demonstrate the usefulness of probabilistic approaches such as $\mathsf{ProbRoute}$, especially in scenarios where experienced drivers navigate according to their own heuristics which may be independent of the shortest trip. In particular, $\mathsf{ProbRoute}$ would be able to learn and suggest trips that align with the unknown heuristics of driver preferences given start and destination locations. Thus, the results provide an affirmative answer to R1.

We compared our relaxed encoding to existing path encodings across various graphs, specifically to absolute encoding and compact encoding [29]. In the experiment, we had to adapt compact encoding to CNF form with Tseitin transformation [34], as CNF is the standard input for compilation tools. We compiled the CNFs of the encodings into OBDD[$\land$] form with 3600s compilation timeout and compared the size of resultant diagrams. The results are shown in Table 2, with rows corresponding to the different encodings used and columns corresponding to different graphs being encoded. Entries with TO indicate that the compilation has timed out. Table 2 shows that our relaxed encoding consistently results in smaller decision diagrams, up to 91$\times$ smaller. It is also worth noting that relaxed encoding is the only encoding that leads to compilation times under 3600s for the abstracted Singapore graph. The results strongly support our claims about the significant improvements that our relaxed encoding brings.

For wide adoption of new routing approaches, it is crucial to be able to handle the runtime demands of existing applications. As such, we measured the relative runtimes of probabilistic approaches, that is $\mathsf{ProbRoute}$ and CSD, with respect to existing routing system Pyroutelib and show the relative runtimes in Table 3. From the result, $\mathsf{ProbRoute}$ is more than one order of magnitude faster on median than the existing probabilistic approach CSD. The result also shows that $\mathsf{ProbRoute}$ is also on median more than a magnitude closer to Pyroutelib’s runtime using the same $\mathsf{PROB}$ as compared to CSD approach. In addition, CSD approach timed out on 650 of the 1000 test instances, while $\mathsf{ProbRoute}$ did not time out. Additionally, as mentioned in [6], CSD does not guarantee being able to produce a complete trip from start to destination. The results in Table 3 highlight the progress made by $\mathsf{ProbRoute}$ in closing the gap between probabilistic routing approaches and existing routing systems.

An important property to enable a $\mathsf{PROB}$ to learn the correct distribution is smoothness. A non-smooth $\mathsf{PROB}$ could be missing certain parameters. An example would be if we have an assignment $\tau_{1}=[\neg x,y,-z]$, $\psi_{1}$ in Figure 2 (main paper) will not have a counter for $\neg z$ as the traversal ends after reaching the true node from the decision node representing variable $y$. Observe that the above-mentioned issue would not occur in a smooth $\mathsf{PROB}$ $\psi_{2}$ in Figure 4. If a $\mathsf{PROB}$ is not smooth, we can perform smoothing. For a given decision node $n$ (for consistency with algorithm 3), if $\mathsf{VarSet}(\mathsf{Lo}({n}))\setminus\mathsf{VarSet}(\mathsf{Hi}({n}))\neq\emptyset$ we can augment the hi branch of $n$ with the missing variables as shown in lines 7 - 10 of algorithm 3. We create a new conjunction node $c$ with decision nodes representing each missing variable in $\mathsf{VarSet}(\mathsf{Lo}({n}))\setminus\mathsf{VarSet}(\mathsf{Hi}({n}))$ and $\mathsf{Hi}({n})$ as children. For each additional decision node created for $\mathsf{VarSet}(\mathsf{Lo}({n}))\setminus\mathsf{VarSet}(\mathsf{Hi}({n}))$, both branches lead to the true node. We reassign $\mathsf{Hi}({n})$ to be $c$. Similarly, we repeat the operation for $\mathsf{Lo}(n)$. Once the smoothing operation is performed on every decision node in $\psi$, $\psi$ will have the smoothness property.