Implementation Details

Overview

                  Measurements

                    /  |  \
                   |   |   |
                   V   V   V
  +-------------------------------------------------------+
  |                                                       |
  |            [ Candidate Query ]                        |
  |                                                       |
  |               /    |    \                             |
  |  Candidate   |     |     |  Candidate                 | <-- Map Matcher
  |  cluster     V     V     V  cluster                   |
  |                                                       |
  |            [  Map Matching  ] <--- [ Viterbi Search ] |
  |                                \__ [ Routing ]        |
  |              /     |      \                           |
  +-------------|------|-------|--------------------------+
                V      V       V

                 Match  Results

Candidate Query

valhalla/meili/candidate_query.h

Given a position and a radius, this component finds all underlying road segments lying within this radius around the position. For every incoming measurement we need to perform such a query to find a cluster of candidates around it, which will be used as input to the map matching component.

The spatial query algorithm used in Meili is simple and efficient. Before the query, we spatially divide a road network (i.e. a graph tile) into a grid of 500x500 (grid.size) squares. Then we precompute which road segments each square intersects, and add them to the square. The query is simply to retrieve all road segments from the squares that the radius range covers. See [this slide] (http://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/geosearch.pdf) at page 7 for details.

Map Matching

valhalla/meili/map_matching.h

The MapMatching class is the core component that implements the HMM-based map matching algorithm. It takes a sequence of candidate clusters as input, and picks one candidate from each cluster to form the most likely sequence of candidates (Viterbi path). It delegates the actual search task to the Viterbi Search module, but it defines how to quantify the likelihood. Concretely speaking it inherits from the ViterbiSearch class and implements its virtual costing functions namely ViterbiSearch::TransitionCost and ViterbiSearch::EmissionCost.

State

valhalla/meili/map_matching.h

When feeding a cluster of candidates into the component, an unique ID and an identical time will be attached to each candidate. The ID identifies a state, whereas the time tells from which cluster a candidate comes. Internally we name the wrapped candidate as a state.

valhalla/meili/viterbi_search.h

This module focus on finding the most likely sequence (Viterbi path) in a trellis graph in context of HMM model. It provides an uniform interface IViterbiSearch and two implementations: NaiveViterbiSearch implements the naive Viterbi Algorithm and ViterbiSearch implements the lazy Dijkstra-based Viterbi Algorithm. Both implementations are able to find the optimal path. NaiveViterbiSearch is able to work with both maximum and minimum objectives, whereas ViterbiSearch only works with minimum objectives as it's Dijkstra-based.

We derive MapMatching from ViterbiSearch for it has better performance in theory. You can develop your own map matching algorithm to work with other road network sources (e.g. pgRouting) as MapMatching does: inherit from either implementation (depending on your objectives) and implement IViterbiSearch::TransitionCost and IViterbiSearch::EmissionCost.

The details about these algorithms are described here.

Routing

valhalla/meili/routing.h

This module focuses on finding the shortest path (SP) between two candidates in the road network. The path distance is required in the transition cost calculation (MapMatching::TransitionCost). The path will be the inferred path between their respective measurements if both candidates are picked as part of the most likely sequence.

The SP algorithm is based on AStar, and it routes from single origin to multiple destinations. AStar fits here because the destination set is a cluster of candidates around their measurement (provided by the candidate query above). So the algorithm can estimate the heuristic cost by targeting at the measurement's position.

The SP algorithm doesn't construct the paths for you. Instead it gives back the search tree (i.e. LabelSet) directly. Then we store the search tree in the origin state for path construction later.

Turn cost between road segments along the path is aggregated during the path finding. This cost contributes as an independent part of the transition cost (MapMatching::TransitionCost) to penalize paths with turns.

Unlike path algorithms in Thor, the SP algorithm scans nodes instead of edges, so turn restriction is not considered here.

Viterbi Search VS. Routing

It is worth mentioning that they share some similarities but also some differences. Both are finding optimal paths but different objectives (most likely sequence vs. shortest distance path). Both are based on the Dijkstra algorithm (thank you Dijkstra!) but different graphical models (trellis graph vs. road network).

Map Matcher

valhalla/meili/map_matcher.h

A map matcher is a facade component that connects the candidate query component and map matching component, and provides simple interfaces for use. As shown in the overview, you can think of it as a black box that takes measurements as input and gives back match results. In addition, it does some internal filtering work before measurements feeding into the map matching component.

Interpolation

valhalla/meili/map_matcher.h

One thing, which is not shown in the overview, is that not all incoming measurements are sent to the map matching component. If some successive measurements are too spatially close to each other, then only the first measurement will be sent; the rest of measurements will be interpolated into the match route.

For example, assume the numbers below represent a sequence of measurements (in order by numbers) along a straight road, and each space is one meter long. If the interpolation_distance is set to 10 meters, we will only send measurements 1*, 4* and 7* because they are farther apart than 10 meters; measurements 2 and 3 will be interpolated into the route from 1* to 4*; measurement 5 will be interpolated into the route from 4* to 7*, and so on.

1* 2  3                    4*  5                  8 7* 9 10

The first rationale of this design is that for high-density traces it can reduce the number of measurements involved in map matching. Secondly if two successive measurements are too close, the later one is possible to be found at the upstream of the earlier one due to noise error. This error can result in wrong path inference in some modes such as auto, bicycle where U-turns are forbidden. For example, the true location of 8 should be at the downstream (right side) of 7*, but the noise can shift it to upstream (left side). In auto mode, this slight shift can result in either wrong path or no path found from 7* to 8. If we interpolate measurement 8 instead of map matching it, this issue can be avoided.

Match Result

valhalla/meili/match_result.h

Each measurement corresponds to a match result. The match result tells you on which road segment the measurement gets matched or interpolated, the match position, and the distance to the position, etc. The corresponding state ID is attached to the result if the measurement gets matched. Since we have stored route search trees to states, you can find the state with this ID and reconstruct the route with the helpers from valhalla/meili/match_route.h.

Map Matcher Factory

valhalla/meili/map_matcher_factory.h

The map matcher factory can facilitate map matcher creation. Pass it the Valhalla configuration and the travel mode, it reads the parameters and creates a map matcher for this mode. The factory also maintains a graph tile reader instance and a candidate query instance and shares them among all its matchers. Because of the data sharing it is cheap to create a map matcher from a factory. Note that both factory and matcher are not thread-safe.