論文の概要: A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems

• arxiv url: http://arxiv.org/abs/2402.13292v1
• Date: Mon, 19 Feb 2024 19:04:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-22 18:22:10.443337
• Title: A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems
• Title（参考訳）: 競合を意識したマルチロボットシステムの最適目標割当てアルゴリズム
• Authors: Aakash and Indranil Saha
• Abstract要約: マルチロボットアプリケーションは、衝突のない経路を確保しながら、各ロボットにユニークな目標を割り当てることを目的としている。 そこで本研究では,次の最適な割り当てを計算するための効率的な競合誘導手法を提案する。 複数のベンチマークワークスペース上で,最大100個のロボットに対して,我々のアルゴリズムを広範囲に評価した。
• 参考スコア（独自算出の注目度）: 6.853165736531941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The fundamental goal assignment problem for a multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths, minimizing the total movement cost. A plausible algorithmic solution to this NP-hard problem involves an iterative process that integrates a task planner to compute the goal assignment while ignoring the collision possibilities among the robots and a multi-agent path-finding algorithm to find the collision-free trajectories for a given assignment. This procedure involves a method for computing the next best assignment given the current best assignment. A naive way of computing the next best assignment, as done in the state-of-the-art solutions, becomes a roadblock to achieving scalability in solving the overall problem. To obviate this bottleneck, we propose an efficient conflict-guided method to compute the next best assignment. Additionally, we introduce two more optimizations to the algorithm -- first for avoiding the unconstrained path computations between robot-goal pairs wherever possible, and the second to prevent duplicate constrained path computations for multiple robot-goal pairs. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces. The results demonstrate that the proposed algorithm achieves nearly an order of magnitude speedup over the state-of-the-art algorithm, showcasing its efficacy in real-world scenarios.
• Abstract（参考訳）: マルチロボットアプリケーションの基本的な目標割り当て問題は、衝突のない経路を確保しながら各ロボットにユニークな目標を割り当てることであり、全体の移動コストを最小化することである。 このNPハード問題に対する妥当なアルゴリズム的解法は、ロボット間の衝突可能性を無視しながら、タスクプランナーを統合してゴール割り当てを計算する反復プロセスと、与えられた割り当てに対する衝突のない軌道を見つけるマルチエージェントパスフィンディングアルゴリズムを含む。 この手順は、現在の最高の割り当てから次の最適な割り当てを計算する方法を含む。 最先端のソリューションで行われているように、次の最高の割り当てを単純で計算する方法は、全体的な問題を解決する上でスケーラビリティを達成するための障害となります。 このボトルネックを回避するために,次の最適な割り当てを計算するための効率的な競合誘導手法を提案する。 さらに,このアルゴリズムにさらに2つの最適化を導入する。1つはロボットとゴーアペア間の制約のない経路計算を可能な限り回避すること,もう1つは複数のロボットとゴーアペアに対する制約付き経路計算の重複を防止することである。 複数のベンチマークワークスペース上で,最大100個のロボットのアルゴリズムを広範囲に評価した。 その結果,提案アルゴリズムは最先端のアルゴリズムに対してほぼ1桁の高速化を達成し,実世界のシナリオでの有効性を示した。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  本稿では,最小時間ステップにおけるシーンマップ構築の完全化を目的としたマルチロボットアクティブマッピングの問題点について検討する。 この問題の鍵は、より効率的なロボットの動きを可能にするゴール位置推定にある。 本稿では,ニューラルコマッピング(NeuralCoMapping)という新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-30T14:03:17Z)
• A distributed, plug-n-play algorithm for multi-robot applications with a priori non-computable objective functions [2.2452191187045383]
  マルチロボットアプリケーションでは、ミッションのユーザ定義の目的を一般的な最適化問題として当てはめることができる。 これらの問題には標準勾配の差分型アルゴリズムは適用できない。 本稿では,各ロボットのサブコスト関数を慎重に設計するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-14T20:40:00Z)
• Distributed Allocation and Scheduling of Tasks with Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams [2.294915015129229]
  本稿では,異なるロボットのタスクが時間的・優先的な制約に強く結びついているミッションに対して,タスク割り当てとスケジューリングを行うアルゴリズムを提案する。 マルチロボットシステムによって維持される温室の実用ユースケースへの計画手順の適用。
  論文  参考訳（メタデータ） (2021-09-07T13:44:28Z)
• 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)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  複数のロボット(MRPP)の経路計画は、ロボットが最初の位置から指定された目標位置までナビゲートできる非衝突経路を見つけるタスクを表します。 本稿では,既存の SAT ベースの MRPP アルゴリズムを,対象の Boolean 符号化を導出する各ロボットの候補経路の集合を分割することで拡張する。
  論文  参考訳（メタデータ） (2021-03-08T00:57:42Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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