This note accompanies the code available on github.

Krumm [1] has recently introduced the concept of bridgelets. In his work, he aims to use a data-driven approach to interpolate trajectories between the measured locations. The main idea is to compute probabilities for visiting certain regions in between measurements. The regions in question are the cells of a square grid that subdivides the location space. By also discretising time, Krumm arrives at the model where at each time step, the trajectory can stay in the current cell or move to one of its direct neighbours. He uses this model to compute visit probabilities of cells in a grid based on a set of real-life trajectories.

The dynamic program makes computing with bridgelets more efficient, since it avoids constructing the bridgelets explicitly. This makes it possible to use a finer grid and time steps, or to reasonably cover sparser trajectories. A bridgelet is the set of all walks between two given vertices of the grid in $T$ time steps. Krumm enumerates the walks explicitly to count the visits to the cells, which takes time exponential in $T$, making it impractical to use for $T > 12$. Our dynamic programming approach computes all the relevant statistics in $\mathcal{O}(T^3)$ time instead of $\mathcal{O}(5^T)$, making it feasible to compute the relevant statistics easily at least up to $T = 500$. With sufficient parallelisation and optimisation, it is possible to make the approach even faster, as we only need $\mathcal{O}(T)$ time when computing on $\mathcal{O}(T^2)$ computing units in parallel. Furthermore, we show how to use this information to generate random trajectories that follow a certain distribution, in $\mathcal{O}(T)$ time per trajectory of $T$ steps.

We also provide closed-form expressions to compute the number of walks to a specific cell in $T$ steps, and show how to obtain a formula for the visit probabilities. Specifically, the number of walks in a bridgelet from $(0, 0)$ to $(x, y)$ in $T$ steps is $$\lvert W(x, y, T)\rvert = \sum_{i = 0}^{\lfloor k / 2\rfloor} \binom{T}{k - 2i}\binom{T - k + 2i}{i}\binom{T - k + 2i}{x + i},$$ where $k = T - x - y$.

Dynamic Program

Some simple questions stated above can be solved by means of dynamic programming. The basic idea is to count paths that reach a certain cell $(x, y)$ in $T$ steps, so we can count paths reaching this cell and its neighbours in $T + 1$ steps. With some care and exploiting the symmetry of the problem, we can use this simple idea to also compute the visit probabilities for all cells on any possible path from $(0, 0)$ to $(x, y)$.

Counting Paths

The simplest question is the following: given a time limit $T$ and the point $(x, y)$, count the distinct paths in $W(x, y, T)$. By means of dynamic programming, we can even solve a more general question efficiently: given the time limit $T$, count the paths in $W(x, y, t)$ for all possible grid points $(x, y)$ and for all $0 \leq t \leq T$. This can be accomplished by creating a table $P$ on the coordinates $[-T, T] \times [-T, T] \times [0, T]$ and filling it out as follows: $$\begin{aligned} P(0, 0, 0) &= 1\,,\\ P(x, y, 0) &= 0 \quad\text{for all $x \neq 0$ or $y \neq 0$,}\\ P(x, y, t + 1) &= P(x, y, t) + P(x - 1, y, t) + P(x + 1, y, t)\\ &+ P(x, y - 1, t) + P(x, y + 1, t) \quad\text{for all $x$, $y$ and for all $t \geq 0$.}\\\end{aligned}$$

Here and later we assume that out-of-bounds values in the table are $0$. It is easy to see that after filling the entire table, a cell $P(x, y, t)$ for some $(x, y) \in [-T, T]^2$ and $t \in [0, T]$ holds the count of paths in $W(x, y, t)$. Furthermore, for any $(x, y)$ out of range, the value should clearly be $0$, as those points are not reachable in $T$ steps. The dynamic program can clearly be computed in time $\mathcal{O}(T^3)$. We show an example result for $T = 10$ below.

Counting Paths Through a Vertex

Secondly, we can solve the following question: given a time limit $T$ and the point $(x, y)$, count the paths in $W(x, y, T)$ that go through a vertex $(a, b)$. We can compute these counts efficiently for all possible vertices $(a, b)$. We give further details here.

Counting with Obstacles

The approach is quite flexible. In particular, it can be adapted to counting paths on a grid with holes that represent obstacles.

Suppose we have some representation $S$ of a set of obstacles. Depending on the application, it may be best represented as a boundary, or directly as a set of cells; its complexity affects the running time. Then we can formulate the following DP for counting paths in $P(x, y, t)$ for all $(x, y)$ and all $t \leq T$: $$\begin{aligned} P_o(0, 0, 0) &= 1\,,\\ P_o(x, y, 0) &= 0 \quad\text{for all $x \neq 0$ or $y \neq 0$,}\\ P_o(x, y, t + 1) &= 0 \quad\text{for all $(x, y) \in S$,}\\ P_o(x, y, t + 1) &= P_o(x, y, t) + P_o(x - 1, y, t) + P_o(x + 1, y, t)\\ &+ P_o(x, y - 1, t) + P_o(x, y + 1, t) \quad\text{for all $(x, y) \notin S$ and for all $t \geq 0$.}\\\end{aligned}$$ We discuss computing probabilities in the setting with obstacles here.

Generating Random Trajectories

Computing these statistics using dynamic programming makes it easier to also sample realistic trajectories from bridgelets. The easiest way is to generate the trajectory starting from the end point, one segment at a time, by reconstructing the transition probabilities using the counts stored in the DP. The approach takes $\mathcal{O}(T)$ time per trajectory, assuming the DP with path counts for the time limit not smaller than $T$ is precomputed (which can be done in $\mathcal{O}(T^3)$ time). We show some trajectories from $(0, 0)$ to $(40, 20)$ in $T = 400$ steps in Figure 1. These are generated based on the values of $P$, without obstacles. The trajectories appear to exhibit reasonable levels of randomness, with (discretised) wandering behaviour spread throughout the trajectory.

Closed-Form Expressions

We have shown the expression for the path count above; we show further details here (also includes a mathematical derivation for the visit probabilities).