論文の概要: Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
- arxiv url: http://arxiv.org/abs/2603.19502v1
- Date: Thu, 19 Mar 2026 22:10:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-23 19:48:38.905205
- Title: Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
- Title（参考訳）: 分離トレードオフの改善によるラベルなしマルチロボット運動計画
- Abstract要約: 多角形環境下でのユニットディスクロボットのラベルなしマルチロボット動作計画について検討する。
本稿では,ロボット分離と障害物分離の境界で異なるトレードオフを実現する一般化アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.7646713951724009
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al. (SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least $4$, and start--target distances of at least $3$, but without optimality guarantees. Solovey et al. (RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least $4$, and at least $\sqrt{5}\approx2.236$ from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is $2\tfrac{2}{3}$ and the obstacles-separation is $1\tfrac{2}{3}$, or (ii) the robots-separation is $\approx3.291$ and the obstacles-separation $\approx1.354$. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only $2$, and the obstacles-separation is $3$. Finally, we show that without any robots-separation assumption, obstacles-separation of at least $1.5$ may be necessary for a solution to exist.
- Abstract（参考訳）: 多角形環境下でのユニットディスクロボットのラベルなしマルチロボット動作計画について検討する。
この問題は一般には難しいが、多項式時間解は開始位置と目標位置の適切な分離仮定の下で存在する。
Banyassady et al (SoCG'22) はスタート・スタート・ターゲット・ターゲット距離が最低4ドル、スタート・ターゲット距離が最低3ドルだが最適性は保証されていない単純なポリゴンの実現性を保証する。
Solovey et al (RSS'15) は一般的な多角形領域において、より厳密な条件の下で準最適解を提供する: 開始/目標位置は、少なくとも4$と少なくとも$\sqrt{5}\approx2.236$のペア距離を持つ必要がある。
このことは多項式時間アルゴリズムがより密集した環境で得られるかどうかという問題を提起する。
本稿では,ロボット分離と障害物分離の境界の異なるトレードオフを実現する一般化されたアルゴリズムを提案する。
具体的には,多項式時間定数近似アルゴリズムを用いて全経路長の最小化を行う。
(i)ロボット分離は$2\tfrac{2}{3}$、障害物分離は$1\tfrac{2}{3}$、または
(ii)ロボット分離は$\approx3.291$、障害物分離は$\approx1.354$である。
さらに,ロボット分離がわずか2ドルであり,障害物分離が3ドルである場合,多項式時間解が得られる別の戦略を導入する。
最後に,ロボット分離の仮定がなければ,少なくとも1.5ドル以上の障害物分離が実現可能であることを示す。
関連論文リスト
- Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。
この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。
ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
論文 参考訳（メタデータ） (2026-07-28T21:10:39Z) - Min-Sum Uniform Coverage Problem by Autonomous Mobile Robots [0.2446672595462589]
移動ロボット群におけるテクスチミンサム一様被覆問題について検討した。
ロボットは動きを調整し、全ロボットが移動する総量を最小化する均一な空間に到達しなければならない。
本稿では,最小総移動コストのラインセグメンテーション設定において一様カバレッジを実現する決定論的分散アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-02-11T18:38:24Z) - Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT) [5.013737017051114]
我々は、デッドロック障害のある共通空間において、100万ドルのロボットが100万ドルの目標にナビゲートされる仕組みを検討する。
最適計画に基づく戦略を導出し、重複しない軌道を保証する。
本研究では, 時空間構造を最適輸送へ統合し, テクトitremodelplans と textitremodelplans の助けを借りて予測できることを示す。
論文 参考訳（メタデータ） (2025-08-28T20:47:33Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
3ドルの登録アプローチでは、1000万ドル(107ドル)以上のポイントペアを、99%以上のランダムなアウトレイアで処理することができる。
我々はこの手法をTEARと呼び、Trncated Entry-wise Absolute Residualsを演算するoutlier-robust損失を最小限にする。
論文 参考訳（メタデータ） (2024-04-01T04:43:39Z) - Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level
Optimization [11.638394339813154]
本稿では,ソーシャルミニゲームにおけるリアルタイム非協調型マルチロボットナビゲーションのための,完全に分散化されたアプローチを提案する。
我々のコントリビューションは新しいリアルタイムバイレベル最適化アルゴリズムであり、トップレベルの最適化は公正で衝突のない順序付けを演算する。
F$1/10のロボット、Clearpath Jackal、Boston Dynamics Spotを使って提案したアルゴリズムを現実世界に展開することに成功しました。
論文 参考訳（メタデータ） (2023-06-15T02:18:21Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - Multiagent Rollout and Policy Iteration for POMDP with Application to
Multi-Robot Repair Problems [1.6939372704265414]
有限状態および制御空間,部分状態観測,マルチエージェント構造を有する無限地平面割引動的プログラミング問題を考える。
本手法は、部分的に観測可能なマルチエージェント問題の計算問題に特に対処する。
論文 参考訳（メタデータ） (2020-11-09T06:51:50Z) - Optimal Sequential Task Assignment and Path Finding for Multi-Agent
Robotic Assembly Planning [42.38068056643171]
本研究では,タスク間優先制約のあるアプリケーションにおいて,ロボットの大規模チームに対する逐次的タスク割り当てと衝突のないルーティングの問題について検討する。
本稿では,その問題に対する等間隔最適解を計算するための階層的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T00:45:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。