高密度環境下でラベル付き円盤の最適性保証付き運動調整
Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density
ロボット密度50%超の極めて混雑した環境でも、ラベル付き円盤の衝突回避経路を多項式時間で定数倍最適に計画できる理論と、実用的な近似最適アルゴリズムを提案した。
著者: Rupesh Chinta, Shuai D. Han, Jingjin Yu
分類: cs.RO
原文アブストラクト
We push the limit in planning collision-free motions for routing uniform labeled discs in two dimensions. First, from a theoretical perspective, we show that the constant-factor time-optimal routing of labeled discs can be achieved using a polynomial-time algorithm with robot density over $50\%$ in the limit (i.e., over half of the workspace may be occupied by the discs). Second, from a more practical standpoint, we provide a high performance algorithm that computes near-optimal (e.g., $1.x$) solutions under the same density setting.
関連論文
- 限られた知覚を持つ複数ロボットによる3D検査のためのGPU常駐パイプラインマルチロボット経路計画
- 検証器を介したマルチLLM協調によるマルチロボット経路計画マルチロボット経路計画
- ペトリネットの全単模性を利用したタスク割当と経路探索の構造的整合性マルチロボット経路計画
- 連続空間におけるスケーラブルなマルチロボット経路計画のための安全区間RRT*マルチロボット経路計画
- マルチロボット経路計画のための競合ベース探索のターゲット並列化マルチロボット経路計画
- 自動駐車場の効率的な物理・アルゴリズム設計に向けてマルチロボット経路計画
