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

• URL: http://arxiv.org/abs/2404.11891v2
• Date: Tue, 15 Oct 2024 23:18:05 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) still 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 as constrained satisfiability problems. We show that our framework can modify and solve for an average of 81.6% and 91.7% unsatisfiable queries from two datasets.
• Score: 12.875270710153021
• License:
• Abstract: Despite their recent advancements, Large Language Models (LLMs) still 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 travel plans that satisfy user requirements with a 10% success rate given all needed information. In this work, we tackle this difficult problem 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 achieve a success rate of 93.9%. We demonstrate our framework's robustness by showing its effectiveness in diverse paraphrased prompts. More importantly, our framework has strong zero-shot generalizability: It can successfully handle unseen constraints in a completely unseen international travel dataset we created, and it can even generalize well to new domains such as routing and task allocation problems in a zero-shot manner. Moreover, when user input queries are infeasible, our framework can identify the unsatisfiable core, provide failure reasons, and offers personalized modification suggestions to users according to diverse human preferences. 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.

Related papers

• Optimizing Large Language Models for Dynamic Constraints through Human-in-the-Loop Discriminators [0.0]
  Large Language Models (LLMs) have recently demonstrated impressive capabilities across various real-world applications. We propose a flexible framework that enables LLMs to interact with system interfaces, summarize constraint concepts, and continually optimize performance metrics. Our framework achieved a $7.78%$ pass rate with the human discriminator and a $6.11%$ pass rate with the LLM-based discriminator.
  arXiv  Detail & Related papers  (2024-10-19T17:27:38Z)
• 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 LLpreview 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 Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
  We introduce CodePlan, a framework that generates and follows textcode-form plans -- pseudocode that outlines high-level, structured reasoning processes. CodePlan effectively captures the rich semantics and control flows inherent to sophisticated reasoning tasks. It achieves a 25.1% relative improvement compared with directly generating responses.
  arXiv  Detail & Related papers  (2024-09-19T04:13:58Z)
• Multi-agent Planning using Visual Language Models [2.2369578015657954]
  Large Language Models (LLMs) and Visual Language Models (VLMs) are attracting increasing interest due to their improving performance and applications across various domains and tasks. LLMs andVLMs can produce erroneous results, especially when a deep understanding of the problem domain is required. We propose a multi-agent architecture for embodied task planning that operates without the need for specific data structures as input.
  arXiv  Detail & Related papers  (2024-08-10T08:10:17Z)
• 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)
• Scalable Language Model with Generalized Continual Learning [58.700439919096155]
  The Joint Adaptive Re-ization (JARe) is integrated with Dynamic Task-related Knowledge Retrieval (DTKR) to enable adaptive adjustment of language models based on specific downstream tasks. Our method demonstrates state-of-the-art performance on diverse backbones and benchmarks, achieving effective continual learning in both full-set and few-shot scenarios with minimal forgetting.
  arXiv  Detail & Related papers  (2024-04-11T04:22:15Z)
• 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)
• Guiding Language Model Reasoning with Planning Tokens [122.43639723387516]
  Large language models (LLMs) have recently attracted considerable interest for their ability to perform complex reasoning tasks. We propose a hierarchical generation scheme to encourage a more structural generation of chain-of-thought steps. Our approach requires a negligible increase in trainable parameters (0.001%) and can be applied through either full fine-tuning or a more parameter-efficient scheme.
  arXiv  Detail & Related papers  (2023-10-09T13:29:37Z)
• 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)

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.