TGPO: Trace-Guided Policy Optimization for Robot Task Planning via Verifiable Subgoal Generation

The gist Robot task planning in real-world environments requires mapping abstract natural language instructions to executable action sequences under long horizons and complex constraints, and this work proposes Trace-Guided Policy Optimization (TGPO), a reinforcement learning framework that improves structured subgoal generation through verifier-grounded rewards, external correction of intermediate reasoning traces, and constrained policy updates <ref:2602.12244#pg18>.

How it works

The core idea is to formulate robot task planning as learning to generate verifiable subgoals in the Planning Domain Definition Language (PDDL), bridging language understanding and symbolic planning <ref:2602.12244#pg4>. This involves learning a policy that generates verifiable subgoals, which, when coupled with a symbolic planner, enables scalable robot task planning in large-scale environments with long horizons, complex constraints, and abstract instructions <ref:2602.12244#pg6>. The policy is trained to maximize verifier-grounded rewards reflecting subgoal feasibility and overall task success <ref:2602.12244#pg4>.

Trace-Guided Policy Optimization (TGPO)

TGPO is a reinforcement learning algorithm designed to tackle the challenges of sparse, noisy, and delayed feedback in subgoal formulation by introducing structured learning signals at the level of intermediate reasoning <ref:2602.12244#pg4>. It incorporates three components:

1. A verifier-grounded reward that provides outcome-level supervision based on subgoal feasibility and task completion <ref:2602.12244#pg4>.

2. Trace-guided refinement, where an auxiliary model identifies and corrects errors in intermediate reasoning traces, providing fine-grained guidance beyond scalar rewards <ref:2602.12244#pg4>.

3. Constrained policy optimization, which integrates corrected traces into training via token-level constraints while preserving autoregressive generation <ref:2602.12244#pg4>.

Planning Formulation and Objectives

The planning problem is formulated as generating a sequence of intermediate PDDL subgoals (T, G) where T is a sequence of natural-language decomposition steps and G is a sequence of grounded symbolic subgoals <ref:2602.12244#pg4>. Each subgoal gk defines a subproblem that can be solved by a symbolic planner, with the final plan A = op K k=1 obtained by composing the subplans <ref:2602.12244#pg4>. The reward function is defined as R(T, G) = Rfeas(G) · Rcomp(T, G), where Rfeas ∈ 0, 1 indicates whether all subgoals are solvable and Rcomp ∈ [0, 1] measures task completion <ref:2602.12244#pg4>.

Training Data Generation and Pipeline

A large-scale dataset is constructed by jointly sampling household environments and tasks with controlled diversity <ref:2602.12244#pg6>. This involves constructing scene distributions from the Habitat Synthetic Scene Dataset (HSSD) [45] and synthesizing task instructions using a large language model jointly conditioned on S, D, and a sampled user persona <ref:2602.12244#pg6>. Structured outputs (T, G)—including decomposition traces and grounded subgoals—are generated using a prompting-based planner on this data <ref:2602.12244#pg6>. The training pipeline consists of two stages: supervised fine-tuning (SFT) to initialize the policy and reinforcement learning with TGPO to further optimize it <ref:2602.12244#pg6>.

Evaluation and Scalability

TGPO consistently outperforms prompting-based methods by a large margin, with gains that systematically increase as tasks become more long-horizon, abstract, and ambiguous <ref:2602.12244#pg9>. In the scalability study, TGPO remains stable as graph size increases with minimal degradation (16%), whereas SayPlan and GPT-5 degrade significantly. Furthermore, TGPO’s performance drops by only 16% at the longest horizon, due to its decompose-then-solve structure, which prevents error accumulation by solving subplans sequentially. The system-level evaluation shows that the TGPO policy enables compositional generalization by recombining a fixed set of low-level skills to solve novel long-horizon tasks.

Conclusion

TGPO directly optimizes subgoal feasibility, consistency, and task completion, while a trace-guided training scheme improves learning under sparse and noisy supervision. Experiments across diverse benchmarks demonstrate that TGPO significantly outperforms prior prompting-based planners and learning-based methods, with particularly strong gains on complex, long-horizon, and abstract tasks. Despite these results, limitations include reliance on structured scene representations and assumptions about a predefined symbolic domain.

--- Page 1 ---

The gist Robot task planning in real-world environments requires mapping abstract natural language instructions to executable action sequences under long horizons and complex constraints, and this work proposes Trace-Guided Policy Optimization (TGPO), a reinforcement learning framework that improves structured subgoal generation through verifier-grounded rewards, external correction of intermediate reasoning traces, and constrained policy updates <ref:2602.12244#pg4>.

How it works

The core idea is to formulate robot task planning as learning to generate verifiable subgoals in the Planning Domain Definition Language (PDDL), bridging language understanding and symbolic planning. This involves learning a policy that generates verifiable subgoals, which, when coupled with a symbolic planner, enables scalable robot task planning in large-scale environments with long horizons, complex constraints, and abstract instructions. The policy is trained to maximize verifier-grounded rewards reflecting subgoal feasibility and overall task success.

Trace-Guided Policy Optimization (TGPO)

TGPO is a reinforcement learning algorithm designed to tackle the challenges of sparse, noisy, and delayed feedback in subgoal formulation by introducing structured learning signals at the level of intermediate reasoning. It incorporates three components:

1. A verifier-grounded reward that provides outcome-level supervision based on subgoal feasibility and task completion.

2. Trace-guided refinement, where an auxiliary model identifies and corrects errors in intermediate reasoning traces, providing fine-grained guidance beyond scalar rewards.

3. Constrained policy optimization, which integrates corrected traces into training via token-level constraints while preserving autoregressive generation.

Planning Formulation and Objectives

The planning problem is formulated as generating a sequence of intermediate PDDL subgoals (T, G) where T is a sequence of natural-language decomposition steps and G is a sequence of grounded symbolic subgoals. Each subgoal gk defines a subproblem that can be solved by a symbolic planner, with the final plan A = op K k=1 obtained by composing the subplans. The reward function is defined as R(T, G) = Rfeas(G) · Rcomp(T, G), where Rfeas ∈ 0, 1 indicates whether all subgoals are solvable and Rcomp ∈ [0, 1] measures task completion.

Training Data Generation and Pipeline

A large-scale dataset is constructed by jointly sampling household environments and tasks with controlled diversity. This involves constructing scene distributions from the Habitat Synthetic Scene Dataset (HSSD) [45] and synthesizing task instructions using a large language model jointly conditioned on S, D, and a sampled user persona. Structured outputs (T, G)—including decomposition traces and grounded subgoals—are generated using a prompting-based planner on this data. The training pipeline consists of two stages: supervised fine-tuning (SFT) to initialize the policy and reinforcement learning with TGPO to further optimize it.

Evaluation and Scalability

TGPO consistently outperforms prompting-based methods by a large margin, with gains that systematically increase as tasks become more long-horizon, abstract, and ambiguous. In the scalability study, TGPO remains stable as graph size increases with minimal degradation (16%), whereas SayPlan and GPT-5 degrade significantly. Furthermore, TGPO’s performance drops by only 16% at the longest horizon, due to its decompose-then-solve structure, which prevents error accumulation by solving subplans sequentially. The system-level evaluation shows that the TGPO policy enables compositional generalization by recombining a fixed set of low-level skills to solve novel long-horizon tasks.

1. Bold subgoal generation via learning: The system can move beyond prompting-based decomposition by learning a policy that generates verifiable subgoals, which allows for structured, grounded planning instead of brittle translation into PDDL goals.

2. Trace-guided refinement for error correction: By incorporating trace-guided refinement, where an auxiliary model identifies and corrects errors in intermediate reasoning traces, the AI can overcome the limitations of sparse rewards by leveraging external feedback to fix missing subtasks, incorrect temporal ordering, and incomplete grounding of task intent.

3. Robust long-horizon planning under abstraction: The system achieves robust long-horizon planning in large environments with long horizons and abstract instructions because it optimizes for subgoal feasibility, consistency, and task completion, maintaining performance even when the abstraction ratio is 0.76.

4. Scalability across complexity dimensions: The framework demonstrates strong scalability as it maintains performance while increasing complexity; specifically, TGPO's symbolic planner enforces preconditions and effects, allowing it to maintain feasibility even under dense constraints (degrading by only 3% in constraint complexity).

5. Compositional generalization via two-level system: By separating problem formulation from execution (TGPO (Subgoal) vs. TGPO (E2E)), the AI enables compositional generalization by recombining a fixed set of low-level skills to solve novel long-horizon tasks, achieving a 36% task completion rate on recombined tasks.

Open world language conditioned task planning is crucial for robots operating in large-scale household environments. While many recent works attempt to address this problem using Large Language Models (LLMs) via prompting or training, a key challenge remains scalability. Performance often degrades rapidly with increasing environment size, plan length, instruction ambiguity, and constraint complexity. In this work, we propose Any House Any Task (AHAT), a household task planner optimized for long-horizon planning in large environments given ambiguous human instructions. At its core, AHAT utilizes an LLM trained to map task instructions and textual scene graphs into grounded subgoals defined in the Planning Domain Definition Language (PDDL). These subgoals are subsequently solved to generate feasible and optimal long-horizon plans through explicit symbolic reasoning. To enhance the model's ability to decompose complex and ambiguous intentions, we introduce TGPO, a novel reinforcement learning algorithm that integrates external correction of intermediate reasoning traces into Group Relative Policy Optimization (GRPO). Experiments demonstrate that AHAT achieves significant performance gains over state-of-the-art prompting, planning, and learning methods, particularly in human-style household tasks characterized by brief instructions but requiring complex execution plans.