UC San Diego

The ability for a mobile robot to autonomously and efficiently build a map of an environment, termed robotic exploration, is long sought after by researchers and industry professionals. Existing work in this field focuses on local continuous-space optimization or global discrete-space search over hand-designed graph structures with information-theoretic objectives. Global optimization is critical in practice to achieve a precise trade-off between exploration of new areas and map refinement in observed areas. Many existing approaches solve the optimization with a gradient-based method with poor convergence properties, or by heavily constraining the optimization to a lower dimensional search space. A major contribution of this thesis is the automated construction of a graph of potential robot trajectories, optimized to capture long-horizon maximization of the map's information content. The graph represents a significantly larger space of promising robot trajectories compared to existing motion primitive approaches, leading to a combined improvement in exploration speed and uncertainty reduction. This work also provides a thorough evaluation and comparison of several state-of-the-art autonomous exploration techniques over a large dataset of simulated environments as well as several physical robot trials in cluttered environments.