Navigable Space Construction from Sparse Noisy Point Clouds

Robot navigation with noisy perception is a fundamental but challenging task. We present a framework for creating navigable space from cluttered point clouds generated by low-end sensors with high sparsity and noise. Our method incrementally seeds and creates local convex regions free of obstacle points along robot's trajectory. Then a dense version of the point cloud is reconstructed through a map point regulation process where the original noisy map points are first projected onto a series of local convex hull surfaces, after which those points falling inside the convex hulls are culled. We have tested our proposed framework using a public autonomous driving dataset and a manually built structured environment for various performance evaluation, as well as inside our research building for ground robot navigation tasks. Our results reveal that the reconstructed navigable space has small volume loss (error) comparing with the ground truth, and the method is highly efficient, allowing real-time navigation computation.