Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

• URL: http://arxiv.org/abs/2508.02900v1
• Date: Mon, 04 Aug 2025 21:01:03 GMT
• Title: Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game
• Authors: Michael Katz, Harsha Kokel, Sarath Sreedharan,
• Abstract summary: We propose a procedure for creating a planning benchmark centered around the game called Countdown.<n>We discuss how this problem meets many of the desiderata associated with an ideal benchmark for planning capabilities evaluation.<n>Our results show that, unlike other domains like 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches.
• Score: 26.665033202052257
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: There is a broad consensus that the inability to form long-term plans is one of the key limitations of current foundational models and agents. However, the existing planning benchmarks remain woefully inadequate to truly measure their planning capabilities. Most existing benchmarks either focus on loosely defined tasks like travel planning or end up leveraging existing domains and problems from international planning competitions. While the former tasks are hard to formalize and verify, the latter were specifically designed to test and challenge the weaknesses of existing automated planners. To address these shortcomings, we propose a procedure for creating a planning benchmark centered around the game called Countdown, where a player is expected to form a target number from a list of input numbers through arithmetic operations. We discuss how this problem meets many of the desiderata associated with an ideal benchmark for planning capabilities evaluation. Specifically, the domain allows for an intuitive, natural language description for each problem instance, it is computationally challenging (NP-complete), and the instance space is rich enough that we do not have to worry about memorization. We perform an extensive theoretical analysis, establishing the computational complexity result and demonstrate the advantage of our instance generation procedure over public benchmarks. We evaluate a variety of existing LLM-assisted planning methods on instances generated using our procedure. Our results show that, unlike other domains like 24 Game (a special case of Countdown), our proposed dynamic benchmark remains extremely challenging for existing LLM-based approaches.

Related papers

• CRISP: Complex Reasoning with Interpretable Step-based Plans [15.656686375199921]
  We introduce CRISP (Complex Reasoning with Interpretable Step-based Plans), a dataset of high-level plans for mathematical reasoning and code generation.<n>We demonstrate that fine-tuning a small model on CRISP enables it to generate higher-quality plans than much larger models using few-shot prompting.
  arXiv  Detail & Related papers  (2025-07-09T11:40:24Z)
• Natural Language Planning via Coding and Inference Scaling [15.79089054416743]
  We show that programming often but not always outperforms planning.<n>Our detailed error analysis also indicates a lack of robustness and efficiency in the generated code that hinders generalization.
  arXiv  Detail & Related papers  (2025-05-19T15:35:17Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights [49.42133807824413]
  We examine the reasoning and planning capabilities of large language models (LLMs) in solving complex tasks.<n>Recent advances in inference-time techniques demonstrate the potential to enhance LLM reasoning without additional training.<n>OpenAI's o1 model shows promising performance through its novel use of multi-step reasoning and verification.
  arXiv  Detail & Related papers  (2025-02-18T04:11:29Z)
• LLM-Generated Heuristics for AI Planning: Do We Even Need Domain-Independence Anymore? [87.71321254733384]
  Large language models (LLMs) can generate planning approaches tailored to specific planning problems.<n>LLMs can achieve state-of-the-art performance on some standard IPC domains.<n>We discuss whether these results signify a paradigm shift and how they can complement existing planning approaches.
  arXiv  Detail & Related papers  (2025-01-30T22:21:12Z)
• 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)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• On efficient computation in active inference [1.1470070927586016]
  We present a novel planning algorithm for finite temporal horizons with drastically lower computational complexity. We also simplify the process of setting an appropriate target distribution for new and existing active inference planning schemes.
  arXiv  Detail & Related papers  (2023-07-02T07:38:56Z)
• PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change [34.93870615625937]
  PlanBench is a benchmark suite based on the kinds of domains used in the automated planning community. PlanBench provides sufficient diversity in both the task domains and the specific planning capabilities.
  arXiv  Detail & Related papers  (2022-06-21T16:15:27Z)
• Task Scoping: Generating Task-Specific Abstractions for Planning [19.411900372400183]
  Planning to solve any specific task using an open-scope world model is computationally intractable. We propose task scoping: a method that exploits knowledge of the initial condition, goal condition, and transition-dynamics structure of a task. We prove that task scoping never deletes relevant factors or actions, characterize its computational complexity, and characterize the planning problems for which it is especially useful.
  arXiv  Detail & Related papers  (2020-10-17T21:19:25Z)
• STRIPS Action Discovery [67.73368413278631]
  Recent approaches have shown the success of classical planning at synthesizing action models even when all intermediate states are missing. We propose a new algorithm to unsupervisedly synthesize STRIPS action models with a classical planner when action signatures are unknown.
  arXiv  Detail & Related papers  (2020-01-30T17:08:39Z)

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.