Improvements to forcing loops during graph search

[mjjbell]

Issue

As part of investigating negative route durations discussed in #5855, I've discovered the logic around "forcing loops" during graph searches plays an important role, and requires some improvements.

I'll use this issue to describe the current behaviour and outline the changes needed.

Background

OSRM converts the OSM node-based graph (NBG) into an edge-based graph (EBG) for performing routing searches.

A node in the EBG represents a compressed edge from the NBG.
An edge in the EBG represents a turn from one NBG compressed edge onto another.

OSRM also generates a reverse graph for searching backwards from the target (we'll ignore the algorithm optimization details for now).

The edge weight in the EBG is the cost of traversing the NBG source edge and the accompanying turn cost onto the NBG target.
As an example, a simple one-way road loop would have the following edge-based search graph and edge weights.

Snapping Input Locations

OSRM takes the waypoint input locations and snaps them to a position on the OSM geometry.

The EBG nodes representing OSM edges that the locations were snapped to are set as the source and target of the graph search.

Running the search

To get the correct result when running the search, we have to consider that the EBG edges include the cost of the entire NBG edge geometry, whereas our input location will be snapped onto a position on the edge geometry, and so only performs a partial traversal of the first and last edge.

In the forward graph, we need to negatively offset the cost from the start of the geometry to the source position, as any search path from this EBG node will include the entire cost of the geometry traversal.

Conversely, the reverse graph needs to positively offset the cost from the start of the geometry to the target position, as none of the cost of the EBG geometry represented by the NBG node will be included in any reverse search path.

Making the current example more concrete, lets assign each OSM edge to have edge cost 10 and turn cost 1,
The source is snapped to edge_1 with offset cost of 1, target snapped to edge_3 with offset cost 2.

Running the forward and reverse searches with the initial negative and positive offsets, will lead to the correct route cost being found.

Edge cases

For the most part, this use of source and target offsets works for calculating the correct route cost.

The main edge-case is when the source and target snap to the same edge geometry. If source is "downstream" from the target, we would compute a negative route cost.

Assuming we don't allow negative edge weights (OSRM doesn't), this is easy to handle.
If the sum of forward and backward costs is negative, and we see this at a source or target node, we know we're dealing with this edge-case.

The solution: continue the search in both directions from this node.

Forcing loops

The more complicated edge-case is when dealing with routes with via-waypoints. In cases where we don't allow u-turns, we need to include the route cost up to the current waypoint to correctly identify the optimal route to the subsequent waypoint.

This means that even if the source is downstream of the target, the initial starting cost will most likely be positive, as the cost of the previous section of the route will be larger than the negative offset. Therefore, the negative search cost check is insufficient, we need something that "forces a search" at this node.

The criteria for identifying whether we need to "force a search" is simple enough

• Has to be a waypoint node (so found at the start of a foward/reverse search)
• Must be a waypoint on the edge that meets the downstream criteria (source downstream of target)

And this is what OSRM does. It identifies the nodes that match these critieria as a pre-search step

osrm-backend/src/engine/routing_algorithms/routing_base.cpp

Lines 6 to 18 in 7ebd21f

	bool requiresForwardLoop(const PhantomNode &source, const PhantomNode &target)
	{
	return source.IsValidForwardSource() && target.IsValidForwardTarget() &&
	source.forward_segment_id.id == target.forward_segment_id.id &&
	source.GetForwardWeightPlusOffset() > target.GetForwardWeightPlusOffset();
	}
	bool requiresBackwardLoop(const PhantomNode &source, const PhantomNode &target)
	{
	return source.IsValidReverseSource() && target.IsValidReverseTarget() &&
	source.reverse_segment_id.id == target.reverse_segment_id.id &&
	source.GetReverseWeightPlusOffset() > target.GetReverseWeightPlusOffset();
	}

and forces a search on these nodes during the search phase.

osrm-backend/include/engine/routing_algorithms/routing_base_mld.hpp

Lines 405 to 409 in 7ebd21f

	// MLD uses loops forcing only to prune single node paths in forward and/or
	// backward direction (there is no need to force loops in MLD but in CH)
	if (!force_loop(force_loop_forward_nodes, heapNode) &&
	!force_loop(force_loop_reverse_nodes, heapNode) && (path_weight >= EdgeWeight{0}) &&
	(path_weight < path_upper_bound))

osrm-backend/include/engine/routing_algorithms/routing_base_ch.hpp

Lines 126 to 130 in 7ebd21f

	if (force_loop(force_loop_forward_nodes, heapNode) ||
	force_loop(force_loop_reverse_nodes, heapNode) ||
	// in this case we are looking at a bi-directional way where the source
	// and target phantom are on the same edge based node
	new_weight < EdgeWeight{0})

osrm-backend/include/engine/routing_algorithms/routing_base.hpp

Lines 86 to 92 in 7ebd21f

	inline bool force_loop(const std::vector<NodeID> &force_nodes, const HeapNodeT &heap_node)
	{
	// if loops are forced, they are so at the source
	return !force_nodes.empty() &&
	std::find(force_nodes.begin(), force_nodes.end(), heap_node.node) != force_nodes.end() &&
	heap_node.data.parent == heap_node.node;
	}

(The "force loop" name appears to come from the original solution for the Contraction Hierarchy algorithm, where in addition to continuing the search, you would need to consider loop edges back to the node. The name appears to have transferred to the MLD implementation, event though it has no edge loops.)

This concludes the background understanding. Next I'll outline the issues identified with the current implementation.

[mjjbell]

Sub-issue 1 - Via routes that support u-turns don't need to force loops

As mentioned above, loop forcing is needed for multiple via-waypoint routes, where we need to consider the costs in the previous steps to calculate the optimal path for the subsequent step.

However, for via routes that support u-turns at waypoints, we can treat each sub-route independently and sum them together, which means only the consideration of negative cost paths is needed with regards to the downstream edge criteria.

This means we can remove the calculation of nodes requiring forced loops here.

osrm-backend/include/engine/routing_algorithms/shortest_path_impl.hpp

Lines 67 to 68 in 7ebd21f

	getForwardLoopNodes(candidates),
	getBackwardLoopNodes(candidates),

I believe the loops are calculated currently because of the way this plugin was previously implemented, but is now redundant.

A bit of additional refactoring is required as the cost of the previous steps is being passed in when initializing the forward heap weights. However, this is a constant value for all source nodes, so can be pulled out and added later.

osrm-backend/include/engine/routing_algorithms/shortest_path_impl.hpp

Lines 31 to 43 in 7ebd21f

	if (source.IsValidForwardSource())
	{
	forward_heap.Insert(source.forward_segment_id.id,
	total_weight - source.GetForwardWeightPlusOffset(),
	source.forward_segment_id.id);
	}
	if (source.IsValidReverseSource())
	{
	forward_heap.Insert(source.reverse_segment_id.id,
	total_weight - source.GetReverseWeightPlusOffset(),
	source.reverse_segment_id.id);
	}

[DennisOSRM]

Good insights!

[mjjbell]

Sub-issue 2 - Simplify runtime force loop check

Since adding support for multiple snap candidates at an input location (#5953), we now check against two lists of force loop nodes in the forward and reverse edge directions. This is a hangover from the single candidate implementation that had a boolean for forward and reverse edge directions.

osrm-backend/include/engine/routing_algorithms/routing_base_ch.hpp

Lines 126 to 128 in 7ebd21f

	if (force_loop(force_loop_forward_nodes, heapNode) ||
	force_loop(force_loop_reverse_nodes, heapNode) ||
	// in this case we are looking at a bi-directional way where the source

I also inadvertently introduced a change where we only check the forward search node to see if it's a source. (heap_node.data.parent == heap_node.node).

To complete the "downstream" criteria, we should also be checking that the node is a source in the reverse heap too.

Despite not checking, it still satisfies it anyway. We know it's a reverse heap source node because it's in the list of force loop nodes, and it's not possible to have reached that node from another snapped candidate with a lower cost, because it would at least require the cost of a full traversal of the geometry of that edge, which will be at least as big as any reverse source offset.

Proposed Change

The suggested change is to improve the runtime check to be clearer, so that it doesn't rely on non-obvious properties.

• Combine the force_loop_forward_nodes and force_loop_reverse_nodes into one list. The edge direction does not matter in the search graph.

• Make the runtime condition explicit. A loop is forced only when the source and target are on the same edge, so the check should be that node is a source in both the forward and reverse heaps.

heap_node.data.parent == heap_node.node && reverse_heap_node.data.parent == reverse_heap_node.node

• Rename the force_loop function to forceSearch, move the cheapest condition (parent source check) to be first, to quickly short circuit the conditional

osrm-backend/include/engine/routing_algorithms/routing_base.hpp

Lines 86 to 92 in 7ebd21f

	inline bool force_loop(const std::vector<NodeID> &force_nodes, const HeapNodeT &heap_node)
	{
	// if loops are forced, they are so at the source
	return !force_nodes.empty() &&
	std::find(force_nodes.begin(), force_nodes.end(), heap_node.node) != force_nodes.end() &&
	heap_node.data.parent == heap_node.node;
	}

[mjjbell]

Sub-issue 3 - Truncated weight edge-case

There's an additional edge-case which force loops do not cover. This is what leads to the negative durations discussed in #5855.

It happens when we snap the source and target to distinct locations on the same edge, where the source is downstream of the target. However, the offset costs are truncated to fit the integer size used in the graph search. The offsets end up being equal for source and target.

This means when we go to run the graph search, we find that the route cost is zero. However, when we go to calculate additional result data that depends on snapped coordinate locations (e.g. distance) we find that the results are inexplicably negative.

Proposed change

Update the requiresLoop functions to include this additional edge-case

osrm-backend/src/engine/routing_algorithms/routing_base.cpp

Lines 6 to 18 in 7ebd21f

	bool requiresForwardLoop(const PhantomNode &source, const PhantomNode &target)
	{
	return source.IsValidForwardSource() && target.IsValidForwardTarget() &&
	source.forward_segment_id.id == target.forward_segment_id.id &&
	source.GetForwardWeightPlusOffset() > target.GetForwardWeightPlusOffset();
	}
	bool requiresBackwardLoop(const PhantomNode &source, const PhantomNode &target)
	{
	return source.IsValidReverseSource() && target.IsValidReverseTarget() &&
	source.reverse_segment_id.id == target.reverse_segment_id.id &&
	source.GetReverseWeightPlusOffset() > target.GetReverseWeightPlusOffset();
	}

[mjjbell]

Sub-issue 4 - Extending force loops to table plugin

As discussed, force loops are only required for multiple via routes. For direct routes, a negative weight check is sufficient during the graph search.

The same applies for the table plugin. Until now it could rely on the negative weight check, as all routes it calculates are direct source-target paths.

However, the additional weight truncation issue complicates this. Being non-negative is not enough.

To fix this bug, we would need to check the downstream criteria when we see a search path cost of zero.

For the table plugin, evaluating MxN downstream checks for every source-target pair could be something we want to avoid pre-computing. In which case, we could also evaluate this criteria at runtime, given it would affect a tiny number of search steps (cost is zero, forward and reverse nodes are sources).

Potentially this is something we would want to do for the route plugin too, although the number of waypoint pre-computations will be less significant.

Proposed change

Add truncation weight downstream checks at search runtime for the table plugin.