October 26, 2020 • 6 min read

How to Utilize Constraints

In the first episode of this blog post miniseries, we discussed the purpose of constraints and how to go about creating them. In our follow up post, we described how we associate said constraints with graph edges. To wrap up this saga, we will use this post to demonstrate how we utilize and enforce constraints across our stack.

 

At the core of rideOS — serving as the foundation to all of our technology from Ridehail to Delivery — is our Routing Engine. The Routing Engine answers the question: “What is the best way to get from Point A to Point B?” And it is here, in this engine, that we ensure constraints are respected and enforced. 

 

So long as we can trust Routing to provide routes that respect constraints, we can rely on our Optimization API to solve task allocation problems that respect those same constraints. And as long as our Optimization API can solve its problems while respecting constraints, we can trust that the Ridehail and Delivery solutions we present will respect the constraints. It all propagates rather conveniently.

 

The Routing Engine

So, let’s observe this matter from the Routing Engine’s perspective. Down at the Routing Engine, we have a map of the area we are working with in the form of a graph (orange), as well as labels marking which constraint each edge belongs to (blue).

 

 

The orange graph on the left is based on real map locations; the costs are determined by the actual cost of travelling between nodes (whether that is distance or time). The blue labels on the right are the result of three different user-generated constraints, which have been matched to edges of the map graph: “A” happened to match to the three edges in the north, “B” matched to the four edges off of the center spoke node, and “C” matched to the single edge in the south. You might note that not every edge has exactly one label. Nothing prevents an edge from matching to more than one constraint, just as nothing forces an edge to match to any constraint at all.

 

If one were to ask the Routing Engine for the best path from the north west node to the south east node, it would be able to find it simply:

 


We will not get into the specific algorithms that the Routing Engine uses to solve this problem (there are better resources for that). But for graphs this simple it is easy enough to confirm for yourself that the highlighted path is, indeed, the one with the lowest cost.

 

You might find yourself asking: what happened with constraints in this example? The answer is, absolutely nothing. Unless you tell the Routing Engine which constraints you want to enforce, and how you want to use them, they are just decoration. But by allowing users to specify when and how to use constraints for each individual request, we are afforded far more power and flexibility.

 

The higher levels of our stack (Optimization, Ridehail, Delivery, etc.) can intelligently make requests to the Routing Engine with different constraint options. This allows them to treat individual vehicles, entire fleets, and times of day differently from one another. Being able to delineate at different levels leaves us better equipped to handle the particular specifications of our partners.

 

After all, half the power in constraints is in knowing when and how to use them. But now, let’s try to actually make use of them.

 

Avoid Constraints

Perhaps the most direct and obvious use case for employing a constraint is the Avoid constraint, which forbids the Routing Engine from making use of marked edges.

 

For this example, we are making a request to the Routing Engine, specifying that both constraint “A” and constraint “C” are to be avoided at all cost, for a trip from the north west node to the south east node.

 

This is what the graph looks like now from the Routing Engine’s perspective:


 

On the blue label graph on the right, you can see that the “A” and “C” constraint edges have been identified and highlighted, while the “B” constraint edges are ignored as irrelevant. On the orange routing graph, however, the change is far more drastic. Every edge selected on the right has been outright removed from consideration.

 

The Routing Engine applied its solver algorithm to the much smaller graph and returned the highlighted result, which you can quite easily confirm to be one of the lowest cost paths from origin to destination. It is also a different path from what the Routing Engine returned when no constraints were applied. Though it is a longer path than the original, unconstrained route, it correctly avoids the southern edge, as requested.



Soft Constraints

Removing all offending edges from the graph is not the only method of applying an Avoid constraint. Here is a different method:

 

 

Here, “A” and “C” edges are once again selected, but rather than remove them from the orange graph entirely, we drastically increase the cost of those edges.

 

As you can see, the Routing Engine still returns the same route as it did when the edges were removed, and it still avoids touching any of the constrained edges. We refer to the first case, removing the edges, as a Hard constraint. We refer to the second case, updating the costs to be extremely high, as a Soft constraint. Our Routing Engine supports both.

 

You might be wondering why we support both options if they return the same routes, but consider the case where instead of routing from the north west, you were trying to route from the north.

 

 

For the Hard constraint case, the route is literally impossible to achieve. For the Soft constraint case, you are directed onto the constrained road. Both of these situations are legitimate. If the road is illegal or unsafe for a vehicle to drive on, you would use a Hard Constraint to ensure that it never happens, even if it means some routes are impossible.

 

If you would instead vastly prefer to avoid certain roads, but would still do so if required (as an example, it would mean your safety driver would be forced to take over your Autonomous Vehicle for the road segment), then you can use a Soft constraint. The Routing Engine will inform you if it ever is forced to violate them.

 

You might be wondering why we increase the cost of each edge rather than set all of them to an arbitrarily high amount. This is because we want to ensure that even if you are forced to take a constrained edge, we still want the best route among the bad options. Moreover, when we return the result, we need to undo the cost change, because we still need to report accurate ETAs/distances along with the routes.

 

Operational Constraints

The counterpoint to an Avoid Constraint is an Operational Constraint. Rather than inform the Routing Engine to avoid making use of certain edges, an Operational Constraint restricts the Routing Engine to only use the selected edges.

 

Consider the case where we request the Routing Engine to use Constraint “B” as an Operational Constraint:

 

 

As you can see, the edges labeled “B” are discovered, and all unselected edges are removed from the routing graph. This is a Hard Operational Constraint. In the same way, you can have a Soft Operational Constraint:

 

 

Here, the costs are changed drastically, but the edges remain routable.

 

Extensions

In regular use, Operational and Avoid constraints are employed side by side, as are their Soft and Hard variants. The expressiveness of being able to create constraints for any situation and mix and match them as needed gives rideOS the power to solve intricate problems.

 

But this is just the tip of the iceberg. Operational and Avoid are only two different enforcement schemes to make use of constraint creation and evaluation. What if you don’t want to impose an all-or-nothing restriction on an edge, but would rather impose a cost multiplier? What if you want to provide additional information about certain edges to better prepare you to embark on the recommended routes? What if you want certain edges to be penalized by different amounts based on the vehicle embarking on the trip?

 

For all these possibilities, we have expanded the Constraints use case into a full-blown Map Annotations framework, taking the full power of constraint-based routing and the map matching it employs, and unshackling it for even greater flexibility of use. Look forward to future blog posts as we detail the many features and solutions rideOS offers.