CrowdAtlas: Self Updating Maps for Cloud and Personal Use

Motivation: Maps play an important role in everyday life and they can be very inaccurate. 26% users complained that the technology tried to make them go through a no-entry sign or somewhere where vehicles are prohibited. There are several accident reported on this case. Maps should be updated frequently as roads change and this situation is worse in developing countries because of frequent road maintenance and construction. Current manual methods for updating maps are costly, error-prone and have long update cycles.

Solution: CrowdAtlas is an automatic map update system for cloud and personal use. Using GPS traces, CrowdAtlas can analyze the maps on the server as a standalone system. It can be used to learn road geometry, turn restrictions, identify new routes etc.

How does it work?: GPS traces are increasingly abundant from many systems and apps like fleet management systems, telematics and navigation apps. CrowdAtlas can use such data to automatically update maps. Large scale GPS streams first go through a parallel map matching process which finds a most likely route on the existing map for a given sequence of GPS coordinates. The highly accurate mathematical algorithm is customized to separate trace segments that align well with the map, from trace segments that do not map to any route. Mismatched trace segments are used to infer new routes using the map inference algorithm. First, a clustering procedure groups mismatched traces that are likely to form a new route. When cluster gets enough supporting traces, CrowdAtlas extracts the center line from it and adds a new road to the map. Matched segments are used to adjust existing routes. CrowdAtlas detects road closure using change detection algorithm. CrowdAtlas identifies misaligned roads by calculating median location shift of the samples matched to the road. To enable personalized maps, they have also developed a CrowdAtlas app which acts as a GPS data source. In the standalone mode, new roads are added as the user trends them, instead of aggregating multiple GPS traces for high competence. The types of new roads inferred is based on travel mode. This way, CrowdAtlas provides an automatic update on the maps with the help of very accurate algorithms.

Evaluation: A 4.5 km^2 street block was mapped in less than 30 mins and a walking/cycling map was built on the SJTU campus in China. The taxi traces from Beijing were collected to add 61 km of missing roads to the maps, and all these have been done automatically.

TradeOffs:

• During the server update process, after map matching only few updates have remained of the total samples taken. These updates were as less as 1% of the total updates. But, all the updates would be sent to server instead of just the 1% updates, thereby, dramatically increasing the data communication between the server and client.   
• If the user is travelling on a different route other than the one directed by GPS, the GPS would add the new route to the users map. The maps should also be able to provide the tradeoffs of using both the roads, so that the user can choose the best route when he travels the next time.
• The algorithmic computation of map updates would taken place on the server in the server update mode. But, in case of the standalone app, the update would take place locally and this might be a computation intensive process, which would require large amounts of battery and local resources.