凸集合グラフ上のシュタイナー巡回セールスマン問題に対する統一分岐限定探索

本論文は、凸集合のグラフ上の Steiner Traveling Salesman Problem (Steiner-TSP) を定式化し、その無限解空間を探索するための統一的な branch-and-bound 探索を提案する。問題は、必須の凸集合を通過し、任意の通過頂点と再訪問を許容する最小コストの閉軌道を求めるものである。提案手法は、根付き歩行プレフィックス上の探索を統一的に扱い、加法的な下界グラフコストと、カット分離された連結フロー緩和による残差コストの下界を用いる。

先行研究と比べて、Steiner-TSP on GCS を初めて正式に定式化し、無限解空間を扱う統一的な探索を提案した点が新しい。また、一様正コスト仮定の下で、初期 incumbent なしでも best-first 探索が有限回の展開で終了することを理論的に保証し、ユーザー指定の近似係数 ε に対する大域下界を提供する点が優れている。さらに、LTL_f で表現された行動順序制約を組み込んだモバイルマニピュレータ検査タスクへの応用を示し、既存のベースラインよりも高い成功率を達成している。

手法の核は、根付き歩行プレフィックス上の統一的な branch-and-bound 探索である。具体的には、加法的な下界グラフコストがコミット済みプレフィックスのコストを下界し、カット分離された連結フロー緩和が残りのターゲットを訪問して根に戻る残差コストを下界する。探索戦略として best-first と depth-first の両方を扱い、一様正コスト仮定の下で終了性を保証する。また、ユーザー指定の ε に対して、大域下界が incumbent コストの ε 倍以内であることを証明する。

モバイルマニピュレータ検査タスクにおいて、センシングモード、訪問順序、連続軌道の同時選択を実証し、LTL_f で表現された行動順序制約を組み込んだ。ベンチマークインスタンス全てに対して、両方の探索戦略が 30 秒以内に実行可能解を見つけ、平均 certified optimality gap はそれぞれ 28.1% と 29.7% であった。一方、2 つの最近のベースラインは約半分のインスタンスでしか成功しなかった。

要旨からは、提案手法の計算複雑性や、より大規模な問題へのスケーラビリティに関する議論は不明である。また、一様正コスト仮定が現実の問題でどの程度妥当か、また ε の選択が実際の性能に与える影響についての詳細な分析は要旨には含まれていない。さらに、ベースラインとの比較は成功率のみであり、解の質や計算時間の詳細な比較は要旨からは不明である。

要旨で参照されている関連研究として、Steiner-TSP の既存解法や Graphs of Convex Sets (GCS) に関する研究が挙げられる。具体的には、GCS 上の最適化問題を扱った論文や、TSP の branch-and-bound 手法に関する論文が関連する。また、LTL_f を用いたタスク計画に関する研究も関連する。