Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools

• URL: http://arxiv.org/abs/2404.11891v3
• Date: Wed, 29 Jan 2025 17:24:03 GMT
• Title: Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools
• Authors: Yilun Hao, Yongchao Chen, Yang Zhang, Chuchu Fan,
• Abstract summary: Large Language Models (LLMs) struggle to directly generate correct plans for complex multi-constraint planning problems. We propose an LLM-based planning framework that formalizes and solves complex multi-constraint planning problems. Our framework achieves a success rate of 93.9% and is effective with diverse paraphrased prompts.
• Score: 12.875270710153021
• License:
• Abstract: Large Language Models (LLMs) struggle to directly generate correct plans for complex multi-constraint planning problems, even with self-verification and self-critique. For example, a U.S. domestic travel planning benchmark TravelPlanner was proposed in Xie et al. (2024), where the best LLM OpenAI o1-preview can only find viable travel plans with a 10% success rate given all needed information. In this work, we tackle this by proposing an LLM-based planning framework that formalizes and solves complex multi-constraint planning problems as constrained satisfiability problems, which are further consumed by sound and complete satisfiability solvers. We start with TravelPlanner as the primary use case and show that our framework achieves a success rate of 93.9% and is effective with diverse paraphrased prompts. More importantly, our framework has strong zero-shot generalizability, successfully handling unseen constraints in our newly created unseen international travel dataset and generalizing well to new fundamentally different domains. Moreover, when user input queries are infeasible, our framework can identify the unsatisfiable core, provide failure reasons, and offers personalized modification suggestions. We show that our framework can modify and solve for an average of 81.6% and 91.7% unsatisfiable queries from two datasets and prove with ablations that all key components of our framework are effective and necessary. Project page: https://sites.google.com/view/llm-rwplanning.

Related papers

• ChinaTravel: A Real-World Benchmark for Language Agents in Chinese Travel Planning [50.7898120693695]
  We introduce ChinaTravel, a benchmark specifically designed for authentic Chinese travel planning scenarios. We collect the travel requirements from questionnaires and propose a compositionally generalizable domain-specific language. Empirical studies reveal the potential of neuro-symbolic agents in travel planning, achieving a constraint satisfaction rate of 27.9%. We identify key challenges in real-world travel planning deployments, including open language reasoning and unseen concept composition.
  arXiv  Detail & Related papers  (2024-12-18T10:10:12Z)
• EgoPlan-Bench2: A Benchmark for Multimodal Large Language Model Planning in Real-World Scenarios [53.26658545922884]
  We introduce EgoPlan-Bench2, a benchmark designed to assess the planning capabilities of MLLMs across a wide range of real-world scenarios. We evaluate 21 competitive MLLMs and provide an in-depth analysis of their limitations, revealing that they face significant challenges in real-world planning. Our approach enhances the performance of GPT-4V by 10.24 on EgoPlan-Bench2 without additional training.
  arXiv  Detail & Related papers  (2024-12-05T18:57:23Z)
• Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming [13.246017517159043]
  Large language models (LLMs) have recently demonstrated strong potential in solving planning problems. We propose LLpreview, a framework that leverages LLMs to capture key information from planning problems and formally formulate and solve them as optimization problems from scratch. We apply LLpreview to 9 planning problems, ranging from multi-constraint decision making to multi-step planning problems, and demonstrate that LL achieves on average 83.7% and 86.8% optimal rate across 9 tasks for GPTo and Claude 3.5 Sonnet.
  arXiv  Detail & Related papers  (2024-10-15T23:20:54Z)
• On The Planning Abilities of OpenAI's o1 Models: Feasibility, Optimality, and Generalizability [59.72892401927283]
  We evaluate the planning capabilities of OpenAI's o1 models across a variety of benchmark tasks. Our results reveal that o1-preview outperforms GPT-4 in adhering to task constraints.
  arXiv  Detail & Related papers  (2024-09-30T03:58:43Z)
• Unlocking Large Language Model's Planning Capabilities with Maximum Diversity Fine-tuning [10.704716790096498]
  Large language models (LLMs) have demonstrated impressive task-solving capabilities, achieved through either prompting techniques or system designs. This paper investigates the impact of fine-tuning on LLMs' planning capabilities. We propose the Maximum Diversity Fine-Tuning (MDFT) strategy to improve the sample efficiency of fine-tuning in the planning domain.
  arXiv  Detail & Related papers  (2024-06-15T03:06:14Z)
• TRIP-PAL: Travel Planning with Guarantees by Combining Large Language Models and Automated Planners [6.378824981027464]
  Traditional approaches rely on problem formulation in a given formal language. Recent Large Language Model (LLM) based approaches directly output plans from user requests using language. We propose TRIP-PAL, a hybrid method that combines the strengths of LLMs and automated planners.
  arXiv  Detail & Related papers  (2024-06-14T17:31:16Z)
• TravelPlanner: A Benchmark for Real-World Planning with Language Agents [63.199454024966506]
  We propose TravelPlanner, a new planning benchmark that focuses on travel planning, a common real-world planning scenario. It provides a rich sandbox environment, various tools for accessing nearly four million data records, and 1,225 meticulously curated planning intents and reference plans. Comprehensive evaluations show that the current language agents are not yet capable of handling such complex planning tasks-even GPT-4 only achieves a success rate of 0.6%.
  arXiv  Detail & Related papers  (2024-02-02T18:39:51Z)
• LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning [65.86754998249224]
  We develop a novel hybrid planner that leverages a conventional rule-based planner in conjunction with an LLM-based planner. Our approach navigates complex scenarios which existing planners struggle with, produces well-reasoned outputs while also remaining grounded through working alongside the rule-based approach.
  arXiv  Detail & Related papers  (2023-12-30T02:53:45Z)
• 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)

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.