In a previous post, Introduction to Constraint Based Routing, we examined the use case for constraint-based routing. This examination left us with a question: how do we know which roadways (or edges) are affected by constraints? To start, we must define “edge.” A graph data structure is composed of edges and nodes. Edges are the links between the nodes of the graph. A simple graph might look like this:
The simplest representation of a map is a graph. In these graphs, nodes represent intersections, and edges represent roadways between intersections, as this allows systems to use graph search algorithms to resolve navigation queries. To implement constraints then, we must know which edges of a graph are covered by the constraint. As explained in the previous post, we have three types of constraints: area constraints, path constraints, and turn constraints. Area constraints are pretty easy to calculate. We simply take an input polygon, use it as an outer boundary, and query our geospatial storage to retrieve all edges within this boundary.
Path and turn constraints, on the other hand, are slightly more difficult. Drawing tiny bounding polygons around specific roads might work in some cases, but would not be a pleasant user experience, and also would not allow users to constrain only a single direction of travel on a road. Ideally, a user could simply draw a line close to the roads they want to constrain. We need to identify which graph edges match most closely to this user-drawn input polyline (list of latitude and longitude coordinates). We can resolve turn constraints using a similar process to path constraints. If we expand an intersection from a single node to include a set of nodes and edges, such that distinct edges connect each roadway meeting at the intersection, turn constraints may be solved as path constraints. We won’t worry about that for this blog post, and we can simplify the matter by using nodes for intersections.
Translating from external geospatial input to the corresponding graph edges is known as Map Matching. Map Matching systems will typically take a polyline and identify the matching edges within a graph representation of a map, such as the following graph.
This allows the system to convert a series of latitude and longitude points into simple and computable graph entities. Map Matching can be used for various purposes, such as determining traversed roads from a GPS trace, interpreting traffic flow on roadways, or finding the closest roads to a hand-drawn route. We know that Map Matching is the problem we need to solve, now we need a solution. Hidden Markov Models provide us with one possible solution.
Hidden Markov Models
To understand Hidden Markov Models, we should start with the concept of Markov Chains. A Markov Chain is a random process in which the probability of being in some state depends only upon the previous state. Each state has a known likelihood to reach any other state in the chain, known as a transition probability. For example, let’s say we have an example road network in which a car may drive from either point A to points B or C, with equal probability. From B, the car may drive to C, but not to A, due to one-way streets. From C, the car may drive to A, but not to B. This can be represented as a graph:
Assuming the drivers are simply cruising around with no set destination, the likelihood of a car driving from one point to another will only be based on the car’s current location. Thus, this chain of car positions is a Markov Chain.
A Markov Chain forms the core of a Hidden Markov Model (HMM). An HMM builds on a Markov Chain by not only specifying the transition probabilities between states, but also considering the chance to see certain observations based on those states. Rather than build the Markov Chain directly, this model probabilistically infers the chain by looking at these observations.
An HMM is useful in our case, since we know a series of desired positions which form our road constraint, but we don’t immediately know which roadways those positions should represent. For example, let’s say that we know roadways A, B, and C are near Positions 1, 2, and 3 respectively. Therefore, we can construct an HMM in which our observations are the hand drawn positions of a polyline. The likelihood that these observed positions correspond to a certain internal state is known as emission probability. We can assign emission probability values based on how close our recorded positions are to each point on the graph. If a position is near a certain point on our graph, we give it a high likelihood, for example: ‘0.90’. If a position is far from a point on our graph, we give it a low likelihood, for example: ‘0.10’. The given example looks like this:
Once we know the likelihoods of observing different positions of a car based on the car’s actual position, we work backwards through a series of position observations to guess the route that the car traversed. This process forms the basis of HMM Map Matching.
If you want to learn more about Hidden Markov Models, this blog post describes the concept in greater detail.
Hidden Markov Models for Map Matching
Now that we understand HMMs, and how they can represent a vehicle’s travels, we can utilize an HMM to solve our Map Matching problem. In our Map Matching Markov Model, the input series of positions represents our observed positions. A series of map graph edges represents the hidden states. Since an HMM allows us to predict the hidden states given observations, we can convert polylines into graph edges. The transition probability is determined by the difference in distance of the navigable path between two points set on edges in our graph and the expected distance between these points. The expected distance is either given as an input or calculated to be the distance as the crow flies between the two points. After all, it wouldn’t make much sense to match edges that are very far apart when our coordinates are close together.
To revisit our map graph example, let’s say that we’re trying to match from point A to point B. If we measure the distance between the points, we find it to be approximately 100 meters. We then issue a routing request between the two points, and find that possible routes either include the 100 meter orange route, or the 180 meter green route. Based on this result, we set a higher probability to transition to the orange edges, and a lower probability to transition to the green edges.
The emission probability is determined by the distance from the observation to the closest points on nearby road segments. This ensures that we are matching to roads that are close to our input points, as opposed to points on the opposite side of the map. Again considering our map graph, point P snaps to the orange road with a 10 meter distance, and the green road with a 20 meter distance. Point Q snaps to the orange road with a 40 meter distance, and the green road with a 10 meter distance. Therefore, for the orange road we set a high emission probability to P and a low probability to Q. For the green road, we set a high probability to Q and a midrange probability to P.
By plugging our input points into the Viterbi Algorithm, a well known process for solving HMMs, we can identify the closest matching series of roads for a given list of coordinates. To visualize this process, we can expand the Markov Chain with each measurement time as its own layer of nodes. For each layer, we get a set of candidate roadways, and compute the transition and emission probabilities as described above.
The following diagram displays an expanded HMM. Each time layer contains possible road candidates, the links between road candidates, and car position measurements at that point in time. A predicted path is shown in orange, with closest positions for each road candidate linked by a blue line.
Map Matching Examples
Since matching takes place on an actual map, the result is best illustrated by example.
Let’s say a user wants their vehicles to operate on a certain loop of roadway. They could input a series of positions using the rideOS Playground:
A fully drawn constraint following this loop will appear like this:
The input points here are marked with red circles. This will produce a constraint following this roadway loop on the backend:
Given this fairly simple example, we can observe that the map matcher was able to identify a series of road segments matching the user drawn input.
What if we have a more complicated example which crosses over other roads and contains roads with curves?
This constraint path follows curved roadways, passes through a tunnel under a number of 2-dimensionally intersecting roadways, and is formed from longer, less precisely drawn points. This input gives us this output constraint:
Here, you can see that, even though this input has some additional ambiguity, the map matcher is able to produce the desired matching result!
How are These Constraints Used?
Once these constraints are saved in the database, our routing service can apply them to fleet plans, dispatch decisions, and vehicles’ paths. This is known as constraint enforcement, and will be covered in the next constraints blog post.