Graph-Based Mapping & Navigation

Overview

The project took inspiration from Ivanov and Markgraf’s paper Lane Detection using Graph Search and Geometric Constraints for Formula Student Driverless. Their Cone Lane Connector algorithm detects two track boundaries from sparse points by combining depth-first graph search, backtracking, geometric constraints, and candidate ranking. It was designed for compact Formula Student tracks whose layouts and dimensions remain within a relatively narrow operating domain.

Our target was broader: reconstruct tracks substantially larger than those used in Formula Student, from a feature map that was not fixed in advance but expanded as the vehicle explored. Boundary detection also could not depend on cone color. This required an architectural redesign rather than a direct implementation of the paper. The initial Python prototype became computationally expensive as the number of mapped points grew, so the core algorithm was re-engineered in C++. Recursive candidate generation was replaced by an explicit iterative search, while warm-starting preserved useful search state between updates and geometric constraints pruned invalid branches early. The paper’s neural ranking stage was replaced with configurable geometric scoring because a model trained on FSAE layouts did not generalize reliably to tracks with different widths, scales, and geometry.

Planning was divided into two phases. During the exploration lap, the lane detector ran at 10 Hz and continuously generated local left and right boundaries and an online drivable racing line. These local results accumulated into a persistent global map. After loop closure, mapping stopped and a second pass used the complete circuit to optimize the full racing line and its speed profile. Curvature-based limits were refined through alternating braking and acceleration passes, and a 100 Hz Pure Pursuit controller followed the result using a speed-dependent lookahead distance.

Assetto Corsa provided the unknown-track simulation, vehicle feedback, and closed-loop dynamics. ROS 2 connected the lane detector, controller, visualization, and virtual Xbox 360 interface, while Rerun displayed graph vertices, candidate edges, reconstructed boundaries, and both local and global racing lines. Test runs reached 50 km/h during mapping and 150 km/h on the completed racing line.