Reconstruction of terrain shape is an important problem for navigating in unstructured environments. Three dimensional sensors, such as LIDAR systems, provide accurate measurements at isolated points in the environment, but the low, forward-looking sensor placement implied by ground-based sensing means that the data density will be highly variable even for benign, flat terrain. More complex environments make the variability in data density even more extreme.

In this project, we are developing a method that addresses this variable data density problem using implicit surface modeling. Our approach uses visibility information to carve the surface and produces not only a terrain estimate but also uncertainty bounds. We formulate the learning problem as a reproducing kernel Hilbert space (RKHS) optimization and derive a subgradient-based stochastic solution, which gives computational efficiency, allows data to be added online, and makes the approach an anytime algorithm. The evaluation, on both synthetic and natural data, clearly demonstrates the effectiveness of the approach and the utility of the space carving visibility information