HERE Chicago Hackathon: Runner-up teams' solution to use Probe Data to detect roundabouts

Approaches to Problem Solving

Team Norbel’s approach involved experimenting with multiple methods to accurately identify roundabouts from the HERE probe data. They began with a clustering technique using DBSCAN (Density-Based Spatial Clustering of Applications with Noise). DBSCAN was effective because it could identify clusters without predefining the number of clusters, making it suitable for detecting roundabouts by clustering nearby vehicle positions based on spatial proximity. The features used for this included latitude, longitude, heading, and speed, which helped in distinguishing roundabouts based on movement patterns.

To further refine the results, they enhanced their strategy using HDBSCAN (Hierarchical DBSCAN). HDBSCAN provided adaptive clustering, automatically adjusting to variable densities, which was particularly helpful in noisy, real-world data scenarios. It also incorporated automatic noise detection, reducing the need for manual parameter tuning and improving the ability to isolate roundabouts more effectively. They also leveraged a purely mathematical approach to filter out irrelevant data points by considering objects' speed and heading angles and used preprocessing techniques like vectorized commands and parallel processing in Python for performance optimization. 

HERE Data and Services used 

We provided the teams with HERE Probe Data to access real-time probe data from various vehicle navigation systems. This data included timestamped coordinates, vehicle speed, and heading direction. Team Norbel used this information to analyze movement patterns and cluster locations to detect roundabouts.

Furthermore, they integrated the HERE Map Image API to retrieve map images based on the cluster centroids identified through their machine learning models. These images were used to train a Convolutional Neural Network (CNN) that could distinguish between roundabouts and other road structures, ensuring higher accuracy. The retrieval of labeled and unlabeled images was key to enhancing the machine learning pipeline. Given the high volume of API requests required for data labeling, they overcame limitations by utilizing multiple API keys to handle the data load, allowing them to efficiently pull the necessary information without exceeding request limits. 

Challenges 

The main challenge that Team Norbel encountered was managing the high volume of data, which required substantial preprocessing and optimization. Handling too many API requests for both labeled and unlabeled data posed issues, as they often reached the request limit quickly. To circumvent this, they implemented a strategy using multiple API keys to distribute requests, ensuring continuous data retrieval without interruptions. 

Another significant challenge was distinguishing roundabouts from other circular road structures. The noisy data and overlapping traffic patterns in urban areas made it difficult to differentiate these features, even with advanced clustering techniques. They also faced challenges in optimizing the clustering parameters, particularly when using DBSCAN, where manual tuning of epsilon and minimum samples was required. HDBSCAN helped address some of these issues with its adaptive nature. 

Final Solution 

After experimenting with various methods, the team ultimately selected a hybrid approach that combined clustering techniques with machine learning. They initially used K-Means clustering to identify dense clusters of vehicle traces that could indicate roundabouts. By employing the Elbow Method, they determined the optimal value of K, which allowed them to capture maximum variance with the minimal number of clusters. This was particularly useful in isolating potential roundabout locations based on data density. However, K-Means alone had limitations in handling noise and overlapping traffic patterns which they hoped to resolve by incorporating HDBSCAN on top of the stack, however, due to time constraints they were unable to add this modification.

To further refine their solution, they implemented a Convolutional Neural Network (CNN) model. They utilized the HERE Image Maps API to retrieve map images of the clusters identified by the clustering algorithms. These images were then used to train the CNN to distinguish between roundabouts and other similar road structures. The CNN approach allowed them to leverage visual data, improving the ability to correctly classify roundabouts, especially in cases where the clustering methods alone were insufficient. By combining K-Means and CNN with some refinement they achieved a robust solution that effectively identified roundabouts from noisy probe data, while also being scalable and adaptable for different regions. 

Scaling Geographically 

Team Norbel's approach can be scaled globally by adapting the clustering and machine learning models to account for regional variations. For instance, the clustering model can adjust angle filtering based on driving orientation (e.g., negative for left-hand drive, positive for right-hand drive), allowing the method to generalize to different countries' road systems. Additionally, the CNN model can be trained on a broader dataset of roundabouts and non-roundabouts from different regions worldwide, making it versatile and capable of handling varied geographic contexts. By incorporating global datasets and retraining the model with data from new regions, they can maintain accuracy and performance across different road networks and traffic patterns.

Access to Code Rexpository

Their solution is accessible here.