移動目標巡回セールスマン問題に対する並列かつ漸近最適なアルゴリズム

- Moving Target Traveling Salesman Problem (MT-TSP) を解くための枠組みと並列アルゴリズムの研究。 - 各 target に設定された time window 内で複数の移動 target を intercept する trajectory を求める問題を扱う。 - 非線形な target trajectory や agent の kinematic constraints がある場合にも漸近最適性を目指す。 - Iterated Random Generalized (IRG) TSP framework を提案。 - agent configuration-time points のランダムサンプリングと generalized TSP (GTSP) の求解を交互に行う。 - IRG 内の並列アルゴリズムとして IRG-PGLNS と Parallel Communicating GTSPs (PCG) を提案。

- 従来は generic な非線形 target trajectory や agent の kinematic constraints がある場合、最適解への収束を保証するアルゴリズムが存在しなかったと主張。 - IRG framework はこの設定で asymptotically に optimum へ収束する点が新規。 - 並列化により、prior work に基づく baseline より IRG-PGLNS と PCG が速く収束することを示した。 - 具体的な prior 手法名や比較条件の詳細は要旨からは不明。

- IRG の核は、interception に対応する agent configuration-time points の集合をランダムにサンプリングするステップと、その点列を GTSP で解くステップの交互反復。 - この交互反復により asymptotically に最適解へ収束。 - IRG-PGLNS: GTSP を PGLNS で解く。PGLNS は state-of-the-art solver GLNS の並列拡張。 - PCG: 複数の点集合に対する GTSP を同時に解く Parallel Communicating GTSPs。 - 対象は 3 つの MT-TSP variant。 - target への一定距離接近で intercept とする variant。 - agent が variable-speed Dubins car の variant。 - agent が robot arm の variant。

- 3 つの MT-TSP variant に対する numerical results を提示。 - 一定距離での intercept、variable-speed Dubins car、robot arm の各設定。 - IRG-PGLNS と PCG が prior work に基づく baseline より速く収束することを示した。 - さらに physical robot experiments により framework を検証。 - 実験規模や具体的な評価指標の詳細は要旨からは不明。

- 非線形 trajectory や kinematic constraints 下での asymptotically optimal な解法と並列化の有効性が主な主張。 - baseline との収束速度比較と physical robot experiments が示されている。 - 収束保証の条件、計算コスト、並列化のスケーラビリティ、実機実験の限界などに関する議論の詳細は要旨からは不明。

- GLNS (state-of-the-art GTSP solver、PGLNS の基盤)。 - Generalized TSP (GTSP) 関連の解法。 - Moving Target Traveling Salesman Problem (MT-TSP) の prior work（baseline の元研究）。 - Dubins car を用いた経路計画研究。 - robot arm の motion planning 研究。