-
Notifications
You must be signed in to change notification settings - Fork 697
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Fix NoRoute for waypoints with low reachability edges #2914
Conversation
valhalla/loki/search.h
Outdated
@@ -13,22 +13,27 @@ | |||
namespace valhalla { | |||
namespace loki { | |||
|
|||
struct SearchOptions { | |||
uint32_t max_reachability_ = 100; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
why do we need this and why do we need to store an extra bool on the candidates we find? each location already has the max_reach assigned to it (minimum_reachabilty). cant we just add a member to that class that says:
bool high_reach() const {
return outbound >= min_reach && inbound >= min_reach;
}
I fail to see why its needed to keep this information and really make any of the changes in loki search when the candidate is part of the location which already knows what the max reach could be and the candidate knows what the actual reach was.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
yeah, I also don't like this too much. but, current solutions assumes that we detect big connectivity components. so, if we got location with already set minimum_reachability
value that is actually low, in this case high_reach()
method will return true
even in cases when this edge lies in a small component.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
hm, so, probably for route requests we should override minimum_reachability
with the max_reachability
value from the config
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@kevinkreiser outbound, inbound
values are stored in PathEdge
class but minumun_reachability
is kept in PathLocation
. there are 2 possible solutions I see:
- define
bool high_reach(uint32_t min_inbound_reach, uint32_t min_outbound_reach) const
method inPathEdge
class and usemin_outbound_reach_,min_inbound_reach_
values fromLocation
class to pass to this method; - define
bool high_reach(const PathEdge& path_edge) const
method inPathLocation
class and use it to detect if an edge is high reachable or not
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
yep either of those would be good, that is what i was thinking too 👍
either way we have to make an external method (one of the major draw backs of protobuf) but i think we can do this inside of thor whereever we need this information for edge culling
@kevinkreiser as expected, performance hasn't changed. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I looked through the changes. At first sight I haven't found any bugs but I'll leave 🚢 to be Kevin's responsibility ;)
p.s seeing this code for the first time, so I might miss some details
* there are 2 types of routes: 1) with middle points on oneway deadends; 2) points sutiated in different small connectivity components. We should provide some paths instead of "NoRoute" errors that we have right now.
test_requests/through_routes.txt
Outdated
-j '{"costing":"auto","locations":[{"lat":38.245509,"lon":-85.75095,"type":"break"},{"lat":38.251,"lon":-85.763,"type":"through"},{"lat":38.258075,"lon":-85.744407,"type":"break"}]}' | ||
-j '{"costing":"auto","locations":[{"lat":52.027886,"lon":5.077448,"type":"break"},{"lat":52.030559,"lon":5.078592,"type":"through"},{"lat":52.030178,"lon":5.080847,"type":"through"},{"lat":52.025977,"lon":5.08614,"type":"break"}]}' | ||
-j '{"costing":"auto","locations":[{"lat":39.821226,"lon":-84.317642,"type":"break"},{"lat":39.828069,"lon":-84.314242,"type":"through"},{"lat":39.832658,"lon":-84.318762,"type":"through"},{"lat":39.828843,"lon":-84.323137,"type":"break"}]} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
test routes that fail right now
src/baldr/pathlocation.cc
Outdated
@@ -61,5 +61,9 @@ bool PathLocation::shares_edges(const PathLocation& other) const { | |||
return true; | |||
} | |||
|
|||
bool PathLocation::is_high_reachable(const PathEdge& edge) const { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
nit: should be is_highly_reachable
or has_high_reach
@@ -407,7 +407,7 @@ struct bin_handler_t { | |||
auto opposing_edge_id = reader.GetOpposingEdgeId(candidate.edge_id, other_edge, other_tile); | |||
|
|||
if (other_edge && costing->Allowed(other_edge, other_tile)) { | |||
auto reach = get_reach(opposing_edge_id, other_edge); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
hahaha oops! thanks for removing the shadowing!
test/gurka/test_reachability.cc
Outdated
// Should give the same result as A->1->C | ||
auto result = gurka::do_action(valhalla::Options::route, map, {"A", "D", "C"}, "auto", {}, {}, | ||
nullptr, "break_through"); | ||
gurka::assert::raw::expect_path(result, {"AB", "AB", "AB", "BC"}); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
why are there three AB edges? im sure there is some detail i just cant remember at the moment... i get why there is one from A to the snap point at or near 1 and that then there is another for the next leg from that point to B but i cant figure out where the 3rd one is coming from at the moment. can you jog my memory?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ha, great question!) actually, the first AB
edge is reversed. I think there is a small bug in TimeDepForward
algorithm. I debugged it, there is a combination of conditions in TimeDepForward::SetOrigin
method that led to this:
- looks like we should remove all inbound edges in case of the origin was snapped to the node, but we didn't do ti because of this https://github.com/valhalla/valhalla/blob/master/src/thor/timedep_forward.cc#L432 : origin and destination is on the same edge;
- when we got forward path edge
AB
we found that the destination also on this edge, and added forwardAB
edge to the priority queue with cost equal toA -> 1
, BUT didn't settle this edge because of this comment https://github.com/valhalla/valhalla/blob/master/src/thor/timedep_forward.cc#L530 ; - last step, we have edges
ABr
andABf
in the queue and sortcost forABr
edge is less than sortcost forABf
. So, pop edgeABr
from the queue, start expansion from the nodeA
and found destination edgeABf
. The end)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think, this should be fixed in another PR.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
interesting, we have a bit of code that is supposed to do this if i can remember where it is. it should say somethign like if its node snapped and its an origin no point in using the edge that is snapped to its end node...
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
the purpose is to ignore end node snaps for origins of the route unless that is all we have
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
https://github.com/valhalla/valhalla/blob/master/src/thor/timedep_forward.cc#L432 - we also use this condition that just checks that origin and destination on the same edge. so , probably it's needless
src/thor/route_action.cc
Outdated
auto destination = std::prev(origin); | ||
thor::PathAlgorithm* path_algorithm = | ||
get_path_algorithm(costing, *origin, *destination, api.options()); | ||
thor::PathAlgorithm* path_algorithm = get_path_algorithm(costing, *origin, *destination, options); | ||
path_algorithm->Clear(); | ||
algorithms.push_back(path_algorithm->name()); | ||
LOG_INFO(std::string("algorithm::") + path_algorithm->name()); | ||
|
||
// TODO: delete this and send all cases to the function above |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
so since we deleted this, then can we delete that function i had lying around above and also delete this comment?
} | ||
loc.mutable_filtered_edges()->Clear(); | ||
} | ||
|
||
/** | ||
// removes any edges from the location that aren't connected to it (because of radius) | ||
void remove_edges(const GraphId& edge_id, valhalla::Location& loc, GraphReader& reader) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
delete this function i mean, since you are doing it a different way
valhalla/baldr/pathlocation.h
Outdated
/** | ||
* Check if path edge has high reachability for this location. | ||
* @param edge PathEdge that should be checked | ||
* @return true if the edge is high reachable | ||
*/ | ||
bool is_high_reachable(const PathEdge& edge) const; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
seems this method is actually unused. we instead use the free function inside thor route_action
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
will remove, thanks
src/thor/route_action.cc
Outdated
// reset state and try to route again | ||
route = nullptr; | ||
first_edge = {}; | ||
vias.clear(); | ||
path.clear(); | ||
algorithms.clear(); | ||
trip.mutable_routes()->Clear(); | ||
origin = ++correlated.rbegin(); | ||
continue; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
resets the entire state of all the legs of the route and starts completely over from the beginning doing all the legs over.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
is it proposition for comment ? to make more detailed ?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's just me clarifying my understanding or anyone else's who is following along haha
src/thor/route_action.cc
Outdated
// if routing failed because an intermediate waypoint was snapped to the low reachability road | ||
// (such road lies in a small connectivity component that is not connected to other locations) | ||
// we should leave only high reachability candidates and try to route again | ||
if (allow_retry && is_through_point(*destination) && |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
cant this happen on other locations types than through
though? like even the break
or via
types could fail right?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
for break
and via
types we use all path edges. it means if we failed to find a route it's definitely not a connectivity problem, so it doesn't make sense to remove low reachable edges and retry
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
haha i made the mistake of leaving this comment on the arrive_by which is harder to think about. let me see if i can mentally find a crack in the forward direction (depart_at). i just need to mull it over a bit to see if it handles everything we're worried about sorry for the confusion, just want to really understand the changes to this critical section ;)
src/thor/route_action.cc
Outdated
// (such road lies in a small connectivity component that is not connected to other locations) | ||
// we should leave only high reachability candidates and try to route again | ||
if (allow_retry && is_through_point(*destination) && | ||
!is_high_reachable(*destination, destination->path_edges(0))) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
the reason why 0
works here is only because its a through
which means we've culled all other edges but the matching ones? what about on the first leg of the route where we havent dont any culling yet, why does 0
always work here?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
hm, good question. I though that the first (last) point can't be a through
type
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
youre right it cant!
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
should we handle it somehow ?
src/thor/route_action.cc
Outdated
if (allow_retry && is_through_point(*origin) && | ||
!is_high_reachable(*origin, origin->path_edges(0))) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@kevinkreiser I think such condition
if (allow_retry && origin != correlated.begin() && is_through_point(*origin) && origin->path_edges_size() > 0 &&
!is_highly_reachable(*origin, origin->path_edges(0)))
should handle all cases
* move all logic about removing path edges into one general function; * fixed naming: is_high_reachable -> is_highly_reachable; * made comment about resetting state more detailed (thanks Kevin);
if (allow_retry && origin != correlated.begin() && is_through_point(*origin) && | ||
origin->path_edges_size() > 0 && !is_highly_reachable(*origin, origin->path_edges(0))) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ok so we dont have to solve this in this PR but... it is possible that the router will use a different edge at the end of one leg than the beginning of the next one. so while you were right that we only need to currently care about handling a failure for through locations (because only they widdle down the edges to just the one that was used in the adjacent leg) it is the case that the router could have a situation like i described in my previous comment.
lets go with the simple case: break->break->break
assume that the middle break point has two pairs of edge candidates one inside a small component and one outside. assume also that the first break point is inside the small component. what happens is then the fist leg is in the component and the second leg is outside of it. makign the returned route, invalid. so you are right, it wont fail the route but it will return something unusable to the user. this is a long standing issue and a rare occurance, but i wanted to point it out to you here.
we probably should be removing some of the pairs of candidates even for breaks and vias if they arent directly connected to the last edge in the previous edge. thats i think what i planned to do with that commented out function above but it was so long ago i dont quite remember ))
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
it's very useful comment, thank you! we should rethink this logic and fix in a separate issue. I'll crate after this one gets merged
auto temp_paths = get_path(path_algorithm, *origin, *destination, costing, api.options()); | ||
auto temp_paths = get_path(path_algorithm, *origin, *destination, costing, options); | ||
if (temp_paths.empty()) | ||
return false; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
nit: this line isnt covered because your unit test doesnt use date_time type=2 (arrive_by). you could increase coverage by adding another permutation just in case to make sure that the fix works for arrive_by as well.
// no route found | ||
throw valhalla_exception_t{442}; | ||
} | ||
// resets the entire state of all the legs of the route and starts completely |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
all the coverage checks above are the same thing, if you add an arrive_by route that needs a retry then these will all be resolved
test/gurka/test_reachability.cc
Outdated
@@ -0,0 +1,51 @@ | |||
#include "gurka.h" |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
nit: there is already a test_reach
and a test_route
gurka test, maybe this should just go in one of those?
@kevinkreiser updates tests to check both depart_at and arrive_by attributes. |
Issue
The main idea and unittest described here #2872 . This PR fixes problem with "no route found" for multipoint requests with intermediate points on isolated (unreachable) islands. In case of fail, we remove all low reachable edge candidates for all intermediate waypoints. It forces routing algorithm to use edges from large network that should be the same with a high probability.
Tasklist
Requirements / Relations
Link any requirements here. Other pull requests this PR is based on?