論文の概要: Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning

• arxiv url: http://arxiv.org/abs/2607.05359v1
• Date: Mon, 06 Jul 2026 17:36:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:30.267558
• Title: Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning
• Title（参考訳）: グラフスパースサンプリング:連続MDP計画における水平の曲線を破る
• Authors: Idan Lev-Yehudi, Vadim Indelman,
• Abstract要約: 連続領域における不確実性の下での計画は自律システムにとって不可欠である。 モンテカルロ木探索 (MCTS) のような木に基づく探索手法は今でも人気がある。 提案するグラフスパースサンプリング(GSS: Graph Sparse Sampling)は,提案するオンライン計画アルゴリズムである。
• 参考スコア（独自算出の注目度）: 10.558515062670692
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Planning under uncertainty in continuous domains is essential for autonomous systems, yet computationally demanding. Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular, but their branching structure can require sampling budgets that grow exponentially with lookahead depth in the worst case. From a tree perspective, continuous state or action spaces become especially challenging, since the planner must decide where to search in an infinite branching hierarchy. We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions, rather than sampling separate successors for each candidate action. This branch-free graph exposes large GPU-friendly batches, while using heuristics to focus computation. We prove finite-sample performance guarantees for GSS covering full-rank or low-rank generative simulators via smoothed backups, and discrete or sampled continuous action spaces. Under suitable overlap, regularity, and action-coverage conditions, these bounds have polynomial dependence on the planning horizon, formalizing when shared futures can avoid the exponential horizon dependence of tree-shaped sparse sampling. We demonstrate continuous-control simulations where GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance, supporting no-branching graph planning as a complementary design principle for online control.
• Abstract（参考訳）: 連続領域における不確実性の下での計画は、自律システムには不可欠であるが、計算的に要求される。 モンテカルロ木探索 (MCTS) のような木をベースとした探索手法は依然として人気があるが、その分岐構造は、最悪の場合、目視深度で指数関数的に成長するサンプリング予算を必要とする可能性がある。 木の観点からは、連続状態やアクション空間は、プランナーが無限分岐階層のどこに探索するかを決定する必要があるため、特に困難になる。 提案するグラフスパースサンプリング(GSS, Graph Sparse Sampling)は, 候補者の行動毎に個別の後継者をサンプリングするのではなく, 多数の候補決定にまたがってサンプル化された未来を共有するオンライン計画アルゴリズムである。 このブランチフリーグラフは、計算に集中するためにヒューリスティックスを使用しながら、大きなGPUフレンドリーなバッチを公開する。 本研究では,GASがスムーズなバックアップや離散的あるいはサンプル的連続行動空間を通じて,フルランクまたはローランク生成シミュレータをカバーすることを保証する。 適切な重なり合い、規則性、行動被覆条件の下で、これらの境界は計画的地平線に多項式依存を持ち、共有された未来が木の形をしたスパースサンプリングの指数的地平線依存を避けることができるときに定式化される。 オンライン制御の補完設計原則として, GSS がツリーベースプランナーを著しく上回ったり, ほぼ最適性能を達成したりする連続制御シミュレーションを実証する。

関連論文リスト

• Optimizing Trajectory-Trees in Belief Space: An Application from Model Predictive Control to Task and Motion Planning [12.236092368066332]
  本稿では,部分的に観測可能なロボット計画問題に対して,一般的な逐次的トラジェクトリではなく,アーボラキシートラジェクトリ(トラジェクトリ木)の利点を考察する。 システムの1つの前方進化をモデル化するシーケンシャルなトラジェクトリとは異なり、トラジェクトリツリーは複数の可能なコンティニュエーションをキャプチャする。
  論文  参考訳（メタデータ） (2026-05-03T13:06:20Z)
• SGA-MCTS: Decoupling Planning from Execution via Training-Free Atomic Experience Retrieval [74.1918709002557]
  我々は, LLM計画を非パラメトリック検索として活用するフレームワークである textbfSGA-MCTS を紹介する。 オンラインでは、検索増強剤は、関連するステート-ゴール-アクション原子を取得するために、ハイブリッドシンボリック-セマンティック機構を使用する。 SGA-MCTSは、探索の重い計算コストを効果的に減らし、System 1推論速度におけるシステム2推論の深さを達成し、スケーラブルかつリアルタイムに自律的な計画が実現可能である。
  論文  参考訳（メタデータ） (2026-04-16T07:22:36Z)
• Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding [44.79409119345322]
  Multi-Agent Path Finding (MAPF) は、共有グラフ上の複数のエージェントに対して衝突のない軌道を必要とする。 本稿では,幾何計画と実行時競合解決を分離するハイブリッドな優先順位付けフレームワークを提案する。
  論文  参考訳（メタデータ） (2026-03-11T11:04:54Z)
• 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)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。 並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
  論文  参考訳（メタデータ） (2022-10-04T07:34:06Z)
• Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
  グラフ散乱変換(GST)は、グラフデータから特徴を抽出する訓練のないディープGCNモデルを提供する。 GSTが支払う価格は、層の数によって増加する空間と時間の指数関数的な複雑さである。 本研究は, GST の複雑性の限界に対処し, 効率的な (p) GST アプローチを導入する。
  論文  参考訳（メタデータ） (2020-01-27T16:05:56Z)

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

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