Change sharing criterion to avoid artificial detours #3302

genadz · 2021-09-02T15:09:10Z

Changes:

use continuous function to calculate sharing coefficient (instead of piecewise constant function);
change definition of "sharing": it was modified from "part of edges that a candidate shares" to "part of edges that already chosen path shares with alternative";
extend alternatives search.

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
If you made changes to the lua files, update the taginfo too.

Requirements / Relations

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

Before 'sharing' was defined as a part of shared edges of an alternative candidate. Now it's a part of shared edges of already chosen route. It prevents from getting alternatives with artificial detours.

Changed alternative_cost_extend coefficient from 1.1 to 1.2

genadz · 2021-09-02T15:33:31Z

Quantity

ETA < 10m

	master	branch
1st alternative	1454	1463
2nd alternative	918	930

10m < ETA < 30m

	master	branch
1st alternative	511	508
2nd alternative	356	352

30m < ETA < 1h

	master	branch
1st alternative	707	754 (+7%)
2nd alternative	545	602 (+10%)

1h < ETA < 5h

	master	branch
1st alternative	3537	4045 (+14%)
2nd alternative	2360	3201 (+36%)

Quality

Let me share several examples:

with alternatives only in master

before	after

As expected, some alternatives that have unreasonable detours were filtered out.

with alternatives only in branch

before	after

These changes caused by increased kAlternativeCostExtend parameter.

different alternatives were proposed

before	after

Performance

master

5%	10%	50%	90%	95%	99%	100%	
0.0088	0.0126	0.0991	0.3900	0.8046	1.7444	6.8323	
mean: 0.1885

branch

5%	10%	50%	90%	95%	99%	100%	
0.0088	0.0127	0.1081	0.4341	0.8226	1.8168	7.8100	
mean: 0.2057

Average performance drop is about 10%. Taking into account quality/quantity improvements I think it's a good deal.

genadz · 2021-09-02T15:36:30Z

src/thor/alternates.cc

-    return 0.65;
-  }
+  if (distance < 10000.f)
+    return 0.6f;


changed min at_most_shared coefficient from 0.5 to 0.6

genadz · 2021-09-02T15:36:52Z

src/thor/alternates.cc

+  if (distance < 100000.f) {
+    // Uniformly increase 'at_most_shared' value from 0.6 to 0.75 for routes
+    // from 10km to 100km
+    return 0.6f + (kAtMostShared - 0.6f) * (distance - 10000.f) / (100000.f - 10000.f);


replaced piecewise constant function with a continuous one

genadz · 2021-09-02T15:42:07Z

src/thor/alternates.cc

-    if ((shared_length / total_length) > at_most_shared) {
+    // throw this alternate away if any of the chosen paths shares more than at_most_shared with it
+    assert(paths[i].back().path_distance > 0);
+    if ((shared_length / paths[i].back().path_distance) > at_most_shared) {


this is important change. What was before:
"sharing value is a part of shared edges of an alternative candidate with some already chosen route"
now is
"sharing value is a part of shared edges of some already chosen route with an alternative candidate".

It should prevent from getting artificial alternatives with unreasonable detours.

Let's consider a particular example:

A------------------------------------B---------C----------------------------------------D | | | | | | | | E---------F

here ABCD is an optimal route and ABEFCD is an alternative candidate.
Let's assume that len(AB + CD) / len(ABCD) = 0.85 and len(AB + CD) / len(ABEFCD) = 0.75. Current master will allow ABEFCD to be an alternative despite the fact that BEFC detour is obviously unreasonable. This branch will reject this alternative due to the fact that sharing = 0.85 > 0.75 = at_most_shared value.

this was what was originally intended actually... good catch! i should also note though that in another pr we are looking into problems with teh path_distance not being set on the last edge label, which is where the pathinfo gets it. it is my h unch that this is in the case that we find a path using only the forward search tree but i havent proven it yet.

Hm, thanks for the comment, I will check it

@kevinkreiser replaced division with multiplication to avoid possible problems

genadz · 2021-09-02T15:43:37Z

src/thor/bidirectional_astar.cc

@@ -28,7 +28,7 @@ constexpr float kThresholdDelta = 420.0f;
 // an upper bound value cost for alternative routes we're looking for. Due to the fact that
 // we can't estimate route cost that goes through some particular edge very precisely, we
 // can find alternatives with costs greater than the threshold.
-constexpr float kAlternativeCostExtend = 1.1f;
+constexpr float kAlternativeCostExtend = 1.2f;


It doesn't drop performance too much, see "Performance" section in the comment above #3302 (comment)

merkispavel · 2021-09-06T12:27:55Z

I guess this is a sign that valhalla's Gods like your changes

merkispavel

reapprove, looks good

genadz added 4 commits September 2, 2021 16:35

Replace piecewise constant function for sharing with a continuous one

0b86718

Change 'sharing' coefficient calculation

c800b23

Before 'sharing' was defined as a part of shared edges of an alternative candidate. Now it's a part of shared edges of already chosen route. It prevents from getting alternatives with artificial detours.

Extend alternatives search to get more routes

2db88b6

Changed alternative_cost_extend coefficient from 1.1 to 1.2

Updated changelog

8483dba

genadz commented Sep 2, 2021

View reviewed changes

genadz requested a review from kevinkreiser September 2, 2021 16:22

kevinkreiser previously approved these changes Sep 3, 2021

View reviewed changes

genadz added 2 commits September 6, 2021 12:10

Replace division by path_length with multiplication

63d3689

Merge branch 'master' into kgv_sharing

1060748

genadz dismissed kevinkreiser’s stale review via 1060748 September 6, 2021 09:11

genadz requested review from kevinkreiser and merkispavel September 6, 2021 09:12

merkispavel approved these changes Sep 6, 2021

View reviewed changes

genadz merged commit d425e99 into master Sep 6, 2021

genadz deleted the kgv_sharing branch September 6, 2021 12:30

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Change sharing criterion to avoid artificial detours #3302

Change sharing criterion to avoid artificial detours #3302

genadz commented Sep 2, 2021

genadz commented Sep 2, 2021 •

edited

Loading

genadz Sep 2, 2021

genadz Sep 2, 2021 •

edited

Loading

genadz Sep 2, 2021 •

edited

Loading

genadz Sep 3, 2021

kevinkreiser Sep 3, 2021

genadz Sep 3, 2021

genadz Sep 6, 2021

genadz Sep 2, 2021 •

edited

Loading

merkispavel commented Sep 6, 2021

merkispavel left a comment

Change sharing criterion to avoid artificial detours #3302

Change sharing criterion to avoid artificial detours #3302

Conversation

genadz commented Sep 2, 2021

Tasklist

Requirements / Relations

genadz commented Sep 2, 2021 • edited Loading

Quantity

ETA < 10m

10m < ETA < 30m

30m < ETA < 1h

1h < ETA < 5h

Quality

with alternatives only in master

with alternatives only in branch

different alternatives were proposed

Performance

genadz Sep 2, 2021

Choose a reason for hiding this comment

genadz Sep 2, 2021 • edited Loading

Choose a reason for hiding this comment

genadz Sep 2, 2021 • edited Loading

Choose a reason for hiding this comment

genadz Sep 3, 2021

Choose a reason for hiding this comment

kevinkreiser Sep 3, 2021

Choose a reason for hiding this comment

genadz Sep 3, 2021

Choose a reason for hiding this comment

genadz Sep 6, 2021

Choose a reason for hiding this comment

genadz Sep 2, 2021 • edited Loading

Choose a reason for hiding this comment

merkispavel commented Sep 6, 2021

merkispavel left a comment

Choose a reason for hiding this comment

genadz commented Sep 2, 2021 •

edited

Loading

genadz Sep 2, 2021 •

edited

Loading

genadz Sep 2, 2021 •

edited

Loading

genadz Sep 2, 2021 •

edited

Loading