Core, Path Matching Customizations

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

libraryDependencies ++= Seq(
  "com.here.platform.location" %% "location-core" % "0.21.755"
)

<dependencies>
    <dependency>
        <groupId>com.here.platform.location</groupId>
        <artifactId>location-core_${scala.compat.version}</artifactId>
        <version>0.21.755</version>
    </dependency>
</dependencies>

dependencies {
    compile group: 'com.here.platform.location', name: 'location-core_2.12', version:'0.21.755'
}

Candidate Generator

The candidate generator is the component of the map matcher that expands a location (observation) into the list of candidate locations on the map (candidate states). The map matcher algorithm will in the end select the most likely state for each observation.

To obtain candidate states for an observation, use the CandidateGenerator.

The Location Library provides a 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 quality or number of visible satellites of the GPS signal.

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)

Emission Probability

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

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

The DistanceEmissionProbabilityStrategy implements this heuristic.

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

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 few implementations.

The directDistance is the simplest (and also usually fastest) method and is only suitable for dense traces. This strategy only takes into account whether the routing graph directly connects the two states and is used in the carPathMatcher and understrictedPathMatcher.

type Transition = Seq[Vertex]
val transitionProbabilityStrategy: TransitionProbabilityStrategy[Point, Vertex, Transition] =
  TransitionProbabilityStrategies.directDistance[Point, Vertex, Edge](
    graph,
    length,
    roadAccess,
    new ProjectionDistanceCalculator(SinusoidalProjection))

There are a number of other implementations available 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 (as little as one point every 60 seconds). In some cases, if the observations are too far apart, they could be considered unreachable when computing transition probabilities. This strategy is used by the carPathMatcherWithTransitions and by the unrestrictedPathMatcherWithTransitions with different filters applied. There is a hard limitation of ~30km that is applied to the search when computing transitions.

Path Matcher

In general you will create path matchers following the guide in Create Path Matchers.

To obtain fine-grained control and construct and use a path matcher from the core parts, you can use TransitionProbabilityStrategy and EmissionProbabilityStrategy, as follows:

val pathMatcher = new HMMPathMatcher[Point, Vertex, Transition](
  candidateGenerator,
  emissionProbabilityStrategy,
  transitionProbabilityStrategy
)

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

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