マルチロボット運動計画2026/10/14arXiv:2610.20244

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

FPTAS for Polygonal Multi-Robot Motion Planning

多角形環境で複数の多角形ロボットを衝突なく最短で動かす問題に対し、ロボット数が固定なら任意の目的関数で初のFPTASを与えた。

詳しい要約

1. どんなもの？

- 多角形環境で多角形ロボットを並進移動させる 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 ロボットにも直接一般化できる。

2. 先行研究と比べてどこがすごい？

- 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 である。

3. 技術・手法の肝は？

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

4. どうやって有効だと検証した？

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

5. 議論はある？

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

6. 次に読むべき論文は？

- 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 研究

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue

分類: cs.CG, cs.DS, cs.RO

原文アブストラクト

We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain $\mathcal{W}$ with $n$ vertices and $k$ robots $R_1,\dots,R_k$ translating in $\mathcal{W}$ each of which is represented by a polygon of constant complexity. Given a source configuration $\mathbf{s}$ and a target configuration $\mathbf{t}$ of the robots in $\mathcal{W}$, the goal of the problem is to find a collision-free motion plan from $\mathbf{s}$ to $\mathbf{t}$ that is shortest with respect to some cost function. We present the first fully polynomial-time approximation schemes (FPTAS) for motion planning with any fixed number $k$ of robots, under the min-sum objective, the min-max objective, and the min-makespan objective. Here, the min-sum variant aims to minimize the total traveling distance of all robots, the min-max variant aims to minimize the maximum traveling distance of a single robot, and the min-makespan variant aims to minimize the total time cost under the assumption that all robots move with a maximum speed $1$. The algorithm directly generalizes to the problem in any fixed dimension $d$, with a polytope environment and polytope robots. Our result settles an open question of Agarwal, Halperin, Sharir, Steiger [SODA'24] and Agarwal, Holmgren, Steiger [SODA'26], who gave an FPTAS for $k=2$ unit-square robots and a bicriteria-approximation algorithm for a fixed number $k$ of unit-square or unit-disk robots, respectively. Compared to the previous results, our algorithm is substantially simpler.

arXivで原文を読む →arXiv概要ページ

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

詳しい要約

1. どんなもの？

2. 先行研究と比べてどこがすごい？

3. 技術・手法の肝は？

4. どうやって有効だと検証した？

5. 議論はある？

6. 次に読むべき論文は？

原文アブストラクト

関連論文