論文の概要: Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding
in High Dimensions
- arxiv url: http://arxiv.org/abs/2205.04548v1
- Date: Mon, 9 May 2022 20:46:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-12 20:56:53.231613
- Title: Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding
in High Dimensions
- Title(参考訳): インフォームド・スタイナー木:高次元の多方向経路探索のためのサンプリングとプルーニング
- Authors: Nikhil Chandak, Kenny Chour, Sivakumar Rathinam, R. Ravi
- Abstract要約: 本研究では,高次元空間における多目的経路探索問題の解法を提案する。
この手法は、探索空間内の選択された領域からのサンプリングポイントと、MGPFのよい解に導かないかもしれない非強調領域との交互に行われる。
- 参考スコア(独自算出の注目度): 6.291017032214274
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We interleave sampling based motion planning methods with pruning ideas from
minimum spanning tree algorithms to develop a new approach for solving a
Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach
alternates between sampling points from selected regions in the search space
and de-emphasizing regions that may not lead to good solutions for MGPF. Our
approach provides an asymptotic, 2-approximation guarantee for MGPF. We also
present extensive numerical results to illustrate the advantages of our
proposed approach over uniform sampling in terms of the quality of the
solutions found and computation speed.
- Abstract(参考訳): 高次元空間における多方向経路探索(mgpf)問題を解くための新しい手法を開発するために,最小スパンディングツリーアルゴリズムを用いたサンプルベース動作計画法とプルーニングアイデアをインターリーブする。
この手法は、探索空間内の選択された領域からのサンプリングポイントと、MGPFのよい解に導かないかもしれない非強調領域との交互に行われる。
MGPF に対する漸近的 2-近似保証を提供する。
また,提案手法による一様サンプリングの利点を,解の質と計算速度の観点から示すために,広範な数値計算結果を提示した。
関連論文リスト
- Multi-Resolution Planar Region Extraction for Uneven Terrains [6.482137641059034]
本稿では,不整点雲観測から不均質な地形の平面領域を抽出する問題について検討する。
境界の精度と計算効率のバランスをとる多分解能平面領域抽出戦略を提案する。
論文 参考訳(メタデータ) (2023-11-21T12:17:51Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。
数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
論文 参考訳(メタデータ) (2023-08-31T14:16:30Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳(メタデータ) (2023-06-15T15:37:31Z) - Calibrate and Debias Layer-wise Sampling for Graph Convolutional
Networks [39.56471534442315]
本稿では,行列近似の観点からアプローチを再考する。
本稿では,サンプリング確率と効率的なデバイアスアルゴリズムを構築するための新しい原理を提案する。
改良は、推定分散の広範囲な解析と、一般的なベンチマークの実験によって実証される。
論文 参考訳(メタデータ) (2022-06-01T15:52:06Z) - An Improved Greedy Algorithm for Subset Selection in Linear Estimation [5.994412766684842]
有限個の予測位置において、観測値の最もよい推定値を与えるような k 個の位置の集合を求める空間場における部分選択問題を考える。
観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。
本稿では,予測位置と予測位置によって形成される傾斜角の遠心点のみからなる探索空間を考慮し,計算複雑性を低減する手法を提案する。
論文 参考訳(メタデータ) (2022-03-30T05:52:16Z) - Super-resolution GANs of randomly-seeded fields [68.8204255655161]
ランダムスパースセンサからフィールド量の推定を行うための,GAN(Super- resolution Generative Adversarial Network)フレームワークを提案する。
このアルゴリズムはランダムサンプリングを利用して、高解像度の基底分布の不完全ビューを提供する。
提案手法は, 流体流動シミュレーション, 海洋表面温度分布測定, 粒子画像速度測定データの合成データベースを用いて検証した。
論文 参考訳(メタデータ) (2022-02-23T18:57:53Z) - S$^*$: A Heuristic Information-Based Approximation Framework for
Multi-Goal Path Finding [0.0]
2近似保証を提供するマルチゴールパス探索(MGPF)問題のための新しいフレームワークを開発する。
MGPFは、特定の目標セット内の各ノードが少なくとも1回はパスに沿って訪問されるように、原点から目的地までの最小コストのパスを見つけることを目指しています。
拡張ノード数と実行時間の観点から,従来の代替よりもフレームワークが優れていることを示す数値的結果を提示する。
論文 参考訳(メタデータ) (2021-03-15T06:27:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Planning in Markov Decision Processes with Gap-Dependent Sample
Complexity [48.98199700043158]
マルコフ決定過程における計画のための新しいトラジェクトリに基づくモンテカルロ木探索アルゴリズム MDP-GapE を提案する。
我々は, MDP-GapE に要求される生成モデルに対する呼び出し回数の上限を証明し, 確率の高い準最適動作を同定する。
論文 参考訳(メタデータ) (2020-06-10T15:05:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。