日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

軌道計画arXiv:2511.06471

GHOST: 凸集合グラフ上の巡回セールスマン問題を解く

GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets

シェア:XThreadsFacebookLINEはてブBluesky

凸集合グラフ上で定義される新しい巡回セールスマン問題に対し、組合せ探索と凸軌道最適化を組み合わせた階層的フレームワークGHOSTを提案し、最適性を保証しつつ高速に解く。

詳しい要約

1. どんなもの?

- GCS-TSP という新しい TSP 変種を扱う研究 - Graph of Convex Sets (GCS) 上で定義される TSP - 各 convex region 内の軌道に依存して edge cost が変わる - 古典的 TSP 手法が適用できない設定 - GHOST という階層的フレームワークを提案 - combinatorial tour search と convex trajectory optimization を統合 - 最適解を保証 - 時間制約向けの bounded-suboptimal 変種も提示

2. 先行研究と比べてどこがすごい?

- 古典的 TSP 手法は edge cost 固定を前提とし GCS-TSP に適用不可 - unified mixed-integer convex programming ベースラインと比較 - 単純なケースで GHOST は orders-of-magnitude 高速 - 高次連続性制約や incomplete GCS を含む複雑な trajectory planning を扱える点が独自 - ベースラインでは対応困難と示唆

3. 技術・手法の肝は?

- GCS が誘導する complete graph 上で tour を系統的に探索 - 新規の abstract-path-unfolding algorithm を利用 - admissible lower bounds を計算 - best-first search を二層で実施 - 高レベル: tour 上の探索 - 低レベル: tour を実現する feasible GCS path 上の探索 - 強い pruning により不要な convex optimization 呼び出しを回避 - 最適性を証明、bounded-suboptimal 変種も用意

4. どうやって有効だと検証した?

- unified mixed-integer convex programming ベースラインとの比較実験 - 単純ケースで orders-of-magnitude の高速化を報告 - 高次連続性制約を含む複雑な trajectory planning 問題に適用 - incomplete GCS を含む問題も扱えることを示す - 詳細なデータセット名や評価指標は要旨からは不明

5. 議論はある?

- 最適性の証明と bounded-suboptimal 変種の位置づけが議論の中心 - 高次連続性制約や incomplete GCS への適用可能性を示唆 - 計算コストやスケーラビリティの限界は要旨からは不明 - ベースライン以外との比較や実機検証は要旨からは不明

6. 次に読むべき論文は?

- Graph of Convex Sets (GCS) に関する研究 - GCS 上の trajectory planning 手法 - mixed-integer convex programming による TSP/軌道計画 - 古典的 Traveling Salesman Problem の厳密解法 - bounded-suboptimal search (例: A* 系の重み付き探索)

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Jingtao Tang, Hang Ma

分類: cs.AI, cs.RO

原文アブストラクト

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.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI