論文の概要: FPTAS for Polygonal Multi-Robot Motion Planning

• arxiv url: http://arxiv.org/abs/2610.20244v2
• Date: Tue, 20 Oct 2026 07:20:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-21 21:58:47.207974
• Title: FPTAS for Polygonal Multi-Robot Motion Planning
• Title（参考訳）: 多角形多足歩行計画のためのFPTAS
• Abstract要約: ロボットを用いた多角形環境におけるマルチロボット動作計画について検討する。 固定数$kのロボットを用いた動作計画のための完全基準自由近似スキーム(FPTAS)を初めて提示する。
• 参考スコア（独自算出の注目度）: 6.158863936552318
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 多角形ロボットを用いた多角形環境におけるマルチロボット動作計画について検討した。 問題の設定は多角形ドメイン $\mathcal{W}$ と $n$ vertices と $k$ のロボット $R_1,\dots,R_k$ の変換からなる。 ソース設定 $\mathbf{s}$ とターゲット設定 $\mathbf{t}$ のロボットの $\mathcal{W}$ が与えられた場合、問題の目標は、コスト関数に関して最も短い $\mathbf{s}$ から $\mathbf{t}$ までの衝突のない運動計画を見つけることである。 本研究では, 最小目標, 最小目標, 最小目標, 最小目標に基づいて, 固定数$k$のロボットによる動作計画のための最初の完全多項式時間近似スキーム(FPTAS)を提案する。 min-sum型は全ロボットの走行距離を最小化することを目的としており、min-max型は単一ロボットの走行距離を最大化することを目的としており、min-makespan型は全ロボットが最大速度で移動するという仮定の下で、総走行時間コストを最小化することを目的としている。 このアルゴリズムは、ポリトープ環境とポリトープロボットを用いて、任意の固定次元$d$で問題に直接一般化する。 Agarwal, Halperin, Sharir, Steiger [SODA'24] と Agarwal, Holmgren, Steiger [SODA'26] は FPTAS for $k=2$ Unit-square Robot と bicriteria-approximation algorithm for a fixed number $k$ of unit-square or unit-disk Robot をそれぞれ与えている。 従来の結果と比較すると,アルゴリズムはかなり単純である。

関連論文リスト

• Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs [0.7646713951724009]
  多角形環境下でのユニットディスクロボットのラベルなしマルチロボット動作計画について検討する。 本稿では,ロボット分離と障害物分離の境界で異なるトレードオフを実現する一般化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-19T22:10:47Z)
• Min-Sum Uniform Coverage Problem by Autonomous Mobile Robots [0.2446672595462589]
  移動ロボット群におけるテクスチミンサム一様被覆問題について検討した。 ロボットは動きを調整し、全ロボットが移動する総量を最小化する均一な空間に到達しなければならない。 本稿では,最小総移動コストのラインセグメンテーション設定において一様カバレッジを実現する決定論的分散アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-02-11T18:38:24Z)
• The Parameterized Complexity of Coordinated Motion Planning [28.39902924923273]
  コーディネート・モーション・プランニング(CMP)では、$k$ロボットが異なるスタート・グリッドポイントを$k$で占有し、異なる目的地・グリッドポイントに$k$で到達する必要がある。 目標は、目標目標を最小限に抑えるために、$k$のロボットを目的地に移動するためのスケジュールを計算することだ。 本稿では,CMP-MとCMP-Lのパラメータ化複雑性を2つの基本パラメータについて検討する。
  論文  参考訳（メタデータ） (2023-12-12T10:26:01Z)
• Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。 一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-08-20T11:56:02Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency [8.115135096974047]
  我々は、メートル法空間内の所定の$n$のサイトを訪れるために、$k$ロボットのパトロールスケジュールを見つけることの問題を考察する。 それぞれのロボットの最大速度は同じで、その目標は、どのサイトでも最大遅延を最小化することだ。 我々は,各サイトにおける最大重量と最小重量をそれぞれ$O(k2 log fracw_max$)と$w_min$の近似係数を持つa-timeアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-05T23:18:53Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。