This thesis develops planning, monitoring, and interaction frameworks that advance robots towards human-level planning intelligence in large, complicated environments. Across six chapters, we progress from domain-specific autonomous systems to general planning algorithms, spanning underwater and household robotics. In the marine domain, we build GENIoS_Python for real-time flow-informed glider navigation and an anomaly detection algorithm for autonomous health monitoring - together forming a complete autonomous glider operation stack. We then develop OceanChat and OceanPlan, which for the first time enable natural language AUV piloting through LLM-guided hierarchical task and motion planning with replanning. Transitioning to household robotics, we propose Inter-LLM, an interleaved LLM and motion planning algorithm that grounds semantic reasoning with physical execution costs for scalable multi-object collection. Finally, we present Inter-POMDP, an interleaved POMDP planning algorithm that systematically handles extensive uncertainty in multi-object search across unknown multi-room environments. Unifying these contributions is a consistent pursuit: like humans, robots should decompose complex missions hierarchically, adapt to unexpected situations in real time, reason jointly about semantics and physics, and interact with users through natural language. We believe the frameworks developed in this thesis represent meaningful steps towards this vision.