論文の概要: Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space
- arxiv url: http://arxiv.org/abs/2404.01752v3
- Date: Tue, 11 Feb 2025 13:46:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:03:26.306298
- Title: Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space
- Title(参考訳): 連続空間におけるスケーラブルなマルチロボット経路計画のためのセーフインターバルRT*
- Authors: Joonyeol Sim, Joonkyung Kim, Changjoo Nam,
- Abstract要約: 連続空間におけるMRPP(Multi-Robot Path Planning)の問題点を考察する。
本稿では,低レベルをサンプリングベースとしたSafe Interval RRT* (SI-RRT*) とし,個々のロボットに対して衝突のない軌道を求める2段階のアプローチを提案する。
- 参考スコア(独自算出の注目度): 4.678150356894013
- License:
- Abstract: In this paper, we consider the problem of Multi-Robot Path Planning (MRPP) in continuous space. The difficulty of the problem arises from the extremely large search space caused by the combinatorial nature of the problem and the continuous state space. We propose a two-level approach where the low level is a sampling-based planner Safe Interval RRT* (SI-RRT*) that finds a collision-free trajectory for individual robots. The high level can use any method that can resolve inter-robot conflicts where we employ two representative methods that are Prioritized Planning (SI-CPP) and Conflict Based Search (SI-CCBS). Experimental results show that SI-RRT* can quickly find a high-quality solution with a few samples. SI-CPP exhibits improved scalability while SI-CCBS produces higher-quality solutions compared to the state-of-the-art planners for continuous space.
- Abstract(参考訳): 本稿では,連続空間におけるMRPP(Multi-Robot Path Planning)の問題について考察する。
問題の難しさは、問題の組合せの性質と連続状態空間に起因する非常に大きな探索空間から生じる。
本稿では,低レベルをサンプリングベースとしたSafe Interval RRT* (SI-RRT*) とし,個々のロボットに対して衝突のない軌道を求める2段階のアプローチを提案する。
高レベルは、優先順位付け計画(SI-CPP)と競合ベース探索(SI-CCBS)という2つの代表的手法を用いて、ロボット間の衝突を解消できるあらゆる方法を使用することができる。
実験の結果,SI-RRT* はいくつかのサンプルを用いて,高品質な解を見つけることができることがわかった。
SI-CPPは拡張性の向上を示し、SI-CCBSは連続空間の最先端プランナーに比べて高品質なソリューションを生産している。
関連論文リスト
- Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction [2.5580729045474015]
マルチロボット被覆経路計画(MCPP: Multi-Robot Coverage Path Planning)を4つの隣接する2DグリッドG上で検討し、複数のロボットがGのすべてのセルをカバーする経路を計算することを目的とした。
問題を直接Gで修正し、グリッドベースのMCPPの解法を革新し、新しいNP硬度結果を確立する。
提案手法は,最大100台のロボットを最大256x256まで実行時間内にグリッド上で管理することにより,ソリューションの品質と効率を大幅に向上することを示す。
論文 参考訳(メタデータ) (2024-11-03T22:37:56Z) - Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory [87.62730694973696]
STEELは、単一軌道から外因性ブロックマルコフ決定過程の制御可能なダイナミクスを学習するための、最初の証明可能なサンプル効率アルゴリズムである。
我々は,STEELが正解であり,サンプル効率が良いことを証明し,STEELを2つの玩具問題で実証した。
論文 参考訳(メタデータ) (2024-10-03T21:57:21Z) - Multi-agent Path Finding in Continuous Environment [11.325849006178737]
本研究では,新たな連続環境競合探索(CE-CBS)アルゴリズムを提案する。
CE-CBSは、ハイレベル検索フレームワークのためのコンフリクトベースの検索(CBS)と低レベルパス計画のためのRT*を組み合わせる。
実験の結果、CE-CBSはMAPFの連続的な側面を連続的に考慮する他のアルゴリズムと競合していることがわかった。
論文 参考訳(メタデータ) (2024-09-16T19:23:04Z) - Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling [9.651071174735804]
本稿では,SSP問題に対するリスク対応型Rapidly-Exploring Random Trees (RRT*)計画アルゴリズムを提案する。
我々のモチベーションは、条件付きバリュー・アット・リスク尺度(CVaR)の段階的コヒーレンスと、SSP問題の最適部分構造に依存している。
解析の結果,木の成長過程にリスクを組み込むことで,騒音パラメータの変動に敏感でない長さの経路が得られることがわかった。
論文 参考訳(メタデータ) (2024-08-16T11:21:52Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳(メタデータ) (2023-04-01T15:50:18Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳(メタデータ) (2021-05-28T18:07:16Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳(メタデータ) (2021-05-05T03:36:00Z) - Online search of unknown terrains using a dynamical system-based path
planning approach [0.0]
この研究では、ロボットが障害物から離れて操縦し、短期間で空間全体を覆うのに役立つ新しいスケーラブルな技術を紹介します。
この手法を用いた場合、ロボットの性能は最先端のプランナーと比較して平均49%向上した。
論文 参考訳(メタデータ) (2021-03-22T14:00:04Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。