論文の概要: 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%低い。
関連論文リスト
- 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) - Fast Continuous and Integer L-shaped Heuristics Through Supervised
Learning [4.521119623956821]
混合整数線形二段階プログラムの解を高速化する手法を提案する。
我々は,第2段階の要求の高い問題を解決することを目的としている。
私たちの中核となる考え方は、オンラインソリューションの時間を大幅に削減し、第一段階ソリューションの精度を小さくすることです。
論文 参考訳(メタデータ) (2022-05-02T13:15:32Z) - Distributed Swarm Collision Avoidance Based on Angular Calculations [0.0]
本稿では,高密度で複雑な2Dおよび3D環境のための分散リアルタイムアルゴリズムを提案する。
角計算を用いて、各ロボットの動きの最適な方向を選択する。
提案手法は,ハエ群集の完全自律航法を可能にする。
論文 参考訳(メタデータ) (2021-08-29T23:12:38Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳(メタデータ) (2021-08-11T10:42:11Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。