Efforts to understand our world drive the development of autonomous systems capable of effectively planning exploration tasks across applications like scientific sampling, environmental monitoring, surveillance, and search and rescue. When deployed in real-world settings, these robotic systems face dynamic changes and environmental uncertainties that dramatically increase decision complexity, making planning challenging. By leveraging the geometric properties of target areas, planning can be reframed as a combinatorial optimization problem, reducing complexity and enabling the breakdown of tasks into manageable subproblems. This talk presents a hierarchical approach to creating robust exploration and coverage plans, focusing on (i) generating global trajectory plans and (ii) adapting these trajectories in response to dynamic changes. We will discuss single and multi-robot coverage strategies that consider obstacles, environmental features, and sensor-specific data collection optimization, along with approaches to incorporate uncertainties into these plans. Real-world applications, such as automated scientific sampling in marine environments, will demonstrate the feasibility and impact of these techniques.