論文の概要: Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
- arxiv url: http://arxiv.org/abs/2608.21319v1
- Date: Fri, 21 Aug 2026 17:28:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-24 14:49:32.660221
- Title: Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
- Title（参考訳）: 凸集合グラフ上のスタイナー走行セールスマン問題の統一分岐境界探索
- Abstract要約: コンベックス集合グラフ上でのSteiner Traveling Salesman問題(Steiner-TSP)を定式化する。
結果の無限解空間を探索するために、ルート付きウォークプレフィックス上での分岐とバウンドの統一探索を提案する。
- 参考スコア（独自算出の注目度）: 4.8236998950073255
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor $ε\geq1$, a global lower bound certifies that either strategy's incumbent cost is at most $ε$ times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces (LTL$_f$). Both traversal strategies find feasible solutions on all benchmark instances within 30s with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances
- Abstract（参考訳）: コンベックス集合グラフ (GCS) 上のステイナートラベリングセールスマン問題 (Steiner-TSP) を定式化し、任意のトランジット頂点と再訪を許容しながら、必要凸集合を通して最小コストの閉軌道を求める。
結果の無限解空間を探索するために、ルート付きウォークプレフィックス上での分岐とバウンドの統一探索を提案する。
付加的なローバウンドグラフコストはコミットプレフィックスに束縛され、カットされたコネクテッドフロー緩和は残りのすべてのターゲットを訪れてルートに戻る残留コストを下げる。
均一な正のコストの仮定の下では、最優先トラバーサルは、初期存在のないすべての実現可能なインスタンス上の有限個の拡張の後で終了するが、一方、深さ第一トラバーサルは有限存在が得られればそのように終わる。
ユーザ指定因子 $ε\geq1$ に対して、大域的下限は、どちらの戦略の既存のコストも、大域的最適の ε$ 倍であることを示す。
さらに,有限トレース (LTL$_f$) 上の線形時間論理で表される動作優先を含む,移動マニピュレータ検査タスクにおける共同センシングモード,訪問順序,連続軌道選択について述べる。
両方のトラバーサル戦略は、それぞれ28.1%と29.7%の証明された最適性ギャップを持つ30秒以内のすべてのベンチマークインスタンスで実現可能なソリューションを見つける一方、最近の2つのベースラインは、インスタンスの約半分で成功する。
関連論文リスト
- DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning [4.941039246565574]
大規模走行セールスマン問題 (TSP) では、出力の妥当性を保ちながら限られた計算を割り当てることが求められる。
DualCertは、Emphconstraint-coupled learningを導入し、現在の等級方程式と動的に分離されたサブチュール除去制約がそれぞれの学習遷移を定義する。
1000の保持されたTSP1000インスタンス上で、DualCertは、Lin--Kernighan--Helsgaunバージョン3(LKH-3)からの平均的なツアーコストギャップ(0.0573%)をインスタンス当たり9.55秒のバッチ修正秒で達成した。
論文 参考訳（メタデータ） (2026-08-10T02:48:16Z) - Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates [1.2891210250935148]
我々は,境界遷移をサポートするMPPに対して,証明書を搬送するサブクワッドラティックな方法を提案する。
近似アレスト近傍指数は、正確に制限された演算子によって更新されたペアを選択する。
ローカルインデックスの品質だけでは、グローバルエラーを制御できない。
論文 参考訳（メタデータ） (2026-08-07T03:32:40Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search [0.0]
本稿では,制約付きコストモデル,有限コストグリッド,マルコフ遷移,非ゼロプログレッシブ測度の下では,パレート幾何学だけでスケジューリングと終了の両立が可能であることを示す。
本分析では, 決定論的ポテンシャル降下, 支配範囲による認定終了, コストグリッド形状によって誘導される層幅の均一化, スカイライン内におけるコスト空間の分散について検討した。
論文 参考訳（メタデータ） (2026-04-14T08:44:24Z) - Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。
非定常環境でこの問題を研究する。
非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
論文 参考訳（メタデータ） (2025-06-03T15:18:41Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。