Building an Algorithm to Find the Safest Route Home
Recently a good friend of mine dragged me along to the Kiwi Global Travel Hackathon. My intention was to go all in on the free pizza for a few hours then waddle home in a food coma. I ended up coding for 24 hours straight, building one of the most interesting pieces of software I have ever built. Not to mention we beat 19 other teams and won several thousand dollars!
The outset of the hackathon was bleak. We had a few mediocre ideas we were vaguely excited about. I was the only developer in a team of four – making building a working product tricky. During the event introduction teams seeking collaborators pitched their idea on stage. River, a lone developer, pitched her idea. We all jumped at her idea and summoned her on to our team. We also managed to acquire another developer. Suddenly we were a motivated team of five. Three developers and two designers on a mission!
River’s idea was based on real user needs. She had come across several call outs from people looking for an alternative to Google maps - a product that could offer well-lit and safer walking routes.
Here is somebody else complaining about their real-life fears about walking home in the dark.
Here is somebody else who took matters into their own hands and manually mapped out well lit routes.
After seeing these we felt there was a clear demand for an alternative route finder for generating safe, well lit walking routes.
Two big questions remained. Where would we get street data that included lighting information? How the hell were we going to rebuild Google Maps in 24 hours?
After some overambitious ideas based around deep learning on satellite data to determine street lighting, we realized that before we even get to that point we were going to have to build a custom path finding algorithm. A path, in this case, is a long list of coordinates from the starting coordinate to the destination coordinate. Each coordinate corresponds to a geographical location on earth. Here’s an example: the black line is represented by those four coordinates.
[ [-0.2113435, 51.4093041], [-0.2114654, 51.4094407], [-0.2118623, 51.4098222], [-0.2119443, 51.4099035] ]
To find the best path we need to know all the available paths. To know all the available paths we need to know all the coordinates of all the streets on earth. Easy right? After exercising some well honed google fu we managed to get all that data from OpenStreetMap (OSM). OSM is like a wikipedia for street data. A street is represented by a list of coordinates almost exactly like our path above.
In a fortuitous turn of events, OSM also provides data about, you guessed it, whether a street is lit or not. Perfect! We could keep our TensorFlow sword firmly in its sheath.
The next step is converting this long list of streets into what is called a graph. This isn’t your everyday line or bar graph. In computer science, a graph is an abstract data type, or in other words, a different way of arranging data. Graphs are fundamental for most path finding algorithms. A graph represents connections between objects. For example, LinkedIn is a graph. In the LinkedIn graph the objects are people and the connections are, well, connections. Facebook is a similar graph. People are connected by being friends.
The London Underground could be represented by a graph where the objects are stations and the connections are the direct neighbours of that station.
Here’s how you could represent the above section of the London Underground as a graph.
In the OSM graph, coordinates are our central asset. For a given street we connect a given coordinate with the next coordinate of that street and the previous coordinate of that street. If another street references the same coordinate, i.e an intersection, we extend the connections of the coordinate at the intersection. In the example above, Wembley Park is the intersection coordinate.
Once we have a graph, we can implement the path finding algorithm. We implemented the A* algorithm. The A* algorithm works a bit like pouring water into a complex plumbing system where the different pipes are streets. The water gets poured in at the source location and explores all the pipes until it meets the desired destination. However the A* algorithm is a bit more intelligent than the water as it prioritizes the pipes in the right direction of the destination first.
Back to the hackathon: the organizers announced there were just 15 minutes left. We were still frantically coding away. Somehow we managed to finish in time and had a working prototype to show the judges.
Despite some very impressive entries from other teams – the judges loved it and we were awarded first place! It was great to have them share our enthusiasm for the product, recognise that were solving a real problem and reward us for the feat of building a product that actually worked.
A live version of the prototype can be found here.
Almost a month on, some of our team still use the product to find the safest route home. Coincidentally, I realized that brightpath also produces a much better cycling route than google maps. The reason being that google maps optimizes heavily for cycle paths which are often very meandering indirect routes. I added current location tracking into the app and I now use brightpath everyday for my cycling needs.