論文の概要: Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
- arxiv url: http://arxiv.org/abs/2609.10584v1
- Date: Sun, 06 Sep 2026 11:46:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.07014
- Title: Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
- Title（参考訳）: Probabilistic Focal Search: 境界下探索の高速化
- Abstract要約: Probabilistic Focal Searchは、検索の労力を減らしながら最適な係数$w$以内の解を求める。
本稿では,確率$p$のFSガイド選択に従って,確率$1-p$のOPENノードを最小$f$で拡張する確率的フォカルサーチを提案する。
誘導と低バウンド進行のバランスをとることで、このメカニズムは、遅れたFOCALの入場によって進行が制限された場合、境界解まで時間を短縮することができる。
- 参考スコア（独自算出の注目度）: 8.225799201120973
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bounded-suboptimal search seeks a solution within a factor $w$ of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold $w f_{\min}$, but its deterministic policy may leave $f_{\min}$ unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability $p$ and expands a minimum-$f$ OPEN node with probability $1-p$. The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple $w$ and $p$ values. Across these benchmarks, the largest gains occur when long $f_{\min}$ plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90\% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.
- Abstract（参考訳）: 境界付き最適探索は、探索の労力を減らしながら、最適な係数$w$以内の解を求める。
Focal Search (FS) は FOCAL 内でのヒューリスティックなガイダンスを用いており、フロンティアノードは閾値 $w f_{\min}$ で指定できるが、その決定論的ポリシーは、多くの拡張に対して$f_{\min}$ は変わらないかもしれない。
本稿では,確率$p$のFSガイド選択に従って,確率$1-p$のOPENノードを最小$f$のOPENノードに拡張する確率的フォカルサーチ(PFS)を提案する。
後者のブランチは、下位のバウンダリを前進させ、FOCALを拡大し、実現可能なソリューションにつながる可能性のあるノードを認める。
誘導と低バウンド進行のバランスをとることで、このメカニズムは、遅れたFOCALの入場によって進行が制限された場合、境界解まで時間を短縮することができる。
二次移動実験として、同じスケジューラを動的ポテンシャル探索に適用し、確率的動的ポテンシャル探索(PDPS)を得る。
N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP) 上のFSとFSのベンチマークを行い,複数の$w$と$p$の値を用いて一般被覆TSP (GCTSP) 上の任意の拡張を評価する。
これらのベンチマーク全体では、長い$f_{\min}$ Plateaus が有用な FOCAL の入力を遅らせた場合に最も大きな利得が生じる。
任意のアルゴリズムファミリに対して、Anytime Probabilistic Focal Search (APFS)は、GCTSP上の任意の時間メソッドの評価において、すべてのテスト済みアルゴリズムより優れている。
また、決定論的探索が既に効率的に進行している場合(例えば、パンケーキソーティング)、その利点は小さくなり、FOCALが検索ボトルネックとなる場合、確率的因子が最も有用であることを示す。
PDPS転送は、この機構がドメインに依存したままでも、潜在的誘導に遷移することを示している。
関連論文リスト
- GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
GONDORはGreedy Best-First Search(GBFS)の拡張である
GONDORは、アンカー状態のスパースセットを保持しながら周期的に探索木を圧縮し、ゴールに達するとスパース状態間の再探索によって経路を再構築する。
実験により、GONDORは標準のGBFSと比較して、低メモリ予算下でのカバレッジを一貫して改善することが示された。
論文 参考訳（メタデータ） (2026-05-27T13:20:58Z) - Unsupervised Learning for the Elementary Shortest Path Problem [5.617211365270248]
プライマリ・ショート・パス問題(英語版) (ESPP) は、s から t への最小のコストパスを求め、それぞれを一度に訪問する。
本稿では,教師なしグラフニューラルネットワークによって実現された近似ESPPの確率的探索法を提案する。
論文 参考訳（メタデータ） (2025-08-03T03:03:05Z) - Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds [18.390974792959685]
MAPF (Multi-Agent Path Finding) は、NP困難問題であるコスト関数を最小化しながら、複数のエージェントの衝突のない経路を見つける。
本稿では、まず最大LB値を決定し、次にこのLBで導かれた最優先探索を用いて衝突のない経路を求めることにより、この問題に対処する新しい有界準最適アルゴリズム(DECBS)を提案する。
論文 参考訳（メタデータ） (2025-03-04T20:39:00Z) - Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。
割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。
本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-05T02:33:50Z) - High Probability Bounds for Stochastic Continuous Submodular
Maximization [5.362258158646462]
単調連続部分モジュラ函数の戻り特性の低下を考える。
最悪の場合においても、PGAは$OPT/2$に収束し、PGA、SCG、SCG++は$(1 - 1/e)OPT$に収束するが、期待するソリューションよりも遅い速度で収束する。
論文 参考訳（メタデータ） (2023-03-20T17:20:39Z) - B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming
Approach to Solving POMDPs [17.956744635160568]
我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。
我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。
B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
論文 参考訳（メタデータ） (2022-10-22T21:42:59Z) - Neural Greedy Pursuit for Feature Selection [72.4121881681861]
我々は,非線形予測問題に対する$P$入力機能のうち,$N$重要な特徴を選択するための欲求アルゴリズムを提案する。
ニューラルネットワークをアルゴリズムの予測子として使用し、損失を計算します。
論文 参考訳（メタデータ） (2022-07-19T16:39:16Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。
我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
論文 参考訳（メタデータ） (2019-04-08T06:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。