制約環境におけるマルチエージェント動作計画と衝突回避のためのMILPベース解法

制約環境下での multi-agent motion planning と衝突回避のための mixed-integer linear program (MILP) を提案する研究。Polytopic Action-based Motion Planning (PAAMP) を sequence-then-solve パイプラインに組み込み、各 agent を隣接する凸 polytope 列に制限しつつ、big-M hyperplane model で agent 間の分離を強制する。L1 の path-length-plus-acceleration コストで滑らかな軌道を得る。

- naive な MILP 定式化と比較し、衝突制約を同一または隣接 region を共有する agent のみに適用することで binary variables を指数的に削減。 - 障害物を含む代表的な multi-agent シナリオで、unstructured MILP baseline より桁違いに高速に衝突のない軌道を生成。 - 有限時間収束を証明している点も特徴。

- Polytopic Action-based Motion Planning (PAAMP) を sequence-then-solve pipeline に埋め込む。 - region sequences により各 agent を隣接する convex polytopes に閉じ込める。 - big-M hyperplane model で inter-agent separation を強制。 - 衝突制約は同一または隣接 region を共有する agent のみに適用し binary variables を削減。 - L1 path-length-plus-acceleration cost で滑らかな軌道を生成。

- 障害物を含む代表的な multi-agent シナリオで実証。 - 提案手法が衝突のない軌道を生成することを確認。 - unstructured MILP baseline と比較し、桁違いに高速であることを示す。 - 有限時間収束の証明も提示。

要旨からは不明。

- unstructured MILP baseline（本論文で比較対象） - Polytopic Action-based Motion Planning (PAAMP) の原論文 - big-M を用いた MILP ベースの multi-agent collision avoidance の既存研究