多角形環境におけるマルチロボット運動計画のFPTAS

- 多角形環境で多角形ロボットを並進移動させる multi-robot motion planning を扱う。 - 環境 W は n 頂点の polygonal domain、ロボット R_1,...,R_k は定数複雑度の polygon。 - 与えられた source configuration s から target configuration t への衝突のない最短 motion plan を求める。 - 固定された任意のロボット数 k に対し、min-sum、min-max、min-makespan の各目的関数で初の FPTAS を与える。 - 任意の固定次元 d の polytope 環境・polytope ロボットにも直接一般化できる。

- Agarwal, Halperin, Sharir, Steiger [SODA'24] は k=2 の unit-square robots に対する FPTAS を与えていた。 - Agarwal, Holmgren, Steiger [SODA'26] は固定 k の unit-square または unit-disk robots に対する bicriteria-approximation algorithm を与えていた。 - 本研究はこれらの open question を解決し、任意の固定 k と一般の polygonal robots に対する FPTAS を初めて与える。 - 先行結果と比べてアルゴリズムは substantially simpler である。

- 固定された任意のロボット数 k に対する FPTAS を構成する。 - min-sum、min-max、min-makespan の3目的関数を扱う。 - min-makespan では全ロボットが最大速度 1 で動く仮定の下で総時間コストを最小化する。 - 任意の固定次元 d の polytope 環境・polytope ロボットへ直接一般化する。 - 具体的なアルゴリズムの詳細は要旨からは不明。

- 要旨からは不明。 - 理論的な近似保証 (FPTAS) の提示が主な主張であり、実験的検証については記述がない。

- 本研究は Agarwal ら [SODA'24] と Agarwal ら [SODA'26] の open question を解決する。 - 先行研究の unit-square/unit-disk robots より一般の polygonal robots と任意固定 k を扱う。 - アルゴリズムが substantially simpler である点を主張する。 - 限界や未解決問題についての議論は要旨からは不明。

- Agarwal, Halperin, Sharir, Steiger [SODA'24] (k=2 unit-square robots の FPTAS) - Agarwal, Holmgren, Steiger [SODA'26] (固定 k の unit-square/unit-disk robots の bicriteria-approximation) - 関連する multi-robot motion planning の FPTAS/approximation 研究