論文の概要: Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space

• arxiv url: http://arxiv.org/abs/2404.01752v1
• Date: Tue, 2 Apr 2024 09:07:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-04-03 17:18:56.575514
• 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)の問題を考える。 そこで本研究では,各ロボットの衝突のない軌道を検知するサンプリングベースプランナを低レベルに構成する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%低い。

関連論文リスト

• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。 我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
  論文  参考訳（メタデータ） (2025-03-01T21:25:21Z)
• Risk-aware Integrated Task and Motion Planning for Versatile Snake Robots under Localization Failures [6.250953826294371]
  スネークロボットは、地球と宇宙の応用において、極端な地形や制限された環境を通して移動を可能にする。 この問題に対処するために、間欠的にスケジューリングされたスコープ(BLISS)を用いたブラインドモーションを提案する。 BLISSは、プロピロセプションのみのモビリティと間欠的なスキャンを組み合わせることで、ローカライゼーション障害と衝突リスクの両方に対して耐性がある。
  論文  参考訳（メタデータ） (2025-02-27T02:02:51Z)
• 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)
• Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
  ラベルなしの動作計画では、衝突回避を確保しながら、ロボットのセットを目標の場所に割り当てる。 この問題は、探査、監視、輸送などの応用において、マルチロボットシステムにとって不可欠なビルディングブロックを形成している。 この問題に対処するために、各ロボットは、その400ドルのアネレストロボットと$k$アネレストターゲットの位置のみを知っている分散環境で対処する。
  論文  参考訳（メタデータ） (2024-09-29T23:57:25Z)
• 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)
• 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)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)

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

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