Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming

Yilun Hao, Yang Zhang, Chuchu Fan

Massachusetts Institute of Technology

ICLR 2025

See our closely related work specifically designed for complex realistic travel planning problems

Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools (NAACL' 2025 Main)

Abstract

While large language models (LLMs) have recently demonstrated strong potential in solving planning problems, there is a trade-off between flexibility and complexity. LLMs, as zero-shot planners themselves, are still not capable of directly generating valid plans for complex planning problems such as multi-constraint or long-horizon tasks. On the other hand, many frameworks aiming to solve complex planning problems often rely on task-specific preparatory efforts, such as task-specific in-context examples and pre-defined critics/verifiers, which limits their cross-task generalization capability. In this paper, we tackle these challenges by observing that the core of many planning problems lies in optimization problems: searching for the optimal solution (best plan) with goals subject to constraints (preconditions and effects of decisions). With LLMs' commonsense, reasoning, and programming capabilities, this opens up the possibilities of a universal LLM-based approach to planning problems. Inspired by this observation, we propose LLMFP, a general-purpose framework that leverages LLMs to capture key information from planning problems and formally formulate and solve them as optimization problems from scratch, with no task-specific examples needed. We apply LLMFP to 9 planning problems, ranging from multi-constraint decision making to multi-step planning problems, and demonstrate that LLMFP achieves on average 83.7% and 86.8% optimal rate across 9 tasks for GPT-4o and Claude 3.5 Sonnet, significantly outperforming the best baseline (direct planning with OpenAI o1-preview) with 37.6% and 40.7% improvements. We also validate components of LLMFP with ablation experiments and analyzed the underlying success and failure reasons.

An overview of LLMFP and how it is applied to a coffee supply chain example. All sections in yellow are inputs, and all sections in blue are steps accomplished by LLMs. With task description, background information, and query as inputs, LLMFP defines the goal, decision vari- ables, and constraints of this optimization problem, identifies all necessary variables and summarizes their key information into a JSON representation, generates codes to solve the optimization problem, executes the codes and formats the execution results, and performs self-assessment for each step.

BibTeX

@article{hao2024planning,

title={Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming},

author={Hao, Yilun and Zhang, Yang and Fan, Chuchu},

journal={arXiv preprint arXiv:2410.12112},

year={2024}

}

Page updated

Google Sites

Report abuse