Navigating intersections is obviously important when driving in Duckietown. It is not as obvious that the mechanics of intersection navigation for autonomous vehicles are very different from those used for standard lane following. There typically is a finite state machine that transitions the agent behavior from one set of algorithms, appropriate for driving down the road, and a different set of algorithms, to actually solve the “intersections” problem. 

The intersection problem in Duckietown has several steps: 

1. Identifying the beginning of the intersection (identified with a horizontal red line on the road floor)
2. Stopping at the red line, before engaging the intersection
3. Identifying what kind of intersection it is (3-way or 4-way, according to the Duckietown appearance specifications at the time of writing)
4. Identifying the relative position of the Duckiebot at the intersection, hence the available routes forward
5. Choosing a route
6. Identifying when it is appropriate to engage the intersection to avoid potentially colliding with other Duckiebots (e.g., is there a centralized coordinator – a traffic light – or not?)
7. Engaging and navigating the intersection toward the chosen feasible route
8. Switching the state back to lane following. 

Easier said than done, right?

For each of the points above different approaches could be used. This project focuses on improving the baseline solutions for points 2., and most importantly, 7. of the above.

The real challenge is the actual driving across the intersection (in a safe way, i.e., by “keeping your lane”), because the features that provide robust feedback control in the lane following pipeline are not present inside intersections. The baseline solution for this problem in Duckietown is open loop control, relying on the model of the Duckiebots and the Duckietown to magic-tune a few parameters and the curves just about right. 

As all students of autonomy know, open-loop control is ideally perfect (when all models are known exactly), but it is practically pretty useless on its own, as “all models are wrong” [learn why, e.g., in the Modeling of a Differential Drive robot class]. 

In this project, the authors seek to close the loop around intersection navigation, and chose to use an algorithm called “DBSCAN” (Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise) to do it. 

DBSCAN (Density-Based Spatial Clustering of Applications with Noise – wiki) is a clustering algorithm that groups data points based on density, identifying clusters of varying shapes and filtering out noise. It is used to find the red stop lines at intersections without needing predefined geometric priors (colors, shapes, or fixed positions). This allows to track meaningful visual features in intersections efficiently, localize with respect to them, and hence attempt to navigate along optimal precomputed trajectories depending on the chosen direction.