CrowdAtlas: Self-Updating Maps for Cloud and Personal Use

Overview:

This paper talks about providing the solution for accurate navigable digital maps (based on GPS), which includes the paths of off-road driving, cycling, hiking, and skiing maps. This is achieved using the crowdsourcing technique where people (fleet management, telematics and smartphone users) would share their navigations to provide training samples. By this, they solve the problem of updating the maps at regular intervals (automatic) where an update may include unexplored new roads or closed roads due to any construction. They also provide a CrowdAtlas app for users without internet connection and for those who want to create and use customized maps.

Key Points:

1. CrowdAtlas employs a Hidden Markov Model (HMM) based map matching algorithm (offline) which detects any discrepancies between GPS samples and roads, and applies a clustering-based map inference algorithm to update the maps.
2. Unmatched segments are used to infer new roads, using the map inference algorithm. This uses unmatched traces clustering algorithm (single linkage) to form clusters for the most used roads.
3. CrowdAtlas invokes the polygonal principal curve algorithm to extract the road centerline from the cluster. This is done by selecting the appropriate values of the support threshold. Douglas-Peucker algorithm is used to remove any unnecessary nodes in between and find the start and end points of the connecting path.
4. It also extends the map inference algorithm to infer missing features like intersections, new turn possibilities, and one way road directions and corrections, by iteratively updating the maps and finding out the changes in the roads of a specific area.  
5. CrowdAtlas uses the traces that match the map to monitor for road closures and fix road geometry. It uses tight clusters of trace segments from many vehicles that do not match the map in order to infer missing roads that connect to existing roads. The existing roads provide good segmentation of the traces to produce high quality clusters, enabling the automated (and even unsupervised) addition of missing roads.
6. CrowdAtlas applies different error radius thresholds to matched and unmatched segments, since the goal is to capture all unmatched segments as well as match GPS sample to the right roads, which is also crucial for detecting walking/cycling trails, which are often closely parallel to drive roads.
7. Dynamic sampling is implemented in the CloudAtlas app (for only the data transmitted to the server), where high sampling rate is for unmatched segments and low sampling rate is for matched ones.

Strengths:

1. Main strength of this paper is the motivation of the problem. The authors have used the unsupervised learning to solve the navigation problems which are seen frequently these days.
2. The evaluation done on the specific area in Beijing is intensive and seems very useful if extended to other parts of the world.
3. The authors have addressed the challenges/limitations pretty well, which are mostly intrinsic to the GPS based navigation.
4. CrowdAtlas App can be very useful for personal use specifically, since it covers all the paths like cycling/skiing/ off-road driving or even walking.

Weaknesses/Discussion Points:

1. As identified by the authors, map matching algorithm is fairly intensive which is the bottleneck of the whole process. The parallelization techniques also have been discussed. One thought here is, Can we use local edge servers (or fog computing) architecture like DeepCham, where these computations can be brought closer to the people using this service?
2. Not many users would be willing to share their data about where they are traveling, and updates would solely be based on only certain areas (support threshold value plays an important role here).
3. GPS coverage in some areas(even heavily populated) can also be a limitation since many developing countries still don’t have it.