以下は、提示された論文「Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM」の詳細な技術的サマリーです。

論文サマリー：事前定義された経路における多エージェントシステムの衝突回避速度スケジューリング

1. 問題設定 (Problem Statement)

本論文は、都市空中モビリティ（UAM）、自動倉庫物流、廊下型ロボット運用など、構造化された多エージェント輸送システムにおける協調制御の問題を取り扱っています。

• 制約条件: 多くの実用的なシナリオでは、インフラや運用上の要件により、エージェントは**事前定義された経路（ウェイポイントの順序と位置が固定）**に従わなければなりません。このため、衝突回避のために空間的な経路変更（リルート）を行うことは望ましくないか、不可能です。
• 課題: 経路が固定されている場合、衝突回避は「空間的な回避」ではなく、経路上での運動のタイミング（速度）の調整によってのみ達成されなければなりません。
• 既存手法の限界:
  • 反応型（局所）手法：計算コストは低いですが、高密度環境では保守的になったり、デッドロックに陥ったりする。
  • 計画型（大域）手法：混合整数計画法（MIP）などを用いて通過順序を決定する手法は存在するが、離散変数（順序変数）の組み合わせ爆発によりスケーラビリティが低く、数値的な感度が高い。また、多くの手法は経路変更を前提としており、経路固定システムには不向き。

2. 提案手法 (Methodology)

本論文は、事前定義された経路における多エージェント協調を、ウェイポイント通過時刻の最適化問題として定式化し、不正確射影（Inexact-Projection）ADMMアルゴリズムを用いて解くフレームワークを提案しています。

2.1 定式化

• 決定変数: 各エージェントの各ウェイポイント通過時刻 $\{t^{(i)}\}$。
• 目的関数: 到着時間が指定されていないエージェントの完了時刻の合計を最小化（タスクの早期完了の促進）。
• 制約条件:
  1. 出発時刻の固定。
  2. 到着時刻の固定（任意）。
  3. 速度の上下限（セグメント長と時間の関係から線形制約）。
  4. 連続時間における衝突回避: ミッション期間全体を通じて、任意のエージェントペア間の距離が安全距離 $d_{safe}$ 以上であること。

2.2 微分可能な代理軌道モデル (Differentiable Surrogate Trajectory Model)

従来の定速セグメントモデルはウェイポイントで速度が不連続になるため、勾配ベースの最適化には適しません。そこで、以下の工夫を行っています：

• 滑らかな近似: 硬いセグメントの切り替えを、シグモイド関数を用いた滑らかな遷移で近似します。
• 追従遅延の考慮: 実際の制御システムにおける追従遅延（Tracking Lag）を、時間バイアス $b$ を導入することでモデルに組み込みます。
• 効果: これにより、ウェイポイント時刻から連続的な位置プロファイルへの微分可能なマッピングが可能になり、距離ベースのペナルティを密な時間グリッド上で評価できるようになります。

2.3 不正確射影 ADMM ソルバー

衝突回避制約は非凸かつ非線形であるため、直接解くのが困難です。これを解決するために、ADMM（Alternating Direction Method of Multipliers）を適用し、問題を以下のように分割します：

1. タイミングと速度制約の更新: 線形制約（出発/到着時刻、速度限界）を含む部分。これは閉形式（線形方程式の解）で効率的に更新可能。
2. 衝突回避の処理（不正確射影）: 非凸な衝突回避制約集合への射影は計算的に困難です。そこで、不正確射影アプローチを採用します。
   • 密な時間グリッド上で定義された距離ベースのペナルティ関数 $f(z)$ を使用。
   • 厳密な射影の代わりに、このペナルティ関数の勾配に基づいたステップ（Polyak 型勾配ステップ）を用いて、衝突を回避する方向に $z$（時刻変数のコピー）を更新します。
   • 適応的モーメント: 最適化が停滞した場合にモーメント項を活性化し、数値的なデッドロックを回避する仕組みを導入しています。

このアプローチにより、明示的な整数順序変数（誰が先に通るかという離散変数）を必要とせず、連続最適化の枠組みで協調を実現しています。

3. 主要な貢献 (Key Contributions)

1. 新しい定式化: ミッション期間全体にわたる距離ベースの安全制約を定義し、経路制約付き多エージェント協調をウェイポイント時刻最適化問題として定式化した。
2. アルゴリズム開発: 非凸構造に適した微分可能な代理軌道モデルと、不正確射影 ADMM ソルバーを開発し、離散順序変数なしで衝突回避を解決した。
3. 実証評価: ランダム交差、ボトルネック、グラフベースネットワークなど多様なシナリオで手法を検証し、既存の階層的 MIP-SOCP ベースラインと比較して、より短時間で効率的なスケジュールを生成できることを示した。

4. 実験結果 (Results)

シミュレーションは、ランダム交差、ボトルネック、グラフネットワークの 3 つのシナリオで行われました。

• ランダム交差（同方向・対向）:
  • 対向するエージェント間の衝突（ヘッドオン）は特に困難ですが、提案手法は適応的モーメントにより数値的なデッドロックを回避し、400 回以下の反復で収束しました。
  • 占有密度（Crowding level）が高くなっても、多くのケースで成功し、旅行時間のオーバーヘッドは限定的でした。
• ボトルネックシナリオ:
  • 狭い廊下を通過するシナリオでは、空間的な回避が不可能なため、速度調整による順序付けが必須です。
  • 提案手法は、エージェントが自然に列を形成し、中程度の速度調整で衝突を解決できることを示しました。
  • 比較評価: 既存の階層的 MIP-SOCP ベースラインと比較し、特に高密度（$\phi=10\%$）において、ベースラインが実行不可能（Infeasible）となったのに対し、提案手法は実行可能かつより短い完了時間を達成しました。
• グラフベースネットワーク（UAM 等）:
  • 事前定義されたエッジを移動するシナリオで、幾何学的な制約（安全距離がノード間距離に対して大きすぎると解が存在しない）の限界を明確に示しました。
  • 幾何学的に実行可能な領域内では、高い成功率（100%）と効率的な解決が得られました。

5. 意義と結論 (Significance & Conclusion)

本論文の提案手法は、**「経路変更ができない環境」**における多エージェント協調の重要な課題に対して、以下のような意義を持ちます：

• スケーラビリティの向上: 離散変数（順序変数）を排除した連続最適化アプローチにより、エージェント数が増加しても組み合わせ爆発を回避し、計算効率が向上します。
• 実用性の高いモデル: 実際の制御システムにおける追従遅延をモデルに組み込むことで、理論的な計画と実機の実行のギャップを縮めています。
• 高性能な解決: 既存の手法よりも短時間でタスクを完了させることが可能であり、特に高密度な環境やボトルネック状況において優位性を示しました。

将来的には、より高忠実度な車両ダイナミクスへの対応や、不確実性を含むオンライン再計画への拡張が課題として挙げられています。