Jun 21, 2025
Certifiably-Correct Mapping for Safe Navigation Despite Odometry Drift
Certifiably-Correct Mapping for Safe Navigation Despite Odometry Drift
We introduce a mapping framework that guarantees safe navigation by certifying obstacle-free regions—even under odometry drift—using deflated ESDFs and convex polytopes.
We introduce a mapping framework that guarantees safe navigation by certifying obstacle-free regions—even under odometry drift—using deflated ESDFs and convex polytopes.
Ensuring safe and reliable navigation in uncertain environments is a fundamental challenge in robotics. This paper, Certifiably-Correct Mapping for Safe Navigation Despite Odometry Drift, presents a novel framework that guarantees correctness of obstacle maps even when vision-based odometry drifts over time. Traditional mapping methods often assume perfect localization, but this can lead to critical safety failures in the presence of drift. To address this, the authors propose a methodology to construct and maintain certifiably-correct maps, where the claimed free space is always a subset of the true free space—ensuring that safety is never compromised.
A key contribution of the work lies in the development of Certified Euclidean Signed Distance Fields (C-ESDFs). This method deflates the estimated distance to obstacles at every voxel, using the pose uncertainty of the robot’s odometry. By bounding the error ellipsoid of each voxel based on incremental pose covariance, the algorithm guarantees that the ESDF always underestimates distance to obstacles—avoiding overly optimistic planning that could lead to collisions. The update is lightweight, fully parallelizable on a GPU, and integrates seamlessly into modern mapping stacks like Voxblox and NvBlox. This ESDF-based correction ensures a certified-safe planning layer even as localization uncertainty increases.
Through extensive experiments on the Replica dataset and real-world tests with a ground rover, the certified ESDF method is shown to significantly outperform baseline and heuristic mapping strategies. While baseline ESDFs suffer from high violation rates (over 50% in some cases), the certified version brings this down to near-zero, with only minor trade-offs in mapped free space volume. Visualizations reveal how the certified maps actively shrink uncertain regions over time, while maintaining correctness around the robot’s immediate vicinity.
The practical impact is demonstrated in rover experiments where a robot must reverse through a tunnel it previously mapped. While the baseline ESDF led to a collision due to drift-induced error, the certified ESDF correctly deflated the map, allowing the onboard safety filter to prevent the robot from entering potentially unsafe zones. This real-time correction capability highlights the value of the certified ESDF framework in ensuring robust and fail-safe autonomous navigation—especially in blind-spot conditions where new sensor data is unavailable.
Ensuring safe and reliable navigation in uncertain environments is a fundamental challenge in robotics. This paper, Certifiably-Correct Mapping for Safe Navigation Despite Odometry Drift, presents a novel framework that guarantees correctness of obstacle maps even when vision-based odometry drifts over time. Traditional mapping methods often assume perfect localization, but this can lead to critical safety failures in the presence of drift. To address this, the authors propose a methodology to construct and maintain certifiably-correct maps, where the claimed free space is always a subset of the true free space—ensuring that safety is never compromised.
A key contribution of the work lies in the development of Certified Euclidean Signed Distance Fields (C-ESDFs). This method deflates the estimated distance to obstacles at every voxel, using the pose uncertainty of the robot’s odometry. By bounding the error ellipsoid of each voxel based on incremental pose covariance, the algorithm guarantees that the ESDF always underestimates distance to obstacles—avoiding overly optimistic planning that could lead to collisions. The update is lightweight, fully parallelizable on a GPU, and integrates seamlessly into modern mapping stacks like Voxblox and NvBlox. This ESDF-based correction ensures a certified-safe planning layer even as localization uncertainty increases.
Through extensive experiments on the Replica dataset and real-world tests with a ground rover, the certified ESDF method is shown to significantly outperform baseline and heuristic mapping strategies. While baseline ESDFs suffer from high violation rates (over 50% in some cases), the certified version brings this down to near-zero, with only minor trade-offs in mapped free space volume. Visualizations reveal how the certified maps actively shrink uncertain regions over time, while maintaining correctness around the robot’s immediate vicinity.
The practical impact is demonstrated in rover experiments where a robot must reverse through a tunnel it previously mapped. While the baseline ESDF led to a collision due to drift-induced error, the certified ESDF correctly deflated the map, allowing the onboard safety filter to prevent the robot from entering potentially unsafe zones. This real-time correction capability highlights the value of the certified ESDF framework in ensuring robust and fail-safe autonomous navigation—especially in blind-spot conditions where new sensor data is unavailable.
Ensuring safe and reliable navigation in uncertain environments is a fundamental challenge in robotics. This paper, Certifiably-Correct Mapping for Safe Navigation Despite Odometry Drift, presents a novel framework that guarantees correctness of obstacle maps even when vision-based odometry drifts over time. Traditional mapping methods often assume perfect localization, but this can lead to critical safety failures in the presence of drift. To address this, the authors propose a methodology to construct and maintain certifiably-correct maps, where the claimed free space is always a subset of the true free space—ensuring that safety is never compromised.
A key contribution of the work lies in the development of Certified Euclidean Signed Distance Fields (C-ESDFs). This method deflates the estimated distance to obstacles at every voxel, using the pose uncertainty of the robot’s odometry. By bounding the error ellipsoid of each voxel based on incremental pose covariance, the algorithm guarantees that the ESDF always underestimates distance to obstacles—avoiding overly optimistic planning that could lead to collisions. The update is lightweight, fully parallelizable on a GPU, and integrates seamlessly into modern mapping stacks like Voxblox and NvBlox. This ESDF-based correction ensures a certified-safe planning layer even as localization uncertainty increases.
Through extensive experiments on the Replica dataset and real-world tests with a ground rover, the certified ESDF method is shown to significantly outperform baseline and heuristic mapping strategies. While baseline ESDFs suffer from high violation rates (over 50% in some cases), the certified version brings this down to near-zero, with only minor trade-offs in mapped free space volume. Visualizations reveal how the certified maps actively shrink uncertain regions over time, while maintaining correctness around the robot’s immediate vicinity.
The practical impact is demonstrated in rover experiments where a robot must reverse through a tunnel it previously mapped. While the baseline ESDF led to a collision due to drift-induced error, the certified ESDF correctly deflated the map, allowing the onboard safety filter to prevent the robot from entering potentially unsafe zones. This real-time correction capability highlights the value of the certified ESDF framework in ensuring robust and fail-safe autonomous navigation—especially in blind-spot conditions where new sensor data is unavailable.
