Add new function route_between() to calculate routes between two known locations

[ethanplunkett]

Given two points in space and time, for example a tag location and later encounter of that tag, a new function, route_between() would generate synthetic routes that connect them based on the probabilities in the BirdFlow model. It could be called iteratively to generate routes among a larger set of recapture locations (route_among() ?). Only one public facing function is needed for both purposes.

From @dsheldon (slack):

The idea is pretty simple: treat the model as an HMM with hard observations that X1=x1 and XT=xt, then do standard HMM inference. The specific algorithm for sampling is called forward-filtering-backward-sampling, and Raphael used it in his recent paper.

From a graphical model perspective, another way to think about it is as an undirected graphical model. We start with the factors p(x2 | x1) p(x3 | x2) … p(X_{T} | X_{T-1}). This is a directed model so it is normalized (sums to one over all settings of x1, …, xT).
Add two “hard” factors which are delta functions at the observed values of x1 and xT. The model is no longer normalized/directed but it’s still a chain model when treated as an undirected graphical model, so we can still compute all the needed normalized distributions via message passing aka the forward-backward algorithm.

Another way to see it is this: using standard Markov chain computations we can compute p(xt | x1) for any t. To sample from the trajectory given x1 and xT, the first thing we would need to do is to sample from
p(x_{T-1} | x1, x_T)
= p(x_{T-1}, x_T | x_1)/p(x_T | x_1)
= p(x_{T-1} | x_1) p(x_T | x_{T-1}) / p(x_T | x_1)
All quantities in the final expression are easy to compute (and are exactly what would be computed in forward-filtering-backward-sampling).

@dsheldon walks through the implementation in the attached PDF.
BirdFlow Forward Filtering Backward Sampling.pdf

@Rafnuss provided a link to his implementation:
https://github.com/Rafnuss/GeoPressureR/blob/v3/R/graph_product.R#L17