論文の概要: Learning How to Search for Plans with Exponentially Less Space

• arxiv url: http://arxiv.org/abs/2610.10954v1
• Date: Wed, 07 Oct 2026 22:14:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:53.687876
• Title: Learning How to Search for Plans with Exponentially Less Space
• Title（参考訳）: 指数的に少ない空間で計画の探索方法を学ぶ
• Abstract要約: 我々は、インデックスポリシーとして記述されたドメインごとの1つの仕様である検索制御を学習する。 我々はこれらのポリシーを,反例誘導ループで言語モデルを用いて学習する。 学習ポリシーでは、ICC 2023 Learning Trackの1,890の試験タスクのうち1,709を解決している。
• 参考スコア（独自算出の注目度）: 4.654827623279546
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristic search for a plan can store exponentially many states, even when its heuristic is almost perfect. We instead learn search control, one specification per domain, written as an indexical policy: a generalized policy with registers that hold objects and modes that sequence its rules. We add the choose rule, which loads an object into a register and marks a backtracking point, where one candidate suffices; every other rule must work for all of its outcomes and needs no search. Our main result is that structural termination, which rules out infinite executions, also bounds every execution by a polynomial in the number of objects. A depth-first procedure then finds a plan in polynomial space, however large the state space, with no list of visited states. The cost is time, exponential only in the choice depth, the number of real choices along an execution. Any class that such a policy solves therefore lies in NP, and in P at constant choice depth. We learn these policies with a language model in a counterexample-guided loop that certifies termination, verifies the training tasks, and keeps the choice depth small. With the learned policies, the procedure solves 1,709 of 1,890 test tasks of the IPC 2023 Learning Track and the Autoscale Agile suite, more than LAMA, BFWS, and Levitron, and most of them within one second and 100 MiB.
• Abstract（参考訳）: 計画のヒューリスティック探索は、そのヒューリスティックがほぼ完璧であっても、指数関数的に多くの状態を保存することができる。 代わりに、ドメインごとの1つの仕様である検索制御を、インデックスポリシーとして記述します。 レジスタにオブジェクトをロードし、1つの候補が満足するバックトラックポイントをマークするセレクトルールを追加します。 私たちの主な結果は、無限実行を規定する構造的終了が、オブジェクトの個数の多項式による全ての実行を束縛していることです。 深さ優先の手順は多項式空間において計画を見つけるが、訪問状態のリストが存在しない状態空間は大きい。 コストは時間であり、選択の深さだけ指数関数的であり、実行に伴う実際の選択数である。 したがって、そのようなポリシーが解けるクラスは、NP と P の任意の選択深さにある。 我々はこれらのポリシーを言語モデルを用いて学習し、終端を認証し、トレーニングタスクを検証し、選択の深さを小さくする。 学習方針では、IPC 2023 Learning TrackとAutoscale Agileスイートの1,890のテストタスクのうち1,709を、LAMA, BFWS, Levitronよりも多く解決する。

関連論文リスト

• Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning [7.31472912229643]
  一般的な計画は、古典的な計画領域内のインスタンスの集合をまたいで一般化するポリシーを学ぶことを目的としている。 最近のグラフニューラルネットワーク(GNN)アプローチは、いくつかのドメインでほぼ完璧なポリシーを学びました。 この作業は、最近公開されたIterated Width(IW)ポリシーの考え方を改善している。
  論文  参考訳（メタデータ） (2026-05-18T17:15:23Z)
• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces [58.298135359318024]
  コンパクトなアクション空間を自動構築する新しいフレームワークtextscDynaActを提案する。 当社のアプローチは,大幅な遅延を発生させることなく,効率的な推論を維持しながら,全体的なパフォーマンスを著しく向上させる。
  論文  参考訳（メタデータ） (2025-11-11T09:47:13Z)
• Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
  ここでは,報酬分布が (0, 1) で最大$alpha$-quantileを持つポリシーを見つけることを目標とする量子最適政策学習について検討する。 このような問題は、(i)報酬分布の関数としての量子目標の非線形性、(ii)未観測の共起問題、(iii)オフラインデータセットのカバー不足という3つの大きな課題に悩まされている。
  論文  参考訳（メタデータ） (2025-06-08T13:37:38Z)
• Search Strategy Generation for Branch and Bound Using Genetic Programming [0.0]
  GP2S(Genetic Programming for Search Strategy)は,B&B検索戦略を自動生成する機械学習手法である。 我々は、SCIPソルバの標準手法、最近のグラフニューラルネットワークに基づく手法、手工芸品との比較を行った。 我々の手法は最良基準よりも2%遅く、SCIPを一貫して上回り、平均速度は11.3%に達する。
  論文  参考訳（メタデータ） (2024-12-12T16:57:46Z)
• Pure Planning to Pure Policies and In Between with a Recursive Tree Planner [0.0]
  RTPは、一方の極端にポリシーのない純粋なプランナーとして機能し、もう一方の極端に純粋に欲求的なポリシーを実行するように設計されている。 その間に、RTPは計画性能を改善し、ある計画問題から別の計画問題へのゼロショット転送を改善するためにポリシーを利用する。 RTPは、古典的な月面着陸機(Farama 2022)や、MuJoCo(Todorov et al 2012)逆振り子など、さまざまなBox2d(Cato 2022)問題でテストされている。
  論文  参考訳（メタデータ） (2024-05-21T18:02:47Z)
• Learning Logic Specifications for Soft Policy Guidance in POMCP [71.69251176275638]
  部分観測可能なモンテカルロ計画(POMCP)は部分観測可能なマルコフ決定過程(POMDP)の効率的な解法である POMCPはスパース報酬機能、すなわち最終ゴールに達するときのみ得られる報酬に悩まされる。 本稿では,POMCP実行のトレースから論理仕様を学習するために帰納的論理プログラミングを用いる。
  論文  参考訳（メタデータ） (2023-03-16T09:37:10Z)
• Exploration via Planning for Information about the Optimal Trajectory [67.33886176127578]
  我々は,タスクと現在の知識を考慮に入れながら,探索を計画できる手法を開発した。 本手法は, 探索基準値よりも2倍少ないサンプルで, 強いポリシーを学習できることを実証する。
  論文  参考訳（メタデータ） (2022-10-06T20:28:55Z)
• Planning to Practice: Efficient Online Fine-Tuning by Composing Goals in Latent Space [76.46113138484947]
  汎用ロボットは、現実世界の非構造環境において困難なタスクを完了するために、多様な行動レパートリーを必要とする。 この問題に対処するため、目標条件強化学習は、コマンド上の幅広いタスクの目標に到達可能なポリシーを取得することを目的としている。 本研究では,長期的課題に対する目標条件付き政策を実践的に訓練する手法であるPlanning to Practiceを提案する。
  論文  参考訳（メタデータ） (2022-05-17T06:58:17Z)
• PG3: Policy-Guided Planning for Generalized Policy Generation [25.418642034856365]
  本稿では,政策探索の指針となるスコア関数に着目した一般政策探索手法について検討する。 このアプローチの背景にある主な考え方は、その候補を評価するためのメカニズムとして、トレーニング問題の計画立案に候補ポリシーを使うべきだということです。 6つのドメインの実証的な結果は、PG3が複数のベースラインよりも効率的かつ効果的に一般化されたポリシーを学習していることを確認する。
  論文  参考訳（メタデータ） (2022-04-21T21:59:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。