turn penalties for cars, to avoid sharp turns

[emiltin]

as a follow op to #859, shouldn't the car profile use turn penalties, to avoid very sharp turns?

the bike profile squares the angle (angle*angle), which works well:

turn_penalty = 60
turn_bias      = 1.4

function turn_function (angle)
    -- compute turn penalty as angle^2, with a left/right bias
    k = turn_penalty/(90.0*90.0)
    if angle>=0 then
        return angle*angle*k/turn_bias
    else
        return angle*angle*k*turn_bias
    end
end

the bias should probably be set to 1, so that it works equally well for countries with left/right side driving.

[DennisOSRM]

The code can be shortened to:

turn_penalty = 60
turn_bias = 1.4

function turn_function (angle)
    -- compute turn penalty as angle^2, with a left/right bias
    k = turn_penalty/(90.0*90.0)
    if angle>=0 then
        return angle*angle*k/turn_bias
    end
    return angle*angle*k*turn_bias
end

While its tempting to add a simple turn penalty function, I'd like to look at a radial plot of the penalty values (depending on angle) first.

[emiltin]

do you mean that this a simple turn function?

[emiltin]

here's a polar plot of theta^2 http://fooplot.com/plot/2fn94dci58

[emiltin]

and here's a plot with a left/right bias of 1.4 http://fooplot.com/plot/76s3iqjvzk

[emiltin]

and for comparison, a plot of using just theta, rather that theta^2 http://fooplot.com/plot/msk7g4gpq2

[DennisOSRM]

Prepared two plots of my own:

Please note: It plots the full range from 0..360, so one half is technically superfluous, and it needs to be shifted by 180 degrees, but it gives a good idea. I like the curvature of the penalty function.

To put the thing in, we need to figure out when to apply left-hand or right-hand bias or leave the bias out at all, i.e. turns are equally bad. What's your take on this?

[emiltin]

if the service is to work equally well in all countries, i think we should leave out bias for now.
to really support it, we need to know what country a specific road is in, ie. what i suggested in #333.

[emiltin]

i originally decided on theta^2 based on looking at the resulting bike routes. plain theta didn't result in enough penalties for sharp edges. theta^2 produces routes with less sharp turns, and as such routes that are more natural and easier to follow/remember. the trade-off is that routes will sometimes be marginally longer. however i think overall it results in much better routes.

real-world test with car routes might be a good idea. using a higher exponent than 2, like theta^3 ,might even be preferably, since turning in a car is harder than on a bike.

[DennisOSRM]

I am experimenting on a simplified version of the turn penalty function:

function turn_function (angle)
    local k = turn_penalty/(90.0*90.0)
    return angle*angle*k/turn_bias
end

For the time being it may make sense to stick to something simple as this and see this needs further tweaking in the future.

[emiltin]

well, if we don't want bias, we can use

function turn_function (angle)
    local k = turn_penalty/(90.0*90.0)
    return angle*angle*k
end

[emiltin]

one other thing to note is that since impedance and travel time is not separate yet, a turn penalty will affect the estimated travel time. (hopefully making it more realistic)

[DennisOSRM]

Yeah, good point. It should indeed make it more realistic.

[danpat]

These were added to the car profile with in b3822d5 after some comparison of real-world routing behavior against OSRM with/without these penalties. They definitely help decrease zig-zag routing in grid-like city regions.