All roads lead to ROMA: Design and evaluation of a Robust Online Map-generation Algorithm based on position traces

Keeping maps up to date is quite costly because road geometry changes over time and mapping by professional surveyors is an expensive operation. With the presence of GPS sensors on mobile phones and in most cars today it becomes possible to measure the location of roads with many measurements from sensors of lower accuracy. In this thesis we explored a method to use these less-accurate measurements for the development and maintenance of a dynamic road map. The main research question is: How to create and maintain an accurate and dynamic map based on position traces? --Method-- To answer the main research question, we have developed a quadratic time robust online mapgeneration algorithm (ROMA) for creation a dynamic vector-representation of the world where position signals are gathered. The world and GPS signals were simulated so that an absolute ground truth representation off the world was available. For the evaluation of map quality we developed a cubic time metric which finds a common edge subgraph of the world and the developed map. This subgraph indicates the true positives and enabled us to determine both precision and recall for the generated map. Using the harmonic mean of precision and recall we were able to indicate map quality in one number on the interval [0,1]. We tested the dynamic behaviour of ROMA on scenario’s of road introduction and road removal. --Results-- Each run of the road introduction experiment showed an increase in map quality followed by stabilisation or even a decline in map quality. Map quality generally reached a value of 0.5 within 5 minutes of road introduction. In all experiments the recall was constantly higher than the measured precision. Recall generally reached a maximum of over 0.8 whereas precision stayed at 0.5. For the road removal experiment we introduced roadblocks at the peak of measured map quality for traffic densities showing a clear decline afterwards. Road removal was detected within 30 minutes after the introduction of roadblocks for removal of up to 50% of all roads in the world. All experiments showed a build up of web-like road structures around the location of roads in the world. This build-up was stronger present in experiments with higher traffic densities. --Discussion and conclusion-- This research has provided new insight into incremental map-development by looking at the temporal aspects of the process. Within this research we have provided insight in the formation over time of web-like structures within trace-merging algorithms. Due to the investigation of this phenomenon we have also provided suggestions for the decrease of this effect over time by merging parallel roads. The novel graph based method for map comparison offers advantages to existing approaches and is especially suitable for incremental maps while the road takes shape. ROMA offers a method for dynamic map generation which robustly creates and maintains a map representation of the world through the collection of GPS traces. The experiments show that a navigable map is generated which detects new roads being travelled and also forgets roads no longer travelled. We therefore conclude that ROMA is a decent proof of concept for dynamic vector-map generation in an online fashion.

Subject

GIS
map-generation
online
algorithm
graph comparison
MCES
GPS
dynamic
map
proof-of-concept

To reference this document use:

http://resolver.tudelft.nl/uuid:efc7664b-7c60-484a-8f18-ca42abd1c842

Part of collection

Student theses

Document type

master thesis

Rights

Files

PDF

vandenberg_2015_all_roads ... o_roma.pdf

6.34 MB

Close viewer