Robust Asynchronous Planning via Auto-Formalization

• URL: http://arxiv.org/abs/2606.00981v1
• Date: Sun, 31 May 2026 03:28:42 GMT
• Title: Robust Asynchronous Planning via Auto-Formalization
• Abstract summary: LLMs can plan by either generating action sequences directly as a Planner or translating tasks into domain specific language for an external solver as a Formalizer.<n>We unify these challenges that under a single formulation and introduce the first three benchmarks that address each at scale.<n>We conclude the choice of formal representation primarily determines whether planning scales.
• Score: 18.999996458563373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: LLMs can plan by either generating action sequences directly as a Planner or translating tasks into domain specific language for an external solver as a Formalizer. While most real-world tasks are asynchronous with non-uniform durations, concurrency, and execution-time constraints, existing benchmarks hardly cover them. We unify these asynchronous planning challenges under a single formulation and introduce the first three benchmarks that address each at scale. We conclude that the choice of formal representation primarily determines whether planning scales: as dependency graphs grow from 5 to 100 actions, Planner collapses from 96% to 5% plan accuracy and PDDL2.1 Formalizer from 13% to 0%, while CP-SAT Formalizer averages 94% and still achieves 83% at 100 actions. Faithfulness diagnostics show that PDDL2.1's predicate-based planning representation becomes brittle compared to general constraint satisfaction programs, when LLMs must keep predicates, effects, and goals consistent. Execution-time updates of planning constraints further degrade performance sharply (Planner 23.9%, PDDL2.1 0.7%, CP-SAT 46.1%), but a state-aware repair strategy that updates only event-induced constraints recovers CP-SAT Formalizer to 84.5%.

Related papers

• SUN: Persistent Programs For Language-Grounded Control-to-Learning-to-Real Policies [61.941546372624686]
  Existing protocols discard task semantics, leaving rewards hand-crafted and behavior drifting from what control verified.<n>We introduce Semantically UNified (SUN) Programs, typed executables where geometric and contact relations are defined once and compiled into aligned Model Predictive Control.<n>Our system, Kuafu, automatically synthesizes SUN Programs from language and scene semantics, screens feasibility via MPC, and retains semantics while training stage-conditioned policies.
  arXiv  Detail & Related papers  (2026-08-31T17:59:16Z)
• PDDLCoder: Agentic PDDL Generation for LLM-Assisted Symbolic Planning [0.4433169165028139]
  We present PDDLCoder, an agentic framework for PDDL generation from natural language that iteratively generates, analyzes, and refines planning specifications.<n>Experiments on the NL-pddlgym test set show that PDDLCoder generates applicable plans for 89.6% of tested planning problems.
  arXiv  Detail & Related papers  (2026-08-17T14:34:56Z)
• From Feasibility to Desirability: Plan, Learn, Adapt (PLA) Framework for Personalized On-Device Itinerary Generation [1.6391892978433935]
  Plan, Learn, Adapt is a three-stage framework for personalized on-device itinerary generation.<n>On 2,519 pairwise human comparisons across more than 100 U.S. cities, PLA achieves a 67.8% win rate, 11.2 percentage points above the best single planner, with 100% feasibility.<n>In production deployment within FlyEnJoy, PLA increased itinerary completion rates by 91%, with 109.9 ms average on-device latency.
  arXiv  Detail & Related papers  (2026-07-17T01:52:02Z)
• PlanCompiler: A Deterministic Compilation Architecture for Structured Multi-Step LLM Pipelines [0.0]
  We present PlanCompiler, a compilation architecture for structured pipelines that separates planning from execution through a typed node registry registry.<n>PlanCompiler produces a typed plan over a fixed registry of primitives, validates that plan against explicit structural and type constraints, and compiles only validated plans into executable Python.
  arXiv  Detail & Related papers  (2026-04-08T00:54:41Z)
• GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models [4.400420377775205]
  We present GenePlan, a novel framework that leverages large language model (LLM) to generate domain-dependent generalized planners.<n>GenePlan iteratively evolves interpretable Python planners that minimize plan length across diverse problem instances.<n>In empirical evaluation, GenePlan achieved an average SAT score of 0.91, closely matching the performance of the state-of-the-art planners.
  arXiv  Detail & Related papers  (2026-03-10T10:32:05Z)
• Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation [1.2832858109291982]
  Large language models (LLMs) can serve as viable planners alongside classical symbolic methods.<n>We present PyPDDLEngine, an open-source Planning Domain Definition Language (PDDL) simulation engine.<n>We evaluate four approaches on 102 International Planning Competition (IPC) Blocksworld instances under a uniform 180-second budget.
  arXiv  Detail & Related papers  (2026-03-06T09:16:49Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• NATURAL PLAN: Benchmarking LLMs on Natural Language Planning [109.73382347588417]
  We introduce NATURAL PLAN, a realistic planning benchmark in natural language containing 3 key tasks: Trip Planning, Meeting Planning, and Calendar Scheduling. We focus our evaluation on the planning capabilities of LLMs with full information on the task, by providing outputs from tools such as Google Flights, Google Maps, and Google Calendar as contexts to the models.
  arXiv  Detail & Related papers  (2024-06-06T21:27:35Z)
• PDDLEGO: Iterative Planning in Textual Environments [56.12148805913657]
  Planning in textual environments has been shown to be a long-standing challenge even for current models. We propose PDDLEGO that iteratively construct a planning representation that can lead to a partial plan for a given sub-goal. We show that plans produced by few-shot PDDLEGO are 43% more efficient than generating plans end-to-end on the Coin Collector simulation.
  arXiv  Detail & Related papers  (2024-05-30T08:01:20Z)
• AdaPlanner: Adaptive Planning from Feedback with Language Models [56.367020818139665]
  Large language models (LLMs) have recently demonstrated the potential in acting as autonomous agents for sequential decision-making tasks. We propose a closed-loop approach, AdaPlanner, which allows the LLM agent to refine its self-generated plan adaptively in response to environmental feedback. To mitigate hallucination, we develop a code-style LLM prompt structure that facilitates plan generation across a variety of tasks, environments, and agent capabilities.
  arXiv  Detail & Related papers  (2023-05-26T05:52:27Z)
• A Framework for Neurosymbolic Robot Action Planning using Large Language Models [3.0501524254444767]
  We present a framework aimed at bridging the gap between symbolic task planning and machine learning approaches. The rationale is training Large Language Models (LLMs) into a neurosymbolic task planner compatible with the Planning Domain Definition Language (PDDL) Preliminary results in selected domains show that our method can: (i) solve 95.5% of problems in a test data set of 1,000 samples; (ii) produce plans up to 13.5% shorter than a traditional symbolic planner; (iii) reduce average overall waiting times for a plan availability by up to 61.4%.
  arXiv  Detail & Related papers  (2023-03-01T11:54:22Z)
• A feasibility study of a hyperparameter tuning approach to automated inverse planning in radiotherapy [68.8204255655161]
  The purpose of this study is to automate the inverse planning process to reduce active planning time while maintaining plan quality. We investigated the impact of the choice of dose parameters, random and Bayesian search methods, and utility function form on planning time and plan quality. Using 100 samples was found to produce satisfactory plan quality, and the average planning time was 2.3 hours.
  arXiv  Detail & Related papers  (2021-05-14T18:37:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.