  Lane detection is a fundamental task in autonomous driving. While the problem
is typically formulated as the detection of continuous boundaries, we study the
problem of detecting lane boundaries that are sparsely marked by 2D points with
many false positives. This problem arises in the Formula Student Driverless
(FSD) competition and is challenging due to its inherent ambiguity. Previous
methods are inefficient and unable to find long-horizon solutions. We propose a
deterministic algorithm called CLC that uses backtracking graph search with a
learned likelihood function to overcome these limitations. We impose geometric
constraints on the lane candidates to guarantee a geometrically sound lane. Our
exhaustive search leads to finding the global optimum in 45% of instances, and
the algorithm is overall robust to up to 50% false positives. Our algorithm
runs in less than 15 ms on a single CPU core, meeting the low latency
requirements of autonomous racing. We extensively evaluate our method on real
data and realistic racetrack layouts, and show that it outperforms the
state-of-the-art by detecting long lanes over 100 m with few (0.6%) critical
failures. This allows our autonomous racecar to drive close to its physical
limits on a previously unknown racetrack without being limited by perception.
We release our dataset with realistic Formula Student racetracks to enable
further research.
