論文の概要: Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game
- arxiv url: http://arxiv.org/abs/2508.02900v1
- Date: Mon, 04 Aug 2025 21:01:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-06 18:18:55.680108
- Title: Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game
- Title（参考訳）: 単純な計画上の問題は計算的に混ざり合っている: カウントダウンゲーム
- Authors: Michael Katz, Harsha Kokel, Sarath Sreedharan,
- Abstract要約: 本稿では,Countdownと呼ばれるゲームを中心とした計画ベンチマークを作成する手順を提案する。
本稿では,この課題が,計画能力評価のための理想的なベンチマークと関連するデシラタの多くにどのように適合するかを論じる。
その結果、24 Game(Countdownの特殊な場合)のような他の領域とは異なり、提案した動的ベンチマークは既存のLCMベースのアプローチでは極めて困難であることが判明した。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 長期的な計画を立てることのできないことは、現在の基礎モデルとエージェントの重要な制限の1つであるという広い意見の一致がある。
しかし、既存の計画ベンチマークは、その計画能力を真に測定するのに不適切です。
既存のベンチマークのほとんどは、旅行計画のような緩やかに定義されたタスクに焦点を当てるか、あるいは既存のドメインと国際計画コンペティションの課題を活用することになる。
以前のタスクは形式化と検証が難しいが、後者は、既存の自動プランナの弱点をテストし、挑戦するために特別に設計されたものだ。
これらの欠点に対処するため,プレイヤーは算術演算によって入力番号のリストからターゲット番号を作成することを期待する,Countdownと呼ばれるゲームを中心とした計画ベンチマークを作成する手順を提案する。
本稿では,この課題が,計画能力評価のための理想的なベンチマークと関連するデシラタの多くにどのように適合するかを論じる。
具体的には、ドメインは各問題インスタンスに対して直感的で自然言語の記述を可能にし、計算的に困難である(NP完全)。
我々は、計算複雑性の計算結果を確立し、パブリックベンチマークよりもインスタンス生成手順の利点を実証する、広範囲な理論的解析を行う。
提案手法を用いて生成されたインスタンスに対して,既存のLCM支援計画手法の評価を行った。
その結果、24 Game(Countdownの特殊な場合)のような他の領域とは異なり、提案した動的ベンチマークは既存のLCMベースのアプローチでは極めて困難であることが判明した。
関連論文リスト
- CRISP: Complex Reasoning with Interpretable Step-based Plans [15.656686375199921]
数学的推論とコード生成のための高レベルプランのデータセットであるCRISP(Complex Reasoning with Interpretable Step-based Plans)を紹介する。
CRISP上で小さなモデルを微調整することで、より大規模なモデルよりも高品質なプランを少数ショットプロンプトで作成できることを実証する。
論文 参考訳（メタデータ） (2025-07-09T11:40:24Z) - Natural Language Planning via Coding and Inference Scaling [15.79089054416743]
プログラミングは多くの場合、計画よりも優れていますが、必ずしも優れていません。
我々の詳細なエラー解析は、一般化を妨げる生成コードの堅牢性と効率性の欠如も示している。
論文 参考訳（メタデータ） (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]
本稿では,現実の調理シナリオに基づいた新しいベンチマークフレームワークRecipe2Planを紹介する。
従来のベンチマークとは異なり、Recipe2Planは並列タスク実行による調理時間を最適化するためにエージェントに挑戦する。
論文 参考訳（メタデータ） (2025-03-04T03:27:02Z) - Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights [49.42133807824413]
本稿では,大規模言語モデル(LLM)の複雑な課題解決における推論と計画能力について検討する。
近年の推論時間技術の発展は,LLM推論を追加訓練なしで向上させる可能性を示している。
OpenAIのo1モデルは、マルチステップ推論と検証の新たな使用を通じて、有望なパフォーマンスを示している。
論文 参考訳（メタデータ） (2025-02-18T04:11:29Z) - LLM-Generated Heuristics for AI Planning: Do We Even Need Domain-Independence Anymore? [87.71321254733384]
大規模言語モデル(LLM)は、特定の計画問題に適した計画手法を生成することができる。
LLMは、いくつかの標準IPCドメインで最先端のパフォーマンスを達成することができる。
これらの結果がパラダイムシフトを意味するのか、既存の計画手法をどのように補完するかについて議論する。
論文 参考訳（メタデータ） (2025-01-30T22:21:12Z) - Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
CodePlanは、テキストコード形式の計画を生成し、追跡するフレームワークで、高いレベルの構造化された推論プロセスの概要を擬似コードで示します。
CodePlanは、洗練された推論タスク固有のリッチなセマンティクスと制御フローを効果的にキャプチャする。
反応を直接生成するのに比べて25.1%の相対的な改善が達成されている。
論文 参考訳（メタデータ） (2024-09-19T04:13:58Z) - Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。
我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。
ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
論文 参考訳（メタデータ） (2024-02-29T15:36:01Z) - On efficient computation in active inference [1.1470070927586016]
計算量を大幅に減らした有限時間地平線に対する新しい計画アルゴリズムを提案する。
また、新規かつ既存のアクティブな推論計画スキームに対して適切な目標分布を設定するプロセスを簡単にする。
論文 参考訳（メタデータ） (2023-07-02T07:38:56Z) - PlanBench: An Extensible Benchmark for Evaluating Large Language Models
on Planning and Reasoning about Change [34.93870615625937]
PlanBenchは、自動計画コミュニティで使用されるドメインの種類に基づいたベンチマークスイートである。
PlanBenchはタスクドメインと特定の計画機能の両方に十分な多様性を提供します。
論文 参考訳（メタデータ） (2022-06-21T16:15:27Z) - Task Scoping: Generating Task-Specific Abstractions for Planning [19.411900372400183]
オープンスコープの世界モデルを用いた特定のタスクの計画は、計算的に難解である。
本稿では,初期条件,目標条件,タスクの遷移力学構造に関する知識を活用するタスクスコーピングを提案する。
タスクスコーピングは、関連要因やアクションを決して削除せず、その計算複雑性を特徴づけ、特に有用である計画上の問題を特徴づける。
論文 参考訳（メタデータ） (2020-10-17T21:19:25Z) - STRIPS Action Discovery [67.73368413278631]
近年のアプローチでは、すべての中間状態が欠如している場合でも、アクションモデルを合成する古典的な計画が成功している。
アクションシグネチャが不明な場合に,従来のプランナーを用いてSTRIPSアクションモデルを教師なしで合成するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-30T17:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。