static penalty for way?

[bjtaylor1]

Hi, (sorry if this has been covered before, but couldn't find anything on searching.)

Is there any way in my .lua profile I can add a static time-based penalty, e.g. 20 seconds/60 seconds, to a particular way (not a node)? If so how would I do that in the way_function?

Cheers.

[TheMarex]

You can use way:id() to get the OSM id of the way and set result.duration to whatever you like.

[emiltin]

or if the penalty depends on OMS tags, simple read the tags and set the penalty as you like.

[bjtaylor1]

ok cheers, so does result.duration get added on to speed * distance, or does it override it?

[emiltin]

duration is only for ferries and similar. for normal ways, you only need to set result.speed.

[bjtaylor1]

I know. But what I actually want to do is impose a penalty on certain ways in addition to the cost calculated from their distance multiplied by speed. Will result.duration do this? Basically my end goal is to prefer to avoid extremely steep hills.

I am ok with identifying which ways have a steep hill, however I've drawn the line at going to the level of working out how much of each way is steep, or what its actual elevation gain is - that's too complicated - I'm just saying either it has a significant section of steepness, or not - yes or no. So, say, a mile-long way that has a steep hill shouldn't impose any more penalty i.e. proportional to its length, than a short (100yard) way that has a steep hill - because it might only be the first 100yard of the mile that is steep. Make sense?

[danpat]

@bjtaylor1 You could just apply a multiplier to the speed, say 1.25, and do it after the regular speed has already been calculated.

However, you might be interested in this work, by @lbud :

https://www.mapbox.com/blog/third-party-data-in-osrm/

The code is living here, with the intention to (eventually) bring it into the mainline OSRM backend:

https://github.com/Project-OSRM/osrm-backend/tree/feature/raster_sources

[bjtaylor1]

no, thanks anyway but that looks far too involved. I don't want to modify the speed because then the penalty would be proportional to the length of the way which like i said I don't want. I'm fairly definite that all I want to do is to apply a static penalty in the lua. What bit of code in C++ calculates the overall 'cost for comparison' of the result of the way_function?

[danpat]

At the end, all routing calculations are made based on travel time. We convert length x speed to travel time here:

https://github.com/Project-OSRM/osrm-backend/blob/master/extractor/extraction_containers.cpp#L261-L279

The only two variables that affect the weight at this stage are the length of the segment, and the speed value linked to it, there is no place to add an arbitrary penalty. Note that this is done for each segment of a way (i.e. line between two nodes), not just the whole way.

After all this is done, the network graph is compressed (multiple edges between intersections are added together), and then "edge expanded", where edges now represent turns between ways. At this point, you could add an arbitrary time penalty to all turns to/from your way in question. The only problem is that the way_id is not available any more at this point in processing. This code is here, where it calls the turn_function:

https://github.com/Project-OSRM/osrm-backend/blob/develop/contractor/edge_based_graph_factory.cpp#L489-L506

However, this function is only given the turn angle.

In a nutshell, your options are:

• add a multiplier to the speed field for ways that you want slowed down (like, 0.9)
• look at adding an arbitrary penalty flag on the EdgeData structure, and adding it to the time calculation linked above, note that we probably won't take that upstream
• look into existing work adjusting ways arbitrarily, like @lbud's work linked above

[danpat]

One thing you should also realize: in OSM, ways can extend across multiple intersections. We break this down into unique edges for routing (i.e. we only store 1 edge between each intersection), but the way_function is only called once per way, so there's no place to be fine-grained about how your static penalty would be applied. You will want to consider which of these edges you need your penalty applied to, if it's not being applied to the whole way.

@lbud 's work lets you apply arbitrary penalties to individual road segments, which is exactly what you need for biasing some sections of a way, but not others.

[bjtaylor1]

Hmm, interesting. So how do you identify a "segment"? I identify ways in postgis by the osm_id field, how would it work with edges?

[danpat]

A segment is just the line between two <node> values on a way. It has no unique ID in OSM, but when we load them into the OSRM backend, we give each one, and we store the lat/lon of the start/end points. It's not a stable identifier, you probably shouldn't use it to look anything up, it can change from run-to-run. Segments are assigned the speed value from the way they belong to, and in vanilla OSRM, that's how they stay. @lbud's work uses the lat/lon start/end points to do a lookup on an elevation raster layer to assign a speed penalty for slope to each segment in each direction. Once each of these segments has been adjusted, they're merged to form the final graph which is just a single edge between each intersection.

[danpat]

The issue of sub-portions of ways getting stable identifiers is extensively discussed here https://github.com/opentraffic/architecture/issues/1

It's a thorny problem.

[bjtaylor1]

That's interesting, but just the start and end points are not good enough to determine whether it's a steep hill or not - consider a U shape which would yield a false positive. Ok for total height gain, but I'm not interested in that I'm interested in max gradient. You need the full shape. I think the occurrence of a segment being unfairly "tarred with the same brush" as another segment on the same way, is probably rare enough to live with.

[danpat]

Right. A U-shape is made up of a collection of segments, OSM does not support curves, they're implemented as a series of short, straight lines. The raster-lookup branch examines each of these short straight pieces. It relies on the segmentation of the way being granular enough to capture the curves of the road.

We've been experimenting with it for bicycle routing. You can do things like penalize the uphills, but not the flats or downs. This means that U-shapes on hills do what you would expect: help cyclists avoid the climbs, but basically ignores descents. In pseudocode:

if gradient > 3:
    speed = speed * 0.75
else
    # do nothing, speed remains untouched
endif

Also note that the weighting needs to be done in both directions, because the penalties could be different depending on which way you go. Again, @lbud 's work does this.

[perliedman]

Related, I have had success adding penalties for steep climbs without actually modifying OSRM. I have described how I did it here: http://www.liedman.net/2015/04/13/add-elevation-data-to-osrm/

Supporting this directly in OSRM will likely be more powerful and possibly efficient, but I'm pretty happy with my results in the meantime.

[bjtaylor1]

Ok that might work. I'll have a look into it. What elevation data does it use, or is it my job to plug in my own? I'm currently using ordnance survey terrain 50 contour data and some c++ code that counts the number of times a segment crosses a contour. Not sure if spot heights would be better or worse.

[bjtaylor1]

Interestingly however I want to avoid very steep descents as well!

[emiltin]

some ways in osm are modelled using long segments, which mean the segment-based processing would miss up/downhills; the start and end points might be at the same elevation even though there's a lof of hills in between.

[perliedman]

@bjtaylor1 I use HGT files, they are automatically downloaded, unless you provide them. It probably wouldn't be too much work modifying osm-slope to calculate slope using contour lines instead, if you prefer it.

@emiltin I guess you could detect if a way's nodes are too far apart and add interpolated virtual nodes to sample elevation from, right?

[emiltin]

yes that would be possible. i'm not sure if the work by @lbud is doing something like that to handle long segments?

[emiltin]

if you're only need to handle particular steep ascents/descents, and are working with a limited geographical area (where you can add missing tags), you could rely on the 'incline' tag, and simply use that to incur a penalty. http://wiki.openstreetmap.org/wiki/Key:incline

[bjtaylor1]

incline tag: not nearly prevalent enough for me I'm afraid. https://www.openstreetmap.org/way/24895610 should certainly have it - turns out devon is a great area to test the changes it has on routing functionality as it has loads of steep hills! edit: no, I'm not working on a limited area. I want it to work anywhere in the UK really.

[bjtaylor1]

some ways in osm are modelled using long segments, which mean the segment-based processing would miss up/downhills; the start and end points might be at the same elevation even though there's a lof of hills in between.

that wouldn't matter as long as the shape is preserved, because I have some code that finds all the contour crosses on a particular segment - this very problem is why I like this method over spot heights. However the lack of ids means I would have to find an extensibility point but that might be possible.

[bjtaylor1]

Right, ok - so in @lbud 's branch there is this code.

luabind::call_function<void>(
            segment_state, "segment_function",
            boost::cref((*edge_iterator).source_coordinate),
            boost::cref(*node_iterator),
            boost::cref(distance),
            boost::ref((*edge_iterator).weight_data));

        const double weight = [distance](const InternalExtractorEdge::WeightData& data) {
            switch (data.type)
            {
                case InternalExtractorEdge::WeightType::EDGE_DURATION:
                case InternalExtractorEdge::WeightType::WAY_DURATION:
                    return data.duration * 10.;
                    break;
                case InternalExtractorEdge::WeightType::SPEED:
                    return (distance * 10.) / (data.speed / 3.6);
                    break;
                case InternalExtractorEdge::WeightType::INVALID:
                    osrm::exception("invalid weight type");
            }
            return -1.0;
        }(edge_iterator->weight_data);

Now what I actually want to do is for my "segment_function" to be some of my own C++ code, not a lua function. And I want to apply a static penalty.

now I presume "boost::cref((_edge_iterator).source_coordinate)" is the start lat long and "boost::cref(_node_iterator)" is the end lat long, my question really is what would I have to do to " boost::ref((*edge_iterator).weight_data))" to apply a static penalty?

Also what would be the easiest way of getting my own .cpp sources to link in, by 'make'? I get how makefiles work but don't really understand how 'configure' and autogenerated makefiles work.

Cheers

[danpat]

In this code, distance is in metres, data.speed is in km/h. The weight value here is measured in deciseconds (1/10th of a second, we do so we can store some reasonable precision in an integer field), hence the * 10 in the calculations. The weight is the actual thing that's stored and used for routing calculations.

Basically, to add a static penalty, add some value to the weight field.

We're using cmake to generate the project makefiles. You'll need to add something to /CMakeLists.txt to get your code included in the build. Some folders are globbed, so you can possibly just drop files in those, but you'll need to take a look in CMakeLists.txt to figure out which, I can't remember off the top of my head.

[bjtaylor1]

Hmm. Just been looking at this recently, and what I've found is that for the gradient-based analysis I want to do, edges are in fact probably too short. In other words, a single edge probably won't return a statistically significant enough sample of contour crosses. It'll either have one, or none - and the calculation won't be accurate.

So I'm possibly focusing more on moving my extensibility point to the contractor. I gather, please correct me if I'm wrong, that this combines groups of edges that are equivalent to a single topological element, and strips the geometry at the same time. What I am now wondering - is it possible to examine the geometry for the grouping before it's stripped, and add weight there?

[danpat]

If you have the whole geometry, how are you going to get better results? You'll probably want to break it down....and look at each segment.

The phase of joining all the segments between an intersection into a single edge is called "compression", see graph_compressor.hpp. This happens in osrm-extract.

The "contractor" implements an algorithm called Contraction Heirachies. Basically, it pre-calculates the shortest paths between many points in the graph, inserts new edges as shortcuts (noting the original route), and prunes provably non-shortest-path links. This is why OSRM is so fast: the graph being searched at the end has very few hops between most sources/destinations.

For what you want to do, the segment function is definitely the place to do it. After that is complete, all geography information is discarded from the graph: osrm-prepare is only working on a pre-weighted graph, it knows nothing about coordinates.

What you'll find is that if you're on flat terrain, you're right, many of your segments won't cross a contour line. But the average between the start and end of your road section will come out the same.

[bjtaylor1]

Ok, sorry, so yes it's compression I'm interested in, not contraction. Excellent diagrams, explains it instantly!

What you'll find is that if you're on flat terrain, you're right, many of your segments won't cross a contour line. But the average between the start and end of your road section will come out the same.

Yes, so the "road section" needs to be as many segments as possible so it averages out. Remember I don't know exact spot heights, only to the nearest 10 metres. So as an example: if a 1km long "road section" crosses 10 contours (10m each) I know it's 10% overall. This is useful for comparing to my threshold of, say, 14%, or 9%.

But if it's made up of 100 10 metre long segments (such as looks typical), then each one will probably either cross 1, or zero, contours. (Probably won't cross 2 in 10 metres unless it literally is a skateboard ramp.) So each segment will be either 0%, or 50%, which is useless information.

[danpat]

They will turn out equivalent. 1 segment at 50% merged with 99 at 0% will turn out the same as 100 segments at 10% each. Given that a geometry is going to simply be a collection of segments, I'm not sure how you see getting more detail out of the full geometry.....

[bjtaylor1]

1 segment at 50% merged with 99 at 0% will turn out the same as 100 segments at 10% each

It will IF and only if I know that those 99 are next to that 1, on the same stretch of road, and I can evaluate them as one contiguous block. So it's no good looking at the 50% and saying, ah no, that's too steep - add a penalty there, because really, the road is only 10% as a whole which is less than my threshold of, say 14%, and I don't want to be adding any penalty at all. It's gradient I'm interested in - not total climbing. In fact I quite like climbing, just as long as it's not steep. I'm happy to trundle up 5-10% stuff all day, it's when you have to keep braking on the descents that it gets annoying and feels like you've wasted your energy getting up it in the first place. Remember also this isn't about choosing the quickest route, so much as the most pleasant.

[danpat]

It will IF and only if I know that those 99 are next to that 1, on the same stretch of road.

The diagram is a little bit simplistic, the geometry compression occurs after the node-based-graph is constructed. So, yes, you will know that those 100 segments belong to a single compressed "edge" and they will be smoothed out to achieve an average gradient over the whole road section.

The downside is that if you have a mostly flat straight road, with a 19% "hump" in the middle on just one of many segments, the gradient will still be averaged, unless you come up with a non-linear penalty based on gradient. You would need to split the way in OSM, and prevent geometry compression there (by either changing the name, or looking at the work in my traffic_data branch to give that section a unique traffic ID) in order to achieve non-averaged weighting along the section.

[bjtaylor1]

the gradient will still be averaged

It won't be if I know the geometry, because my code works out all the crosses encountered on a particular line or line-curve. It not only works out how many contour cross are encountered on a line, but where on that line they are too. So I can detect if they're bunched up or spread out.

[danpat]

I'd be interested in seeing how your code works. If it's not decomposing a LINE geometry into segments, how is it working? OSM only supports segment-based lines, there are no curves or other function-based geometries available. Everything is collections of little straight lines.

However, if you really want to continue down this path, this is where you'd need to add a new Lua callback function:

https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/contractor/processing_chain.cpp#L452-L457

You can look at this:

https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/data_structures/compressed_edge_container.cpp#L197-L220

for an example on how to iterate over all the compressed geometry get all their segments. It will be up to you to recombine those into the kind of geometry you want, and then add the appropriate Lua function to update the overall compressed edge weight before the edge-based-graph is constructed.

[bjtaylor1]

I'd be interested in seeing how your code works. If it's not decomposing a LINE geometry into segments, how is it working? OSM only supports segment-based lines, there are no curves or other function-based geometries available. Everything is collections of little straight lines.

Hmm, it sort of is decomposing it into segments, but its own - not OSRMs. Firstly, this code is not LUA, it's C++, that I'd already written to calculate climbing on my routing website gpxeditor. It uses data the 'OS Terrain 50 GB' dataset from ordance survey which contains the geometry and height of all the contours in Great Britain. So they're just lines, basically. What I then do is take an input line (which for the website is a track the user has drawn, or uploaded) and work out which contours it's crossed. The total climbing of that track is approximated by half the number of contour crosses, multiplied by the height of each one, plus the difference in start height and finish height. The advantages and disadvantages over sampling spot-heights, and origin, of this method of calculating climbing, is probably slightly off topic but can point to if interested. However, it was fairly trivial once the method of working out contour crosses worked, to adapt it to calculate maximum and minimum gradients.

So basically this code calculates the maximum gradient of any line, as long as it's in the UK - it doesn't matter whether it came from OSRM, or was drawn by a user, or dreamt up off the top of your head. The code's here, if you're interested: https://github.com/bjtaylor1/osrm-backend/tree/mine I've just dumped all the cpp files for the existing project into extractor. But basically, extractor/crossfinder.cpp is the only real relevant algorithm. The only thing is, the number of crosses has to be fairly significant. You'll see on line 107-109 I've taken the top 5, and declined to return a result for any line with less than 5 crosses. I may tweak this, I don't know.

Whether this is the right way to go or not I don't know. I've already got something working using PostGIS, but it only distinguishes between whole ways, which as has been pointed out might span a junction. I might go with this, but the holy grail is to get it to operate on as much a geometry as possible, but only the bit between junctions!

[bjtaylor1]

Just a query on this:

You can look at this: https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/data_structures/compressed_edge_container.cpp#L197-L220 for an example on how to iterate over all the compressed geometry get all their segments. It will be up to you to recombine those into the kind of geometry you want, and then add the appropriate Lua function to update the overall compressed edge weight before the edge-based-graph is constructed

In this code, it's got m_compressed_edges which is an std::vector<EdgeBucket>. But an EdgeBucket is just a std::vector<CompressedNode> , and a CompressedNode is just a std::pair<NodeId, EdgeWeight>. So how can I get the geometry from that, or has it already been binned off by then? Can I instead get it from some other data structure available at that point?

[bjtaylor1]

Also, can I just ask - how sure are you that

The phase of joining all the segments between an intersection into a single edge [which] is called "compression", see graph_compressor.hpp...happens in osrm-extract.

It seems to be called by Prepare::BuildEdgeExpandedGraph on: https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/contractor/processing_chain.cpp#L473 which is called by Prepare::run on https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/contractor/processing_chain.cpp#L85 which seems to be called by: https://github.com/Project-OSRM/osrm-backend/blob/feature/raster_sources/prepare.cpp#L96

but prepare.cpp makes osrm-prepare does it not, not osrm-extract ?

[danpat]

Stale.