論文の概要: Combining Safe Intervals and RRT* for Efficient Multi-Robot Path Planning in Complex Environments
- arxiv url: http://arxiv.org/abs/2404.01752v2
- Date: Mon, 26 Aug 2024 07:32:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-27 23:56:35.815064
- Title: Combining Safe Intervals and RRT* for Efficient Multi-Robot Path Planning in Complex Environments
- Title（参考訳）: 複合環境における効率的なマルチロボット経路計画のための安全区間とRT*の組み合わせ
- Authors: Joonyeol Sim, Joonkyung Kim, Changjoo Nam,
- Abstract要約: 本研究では、競合のない経路を見つけるために、連続空間におけるMRPP(Multi-Robot Path Planning)の問題を考える。
そこで本研究では,各ロボットの衝突のない軌道を検知するサンプリングベースプランナを低レベルに構成する2段階の手法を提案する。
実験結果から,SI-RRT* は少数のサンプルで高速に高品質な解を見つけることができることがわかった。
- 参考スコア（独自算出の注目度）: 4.678150356894013
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper, we consider the problem of Multi-Robot Path Planning (MRPP) in continuous space to find conflict-free paths. The difficulty of the problem arises from two primary factors. First, the involvement of multiple robots leads to combinatorial decision-making, which escalates the search space exponentially. Second, the continuous space presents potentially infinite states and actions. For this problem, 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 find a high-quality solution quickly with a small number of samples. SI-CPP exhibits improved scalability while SI-CCBS produces higher-quality solutions compared to the state-of-the-art planners for continuous space. Compared to the most scalable existing algorithm, SI-CPP achieves a success rate that is up to 94% higher with 100 robots while maintaining solution quality (i.e., flowtime, the sum of travel times of all robots) without significant compromise. SI-CPP also decreases the makespan up to 45%. SI-CCBS decreases the flowtime by 9% compared to the competitor, albeit exhibiting a 14% lower success rate.
- Abstract（参考訳）: 本稿では、競合のない経路を見つけるために、連続空間におけるマルチロボットパス計画(MRPP)の問題を検討する。
問題の難しさは2つの主要な要因から生じる。
第一に、複数のロボットの関与は、指数関数的に探索空間をエスカレートする組合せ決定につながる。
第二に、連続空間は潜在的に無限の状態と作用を示す。
そこで本研究では,低レベルをサンプリングベースとしたセーフインターバルRT* (SI-RRT*) とし,個々のロボットに対して衝突のない軌道を求める2段階のアプローチを提案する。
高レベルは、優先順位付け計画(SI-CPP)と競合ベース探索(SI-CCBS)という2つの代表的手法を用いて、ロボット間の衝突を解消できるあらゆる方法を使用することができる。
実験結果から,SI-RRT* は少数のサンプルで高速に高品質な解を見つけることができることがわかった。
SI-CPPは拡張性の向上を示し、SI-CCBSは連続空間の最先端プランナーに比べて高品質なソリューションを生産している。
最もスケーラブルな既存のアルゴリズムと比較して、SI-CPPは、ソリューションの品質(フロータイム、全ロボットの走行時間の合計)を維持しながら、大きな妥協なしに最大94%の成功率を達成する。
SI-CPPはまた、メイクパンを45%まで減少させる。
SI-CCBSは競争相手と比較して流速を9%減少させるが、成功率は14%低い。
関連論文リスト
- 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) - Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
ラベルなしの動作計画では、衝突回避を確保しながら、ロボットのセットを目標の場所に割り当てる。
この問題は、探査、監視、輸送などの応用において、マルチロボットシステムにとって不可欠なビルディングブロックを形成している。
この問題に対処するために、各ロボットは、その400ドルのアネレストロボットと$k$アネレストターゲットの位置のみを知っている分散環境で対処する。
論文 参考訳（メタデータ） (2024-09-29T23:57:25Z) - 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) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
本稿では,倉庫環境における移動ロボットのためのタスク割り当てと分散ナビゲーションアルゴリズムを提案する。
本稿では,共同分散タスク割り当てとナビゲーションの問題について考察し,それを解決するための2段階のアプローチを提案する。
ロボットの衝突のない軌道の計算では,タスク完了時間において最大14%の改善と最大40%の改善が観察される。
論文 参考訳（メタデータ） (2022-09-07T00:35:27Z) - Intelligent Trajectory Design for RIS-NOMA aided Multi-robot
Communications [59.34642007625687]
目的は,ロボットの軌道とNOMA復号命令を協調的に最適化することで,マルチロボットシステムにおける全軌道の総和率を最大化することである。
ARIMAモデルとDouble Deep Q-network (D$3$QN)アルゴリズムを組み合わせたML方式を提案する。
論文 参考訳（メタデータ） (2022-05-03T17:14:47Z) - Distributed Swarm Collision Avoidance Based on Angular Calculations [0.0]
本稿では,高密度で複雑な2Dおよび3D環境のための分散リアルタイムアルゴリズムを提案する。
角計算を用いて、各ロボットの動きの最適な方向を選択する。
提案手法は,ハエ群集の完全自律航法を可能にする。
論文 参考訳（メタデータ） (2021-08-29T23:12:38Z) - 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) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。