# Robust Asynchronous Planning via Auto-Formalization

arXiv: https://arxiv.org/abs/2606.00981 · HTML: https://mlsanity.com/paper/2606.00981/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 53 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 29 of 29)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)
- [WikiHow: A Large Scale Text Summarization Dataset](https://mlsanity.com/paper/1810.09305/) (2018)
- [AdaPlanner: Adaptive Planning from Feedback with Language Models](https://mlsanity.com/paper/2305.16653/) (2023)
- [Generalized Planning in PDDL Domains with Pretrained Large Language Models](https://mlsanity.com/paper/2305.11014/) (2023)
- [Lean Workbook: A large-scale Lean problem set formalized from natural language math problems](https://mlsanity.com/paper/2406.03847/) (2024)
- [Chain of Thoughtlessness? An Analysis of CoT in Planning](https://mlsanity.com/paper/2405.04776/) (2024)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [Plug in the Safety Chip: Enforcing Constraints for LLM-driven Robot Agents](https://mlsanity.com/paper/2309.09919/) (2023)
- [Reasoning about Goals, Steps, and Temporal Ordering with WikiHow](https://mlsanity.com/paper/2009.07690/) (2020)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Graph-enhanced Large Language Models in Asynchronous Plan Reasoning](https://mlsanity.com/paper/2402.02805/) (2024)
- [Learning adaptive planning representations with natural language guidance](https://mlsanity.com/paper/2312.08566/) (2023)
- [Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming](https://mlsanity.com/paper/2410.12112/) (2024)
- [Planetarium: A Rigorous Benchmark for Translating Text to Structured Planning Languages](https://mlsanity.com/paper/2407.03321/) (2024)
- [Flatland-RL : Multi-Agent Reinforcement Learning on Trains](https://mlsanity.com/paper/2012.05893/) (2020)
- [Robotouille: An Asynchronous Planning Benchmark for LLM Agents](https://mlsanity.com/paper/2502.05227/) (2025)
- [Text2World: Benchmarking Large Language Models for Symbolic World Model Generation](https://mlsanity.com/paper/2502.13092/) (2025)
- [On the Limit of Language Models as Planning Formalizers](https://mlsanity.com/paper/2412.09879/) (2024)
- [Plan-over-Graph: Towards Parallelable LLM Agent Schedule](https://mlsanity.com/paper/2502.14563/) (2025)
- [CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planning](https://mlsanity.com/paper/2410.22225/) (2024)
- [Executable Counterfactuals: Improving LLMs' Causal Reasoning Through Code](https://mlsanity.com/paper/2510.01539/) (2025)
- [Language Model as Planner and Formalizer under Constraints](https://mlsanity.com/paper/2510.05486/) (2025)

## Abstract (arXiv)

LLMs can plan by generating schedules directly as a Planner, or by translating a task into a formal specification for a solver as a Formalizer. Most real-world tasks are asynchronous, with non-uniform durations, concurrency, and execution-time changes, yet existing benchmarks hardly cover them. We unify asynchronous planning under one formulation and release three benchmarks spanning task-graph scale, grounded state and resource constraints, and execution-time events. Surprisingly, PDDL2.1, the formalism built for temporal planning, is the weakest pipeline. On AsyncPlan-XXL it averages 30.8% plan accuracy, against 81.7% for the Planner and 94.0% for a CP-SAT Formalizer. The gap widens with scale, and at 100 actions the three pipelines reach 9.0%, 44.5%, and 82.5%, respectively. The formalism is not to blame. Compiled from the same model-extracted intermediate representation, PDDL2.1 and CP-SAT reach nearly identical accuracy (81.6% vs. 81.5%), and gold task graphs reach 100% for both. What remains is a bottleneck shared by every pipeline: recovering the task graph from language. Execution-time events further degrade every pipeline, yet updating only event-induced constraints reaches 81.6% versus 41.6% for full regeneration. Robust asynchronous planning thus hinges not on the expressiveness of the target formalism but on how reliably a model can write and edit it, and a well-chosen interface can let a weaker model match a stronger one.