Master theses

Cross-platform and efficient route planning with WebAssembly

Keywords: Route Planning, Compilers, Emscripten, Programming Languages , Rust, WebAssembly

Supervision: Pieter Colpaert

Students: max 1

Route planning applications are the standard way of finding your way between two locations, sometimes it’s in the form of the navigation software built in your car, sometimes it’s through online services like Google Maps. However, despite how common they are now, there are still some open problems. Giving the option to prioritize scenic routes when the weather’s nice for example, or avoiding streets that are too narrow for bidirectional traffic but are the result of bad urban planning. Client-side route planning could be used to solve these problems because the computation happens on the end-user’s side, so they can tweak any parameter they want.

We have been prototyping this principle over the past couple of years, where all relevant data is published in fragments on the Web, so that clients can pick and choose which data they use. For instance, we have published the road network from OpenStreetMap in tiles of roughly 4 km², and separate mobility profiles determine how the road network is to be translated to a weighted directional graph. A mobility profile for old-timers for example could be set to avoid highways, while one for scooters could be set to avoid cobblestones if possible.

Developing these prototypes into functioning applications has been a challenge however. On one side, we have been working in Javascript so far because of our dependency on resources on the Web. Javascript was never meant for heavy computations, making the end product too slow for end-users. Moreover, there are several platforms that support Javascript -- but code written for one platform does not necessarily work for the others. In practice this means that we now have a route planner that works in browser environments, but that does not work in any of the mobile frameworks.

WebAssembly may fix both problems at the same time. On one hand, it is meant for heavy computational loads, and should in theory be nearly as efficient as regular binary executables, especially compared to Javascript. On the other hand, WebAssembly is so minimalistic that it may very well be more portable than Javascript. There are no dependencies to platform specific standard libraries as there are no standard libraries.

We want to know how mature the WebAssembly ecosystem is. Specifically, we want to know if there are enough libraries to work around the lack of standard library, e.g. can we make asynchronous HTTP requests? There are several projects developing WebAssembly toolchains in parallel, such as Rust’s wasm-bindgen and C/C++’s Emscripten, so the answer to the previous question might not be a simple ‘yes’ or ‘no’. Assuming one of the toolchains is sufficiently mature, we also want to know what the performance impact is, as there will always be some inevitable overhead to client-side data processing.

This project involves a lot of software development, but there is plenty of room for research if so desired. On one hand, WebAssembly is new, and the community is still working towards established best practices. An understanding of the underlying VM, and how programming languages compile to it, is instrumental to benefit from its theoretical benefits. On the other hand, the end goal is an application that is nearly as efficient as relying on online services, even if it is only in very specific circumstances such as short-distance routes. Achieving this will require more than a fast execution environment, the underlying algorithms are at least as important.