Dealing with change - OSRM Version 5

Video thumbnail (Frame 0) Video thumbnail (Frame 1250) Video thumbnail (Frame 3172) Video thumbnail (Frame 3949) Video thumbnail (Frame 9945) Video thumbnail (Frame 11317) Video thumbnail (Frame 13214) Video thumbnail (Frame 13947) Video thumbnail (Frame 15646) Video thumbnail (Frame 16509) Video thumbnail (Frame 17533) Video thumbnail (Frame 18781) Video thumbnail (Frame 19339) Video thumbnail (Frame 19924) Video thumbnail (Frame 21298) Video thumbnail (Frame 23371) Video thumbnail (Frame 24192) Video thumbnail (Frame 24990) Video thumbnail (Frame 27937) Video thumbnail (Frame 28543) Video thumbnail (Frame 31799) Video thumbnail (Frame 38743) Video thumbnail (Frame 41643)
Video in TIB AV-Portal: Dealing with change - OSRM Version 5

Formal Metadata

Dealing with change - OSRM Version 5
Title of Series
Part Number
Number of Parts
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Release Date

Content Metadata

Subject Area
The Open Source Routing Machine (OSRM) is a routing engine, providing blazing fast route-finding on global data sets like OpenStreetMap. With Version 5 of OSRM we tackled two challenges: providing a world-class navigation experience for car drivers and making OSRM easier to work with for developers. To deliver great navigation, we made route duration estimates more realistic, by allowing developers to provide custom speed and turn duration data. We also dramatically shortened pre-processing times and improved turn-by-turn guidance. To deliver a great experience to developers we modernized the code base and improved the build and test systems. We also refactored the HTTP API to support the new features and removed historical short-comings. In this talk we will introduce the subject of routing in general and then explain the new features of OSRM Version 5 in detail. We will highlight the trade-offs we faced and the reasoning behind our decisions.
Keywords Mapbox

Related Material

Satellite Building Open source Mapping Block (periodic table) Interactive television Cartesian coordinate system Special unitary group Value-added network Computer animation Website Cuboid Router (computing) Computing platform
Point (geometry) Medical imaging Open source Lecture/Conference Personal digital assistant Artistic rendering Address space
Structural load Computer network Database Emulation Inflection point 4 (number) Computer animation Software Sieve of Eratosthenes Process (computing) Gamma function Task (computing) Routing
Computer file Transformation (genetics) Multiplication sign Design by contract Inclined plane Mereology Perspective (visual) Number Preprocessor Latent heat User profile Average Befehlsprozessor Hierarchy Cuboid Process (computing) Routing Area Algorithm Information Mapping Inheritance (object-oriented programming) Moment (mathematics) Keyboard shortcut Computer network Coma Berenices Instance (computer science) System call Process (computing) Befehlsprozessor Computer animation Software Personal digital assistant
Metropolitan area network Dependent and independent variables Server (computing) Game controller Information Tesselation Client (computing) Mereology Distance Cartesian coordinate system Medical imaging Computer animation Vector space Interrupt <Informatik> Video game Aerodynamics Figurate number Resultant Computer worm
Dependent and independent variables Mobile app Building Metre Block (periodic table) Virtualization Control flow Mereology Computer animation Software 4 (number) Personal digital assistant Right angle Software testing Right angle 5 (number) Surjective function
Dependent and independent variables Metre Open source Multiplication sign Decision theory Direction (geometry) Device driver Client (computing) Web browser Cartesian coordinate system 4 (number) Right angle Office suite Data structure Right angle Surjective function
Metre Multiplication sign Right angle Client (computing) Nichtlineares Gleichungssystem Control flow Right angle Arm Surjective function Exception handling
Point (geometry) Building Metre Information Multiplication sign Sheaf (mathematics) Online help Frustration Control flow Computer font Type theory Type theory Computer animation Right angle
Revision control Raw image format Theory of relativity Computer animation Personal digital assistant 3 (number) Right angle Client (computing) Control flow Disk read-and-write head
Goodness of fit Ferry Corsten Logic gate
Metropolitan area network Dependent and independent variables Information Open source Multiplication sign Decision theory Constructor (object-oriented programming) Moment (mathematics) Counting Client (computing) Mereology Computer animation Different (Kate Ryan album) Interpreter (computing) Summierbarkeit Library (computing)
Metre Server (computing) Information State of matter Multiplication sign Planning Line (geometry) Client (computing) Word Computer animation Personal digital assistant Statement (computer science) Speech synthesis Right angle Aerodynamics Summierbarkeit Routing
Dataflow Freeware Computer file Structural load Interior (topology) Multiplication sign File format 1 (number) Maxima and minima Event horizon Aerodynamics Process (computing) Mathematical optimization Data type Window Area Dataflow Information File format Software developer Computer file Überlastkontrolle Incidence algebra Limit (category theory) Type theory Computer animation 4 (number) Universe (mathematics) Cycle (graph theory) 5 (number) Freeware Window
Point (geometry) MUD Open source Observational study State of matter Multiplication sign Design by contract Branch (computer science) Student's t-test Mereology 2 (number) Mathematics Cache (computing) Profil (magazine) Term (mathematics) Aerodynamics Process (computing) Office suite Traffic reporting Default (computer science) Graph (mathematics) Mereology Überlastkontrolle Line (geometry) Instance (computer science) Category of being Process (computing) Computer animation Software Query language Speech synthesis Right angle Geometry
Computer virus Implementation Multiplication sign Direction (geometry) Set (mathematics) Design by contract Client (computing) Mereology Rule of inference Goodness of fit Root Natural number Profil (magazine) Hierarchy Energy level Physical system Dependent and independent variables Algorithm Graph (mathematics) Constraint (mathematics) Moment (mathematics) Coma Berenices Instance (computer science) Line (geometry) Limit (category theory) Process (computing) Computer animation Repository (publishing) Personal digital assistant Query language Calculation Video game Speech synthesis Right angle Reading (process)
Point (geometry) Server (computing) Mapping Modal logic Design by contract Real-time operating system Hierarchy Ontology Vector space Query language Energy level Cuboid Selectivity (electronic) Aerodynamics Process (computing) Matching (graph theory) Feedback Constructor (object-oriented programming) Coma Berenices Cartesian coordinate system Process (computing) Computer animation Software Personal digital assistant Video game Figurate number Cuboid Window
Computer animation
but my name is Yolanda hands
and talk about always around
open-source router machine in the 2 previous talks we're already mentioned quite well so I think you
also all really tuned into routing so can dive into it I from before and from a company called box we are platform of building blocks that you applications we do maps and geocoding interactions and satellite imagery all of these things you need to build your own applications and websites of we are mostly built on open data and we tried to use open data where we can try to open datasets and make them available to the public on an
example here is open addresses which is 1 of the alliances that we try to build around having coding data available for
public and we also builds heavily on open source of for example we support Memoranda of we have a client-side rendering Victor tell rendering engine and knuckles generator that flat is and talk about later today and we have them running machine always right but so always around is the shortest path routing engine very similar to the driving images heard about you can set 2 points and get around between them so you have an example I started where I live and I go around Europe the 1 thing you should notice here right away is it's freedom that always room was filled with performance at the heart it's it's really important that you get the right immediately this only shows you have 1 start point and you have 1 endpoint always around can handle label points in between but today only focus on this case so yeah performance is really important if you want to writing
so I if you wanna use
always around to achieve this performance you cannot just take the road network and it but you have to do some work before so very different to PG routing where you've loaded data in the database but then nothing happens and you wrote basically the road network right away we have to do some processing the 4th hour around loads always and data in so it's
filled with always and mind but if you have other role gradually to load them in there as well you just have to could bring them into always and schema so it can be an XML file PDF file you have to write a transformation itself those processing a of there is the step where we basically take those ended up and we filter it and then we we use an algorithm called contraction hierarchies to filter out some of the parts of the network but also create shortcuts so that we don't have to look at the whole network when we do writing requests so for example if you wanna go from Bonn to Berlin were not gonna look at all the roads in between but there will the shortcuts that we can use to not having to look at the whole Rosenberg this achieves like super fast great time body the preprocessing takes a long time and hot working usually have the whole always and planets so we I take this whole planet file that always and creates and we do processing on that so we're taking the creates large instances from 82 to their like really be it's kind of some of the biggest and this is you can buy they're like really expensive as well I think there's 2 bucks for our but they are for to use and after here the random which is quite and think it takes 9 hours for car to process takes 13 hours for byte takes 18 hours for walk of yeah 1 thing you notice here we cannot only do call-routing we can also do other kinds of routing actually you set up so these are the people President Wilson of defined for us are important you there's other people who do different kinds of writing you can track routing you can always just what riding as and there have been no initially so far because light curve information is not really there in OpenStreetMap we'll maps which is wheelchair accessible to all those who have tried to change that we can also use that we're running way better but yeah you can customize user profiles the way you want for your specific use case cases we have these 3 use cases at the moment that we support so but keep in mind processing takes a long time but we do this because 1 of the really pretty fast so this pull these numbers of yesterday this is the average processing time for hours on a map box but always reminiscences for call routing on the planets and this like some spikes there because sometimes people have like the most people Powell doesn't really expensive 25 waypoint various and these take like several hundred milliseconds but usually the to foreign currency we get in 10 ms 20 ms but it is really fast reminders on there are reforms large instances so these have 120 2 gigabytes of RAM currently for always implies we need 7 2 gigabytes of RAM which is quite annoying user just kind of took over the the is that this 60 61 gigabytes of RAM for the lower instance size so we had to like double or inside the cost and everyone was really set for you don't have to do this on the planet but there's like basically proportional less area means less RAM but you will still get the same speed if you have enough CPU available so routing really fast I know this like the status quo but when we were a year ago and you're we set out to OK
what's the next thing you know around that we wanna achieve it thus fast routing it works quite well and we set out to improve the inclination experience so I want to do is always around 1 to make it possible for was ready to work in a car but unlike kind of pounding on the on the car all time but this is again this will work for quite actually doing mostly by uh by writing in of mostly using this as the vision for by but you can also use it for the navigation all of these things are in their cars just like the case that is the most interesting 1 from a business perspective for us In codification there's 2 things 0 yeah this is how much of the this is like basically had the goal and this but what
we want to achieve this we want to give the clients full control over how relevant results are shown in the figure on the client 40 user so also generates a used payload with all the information interrupt response that you need to basically get this this experience out of the next 1 ways all the like part that comes from another part of the stack of the on vector tiles and the rhetoric ice that's like another part of of the important thing is you like distancing of his name there is like distances to the next intersection all these things need to be in the running response the client then can put this together and we don't care who declined is in a way that this can be your applications can be your mobile and this can be in a car this can run in your life on your bike whatever view devices we want to be able to support as long as it can do request to a server but it needs to be connected whoever is going to ask about offline support afterward so going get it and of so yeah there are 2 things we need to figure out for car 1st thing is we prove guidance and
the 2nd thing is we have to add an image features which you already heard a lot about so guidance the 1st thing 1 thing that we set out to do is we figured out all thinking
about is actually really hard so we started building the
bucketfuls for basically doing virtual test right so of we're doing test runs ourselves as well so networks internally we have in the case that I worked with
was a responses that can so that that you can run on the phone of parts of that we try to make available at as a case so you can use them as well in Europe but will likely never release and an end user facing out just because that's not our business went out of business of end-user apps were in the business of building building blocks for
applications so we will this tool runs in the browser does tool actually is open source so it's called directions simulator so you can run it yourself if you're always surrounded since they will work with I'm and it's basically drives the rather that you get back from always around please around you have to think about them an array of steps so every time the user has every time the driver has to make a decision like turn that were given this strength office right every time there is an entry in this array that says here's instruction that the user should get again we bring the responsibility of how this instruction is interpreted to to clients the
client should decide what I want to have this as a Poisson structure or I need to add a steering wheel to flesh or I need that the person's smart watched right or whatever decision isn't like how old the instruction is delivered to to users
is on the client side we want to give you the tools to make it a possible on the right so here you see kind of a the current step that we're in Equation except it's coming so we just which you can see here like a
time it's as of end of road have here so we're coming to the end of instructional this is the end of the road we have to go to right there is modified right then it switches to to the next step and there is like
a bunch more information and there is a section information information and so on I think at some point in the various school and against the and see it again is like a type that says you should continue now should not take not is another instructions has internal fonts when we set out with the with building those we
realize that we don't have enough expression as in the current types that we have these steps instructions so on the left is kind of the the status for all on the right of things we added and then the latest always remember so 1 of the most important things is motorways of what the other 1 where we basically uh didn't have good handling for getting on a lot about getting off at we always have continued and that really doesn't help you because you don't wanna continue without about when you go off and and we had to work going broderies and roundabouts for a long time to make this nice anyone is searching for a lot of frustration try roundabouts and writing the this is an example I said that tonight i in his or great
the all the old case was this is getting off the ramp
in all the bonds and and
just says continue here which of
course is like a really bad but in a
new version it says that take around on the right and actually
also implemented destination sense now so the client like this kind those not positive relations as correctly
but it should have said take the exit 2 words good on the right never example roundabouts already talked about that were not counting exits so back in the days we did and around about at the gates of on fan-in elite where now we're doing and that
1 of the parts and and take a 2nd and so on finally so can
count these the kind of the sad hard part of the annoying part about everything that is
guidance is that you have to tinker all the time is like there a devil in the detail there's all the small things that where is also potentially not of like objectively good opinion but there's different opinions for everyone what we try at the moment is to say we don't actually know how the user should interpreters and how to plan to handle this so we have a responsibility to Clients and that we can rebuild internally libraries that try to pass this information some of this is open source already in some some of it is that we try to figure out what's the right way is there it's hard but we don't want to make these decisions we wanna give them to the clients last of dynasties is we combine constructions and so on the left side
you can see that there's 2 left instructions that the and then in 15 meters trade left again whereas actually just around about this is unit cell right conceded now says making you try of what is the last thing main main information so in always and you can tag line information by saying that you turn tax and then as a value you say it should be left through all right for you turn and now you have applied to separate lanes and this information can then be made into these lies the I on the client this can also be used for voice instructions such as they take the 1st plane on the left that possibility OK next thing that speech but we want to be able to give a realistic case how long will it take to get up to solution if there is a better route we want to show you that it will give you a better so if there is a traffic jam or if there's always rush hour on as 1 segment you should be able to wrap around it of 1 thing we always try to build a skeptic about tools and 1 thing we build this is maybe this like
joke NGO that eventually everything becomes a time server and like half a year ago was really server and now serves book titles and and you can see a statement that says will profile with a speed of 55 kilometers per hour so this is the thing this is kind of the old state with non-dynamic speeds up you assign 1 value to a speech segment that history segment but there's no like local knowledge around the but yeah whole words as desirable Maxfield's already attacked in always and if
it's not text then we need to just the fine weather and for example the big street outside of the conference center is tagged as primary and also then we say well every primary school should have 65 kilometers per hour we actually inner city years so that won't work like you know is and this is tagged as next week 15 which is called but we won't have information like rush hour and there are traffic congestions the how we get this speech in so we can load
external CSV files that are in the format of the from node to node and then the speed of the cycle so we define segments through nodes there's 3 types are the this means that you can you can work with of it is for that the 0 1 is posted speed limits but that really doesn't like me much because that's not how people the 1st one's free flow what happens is there's no congestion on the street if you can just go as fast as as possible as you want and hopefully if you all law-abiding citizens that this will be the posted speed limit but but the idea of universal roads where you can not hit the speed limit because they're so I need In light of these areas also this streets that are just always congested like thinking about the bigger metropolis metropolitan areas of the world but even at nite there's like traffic jams so there's is never like a real do you have draft speed limit but if you want to go more fine-grained than you can do because the free flow speed yet the speed in a certain type of so-called surrogate markers in a typical week what is the speed for just 15 minute window of 5 a window or whatever you think your window should be of the last 1 is the really so what is speed right now if there's an incident but it is a sports event that is where I think when we think about speeds then we mostly think about time that's also the 1 that is the hardest the 1 that seems for us to have the most value optimization even start buckets because rush hours tend to be fairly predictable when so again this feature of the development on the left
you can see of that the default this be defined by a profile on the right you can see that speed is now coming from 1 of our speech sources and on it's actually 24 kilometers per hour and 55 because there's a congestion on the street for the properties that we built we have 1 that's constantly queries our
own internal instances of also and looks like what's the ETA right now so this is going from the networks in the school office to the airport and the blue line that flat lined is no traffic information the orange line is what with traffic information and you can kind we will see a rational going on in the morning and then it stops when rushes over and when I took this picture yesterday evening the rush hour doesn't start again for going and when another tool that we considered a career out we also save geometries operands and you can see how change so there is 1 on instances could especially 2 branches of going to the airport from our office and depending on the time of the year that is a different branch 1 study of the students and also we have to make processing pasta we always said is that it takes 8 hours the like processes car and we can only update on processing so bad that and so what we do is the 1st thing is we have to catch and we catch major parts processing and only by the speed at the very last point and that that's and that's where we apply the speech and the 2nd thing is work with contract less of the graphs but there is a trade-off between the the processing that is the query time and we found that 1 point 8 and from working pretty well maybe concept is also OK the last thing is small directly there is such a state of that which he got the term times to 10 minutes long doing all the North America which is good enough for us this was 3 hours before so that 8 hours before planet it's 3 hours for North America it's 10 minutes if you do all the caching between and do less work done right because times increased from 20 milliseconds to around 20 seconds which for in-car navigation with 2 red points is holy OK OK yes please remember
in In addition and bring their own speech for that I have 1
problem that of slot this summer I'm pulling a trailer behind my course I have a speed restriction on highways that I can't go faster than 80 km now are even if it's mind to 110 we thought about the problem yeah so what you what you want is life even more than and speeds up the way how I would the government advice to solve the problem is that of a known always instances with a profile it says never go higher than this feature which is possible right now but which is told crap because it's way too expensive to do for every case that we can currently not care well for these cases where user defined constraints at query time writing is better the have your fought about updating the average speed and not always based dataset from you speech because you obviously have way more resources to collect and update disputes and always some speech at the moment I'm not good yet where for about it and talking with those and community about mechanical and it's related to its own thing we would like to do that on the other hand we also are not confident enough yet another data so that's the whole is something that we would like to do their thing that could happen before his we open up this data sets of before they actually applied to listen and users can apply to themselves but we have not this is like the talking and not books talking and from Marcato which is formally known as got to and 1 thing what we have done this you can't 6 is pointing out that this paper and 1 thing what we have done is optimized debates is was there and so it works also in mobile so you don't need to like 100 geeks but just copy and like there's some megabytes and it works across Europe but also like 2 1 milliseconds or something so subsets that's true of so I don't ask about offline working sets we haven't already but I wanted to ask about SUSY got navigation as this rule to calculation is just 1 part of the job you also need to follow the GPS and see what is the actual direction is it kind of deviating from the root to do something good for this additional also yes so this work currently happens 2 levels repositories article navigation J S and then that book guy the by natural but is that implementations for right and viruses natural repositories called sorry but these are as the case that work with those responses as well does the problem is that we're still finding ourselves how actually all works of like what is good it's client implementations for this which is why we for now knowledge truly line is that kind of think about this is what the clients have to implement this these things like when the rear out can only find the side and we need to make sure it was real that of responses that have a lot of flexibility they're any more questions you may you can also hold that I think it's great so I question around systems like this trade off a compromise between essentially pre-computing although contraction hierarchies alternatively when he was waiting longer for the line reading algorithm to run right character of this graph yeah exactly so it is there to use a C like if you do think you like hit the limit of the let you think
those efficiencies to be made that what you think you could find ways to improve the the construction contraction hierarchies or you think you'd like that's not style and you can't get any faster if there was easy ways we would have already by the 1st stage of the life I would never excluded is definitely there's definitely more like speedups that can be had of just not necessarily logarithmic level but on just programming level and realization of and yet looking at less data at certain points that possible it's always a question of life or the magnitude of speed up like if we if we share ontologies and then I will also have to know with what the civil more questions continue describe it and that the process of collecting all the real time data to to manage to have their work or a just the real be that people are doing that in a 15 minute window of so we have networks collects filamentary from its mobile as the case so applications that implement that box in publications said and otherwise select feedback servers were were currently collecting 80 million whilst data so that's a lot of traits that are coming in and this data we process match and figure out which road segment is this problem of Iraq modalities so this is actually a car and then from that you can write the thank you so the movement of appeals to the president and so there is 1 of the things you will hear
of over the top the