Core, Path Matching Customizations

This section describes the interfaces provided by the core module to construct path matchers from its components.

libraryDependencies ++= Seq(
  "" %% "location-core" % "0.21.298"
dependencies {
    compile group: '', name: 'location-core_2.11', version:'0.21.298'

Candidate Generator

The CandidateGenerator is used for getting candidate states for an observation.

The Location Library provides an implementation of CandidateGenerator that uses a proximity search, the ProximitySearchCandidateGenerator.

To construct a ProximitySearchCandidateGenerator, you need to provide a proximity search as well as a function that, for each observation, determines the search radius to use. Most of the time, your code will provide a constant radius but you may want your code to provide different radii depending on the observations. For example, you could use a smaller or larger search radius depending on the density of the road network.

The example below demonstrates how to use the factory method CandidateGenerators.fromProximitySearch to create a ProximitySearchCandidateGenerator from a proximity search and a constant radius.

// Use 40 meters as the search radius for every observation.
val FixedSearchRadius = 40.0

val candidateGenerator =
  CandidateGenerators.fromProximitySearch(proximitySearch, FixedSearchRadius)

Note that you can implement a custom CandidateGenerator, for example to make your path matcher filter out candidates not accessible by car.

Emission Probability

For assigning emission probabilities (initial probabilities) to candidate states, the path matcher uses an EmissionProbabilityStrategy.

One method to calculate emission probabilities is using the distance between the candidate and observation: The further the vertex is from the observation, the less probable it is.

DistanceEmissionProbabilityStrategy implements this heuristic.

val emissionProbabilityStrategy =
  new DistanceEmissionProbabilityStrategy[Point, Vertex](
    distanceForUnknown = FixedSearchRadius,
    // Defines how the probability decreases with distance
    // By default, a Gaussian distribution

You can also use the factory method usingDistance of the EmissionProbabilityStrategies to create a DistanceEmissionProbabilityStrategy.

In order to have other information than the distance, for example the heading, affect the emission probabilities, you can use your own logic here.

Transition Probability

TransitionProbabilityStrategy computes the transition probability from one state to another.

There are various ways of calculating transition probabilities using the routing graph. The Location Library provides a simplistic implementation, the SimpleConnectivityTransitionProbabilityStrategy. This strategy only takes into account whether the routing graph directly connects the two states.

type Transition = NoTransition
val transitionProbabilityStrategy: TransitionProbabilityStrategy[Point, Vertex, Transition] =
  new SimpleConnectivityTransitionProbabilityStrategy(
    Graphs.from(optimizedMap, cacheManager)

The SimpleConnectivityTransitionProbabilityStrategy has many limitations:

  • Only considers direct connectivity and, for this reason, does not work well with sparse observation data.
  • Does not consider any properties that may affect transition probabilities, such as, for example, whether the road is accessible by cars or the turn angle of the transition.

There are a number of other implementations provided via factory methods in TransitionProbabilityStrategies. For example, distanceWithTransitions creates a DistanceTransitionProbabilityStrategy, which calculates routes between states to compute transition probabilities. This makes it well suited to handle sparse data. However, if the observations are not sufficiently close enough, they could be considered unreachable when computing transition probabilities.

Path Matcher

Using TransitionProbabilityStrategy and EmissionProbabilityStrategy, you can construct and use the path matcher as follows:

val pathMatcher = new HMMPathMatcher[Point, Vertex, Transition](

val matchedPath: MatchedPath[Vertex, Transition] = pathMatcher.matchPath(trip)

// Each element in matchedPath corresponds to an input point in trip.
for ((observation, candidateState) <- {
  println(s"$observation was matched to $candidateState")

results matching ""

    No results matching ""