GSOC Update

This is a blogpost update describing my work for the Green Navigation project during the Google Summer of Code 2016.

The first ten days have gone by quickly. The main coding work I’ve done is to create a demo of the prototyping tool in Python. This is similar to the functionality of the previous routing-api, except it

• includes a REST API i.e. the backend is separate from the visualization
• uses the A* search algorithm

Here’s the demo in action:

The server uses the Bottle Python framework for a quick-and-easy REST server. The geographic node data is fetched once and cached from the OpenStreetMap Overpass API. The two markers in the gif are the start and end points.

Edges and vertices are represented in the OSM dataset — each vertex is a geographic node with latitude/longitude, and each node is part of a ‘Way’ or a path — thus it is simple to apply graph algorithms on the data.

The A* search algorithm is very similar to a normal priority-queue based Djikstra implementation — the difference is that Djikstra tries to minimize the distance upto that node, while A* tries to minimize the (distance upto that node + estimated distance from node to target).

The resultant data is prepared for visualization and sent to the front-end, handed over to Javascript for visualization. Creation time metadata is included with the nodes, so that setTimeout can be used for animation on the map.

Creating this demo gave me some insight into the roadmap of the project. Researchers currently use Jupyter/iPython notebooks to test out and share algorithms. What they need is a language agnostic solution that allows them to code algorithms in any language (not just Python). For this, an ecosystem of sharing notebooks with a clear and easy workflow is needed. The fact that Jupyter has different kernels for different languages may be useful later. For now, I’ll be continuing work on the back-end of the Prototype Tool and its data sources.