Skip to content
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.

Sign up for GitHub

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

Jump to bottom

U-turns being forbidden at barriers, leading to no-routes when inputs force conditions that would require a u-turn #2875

Merged
merged 1 commit into from
Feb 24, 2021
Merged

U-turns being forbidden at barriers, leading to no-routes when inputs force conditions that would require a u-turn #2875

merged 1 commit into from
Feb 24, 2021

Conversation

danpat
Copy link
Member

@danpat danpat commented Feb 18, 2021 •
edited
Loading

Issue

Not 100% sure what the issue here is yet, but this test case demonstrates the problem. When you use type=break_through at waypoints, and a u-turn is required at a dead-end, a NoRoute result is the outcome.

I'm not sure whether it's the break_through that's the root cause, or the access=no on the necessary u-turn location in this test, but the test shows the problem.

cc @gknisely

Tasklist

  • Add tests
  • Add #fixes with the issue number that this PR addresses
  • Update the docs with any new request parameters or changes to behavior described
  • Update the changelog

Requirements / Relations

Link any requirements here. Other pull requests this PR is based on?

@kevinkreiser
Copy link
Member

yeah break_through means you cant turn around at the snap point. it means you at least have to go to the end of the edge, ie continue through the snap point. its basically a way of saying "break" (i want you to make a new leg here) but "go through" (i want you to keep going in the same direction, no immediate uturn at the snap point). but yeah if that leads you into a black hole then i could see why that'd be a problem 😄

@kevinkreiser
Copy link
Member

kevinkreiser commented Feb 18, 2021 •
edited
Loading

@danpat im a bit confused though. i think recently we (@danpaz) changed this behavior to allow a uturn even where the node has no access: https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L142

🤔

@danpaz
Copy link
Collaborator

danpaz commented Feb 18, 2021

The change in bidirectional at https://github.com/valhalla/valhalla/pull/2705/files#r534545579 was meant to address cases like these, by allowing a uturn at nodes where access is disallowed. Essentially we now enqueue the reverse edge, where before we were bailing and returning a NoRoute. Now it seems we're back to the old behavior.

It seems like there was a regression around that code, or around the special case handling uturns just below it.

@mandeepsandhu
Copy link
Contributor

When routing with multiple waypoints, do we have to start at the same location the previous leg ended on? Is it not acceptable to, say snap to a different edge if its not possible to continue on the edge the previous leg ended on?

@kevinkreiser
Copy link
Member

so currently the code will look at the edge the last leg ended on and remove all candidates but that one when its a "*_through" location. for other types i forget if it does weed them out or not. but if it didnt the route would be pretty wild in that there would be a teleport between snap locations

@danpat
Copy link
Member Author

danpat commented Feb 18, 2021

To be clear - the test isn't expecting a u-turn at the middle waypoint (1) here - it's expecting to continue through the waypoint, then perform the u-turn at the barrier=fence,access=node at the end of the street. For some reason, it's not doing that.

I'm wondering whether use of heading and heading_tolerance could be used to force the same situation without the use of a break_through waypoint. I will try, and push up an additional test if so.

@kevinkreiser
Copy link
Member

@danpat yep that is what i understood from your description. i think the changes @danpaz and i linked should account for that but im not sure why it still fails!

@danpat
Copy link
Member Author

danpat commented Feb 18, 2021

Just pushed an additional test using heading - confirms it's not the type=break_through, but the u-turn at the barrier.

@danpat danpat changed the title access=no on nodes prevents u-turns, leading to no routes when type=break_through used at waypoints requiring a u-turn to escape U-turns being forbidden at barriers, leading to no-routes when inputs force conditions that would require a u-turn Feb 18, 2021
@danpat danpat force-pushed the danpat_break_through_uturns branch from cbbf719 to 210699e Compare February 23, 2021 01:21
@danpat danpat force-pushed the danpat_break_through_uturns branch from 8c99fd3 to dd076bd Compare February 23, 2021 01:49
kevinkreiser
kevinkreiser previously approved these changes Feb 23, 2021
View reviewed changes
danpaz
danpaz previously approved these changes Feb 23, 2021
View reviewed changes
Copy link
Collaborator

@danpaz danpaz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @danpat !

@danpat danpat dismissed stale reviews from danpaz and kevinkreiser via 6cd6e95 February 24, 2021 00:47
@danpat danpat force-pushed the danpat_break_through_uturns branch from 6cd6e95 to 37a529d Compare February 24, 2021 00:49
@danpat
When encountering a no-access node, we need to mark the predecessor e…
c1110e5 
…dge as a deadend so

other admissibility logic will behave consistently.

Graph preparation will not mark these edges as deadends, because deadendiness is access
mode specific (e.g. foot may be allowed).  Many *::Allowed() methods check for u-turns
and depend on the "edgelabel.deadend()" flag to detect u-turns at the end of a dead-end
street.
@danpat danpat force-pushed the danpat_break_through_uturns branch from 9cc0cec to c1110e5 Compare February 24, 2021 01:18
@danpat danpat requested a review from kevinkreiser February 24, 2021 01:18
@danpat
Copy link
Member Author

danpat commented Feb 24, 2021

Did some cleanup on the test - @mandeepsandhu @danpaz @kevinkreiser anyone mind 👍 on this again?

@danpat danpat mentioned this pull request Feb 24, 2021
Open
kevinkreiser
kevinkreiser approved these changes Feb 24, 2021
View reviewed changes
Copy link
Member

@kevinkreiser kevinkreiser left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

thanks again!

@danpat danpat merged commit e8cbc7a into master Feb 24, 2021
@nilsnolde nilsnolde deleted the danpat_break_through_uturns branch February 24, 2024 15:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@mandeepsandhu mandeepsandhu mandeepsandhu left review comments

@kevinkreiser kevinkreiser kevinkreiser approved these changes

@danpaz danpaz danpaz left review comments

Assignees

@danpat danpat

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@danpat @kevinkreiser @danpaz @mandeepsandhu