  We consider the case in which a robot has to navigate in an unknown
environment but does not have enough on-board power or payload to carry a
traditional depth sensor (e.g., a 3D lidar) and thus can only acquire a few
(point-wise) depth measurements. We address the following question: is it
possible to reconstruct the geometry of an unknown environment using sparse and
incomplete depth measurements? Reconstruction from incomplete data is not
possible in general, but when the robot operates in man-made environments, the
depth exhibits some regularity (e.g., many planar surfaces with only a few
edges); we leverage this regularity to infer depth from a small number of
measurements. Our first contribution is a formulation of the depth
reconstruction problem that bridges robot perception with the compressive
sensing literature in signal processing. The second contribution includes a set
of formal results that ascertain the exactness and stability of the depth
reconstruction in 2D and 3D problems, and completely characterize the geometry
of the profiles that we can reconstruct. Our third contribution is a set of
practical algorithms for depth reconstruction: our formulation directly
translates into algorithms for depth estimation based on convex programming. In
real-world problems, these convex programs are very large and general-purpose
solvers are relatively slow. For this reason, we discuss ad-hoc solvers that
enable fast depth reconstruction in real problems. The last contribution is an
extensive experimental evaluation in 2D and 3D problems, including Monte Carlo
runs on simulated instances and testing on multiple real datasets. Empirical
results confirm that the proposed approach ensures accurate depth
reconstruction, outperforms interpolation-based strategies, and performs well
even when the assumption of structured environment is violated.
