[2508.02900] Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game

Computer Science > Artificial Intelligence arXiv:2508.02900 (cs) [Submitted on 4 Aug 2025 (v1), last revised 5 Apr 2026 (this version, v2)] Title:Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game Authors:Michael Katz, Harsha Kokel, Sarath Sreedharan View a PDF of the paper titled Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game, by Michael Katz and 2 other authors View PDF HTML (experimental) 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. From a world-model perspective, each instance induces a fully specified transition model (dynamics) over states and actions, enabling evaluation of planning with verifiable out...