Robots have become ubiquitous in modern life, but their autonomous application has, thus far, been relegated to well known, well structured, or benign environments. Practical guarantees for robotic path planning in unknown environments have been elusive. This work explores three distinct problems in robotic planning and exploration in unknown environments and their interconnections. First, information gathering is considered in an environment with known obstacles. An algorithm is developed which solves the information gathering problem while providing a probabilistic guarantee on localization. The algorithm's behavior is analyzed, and a practical demonstration is presented. Second, multi-robot exploration and tracking of multiple objects is explored. A centralized planning algorithm is developed which provides a guarantee on maintaining tracking accuracy of located objects while continuing exploration. Finally, the problem of minimum time planning under uncertain or incomplete maps is considered, and an optimal planner which guarantees collision avoidance is developed. This planner allows near real-time computation while proving smooth dynamically feasible trajectories.