論文の概要: 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)
• 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)

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

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