Preprint

OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

Babak Barazandeh Subhabrata Majumdar G. Michailidis

Jul 2026 · 0 citations · 25 references

Computer Science

TL;DR

This work reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiates OTAP via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs, which is a pseudo-metric that is provably invariant to dependency-preserving reorderings and has bounded sensitivity to redundant steps.

Abstract

Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish a sound solution from one that succeeds by luck, and says nothing about why a failed run went wrong. Exact matching penalizes plans that are valid but reordered or decomposed differently from the reference. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a pseudo-metric that is provably invariant to dependency-preserving reorderings and has bounded sensitivity to redundant steps. Its unbalanced marginals handle missing or hallucinated steps without forcing a match, and its soft coupling accommodates variation in plan granularity. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its advantage tracks the fidelity of the dependency graph: largest where edges follow from operator semantics, smallest where they are inferred from free text. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available.

arXiv Semantic Scholar

View source

Similar papers

Preprint Jul 2026

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

GATS (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inference while achieving superior planning performance, is presented.

Maureese Williams, Dymitr Nowicki · 0 citations

Preprint Aug 2026

An Actionable Diagnosis of Multilingual, Multi-Agent Planning Failures

To test whether the taxonomy supports mitigation, TART, Taxonomy-Guided Actionable Representation, is introduced that makes the taxonomy's key aspects explicit to the planner and downstream sub-agents and consistently improves performance.

Vikas Pahuja, J. Brokman, O. Hofman et al. · 0 citations

Preprint Jul 2026

EvoPlan: Evolutionary Neuro-Symbolic Robot Planning with Spatio-Temporal Guarantees

LLM-based robot planners are fluent but cannot guarantee that their plans are executable or safe. Classical PDDL planners can guarantee these properties, but only after the problem is fully specified, and they make poor use of an LLM's ability to read context and repair plans. This paper presents a neuro-symbolic framework with three parts. All LLM calls use a locally-hosted open-weight model, so the pipeline can be deployed on-robot with no cloud dependency. First, an offline procedure that mines a single global Signal Temporal Logic (STL) constraint on mobility from demonstration data. The procedure recovers codified rules (e.g., stopping at red lights, mined from nuPlan driving logs) or population preferences (e.g., social-navigation comfort, mined from SCAND teleoperation), depending on what the demonstrations encode. Because the demonstrations are a one-class signal, we generate the missing negatives with counterfactual perturbations and an LLM violation generator and then fit the constraint by evolutionary search. We use the mined constraint to shield a vision-language driving policy on Bench2Drive and two discrete-action navigation policies on HA-VLN-CE. Second, an evolutionary PDDL planner: an LLM proposes and repairs plans, programmatic validators decide which ones survive, and the validated portion of the plan grows over iterations. We test the planner on the open-world ALFWorld Text benchmark, where it beats strong baselines and stays robust when the goal vocabulary does not match the action-model vocabulary. Third, a constrained execution loop: the planner's plan is compiled into waypoints, the waypoints are checked against the mined constraint, and the planner re-plans on a violation. We illustrate the full pipeline via demonstrations using the Gazebo simulator.

Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang et al. · 0 citations

Preprint Jul 2026

Leveraging Trajectory Graphs for Pre-Execution Error Diagnosis in Agentic LLM Systems

This work proposes Trajectory Graph Copilot, a novel framework that acts as a ``copilot'' for LLM agents by diagnosing potential action errors before they are executed, significantly enhancing the agent's ability to complete long-horizon tasks successfully.

Xu Zheng, Zhuomin Chen, Chaohao Lin et al. · 0 citations

Preprint Aug 2026

PlanPO: Group Planning-Aware Policy Optimization for Multi-Turn Agentic LLMs

Group Planning-aware Policy Optimization (PlanPO) is proposed, a simple yet effective RL method for learning generalizable planning abilities beyond task-specific high-quality behavior patterns that enables agents to actively learn generalizable and deliberate behaviors spanning interaction planning and textual generation from high-quality rollouts, without degenerating into vanilla length minimization.

D. Liang, Liyuan He, Xuan Feng et al. · 0 citations

Preprint Jul 2026

Fantastic Adaptive Taxonomies and How to Use Them

It is argued that an agent system should maintain an explicit representation of how it fails, induced from its own behavior and reusable wherever failure feedback is needed, and AdaMAST builds this representation by converting a target system's traces into a compact, evidence-grounded failure taxonomy.

M. Cemri, Andrei Cojocaru, Melissa Z. Pan et al. · 0 citations