論文の概要: Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation

• arxiv url: http://arxiv.org/abs/2608.26314v1
• Date: Wed, 26 Aug 2026 18:46:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-28 16:30:58.156171
• Title: Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation
• Title（参考訳）: 最適制御のための分散前方木探索:被覆,複雑性,計算
• Abstract要約: 本稿では, 決定論的有限サンプル近距離最適保証をもつ伝搬型キノダイナミックプランナを開発した。 局所分散制御コマンドのフォワードツリーは,木の大きさのほぼ最適軌道を含むことを示す。 提案手法は, 探索アルゴリズムである分散フォワードツリー探索(DFT*)をフォワードツリーの広帯域展開として実装する。
• 参考スコア（独自算出の注目度）: 15.03677748041754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Steering-based planners require solutions to state-to-state boundary value problems, which can be inaccessible for nonlinear platforms. Forward propagation evades the steering requirement, but the finite-sample behavior of the associated planners remains uncharacterized and their implementations underperform in practice. This paper develops a propagation-based kinodynamic planner with deterministic finite-sample near-optimality guarantees. We work within the large class of differentially flat nonlinear systems and show that a forward tree of locally dispersive control commands contains a near-optimal trajectory at a certified tree size. We provide a general mechanism to construct dispersive command sets for control-affine systems, which are necessary to implement the search algorithm prescribed by the theory. We show that covering the certified trajectory class irrespective of cost provably demands a tree exponentially sized in the problem horizon, and present a cost-conditioned dominance pruning procedure that retains near-optimality at a tree size polynomial in the horizon. We implement the resulting search algorithm, Dispersive Forward Tree search (DFT*), as breadth-first expansion of the forward tree, which maps naturally onto parallel hardware. We design efficient dispersive samplers for the unicycle, the trailer car, and the quadrotor and evaluate challenging planning tasks for these platforms. DFT* delivers consistently competitive and often substantially better solution quality than state-of-the-art kinodynamic planners at comparable solution times on embedded-tier processors, accelerating further as parallel compute is scaled. We also implement DFT* in a receding-horizon loop to demonstrate real-time planning in dynamic environments at embedded-tier compute budgets.
• Abstract（参考訳）: ステアリングベースのプランナーは状態-状態境界値問題の解を必要とするが、非線形プラットフォームではアクセスできない。 フォワード伝搬はステアリングの要求を回避するが、関連するプランナーの有限サンプルの振る舞いは相変わらず、実際は実装が不十分である。 本稿では, 決定論的有限サンプル近距離最適保証をもつ伝搬型キノダイナミックプランナを開発した。 微分平坦な非線形系の大規模なクラス内で動作し、局所分散制御コマンドのフォワードツリーが、証明された木の大きさの準最適軌道を含むことを示す。 本稿では,制御ファインシステムのための分散コマンドセットを構築するための一般的なメカニズムについて述べる。 提案手法では,コストによらず,保証された軌道クラスをカバーするために,問題地平線において指数関数的に大きさのツリーを要求できることを示し,地平線における木の大きさ多項式のほぼ最適性を維持できるコスト条件ドミナンスプルーニング手法を提案する。 提案手法は,分散フォワードツリー探索 (Dispersive Forward Tree Search, DFT*) を, 並列ハードウェアに自然にマッピングするフォワードツリーの広帯域展開として実装する。 我々は,一輪車,トレーラー車,四輪車のための効率的な分散サンプリング装置を設計し,これらのプラットフォームのための課題計画タスクを評価する。 DFT*は、最先端のキノダイナミックプランナーと同等のソリューションタイムで、一貫した競争力のあるソリューション品質を提供し、並列計算がスケールするにつれてさらに加速する。 また,DFT*を遅延水平ループに実装し,組込み型計算予算での動的環境におけるリアルタイムプランニングを実演する。

関連論文リスト

• Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning [10.558515062670692]
  連続領域における不確実性の下での計画は自律システムにとって不可欠である。 モンテカルロ木探索 (MCTS) のような木に基づく探索手法は今でも人気がある。 提案するグラフスパースサンプリング(GSS: Graph Sparse Sampling)は,提案するオンライン計画アルゴリズムである。
  論文  参考訳（メタデータ） (2026-07-06T17:36:28Z)
• BOWConnect: Parallel Bayesian Optimization over Windows with Learned Local Cost Maps for Sample-Efficient Kinodynamic Motion Planning [1.4499463058550681]
  本稿では,並列キノダイナミックモーションプランナであるBOWConnectについて述べる。 これは、高次元状態空間におけるサンプル非効率性、信頼できないサンプリング、狭い空間における性能の3つの基本的な制限に対処する。 学習ベースの探索フレームワークとしてBOWを統合しており、各作業者はローカルマップと制約を学び、動的に実現可能で衝突のないコントロールへと導くことができる。
  論文  参考訳（メタデータ） (2026-06-25T17:11:33Z)
• 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)
• HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
  我々は階層的拡散政策を備えたエンドツーエンドの計画フレームワークであるHADを提案する。 我々は,NAVSIMとHUGSIMの両方でHADが新たな最先端性能を実現することを示す。
  論文  参考訳（メタデータ） (2026-04-04T04:12:47Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。 本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。 本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
  論文  参考訳（メタデータ） (2026-02-10T14:17:53Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) は大規模言語モデル(LLM)推論を強化し、分散木としての問題解決を構造化する。 推論における推論経路を動的に最適化することを目的とした,新しい並列化フレームワークであるDynamic Parallel Tree Search (DPTS)を提案する。 Qwen-2.5とLlama-3のMath500とGSM8Kデータセットによる実験では、DPTSは平均で2-4倍効率が向上した。
  論文  参考訳（メタデータ） (2025-02-22T14:13:37Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  無線対応経路計画フレームワークであるSCoTTを提案する。 SCoTT は DP-WA* の2% 以内で経路ゲインを達成し, 連続的に短い軌道を生成できることを示す。 また,ガゼボシミュレーションにおいて,SCoTTをROSノードとして配置することにより,本手法の実用性を示す。
  論文  参考訳（メタデータ） (2024-11-27T10:45:49Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• 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)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search [12.457788665461312]
  本稿では,機械学習モデルと最適解法を併用したハイブリッド問題解決プランナを提案する。 我々は現実的なシナリオで実験を行い、GCNのサポートにより、より難しい問題に対して、大幅なスピードアップとスムーズなスケーリングが可能になることを示す。
  論文  参考訳（メタデータ） (2021-08-02T16:53:21Z)

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

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