Investigate Turn Function

[MoKob]

Our new turn function is providing very low cost for turns. Measured in seconds, we currently see the following turn cost per angle:

[0,11] 7.4
[12,22] 7.3
[23,28] 7.2
[29,33] 7.1
[34,36] 7.0
[37,39] 6.9
[40,42] 6.8
[43,44] 6.7
[45,46] 6.6
[47,48] 6.5
[49,49] 6.4
[50,51] 6.3
[52,52] 6.2
[53,54] 6.1
[55,55] 6.0
[56,56] 5.9
[57,57] 5.8
[58,58] 5.7
[59,59] 5.6
[60,60] 5.5
[61,61] 5.4
[62,62] 5.3
[63,63] 5.2
[64,64] 5.1
[65,65] 5.0
[66,66] 4.9
[67,67] 4.8
[68,68] 4.7
[69,69] 4.6
[70,70] 4.4
[71,71] 4.3
[72,72] 4.2
[73,73] 4.1
[74,74] 4.0
[75,75] 3.8
[76,76] 3.7
[77,77] 3.6
[78,78] 3.4
[79,79] 3.3
[80,80] 3.2
[81,81] 3.1
[82,82] 3.0
[83,83] 2.8
[84,84] 2.7
[85,85] 2.6
[86,86] 2.5
[87,87] 2.4
[88,88] 2.3
[89,89] 2.2
[90,90] 2.1
[91,91] 2.0
[92,92] 1.9
[93,93] 1.8
[94,94] 1.7
[95,95] 1.6
[96,96] 1.5
[97,97] 1.4
[98,99] 1.3
[100,100] 1.2
[101,102] 1.1
[103,103] 1.0
[104,105] .9
[106,107] .8
[108,109] .7
[110,112] .6
[113,115] .5
[116,118] .4
[119,123] .3
[124,129] .2
[130,140] .1
[141,202] .0
[203,211] .1
[212,216] .2
[217,220] .3
[221,223] .4
[224,226] .5
[227,228] .6
[229,230] .7
[231,232] .8
[233,233] .9
[234,235] 1.0
[236,236] 1.1
[237,237] 1.2
[238,238] 1.3
[239,240] 1.4
[241,241] 1.5
[242,242] 1.6
[243,243] 1.7
[244,244] 1.9
[245,245] 2.0
[246,246] 2.1
[247,247] 2.2
[248,248] 2.3
[249,249] 2.5
[250,250] 2.6
[251,251] 2.7
[252,252] 2.9
[253,253] 3.0
[254,254] 3.1
[255,255] 3.3
[256,256] 3.4
[257,257] 3.6
[258,258] 3.7
[259,259] 3.9
[260,260] 4.0
[261,261] 4.2
[262,262] 4.3
[263,263] 4.4
[264,264] 4.6
[265,265] 4.7
[266,266] 4.8
[267,267] 5.0
[268,268] 5.1
[269,269] 5.2
[270,270] 5.3
[271,271] 5.5
[272,272] 5.6
[273,273] 5.7
[274,274] 5.8
[275,275] 5.9
[276,276] 6.0
[277,278] 6.1
[279,279] 6.2
[280,280] 6.3
[281,281] 6.4
[282,283] 6.5
[284,285] 6.6
[286,287] 6.7
[288,289] 6.8
[290,291] 6.9
[292,294] 7.0
[295,298] 7.1
[299,304] 7.2
[305,313] 7.3
[314,359] 7.4

All timings are in seconds, assuming 180 degree as going straight, 0-179 as right, 181-359 as left turns.

All these values are the result of our new function that we have introduced in #2849.

The resulting ways feature more turns and have a lower (unrealistic) ETA.
We need to investigate here to find better turn cost, again.

One way we could improve for left-turns is potentially considering #2912.

[danpat]

If I copy/paste the turn function and the constants into a small test Lua script, I get:

local turn_penalty = 7.5
local turn_bias = 1.075


function turn_function (angle)
  -- Use a sigmoid function to return a penalty that maxes out at turn_penalty
  -- over the space of 0-180 degrees.  Values here were chosen by fitting
  -- the function to some turn penalty samples from real driving.
  -- multiplying by 10 converts to deci-seconds see issue #1318
  if angle>=0 then
    return 10 * turn_penalty / (1 + 2.718 ^ - ((13 / turn_bias) * angle/180 - 6.5*turn_bias))
  else
    return 10 * turn_penalty / (1 + 2.718 ^  - ((13 * turn_bias) * - angle/180 - 6.5/turn_bias))
  end
end

print( "0 = " .. turn_function(0) / 10)
print( "45 = " .. turn_function(45)  / 10)
print( "90 = " .. turn_function(90)  / 10)
print( "135 = " .. turn_function(135)  / 10)

print( "-45 = " .. turn_function(-45)  / 10)
print( "-90 = " .. turn_function(-90)  / 10)
print( "-135 = " .. turn_function(-135)  / 10)

print( "-180 = " .. turn_function(-180)  / 10)
print( "180 = " .. turn_function(180)  / 10)

The output I get is:

$ lua5.1 test.lua
0 = 0.0069237615516916
45 = 0.1397720699017
90 = 2.1054032922495
135 = 6.6685980398909
-45 = 0.54194187937457
-90 = 5.3945967077505
-135 = 7.4120660522044
-180 = 7.4972962723689
180 = 7.4547765229124

Comparing this to our old turn function, where the values would be:

0 = 0
45 = 0.20833333333333
90 = 0.83333333333333
135 = 1.875
-45 = 0.3
-90 = 1.2
-135 = 2.7
-180 = 4.8
180 = 3.3333333333333

The major finding from my test driving for #2849 were:

• 90 degree turns without traffic control take add about 2-3 seconds, regardless of left/right
• stop-signs add an additional 2-3 seconds to the turn delay
• turns of <90 degrees often incur very little penalty - the turn radius is often large, which means you don't need to slow down very much
• there is a maximum penalty incurred - once you reach minimum turning speed, it takes little extra time to do a sharp right compared to a right-hand u-turn

The new turn function increases the turn cost from where we had it, penalizes shallow turns less, and doesn't penalize very sharp turns as heavily. Overall, this better models actual timings from real driving than what we had.

What's missing here are factors unrelated to the angle - stop signs, traffic crossing, road speeds. You've already noted that we should penalize crossing traffic.

I made a start on extending the data available to the turn function with this PR: #2822. The factors that seem worth including are:

• approach speed
• exit speed
• angle
• traffic lights
• stop sign
• crossing traffic
• estimate of the turn radius

Right now, all we've got is the angle :-(

[willwhite]

Ok is seems like the function is behaving as expected: turn penalties are higher than they were before? Any more next actions or should we close and continue tracking on #2822 ?

[willwhite]

Talking about more improvements to turn functions in #2822.

[rachha]

@danpat, what's the idea behind using the sigmoid function?