CycleStreets blog

A techy post, since we've not had one for a while!

Over the weekend we rolled out some new infrastructure that has taken most of Simon's time for the last month.

And thanks to donations and grants that we received, we now have a machine that works primarily to churn out imports without slowing down the main server in the evenings, as used to be the case.

Versioned database for routing

We now run a versioned database for the routing. Effectively each import of the OpenStreetMap data to make a routing database is now a dated and separate database. Previously we prepared an import and moved it into place, then shortly removing the old one.

The main benefit of this is that when a new set of data has been imported from OSM we can switch to using it instantly without having to shutdown the database.

The other benefits are that it is much clearer where the routing tables are – and has also resulted in a useful purge of some unneeded data.

The ultimate intention of this work is to enable us to run a much more frequent import cycle. Currently the data is refreshed weekly.

More efficient route generation

The itinerary listing details that you get when you plan a route are extracted from tables generated during the import (rather than re-calculated for each route).

There were quite a few inefficiencies here, and we've restructured how the data is extracted to make it quicker. This forms the conclusion of work to speed up the system for mobile use.

This will mainly be of benefit to API (e.g. mobile phone) users, as the website version itself still has to generate the maplets (which we plan to change in some way in due course, following user feedback).

These changes should not have affected the API output, except hopefully making it faster!

Turns details

The routing output also now includes text like 'bear left', 'sharp right', or even 'double back' with the segments as it did quite a while ago. (This is the cs:turn data in the API output.)

This summer has been ridiculous busy for us. We've had a large number of projects, which has felt a little overwhelming at times!

Simon is our 'routemaster', and he's been working solidly over recent months on a range of improvements to the journey planning engine:

• Main focus has been speeding up the routing engine performance. Thanks to the generous grant from the Rees Jeffreys Road Fund, Simon has been able to dedicate a lot more time than usual on this aspect, such that the system is now fast enough and scalable for mobile usage with a lot more traffic. We're finishing off a final improvement to reduce the response time further.
• Working on improving the translation from OpenStreetMap (OSM) into our optimised routing network format (codename 'Cello');
• Working to fix the 'ferry routing bug' (where routes in London sometimes end up using the Thames ferries rather than cycling!);
• Reducing wigglyness of routes – which is becoming our main focus as the performance work is concluded;
• Speeding up the import time so that we can reflect changes in OSM more quickly. (We're a little way off 'live routing' but that's our ultimate aim!);
• Simon will then be moving on to supporting more advanced data types in OpenStreetMap.

Martin, who tends to deal with usability, code structure and the project management side of CycleStreets, has been working on a range of things:

• A problem-reporting system for Cambridge,  www.cyclingsorted.org - which has just been launched and which we'll blog about soon
• Managing mobile app development, with our iPhone app about to be released (and Android offerings hopefully very soon after – thanks to our volunteers working on that!)
• Starting work on a mobile HTML version of the site … stay tuned!
• New interfaces that use the same database, e.g. www.londoncyclehire.org and others (watch out for blog posts on this soon)
• Working on adding bikeshop data views to the system
• Reworking the Photomap interfaces (thanks to funding from Sustainable City)
• Work which will enable the map size to be increased and related interfaces improved (ditto)
• Adding new functions to our API (used by mobile and other developers)
• A large amount of cleaning up the code behind-the-scenes. Over time, the codebase has had structural problems which has meant adding new functionality and design changes had become too time-consuming. Much of this is now done, but you won't have noticed any changes – other than (hopefully) things appearing faster! This has really been the enabling work for a lot of other projects.
• A London-based project to deal with the cycle parking deficit across the city, to be announced shortly!
• Information for Local Authorities
• Grant funding applications (we could definitely do with a fundraiser still!)
• Shortly starting work on a better feedback interface to make this area and map-based rather than table-based.

We've obviously also other voluneers working on various areas including:

• Working on the mobile versions
• Responding to feedback
• Bike-shop related things for OpenStreetMap, using data we brokered
• Various outreach opportunities

Our mobile app is nearing completion. Unfortunately the schedule slipped by a month as we were keen to complete our backend work to ensure the routing was fast enough to support it, something that is now in place. Also, we've been held up slightly by EXIF-related issues (so that uploaded photos get the correct position even if they were taken a while ago).

Here are screenshots from the latest work in progress, with a few bug fixes due to be implemented by mid-August before we submit to Apple.

Thanks to everyone who has offered to be a beta-tester. We'll be in touch soon – sorry for not acknowledging each offer individually yet!

We've lots of ideas for new features to go in a future release after the initial release. We'd like to create a team of two or three volunteers to work on the app on an ongoing basis. If you'd be interested, please do get in touch.

Planning a route:

Following a route:

Browsing the Photomap:

Adding photos to the Photomap:

Settings and other pages:

The main focus of our development work over the last few months has been to improve the performance of our routing engine. This has become a priority with the need to serve routes on new mobile platforms, where the expectation that a route should appear quickly is even higher than those interacting with CycleStreets via a web browser. We need to generate routes as fast as possible – as that will form the basis for developing a stronger user experience.

We have explored three other routing engine architectures in addition to the original engine.  This has involved changing our system so that it can interface to all four routing engines. Getting that to work has forced our code quality in that area to improve and become more modular and generic.

One of the routing engines is emerging as a clear winner in terms of performance speed. It is written in the Python language, and is based on some code initially provided by a participant at our developer day back in March. This engine has now been serving all routes since last Thursday. The routes it produces are identical to those produced by our previous system, but they are now generated more quickly (and more reliably) than with the previous engine.

API users (mobile phone interface developers) have already remarked at the speed increase.

We shall be extending this engine to cover other parts of the route generation process that are still relatively slow.

We've been able to undertake this concentrated period of work to speed things up and improve resilience thanks to grant funding from two sources: the Rees Jeffreys Road Fund, as part of our efforts to improve performance for mobile interfaces, and hosting optimisation thanks to a grant from the Co-op Community Fund. We are very grateful for their support.

Here's a screen snapshot of work in progress on CycleStreets.

It shows the shortest route from Dover to Cape Wrath – i.e. the entire length of the country! Basically it uses the A1 – so the Romans were about right then!

We've been working on a much faster routing engine that will, as a side-effect, also enable longer distances to be done.

More news soon.

At present, we've a couple of areas of work that we've been prioritising, to address known weaknesses with the system.

Firstly, we've been working to reduce the 'wigglyness' of some routes. The problem is that the journey planner engine does not yet take account of turn delays. Once this is finally rolled out, routes will be straighter and easier to remember.

Secondly, and following our recent Developer Day, it was very clear that we need to rewrite the core network traversal algorithm in a more efficient programming language, and we've started some exploratory work on this. The effect of this will ultimately be to speed up the route planning considerably, and to enable us to add long-awaited features like draggable way-points. It will also mean that we can tackle more quickly problems where the weighting of the data is wrong – e.g. how the engine sometimes gives busy roads when that is potentially avoidable. These are all things which we will address before moving out of 'beta'.

Thirdly, we're keen to address user interface issues, particularly increasing the map size and de-cluttering some screens such as the itinerary result page. If you are a user interface designer who could help us with this, please do get in touch!

Lastly, we're working hard to get more funding. The project so far has been achieved on under £12,000, and our two main developers have worked entirely unpaid so far. Our main target is to get 1 full-time plus two half-time funded developer positions for 12-18 months, so that the project can then be self-sustaining. This will enable us to enable us to ramp up routing quality much more quickly – including adding more attributes in – and to implement new, innovative features faster.

We’ve rolled out an improvement to the journey planning engine which should mean it returns the route solutions about a third more quickly than before.

It’s still not as fast as we would like, but we have plans to make a major change this coming month or so which we believe will make a much bigger difference. With people starting to use our API, we’re even more aware of the need to maximise the planner’s performance, both in terms of speed and route quality.

The current speed-up is due to a set of changes we’ve made to the ‘scoping’ of the map data. When start/end points are determined, an elliptical scoping is done to obtain the likely area in which a set of routes will be found. We’ve implemented a more intelligent way of dealing with the scoping, resulting in a notable reduction of the amount of data taken in – leading to faster route-planning and less memory usage.

Our next improvement will be rolling out the wigglyness reduction work we’ve been doing, which is – for the second time(!) – nearing completion. We’ll blog about that soon.

Here is a planned route (number 121095), with the red (fastest) route highlighted*. Following this is a diagram showing the elliptical scope used – basically what’s within the green oval is the data available to the router.

*Yes, we know we need to make these maps bigger! – User interface designer needed – can you help?

The planned route:    and …

… the elliptical scope used for it:

On Saturday we held an intensive but successful event that focussed on the development challenges for CycleStreets. It was attended by computer scientists, software engineering professionals and webmasters who have experience in managing online services. This summarises some of the stuff we talked about.

Processing OpenStreetMap (OSM) data to build a Graph for Cycle Routing

We began by focussing on how CycleStreets processes OSM data into edges and vertices that can be used by a routing engine.

CycleStreets can find the shortest, fastest or quietest routes according to weightings attached to each edge. For the shortest routes the weight of edges is simply the length of the street between the two vertices. The weighting of the edges for the fastest and quietest routes is more interesting and depends on the type of street, the riding surface, whether there are any traffic lights and if it is going up or down a hill, and other factors going forward.

CycleStreets has its own routing engine that is written in Object-Orientated PHP, this language being a choice purely for legacy/historical reasons that has never been formally reviewed. The space inefficiency of PHP arrays has meant that the CycleStreets routing engine has evolved a suite of techniques for reducing the amount of data exchanged between it and the database.

To make the processing as fast as possible for serving routes live, all the weightings of edges are pre-computed. A data compression technique known as ‘Cello’ (Cellular Optimisation) reduces the number of vertices by a factor of five and the edges by two.

When planning a journey CycleStreets assumes that it needs to look at an area of the map that is up to twice as long as the straight-line distance between the start and finish points. The edges and vertices for that area are extracted from the database and either a Djikstra type or A-star algorithm is applied to produce a route.

Route planning in Central London is the most demanding for the system. An 8-mile journey extacts 22000 vertices and takes 22 seconds to create as a cache in PHP, consuming an unacceptably large amount of memory. It takes a further 2 seconds to search that cache to find a route.

The feedback from this section of the day was that:

1. There are off-the-shelf programs that can process the whole of the UK in less than a second. Using one of these implementations, we could replace the small section of code that does the actual graph traversal, to get a quick speedup.
2. The physics of the routing is of the greatest interest to cyclists. That is what makes CycleStreets special, and is where we add value; it is the focus of our innovation.
3. We need to make it clearer how CycleStreets processes the OpenStreetMap data for cycle routing.

Since the dev day I have had a further look at options for the routing.

Our existing routing engine

At the moment our routing engine exists in two forms: stable and testing.

In the stable form the graph is simply edges and vertices. It has been reliably producing routes for several months, and although in most areas of Britain it can generate routes quickly, it does not work quickly enough in London.

The testing form takes into account the cost of turning at a node and is designed to reduce wiggliness. This has been in development for the last 3 months and has proved complex and difficult to optimise. It has reached the stage where it is nearly ready for release, but has the problem that routing with it takes too much memory.

The key to reducing the amount of data is in reducing the number of edges. In Cello it is quite easy to reduce the number of vertices, but much harder to do that for the edges.

On the developer day we discussed instead how reducing wiggliness could be taken into account by modifying the vertices on the graph, as shown below.

The cost of making the turn from S towards W,N or E shown on the left. can be incorporated into the graph as shown on the right.

The left of the image shows weighted edges joined in the middle with the costs of making the turn from node S towards each of the nodes W,N and E.The total costs of the routes are: SW = 5 + 4 + 4, SN = 5 + 1 + 5 and SE = 5 + 8 + 7.

That can be transformed into the image on the right, in which the turn costs have become extra edges between the vertices. The extra edges are one-way.

Making such a change to our graphs seems relatively simple compared to debugging Cello. At a vertex an extra edge will need to be added for each of the other edges. In this case 4 x 3 = 12 extra vertices and edges.

This modified graph could then be handled by the off-the-shelf routing engine.

Import of Data from OSM

On the developer day we did discuss how CycleStreets imports data. This summary attempts to clarify the process.

The table of how OSM tags are used by CycleStreets is shown at:

http://www.cyclestreets.net/views/howTagsUsed/

This table is orderd by the numbers of matching ways. The first row shows the most common tag pattern that matches half-a-million ways. The table has a long tail.

The table is built by a procedure involving the following steps:

1. Import

The OSM way tags that are relevant to cycling are identified as the following:

• highway
• cycleway
• access
• foot
• bicycle
• oneway
• relation

For each OSM ‘way’ a row is created in the map_way_tags database table.
The above tag names are used for the field names in the rows, but suffixed with ‘Tag’, e.g. onewayTag.

The relation tag is only used where the relation it refers to is something to do with cycling.
Usually these are signed cycle routes with tags such as type=”route”, route=”bicycle” and network=”NCN”, ref=”11″.
Some ways are tagged directly with e.g. ncn_ref=”11″

Node tags such as crossings and traffic_signals are handled by later processing.

2. Canonization

The values of the tags are checked against an allowed set of values that CycleStreets recognizes.

Where there are invalid values some repairs can be made. For instance from oneway=true to oneway=yes.

The full set of repairs is listed at:
http://www.cyclestreets.net/views/repair/

The canonized values are copied into the similarly named fields in the map_way_tags table.
The canonized field names do not include the ‘Tag’ suffix.

So for instance a way with the following tags:

highway = “residential”
oneway = “true”

becomes a row in the map_way_tags table with these original and canonized fields:

highwayTag = residential
onewayTag = true

highway = residential
oneway = yes

The howTagsUsed table lists the contents of the map_way_tags table, grouped by the canonized fields.
Hence there is one row in that table for each unique combination of the canonized values.

3. Initial impressions

The simple mapping between the OSM highway tag and CycleStreets’ provision types defined at:

http://www.cyclestreets.net/views/osmHighwayTranslation/

is used to create an initial suggestion for each row in the howTagsUsed table.

4. Rules

A set of rules is then applied to the permutations to improve the quality of the translations.

For instance a highway=”service” is intially interpreted as provision type “Service Road”.

A rule that matches bicycle=”no” converts this to “Prohibited”.

Inspecting the Translation

The /howTagsUsed/ view provides a detailed and rather complex listing of the translation.

It is possible to click on the items in that table to view the data in filtered ways.

Another way to view the information is via the map on the Journey Planner page.
When signed in with your developer account (which should also include the ‘osm’ privilege) you will have access to the ‘Ways for OSM users’ overlay. This is available via the blue plus symbol at the top right of the map.

I think we could do more to make it a lot clearer how the information has been imported and processed.

One major problem is that the import data cycle has stalled recently due to the on-going work on reducing wiggliness.
This is bad because it means the CycleStreets system is out of date, and any recently added photos will not be included on routes.

Open-sourcing

There was a long discussion about this, with a range of different views. As ‘open source people’ we are keen to Open Source the codebase, but there are a few factors which govern the timing of this, and some work to be done first.

It won’t bring in new developers straight away, but it will be an on-ramp for getting people more involved in the project.

It will improve the quality of the download and installation.

There is a danger that it could be always something we hope to do, but never actually get round to. We definitely want to avoid that.

OpenCycleMap

We were given a useful overview of how the OpenCycleMap.org project works by its creator, Andy.

This site renders cycle-specific OSM data for the whole globe. It has very beautiful rendering of hills, and in fact that accounts for 96% of the data, the remaining 4% is all the other streets, including the tiny amount that have cycling data. That rendering includes all the known, verifiable cycling routes.

The success of this project keeps their servers extremely busy, but they are soon going to expand to bigger and more powerful systems.

What we did not discuss on the developer day

Time did not permit us to get onto a whole series of other things. Here’s a short list:

• Drag drop routing – this is a feature which already exists in Developer Mode but has not been exposed to users generally; it would need some discussion about permalink URLs.
• The layout of the CycleStreets pages – e.g. increasing the size of the map - which is something we’ve always had a lot of feedback about. We now have a grant which could include some design work commissioning.
• Output from CycleStreets – either as printed output or via export to GPX / KML.

Perhaps when some of the issues we’ve learned from this developer day have settled down we shall think about organising a users day to focus on some of these important, but hopefully simpler issues.

We’ve created some long-needed documentation: Overview of CycleStreets: your questions answered, covering a number of areas:

• Features: Cycle journey planner
• Features: Photomap
• Many more features
• Homepages for 1,500+ towns/cities/districts around the UK
• Branded versions for Local Authorities and others
• Community-based, not-for-profit
• The map data: where it comes from and how you can contribute
• How we use the map data
• The routing engine
• The cartographic map base
• Open-sourcing

Many of these are things which we’re often asked about, particularly from people within the technical community.

For a bit of fun I realised I could plot the start points of planned journeys on the photomap. I’ve done this for the last 2009:

The blue markers indicate the approximate location of recently planned journeys.