Don't Miss a Deadline: Online Temporal Planning for Multi-Goal LLM Agents under Partial Observability

Many real-world applications require Large Language Model (LLM) agents to complete multiple tasks subject to strict temporal constraints. Existing methods often assume a static environment where all task specifications are known a priori. However, in many practical robotic domains, agents only have partial observability due to limited sensory capabilities, and critical task information must be actively gathered through exploration or exploratory actions. To address these challenges, we propose a novel online temporal multi-goal planning framework for LLM agents under partial observability. Specifically, we first construct a partial Simple Temporal Network (STN) derived from the agent's current knowledge base. Then, this partial STN serves as a guide for the LLM to balance the exploration-exploitation trade-off while strictly adhering to temporal constraints during action selection. Additionally, we leverage the STN to monitor action validity; when a constraint violation is detected, semantic feedback is integrated into the prompt to trigger iterative action refinement. To empirically evaluate our approach, we construct a new benchmark, DeadlineBench, which requires LLM agents to execute multi-goal tasks under both temporal constraints and partial observability. Experimental results show that our approach consistently outperforms the state-of-the-art methods in terms of success rate across all benchmarks.