論文の概要: Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search

• arxiv url: http://arxiv.org/abs/2607.00156v1
• Date: Tue, 30 Jun 2026 20:31:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-02 19:56:07.625377
• Title: Dual-Informed Vertical Expansion for Multi-Objective Node Selection in Anytime Conflict-Based Search
• Title（参考訳）: 衝突探索における多目的ノード選択のためのデュアルインフォーム垂直展開
• Abstract要約: 競合ベースサーチ(CBS)はマルチエージェントパス探索(MAPF)の高精度アルゴリズムである 標準的なベストファーストの選択は、拡張ノードを最小化し、最適性証明書を閉じるのに強い。 本稿では,CBSにおける一級設計選択としてノード選択について検討する。
• 参考スコア（独自算出の注目度）: 12.686696855241996
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Conflict-Based Search (CBS) is a leading exact algorithm for Multi-Agent Path Finding (MAPF), but its high-level node-selection rule is usually treated as a fixed implementation detail. Standard best-first selection is strong for minimizing expanded nodes and closing the optimality certificate, yet it can maintain a large frontier, interrupt parent-child expansion sequences, and provide no feasible incumbent until termination. This paper studies node selection as a first-class design choice for exact CBS. We introduce Dual-Informed Vertical Expansion (DIVE), a policy that is best-bound between dives and depth-oriented within a dive. DIVE starts each dive from the current best-bound frontier, follows promising children to exploit parent-child locality, and uses incumbent pruning to limit unproductive excursions. We formalize CBS node selection through a branch-and-bound view, prove that the traversal policy can be changed without affecting exactness, and analyze the resulting trade-offs among expanded nodes, dive breaks, queue size, and primal-dual bound progress. The analysis predicts three complementary extremes. Best-first search is node efficient, iterative deepening is memory efficient, and DIVE is dive efficient while retaining regular best-bound reanchoring. Experiments on standard MAPF benchmarks support this trade-off map. DIVE consistently reduces dive breaks, provides early incumbents with certified gaps, uses substantially less queue memory than best-first search, and benefits from warm starts and simple responsive variants in dense or memory-limited regimes.
• Abstract（参考訳）: 競合ベースサーチ(CBS)はマルチエージェントパス探索(MAPF)の主要なアルゴリズムであるが、その高レベルノード選択規則は通常、実装の詳細として扱われる。 標準的な最優先選択は、拡張ノードを最小化し、最適性証明書を閉じる上で強いが、大きなフロンティアを維持し、親子拡張シーケンスを中断し、終了まで実現可能な既存情報を提供しない。 本稿では,CBSにおける一級設計選択としてノード選択について検討する。 DIVE(Dual-Informed Vertical Expansion)は,ダイブとダイブ内での深度指向の最良のバウンドポリシである。 DIVEは、現在最寄りのフロンティアから飛び立ち始め、親子の局所性を活用することを約束する子供たちに続き、非生産的な遠足を制限するために既存のプルーニングを使用する。 CBSノードの選択をブランチ・アンド・バウンド・ビューで形式化し、正確性に影響を与えることなくトラバースポリシーを変更できることを証明し、拡張ノード間のトレードオフ、ダイブ・ブレーク、キューサイズ、プリマル・デュアル・バウンド・プログレスを解析する。 この分析は3つの相補的な極性を予測する。 最優先探索はノード効率が良く、反復深度はメモリ効率が良く、DIVEは通常のベストバウンド再アンチョリングを維持しながらダイブ効率が良い。 MAPFベンチマークの実験は、このトレードオフマップをサポートしている。 DIVEは、ダイブブレイクを継続的に削減し、認定されたギャップを持つ初期現職者を提供し、最優先の検索よりもキューメモリを著しく少なくし、温かいスタートと、高密度またはメモリ制限されたレシエーションにおける単純な応答性変異の恩恵を享受する。

関連論文リスト

• Deeper is Not Always Better: Mitigating the Alignment Tax via Confident Layer Decoding [92.1521161575198]
  我々は、最も信頼性の高いニアファイナル層を動的に選択する、トレーニング不要なデコーディング戦略であるConfident Decodingを紹介する。 密集型および混合型LLMの実験は、挑戦的推論ベンチマークにおいて一貫した利得を示す。
  論文  参考訳（メタデータ） (2026-06-20T07:03:26Z)
• Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics [5.729787815551408]
  本稿では,BixDFBnBを提案する。BixDFBnBは,BixDFBnBとBingle-Frontier Bidirectional Searchフレームワークを併用した,双方向のディープファースト分岐結合アルゴリズムである。 SFBDSはペア状態で動作するため、双方向のフロンティア管理に関連するオーバーヘッドを回避することができる。 BiXDFBnBは、LSP(Longest Simple Path)、Snakes(Snakes)、CIB(Coil-in-the-Box)といった最長パス問題に適用される。
  論文  参考訳（メタデータ） (2026-06-04T09:53:18Z)
• 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)
• UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding [2.486699239459455]
  本稿では,条件付きOT問題として木に基づく検証を行う統一的な視点を提案する。 局所的最適輸送計画を構成することにより,木レベルで共同最適化を行う検証アルゴリズムUniVerを導入する。
  論文  参考訳（メタデータ） (2026-05-06T06:42:58Z)
• Spend Search Where It Pays: Value-Guided Structured Sampling and Optimization for Generative Recommendation [16.991391135071513]
  本稿では,価値誘導型サンプリングおよびツリー構造化アドバンテージ強化フレームワークであるV-STARを提案する。 V-STARは2つの相乗的成分を介して自己進化ループを形成する。まず、決定ノードを識別し、高次接頭辞を選択的に深めるために価値誘導効率復号法(VED)を開発する。 第2に、誘導木トポロジーを利用して兄弟関係の利点を計算し、決定的な分岐決定に学習信号に集中するシブリング-GRPOを提案する。
  論文  参考訳（メタデータ） (2026-02-11T09:57:36Z)
• Inference-time Alignment in Continuous Space [72.19524569646323]
  推論時間アライメントのための単純で効果的なアルゴリズムであるSimple Energy Adaptation(textbfSEA$)を提案する。 SEAは、連続潜時空間における勾配に基づくサンプリングを通じて、基本ポリシーから最適なものへの元の応答を適応する。 例えば、SEAはAdvBenchで最大$textbf77.51%$、MATHで$textbf16.36%$で2番目に高いベースラインを上回っている。
  論文  参考訳（メタデータ） (2025-05-26T14:58:33Z)
• 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)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
  論文  参考訳（メタデータ） (2023-09-29T19:55:56Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP [2.528056693920671]
  このようなポリシーを2つの設定で学習するオフライン手法を提案する。 1つの設定は、プリンギング中に子供のセレクタに対応し、もう1つはダイビングに似ている。 5つのMIPデータセットの実証結果は、我々のノード選択ポリシーが、文献における最先端の先例よりもはるかに高速な解決につながることを示している。
  論文  参考訳（メタデータ） (2020-07-08T08:12:44Z)
• Joint Multi-Dimension Pruning via Numerical Gradient Update [120.59697866489668]
  本稿では,空間,深さ,チャネルの3つの重要な側面において,ネットワークを同時に切断する方法であるジョイント・マルチディメンジョン・プルーニング(ジョイント・プルーニング)を提案する。 本手法は,1つのエンドツーエンドトレーニングにおいて3次元にわたって協調的に最適化され,従来よりも効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-05-18T17:57:09Z)

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

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