OSRM (Open Source Routing Machine) is an open source high performance routing engine for road network routing. Typically OSRM is used as a web server using OpenStreetMap (OSM) data, and is capable of calculating hundreds of routes a second. OSRM gets its speed by pre-processing the road network using Contraction Hierarchies, allowing very fast ‘short cut’ routing at runtime.
Instead of using a static configuration file to store speed and road profiles (e.g. like our MileCharter and MPMileage products), OSRM uses a Lua script. At first sight this seems needlessly complicated, but it allows more sophisticated profiles based on OSM tags and/or external sources. For example, different speeds could be used according to not just the road type, but also the road surface. OSM tags are not always globally consistent and these can also be accounted for. External databases can also be queried, and OSRM ships with a sample Lua script that queries PostGIS to apply speed corrections.
Runtime speeds are not affected because the Lua script is only used during the pre-processing stage.
Unfortunately, OSRM’s Lua scripts have virtually no documentation. This post is an attempt to help correct this. The initial post is incomplete: Please post additions or corrections to the comments, and I can incorporate them into the main text.
Lua (Portugese for ‘Moon’) is a lightweight scripting language. Written in pure ANSI C, it is designed to be embedded in applications as a local scripting language. As such it has become popular in the games industry, and is a logical choice for OSRM. The language itself borrows some concepts from Pascal but is tightly defined and consistent. For example, the only data structure is a ‘table’ which is Lua’s name for an association list. Used as association lists, they are dictionaries. Fill them with functions (which are also values), and you have a library. Mix numbers, strings, and functions; and you have the beginnings of an object.
In order to learn Lua, I recommend Programming in Lua by Roberto Ierusalimschy (2013).
Sample Lua Scripts
OSRM comes with a number of test scripts such as testbot.lua and turnbot.lua. postgis.lua demonstrates the use of OSRM with a PostGIS database, querying the database to find the proximity to an industrial area and lowering the speed if one is nearby.
There are two helper scripts. maxspeed.lua defines the limit() function that applies constant maximum forward and backward speed limits to the speed in an OSM way structure (i.e. road segment).
access.lua defines the find_access_tag() function. This returns a tag’s value for an OSM way structure (i.e. road segment). The way structure may have tags for different ‘vehicles’ (motorcar, bicycle, foot, etc). The OSM name for one of these tags, is an ‘access tag’. find_access_tag() takes a list of acceptable access tags (access_tags_hierarchy) and only returns the value for one of the listed access tags.
Anatomy of an OSRM Lua Script
The three main Lua scripts provided with OSRM are car.lua, bicycle.lua, and foot.lua for car, bicycle, and foot routing, respectively. These are all designed in a similar manner.
OSRM expects two functions to be defined: node_function and way_function.
This determines if a road node is routable or not. Road nodes are the points where road segments (‘ways’) meet. In the real world, road junctions, traffic lights, and barriers, would all be represented with nodes.
node is the OSM node structure, and the standardized results are returned in result. result has two fields that are used: barrier and traffic_lights are boolean flags. Set these to true to switch them on.
The car.lua implementation has lists of acceptable OSM barrier tags (e.g. cattle grids and border controls) listed in barrier_whitelist, and a list of tags to avoid (e.g. private and agricultural roads) listed in access_tag_blacklist. The implementation of node_function then uses these to set the result.barrier field. result.traffic_light is simply copied from node.traffic_light.
This determines if an OSM ‘way’ (i.e. road segment) is routable and at what speed. The OSM way structure is passed in the way parameter, and the results are returned in the result structure.
The car.lua implementation is more complex than node_function(), and most of the constant definitions at the beginning of the script. It uses most of the definitions at the beginning of the file. These include speed_profile which provides the speeds for each road type. surface_speeds provides maximum speeds for different surfaces. For example cobblestones have a much lower maximum speed than cement. Set these values to nil for no limit (e.g. asphalt).
The first section of the implementation checks to see if the road is passable (i.e. routable). For example, the way is not marked as ‘impassable’ or has an access type that is on the blacklist. The function returns without setting any of result‘s fields if the road is determined to be non-routable.
result has four main fields: forward_speed, backward_speed, forward_mode, and backward_mode. Notice that the speed and mode can be specified for both the forward and reverse directions (as defined by the way’s start and end location order). This is most useful for a one-way street, which should be open in one direction, but closed in the other. Differential speed restrictions might be useful for split lanes (e.g. where one direction uses an old bridge, but the other direction uses a modern bridge).
The mode values are 0 (zero) for closed; and 1 (one) for default (i.e. open). Other values are defined in car.lua (plus foot.lua and bicycle.lua). However, these are not consistent between the scripts. For example, car.lua and foot.lua define mode_ferry as 2, but bicycle.lua defines mode_pushing as 2 and mode_ferry is defined as 3 instead.
There is no documentation specifying the significance of the values greater than 1, and it is unclear if they should be consistent. I have checked the OSRM C++ source code. The sparse code comments confirm the meanings of mode 0 and mode 1. There is no documentation or code comments in the source code that explain the higher values.
Another results field is duration for situations where a way has a fixed duration. This is used for situations where the total travel time cannot be easily calculated. For example, a ferry would include loading and unloading in addition to the ferry’s actual travel time.
Other results fields include name (road name) and ref (official road number) which are used to create the routing instructions. Finally there is a boolean flag, roundabout, that indicates a junction road segment (way) is a roundabout.