Classes

class bmm.MMParticles(initial_positions)

Class to store trajectories from a map-matching algorithm.

In particular, contains the self.particles object, which is a list of n arrays each with shape = (_, 8)

where _ represents the trajectory length (number of nodes that are either intersection or observation) and columns:

t: seconds, observation time
u: int, edge start node
v: int, edge end node
k: int, edge key
alpha: in [0,1], position along edge
x: float, metres, cartesian x coordinate
y: float, metres, cartesian y coordinate
d: float, metres, distance travelled since previous observation time

As well as some useful properties: * self.n: number of particles * self.m: number of observations * self.observation_times: array of observation times * self.latest_observation_time: time of most recently received observation * self.route_nodes: list of length n, each element contains the series of nodes traversed for that particle

Initiate MMParticles storage of trajectories with some start positions as input.

Parameters:

initial_positions (List[ndarray]) –

list, length = n_samps, each element is an array of length 6 with elements

u: int, edge start node
v: int, edge end node
k: int, edge key
alpha: in [0,1], position along edge
x: float, metres, cartesian x coordinate
y: float, metres, cartesian y coordinate

property latest_observation_time: float: Extracts most recent observation time. :return: time of most recent observation

property m: int: Number of observations received. :return: number of observations received

property observation_times: ndarray: Extracts all observation times. :return: array, shape = (m,)

route_nodes(): Returns n series of nodes describing the routes :return: length n list of arrays, shape (_,)

where _ represents the trajectory length (number of nodes that are either intersection or observation)

class bmm.MapMatchingModel

Class defining the state-space model used for map-matching.

Transition density (assuming constant time interval): \[p(x_t, e_t | x_{t-1}) \propto \gamma(d_t) \exp(-\beta|d^\text{gc}_t - d_t|)\mathbb{1}[d_t < d_\text{max}],\]

where \(d_t\) is the distance between positions \(x_{t-1}\) and \(x_{t}\) along the series of edges \(e_{t-1}\), restricted to the graph/road network. \(d^\text{gc}_t\) is the great circle distance between \(x_{t-1}\) and \(x_{t}\), not restricted to the graph/road network.

The \(\exp(-\beta|d^\text{gc}_t - d_t|)\) term penalises non-direct or windy routes where \(\beta\) is a parameter stored in self.deviation_beta, yet to be defined.

\(d_\text{max}\) is defined by self.d_max function (metres) and self.max_speed parameter (metres per second), defaults to 35.

The \(\gamma(d_t)\) term penalises overly lengthy routes and is yet to be defined.

Observation density: \[p(y_t| x_{t}) = \mathcal{N}(y_t \mid x_t, \sigma_\text{GPS}^2 \mathbb{I}_2),\]

where \(\sigma_\text{GPS}\) is the standard deviation (metres) of the GPS noise stored in self.gps_sd, yet to be defined. Additional optional self.likelihood_d_truncate for truncated Gaussian noise, defaults to inf.

The parameters self.deviation_beta, self.gps_sd and the distance prior parameters defined in self.distance_params and self.distance_params_bounds can be tuned using expectation-maximisation with bmm.offline_em.

For more details see https://arxiv.org/abs/2012.04602.

d_max(time_interval)

Initiates default value of the maximum distance possibly travelled in the time interval. Assumes a maximum possible speed.

Parameters:	time_interval (float) – float seconds time between observations
Returns:	float defaulted d_max
Return type:	float

deviation_prior_evaluate(previous_cart_coord, route_cart_coords, distances)

Evaluate deviation prior/transition density Vectorised to handle multiple evaluations at once :param previous_cart_coord: shape = (2,) or (_, 2) cartesian coordinate(s) at previous observation time :param route_cart_coords: shape = (_, 2), cartesian coordinates - positions along road network :param distances: shape = (_,) route distances between previous_cart_coord(s) and route_cart_coords :return: deviation prior density evaluation(s)

Parameters:	previous_cart_coord (ndarray) – route_cart_coords (ndarray) – distances (ndarray) –
Return type:	ndarray

distance_prior_bound(time_interval)

Extracts bound on the distance component of the prior/transition density :param time_interval: seconds, time between observations :return: bound on distance prior density

Parameters:	time_interval (float) –
Return type:	float

distance_prior_evaluate(distance, time_interval)

Evaluate distance prior/transition density Vectorised to handle multiple evaluations at once

Parameters:	distance (Union[float, ndarray]) – metres array if multiple evaluations at once time_interval (Union[float, ndarray]) – seconds, time between observations
Returns:	distance prior density evaluation(s)
Return type:	Union[float, ndarray]

distance_prior_gradient(distance, time_interval)

Evaluate gradient of distance prior/transition density in distance_params Vectorised to handle multiple evaluations at once

Parameters:	distance (Union[float, ndarray]) – metres array if multiple evaluations at once time_interval (Union[float, ndarray]) – seconds, time between observations
Returns:	distance prior density evaluation(s)
Return type:	Union[float, ndarray]

likelihood_evaluate(route_cart_coords, observation)

Evaluate probability of generating observation from cartesian coords Vectorised to evaluate over many cart_coords for a single observation Isotropic Gaussian with standard dev self.gps_sd :param route_cart_coords: shape = (_, 2), cartesian coordinates - positions along road network :param observation: shape = (2,) observed GPS cartesian coordinate :return: shape = (_,) likelihood evaluations

Parameters:	route_cart_coords (ndarray) – observation (ndarray) –
Return type:	Union[float, ndarray]

pos_distance_prior_bound(time_interval)

Extracts bound on the distance component of the prior/transition density given the distance is > 0 :param time_interval: seconds, time between observations :return: bound on distance prior density

Parameters:	time_interval (float) –
Return type:	float

class bmm.ExponentialMapMatchingModel(zero_dist_prob_neg_exponent=0.133, lambda_speed=0.068, deviation_beta=0.052, gps_sd=5.23)

Class defining the state-space model used for map-matching with exponential prior on distance travelled.

Transition density (assuming constant time interval): \[p(x_t, e_t | x_{t-1}) \propto \gamma(d_t) \exp(-\beta|d^\text{gc}_t - d_t|)\mathbb{1}[d_t < d_\text{max}],\]

where \(d_t\) is the distance between positions \(x_{t-1}\) and \(x_{t}\) along the series of edges \(e_{t-1}\), restricted to the graph/road network. \(d^\text{gc}_t\) is the great circle distance between \(x_{t-1}\) and \(x_{t}\), not restricted to the graph/road network.

The \(\exp(-\beta|d^\text{gc}_t - d_t|)\) term penalises non-direct or windy routes where \(\beta\) is a parameter stored in self.deviation_beta defaults to 0.052.

\(d_\text{max}\) is defined by self.d_max function (metres) and self.max_speed parameter (metres per second), defaults to 35.

The \(\gamma(d_t)\) term: \[\gamma(d_t) = p^0\mathbb{1}[d_t = 0] + (1-p^0) \mathbb{1}[d_t > 0] \lambda \exp(-\lambda d_t/\Delta t),\]

penalises overly lengthy routes, defined as an exponential distribution with probability mass at \(d_t=0\) to account for traffic, junctions etc.

where \(p^0 = \exp(-r^0 \Delta t)\) with \(\Delta t\) being the time interval between observations. The \(r^0\) parameter is stored in self.zero_dist_prob_neg_exponent and defaults to 0.133. Exponential distribution parameter \(\lambda\) is stored in self.lambda_speed and defaults to 0.068.

Observation density: \[p(y_t| x_{t}) = \mathcal{N}(y_t \mid x_t, \sigma_\text{GPS}^2 \mathbb{I}_2),\]

where \(\sigma_\text{GPS}\) is the standard deviation (metres) of the GPS noise stored in self.gps_sd, defaults to 5.23. Additional optional self.likelihood_d_truncate for truncated Gaussian noise, defaults to inf.

The parameters self.deviation_beta, self.gps_sd as well as the distance prior parameters self.zero_dist_prob_neg_exponent and self.lambda_speed can be tuned using expectation-maximisation with bmm.offline_em.