Recost shortcuts in bidastar: first approach by genadz · Pull Request #2661 · valhalla/valhalla

genadz · 2020-10-20T19:01:57Z

Tasklist

Add tests
Add #fixes with the issue number that this PR addresses
Generally use squash merge to rebase and clean comments before merging
Update the changelog

Requirements / Relations

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

genadz · 2020-10-20T19:09:05Z

@kevinkreiser there are some open questions I wanted to discuss:

Should we skip path in case recosting fails ? or we should fallback to the current logic (right now is fallback).
Should we recost transition costs for recovered shortcuts ? (I mean, we have transition cost between some edge in path and shortcut edge -> should we replace it by transition cost between the edge and first superseded edge that was recovered from shortcut ?)

purew · 2020-11-02T18:54:42Z

Is recosting shortcuts something that could benefit all A-star algorithms? If so, could this be implemented on the base-class?

I think yes, will check

heavy plus for this one

all A-start algorithms inherit from PathAlgorithm interface. as for me, it's too common in order to add recost_shortcut_forward to this interface. instead of that, I will define this function in a separate *.h file (in src/thor folder) that can be used by everyone

genadz · 2020-11-02T19:30:02Z

NOTE: right now shortcut speed equals to speed from the first superseded edge; so, if other superseded edges have different speeds -> after recosting we can get ETA significantly different from the base. this PR #2662 fixes it

purew · 2020-11-02T20:15:47Z

Could you add some gurka tests for this recovering of shortcuts?

kevinkreiser · 2020-11-02T20:25:25Z

@purew we already have tests for recovering shortcuts i dotn think we need more just for that. but we do need them specifically for this. the main point here is that the final path doesnt have shortcuts in it. so it would be enough to make a gurka map that has shortcuts, get a route that takes a shortcut, set the constrained speed on the non shortcut edges to a known value that is substantially different than the shortcut and then check that:

you get back no shortcut edges
your recosting works in that you get speeds/costs that look like the constrained speed you set

kevinkreiser · 2020-11-02T20:26:08Z

@gena with respect to:

Should we recost transition costs for recovered shortcuts ? (I mean, we have transition cost between some edge in path and shortcut edge -> should we replace it by transition cost between the edge and first superseded edge that was recovered from shortcut ?)

No, you dont need to recompute the transition cost for those as the value will be the same.

kevinkreiser · 2020-11-03T02:55:27Z

why make this change? its a bunch of extra allocation and a whole extra loop over the path. what does this give us other than a slightly clearer while loop below?

unless there is a clear reason to do this, i would highly suggest we revert this to using the label index and labelset directly in the while loop as was done before

oh i see in the comment hints at it. you are saying that we have to start at the beginning to get the correct cost? i'm not sure its actually true though. i wonder what kind of penalty this adds. i think we can work around it by looking one label ahead and using that label as the "previous cost" for the recosting of the shortcut to avoid all this allocation

let's suppose we go from the end to the beginning (as before), and we already processed some edges: edge_n, edge_n-1, ...., edge_k and then meet shortcut and recost the edge - it means that costs for all edges from n to k will be invalid anymore (because costs for edges n, n-1, ..., k include shortcut cost that we've just changed) and we must shift all of them by difference we get after recosting.
If we implement this approach directly - it will require approximately n * (number of shortcuts) additional operations (change costs) - doesn't look reasonable. But, I just realized, we can optimize it a little: let's save all cost changes to stack (~ (number of shortcuts) additional memory) and apply these changes once on the second pass - in this case overhead will be num_of_shourctus additional memory (solution implemented now requires n additional memory, so make sense to rewrite). WDYT?

kevinkreiser · 2020-11-03T03:00:05Z

as soon as this fails should we log and return?

On the one hand we already log errors in RecoverShortcut method, but from the other we can treat recovering error as recosting error here and log it.

It might be reasonable not to continue because we already know shortcut cost and there is no need to call recost_forward function in such case.

kevinkreiser · 2020-11-03T03:08:48Z

the last PathId stores boths the cost so far and the transition cost at the beginning of the PathID. so i think you might have the transition cost in the wrong place. i always confuse mysefl on this but thats whta it looks like to me here

hm, didn't get this note. could you run the details ?

alexey-gl · 2020-11-29T22:21:13Z

Hello
While solving my #2692 problem I have tried to use this PR as possible solution.
Unfortunately it has not solved my issue completely.
I noticed when the route has several subsequent shortcuts only the first one was fully restored with original way ids. The rest still have way_id = 0 (i.e. they are still shortcuts). And I have to restored them during postprocessing with graph_reader.RecoverShortcut(...) stuff.
I suppose this PR should solve my issue.
Hope this comment will help with this PR testing.

genadz · 2020-11-30T14:36:58Z

        // Terminate if the cost threshold has been exceeded.
        if (fwd_pred.sortcost() + cost_diff_ > threshold_) {
-          return FormPath(graphreader, options, origin, destination);
+          return FormPath(graphreader, options, origin, destination, forward_time_info, invariant);


not sure if it's fully correct to consider only forward time and ignore reverse time:

on the one hand we adjust times here https://github.com/valhalla/valhalla/blob/master/src/thor/route_action.cc#L409 and here https://github.com/valhalla/valhalla/blob/master/src/thor/route_action.cc#L512 ;

but on the other hand we potentially can miss time restrictions in case we have predefined arrival time.

genadz · 2020-12-07T11:03:08Z

Implemented new approach here #2711 . @kevinkreiser we should compare and choose the best one

genadz · 2020-12-07T11:17:05Z

Hello
While solving my #2692 problem I have tried to use this PR as possible solution.
Unfortunately it has not solved my issue completely.
I noticed when the route has several subsequent shortcuts only the first one was fully restored with original way ids. The rest still have way_id = 0 (i.e. they are still shortcuts). And I have to restored them during postprocessing with graph_reader.RecoverShortcut(...) stuff.
I suppose this PR should solve my issue.
Hope this comment will help with this PR testing.

hm, interesting note about subsequent shortcuts. I added unit test and it works)

kevinkreiser · 2021-03-10T02:08:48Z

@genadz should we close this since we went with the other approach?

genadz marked this pull request as draft October 20, 2020 19:02

genadz force-pushed the recost_shortcuts branch from 5e2fcce to c2e67fe Compare October 20, 2020 19:05

genadz changed the title ~~Recost shortcuts when form final path~~ Recost shortcuts in final path Oct 21, 2020

genadz force-pushed the recost_shortcuts branch from c2e67fe to 6042a6d Compare October 21, 2020 09:44

genadz requested a review from kevinkreiser November 2, 2020 08:50

genadz force-pushed the recost_shortcuts branch from 6042a6d to a09ddc9 Compare November 2, 2020 10:01

purew reviewed Nov 2, 2020

View reviewed changes

genadz marked this pull request as ready for review November 2, 2020 19:25

kevinkreiser reviewed Nov 3, 2020

View reviewed changes

genadz force-pushed the recost_shortcuts branch from a09ddc9 to d3ca6ee Compare November 5, 2020 17:53

genadz requested review from kevinkreiser and purew November 5, 2020 17:54

genadz force-pushed the recost_shortcuts branch 2 times, most recently from af8def2 to 10e6563 Compare November 5, 2020 18:02

kevinkreiser mentioned this pull request Nov 19, 2020

0 values while getting way_id along the route #2692

Open

genadz added 3 commits November 24, 2020 13:11

Use TimeInfo in recost function

48d68cb

Recost shortcuts when form final path in bidi-a*

424f18a

Review fixes: separate out recost function into a header

d7ad2a2

genadz mentioned this pull request Nov 24, 2020

Rework recost function to use TimeInfo #2697

Merged

4 tasks

genadz force-pushed the recost_shortcuts branch 2 times, most recently from ecf25a1 to 80e4375 Compare November 30, 2020 14:14

Add unittest for path recosting in bidi-a*

1a12fa9

genadz added 2 commits November 30, 2020 17:20

Update changelog

0474e05

Use time when recost shortcuts

4879d72

genadz force-pushed the recost_shortcuts branch from 80e4375 to 4879d72 Compare November 30, 2020 14:22

genadz commented Nov 30, 2020

View reviewed changes

genadz marked this pull request as draft December 2, 2020 12:58

genadz changed the title ~~Recost shortcuts in final path~~ Recost shortcuts in bidastar: first approach Dec 7, 2020

kevinkreiser mentioned this pull request Dec 7, 2020

shortcut recovery singleton and cache option #2714

Merged

kevinkreiser and others added 2 commits December 7, 2020 21:45

Merge branch 'master' into recost_shortcuts

84c2fbe

Compilation fix after master got merged

772b157

genadz force-pushed the recost_shortcuts branch from 63f6f75 to 772b157 Compare December 8, 2020 13:01

Fix recost methods

fddabab

genadz closed this Mar 10, 2021

Conversation

genadz commented Oct 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Tasklist

Requirements / Relations

Uh oh!

genadz commented Oct 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

genadz commented Nov 2, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

purew commented Nov 2, 2020

Uh oh!

kevinkreiser commented Nov 2, 2020

Uh oh!

kevinkreiser commented Nov 2, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

genadz Nov 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

genadz Nov 3, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

alexey-gl commented Nov 29, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

genadz commented Dec 7, 2020

Uh oh!

genadz commented Dec 7, 2020

Uh oh!

kevinkreiser commented Mar 10, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

genadz commented Oct 20, 2020 •

edited

Loading

genadz commented Oct 20, 2020 •

edited

Loading

genadz commented Nov 2, 2020 •

edited

Loading

genadz Nov 3, 2020 •

edited

Loading

genadz Nov 3, 2020 •

edited

Loading