論文の概要: GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
- arxiv url: http://arxiv.org/abs/2511.06471v1
- Date: Sun, 09 Nov 2025 17:34:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-11 21:18:44.967363
- Title: GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
- Title（参考訳）: GHOST:コンベックスのグラフ上でのセールスマン問題の解決
- Authors: Jingtao Tang, Hang Ma,
- Abstract要約: 凸集合グラフ上に定義された旅行セールスマン問題(TSP)の新たな変種について検討する。
この設定では、エッジコストは固定されていないが、各凸領域から選択された特定の軌跡に依存している。
本稿では,ツアー探索と凸軌道最適化を組み合わせたGCS-TSPを最適に解く階層型フレームワークであるGHOSTを紹介する。
- 参考スコア（独自算出の注目度）: 4.8236998950073255
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study GCS-TSP, a new variant of the Traveling Salesman Problem (TSP) defined over a Graph of Convex Sets (GCS) -- a powerful representation for trajectory planning that decomposes the configuration space into convex regions connected by a sparse graph. In this setting, edge costs are not fixed but depend on the specific trajectory selected through each convex region, making classical TSP methods inapplicable. We introduce GHOST, a hierarchical framework that optimally solves the GCS-TSP by combining combinatorial tour search with convex trajectory optimization. GHOST systematically explores tours on a complete graph induced by the GCS, using a novel abstract-path-unfolding algorithm to compute admissible lower bounds that guide best-first search at both the high level (over tours) and the low level (over feasible GCS paths realizing the tour). These bounds provide strong pruning power, enabling efficient search while avoiding unnecessary convex optimization calls. We prove that GHOST guarantees optimality and present a bounded-suboptimal variant for time-critical scenarios. Experiments show that GHOST is orders-of-magnitude faster than unified mixed-integer convex programming baselines for simple cases and uniquely handles complex trajectory planning problems involving high-order continuity constraints and an incomplete GCS.
- Abstract（参考訳）: グラフ・オブ・凸集合(GCS)上に定義された旅行セールスマン問題(TSP)の新たな変種であるGCS-TSPについて検討する。
この設定では、エッジコストは固定されないが、各凸領域から選択された特定の軌跡に依存するため、古典的なTSP法は適用できない。
本稿では,組換えツアー探索と凸軌道最適化を組み合わせたGCS-TSPを最適に解く階層型フレームワークであるGHOSTを紹介する。
GHOSTは、GCSによって誘導される完全なグラフ上のツアーを体系的に探索し、新しい抽象パス展開アルゴリズムを用いて、ハイレベル(オーバーツアー)とローレベル(オーバーツアーを実現するGCSパス)の両方でベストファースト検索を導く許容下界を計算する。
これらの境界は強いプルーニング能力を提供し、不要な凸最適化コールを避けながら効率的な探索を可能にする。
GHOSTが最適性を保証することを証明し、時間クリティカルなシナリオに対して有界な準最適変種を示す。
実験により、GHOSTは単純なケースに対して、統一された混合整数凸プログラミングベースラインよりも高速で、高次連続性制約と不完全GCSを含む複雑な軌道計画問題に一意に対処できることが示されている。
関連論文リスト
- Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP [28.92346104523666]
トラベルセールスマン問題(TSP)は古典的なNPハード問題であり、学術と産業の両方から大きな注目を集めている。
大規模TSPインスタンスを対象としたHyper Tour Guided Neighborhood Search (HyperNS)法を提案する。
論文 参考訳（メタデータ） (2025-10-23T03:30:18Z) - Towards Pre-trained Graph Condensation via Optimal Transport [52.6504753271008]
グラフ凝縮は、元のグラフを小さなグラフに蒸留し、冗長性を緩和し、GNNトレーニングを加速することを目的としている。
従来のGCアプローチは、厳格なGNNとタスク固有の監督に大きく依存している。
タスク依存GC法とアーキテクチャ依存GC法の限界を超越するために, 最適輸送による事前学習グラフ凝縮(PreGC)を提案する。
論文 参考訳（メタデータ） (2025-09-18T08:13:24Z) - Hierarchical Refinement: Optimal Transport to Infinity and Beyond [1.8749305679160366]
階層化リファインメントはログ線形時間と線形空間で動作し、低ランクOTの利点を保ちながら、その限定解像度を克服していることを示す。
我々は、100万以上のポイントを含むデータセットを含む複数のデータセットで階層的リファインメントの利点を示し、Sinkhornの範囲を超える問題にフルランクOTをスケールする。
論文 参考訳（メタデータ） (2025-03-04T22:00:12Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Locally Regularized Sparse Graph by Fast Proximal Gradient Descent [6.882546996728011]
本稿では,SRSG を短縮した新しい正規化スパースグラフを提案する。
スパースグラフは高次元データのクラスタリングに有効であることが示されている。
SRSGは他のクラスタリング手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2024-09-25T16:57:47Z) - A Combinatorial Perspective on the Optimization of Shallow ReLU Networks [35.329916555349214]
浅いReLUネットワークを最適化するNPハード問題は、各トレーニング例のアクティベーションパターンの探索として特徴付けられる。
ゾノトープを用いて自然にモデル化できることを示し、その集合は実現可能な活性化パターンの集合であることを示す。
論文 参考訳（メタデータ） (2022-10-01T03:09:02Z) - Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。
提案されたSSCAGは最先端のアプローチと競合する。
論文 参考訳（メタデータ） (2021-04-24T08:09:27Z) - Spatial-spectral Hyperspectral Image Classification via Multiple Random
Anchor Graphs Ensemble Learning [88.60285937702304]
本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。
まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。
次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
論文 参考訳（メタデータ） (2021-03-25T09:31:41Z) - A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。
GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
論文 参考訳（メタデータ） (2020-07-09T17:23:55Z) - Learning to Optimize Non-Rigid Tracking [54.94145312763044]
我々は、堅牢性を改善し、解法収束を高速化するために学習可能な最適化を採用する。
まず、CNNを通じてエンドツーエンドに学習された深い特徴にアライメントデータ項を統合することにより、追跡対象をアップグレードする。
次に,プレコンディショニング手法と学習手法のギャップを,プレコンディショナを生成するためにトレーニングされたConditionNetを導入することで埋める。
論文 参考訳（メタデータ） (2020-03-27T04:40:57Z) - Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
グラフ散乱変換(GST)は、グラフデータから特徴を抽出する訓練のないディープGCNモデルを提供する。
GSTが支払う価格は、層の数によって増加する空間と時間の指数関数的な複雑さである。
本研究は, GST の複雑性の限界に対処し, 効率的な (p) GST アプローチを導入する。
論文 参考訳（メタデータ） (2020-01-27T16:05:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。