論文の概要: Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction

• arxiv url: http://arxiv.org/abs/2411.01707v1
• Date: Sun, 03 Nov 2024 22:37:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:46:40.807942
• Title: Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction
• Title（参考訳）: 経路分割を有する格子上の大規模マルチロボット被覆経路計画
• Authors: Jingtao Tang, Zining Mao, Hang Ma,
• Abstract要約: マルチロボット被覆経路計画(MCPP: Multi-Robot Coverage Path Planning)を4つの隣接する2DグリッドG上で検討し、複数のロボットがGのすべてのセルをカバーする経路を計算することを目的とした。 問題を直接Gで修正し、グリッドベースのMCPPの解法を革新し、新しいNP硬度結果を確立する。 提案手法は,最大100台のロボットを最大256x256まで実行時間内にグリッド上で管理することにより,ソリューションの品質と効率を大幅に向上することを示す。
• 参考スコア（独自算出の注目度）: 2.5580729045474015
• License:
• Abstract: We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G. Traditional approaches are limited as they first compute coverage trees on a quadrant coarsened grid H and then employ the Spanning Tree Coverage (STC) paradigm to generate paths on G, making them inapplicable to grids with partially obstructed 2x2 blocks. To address this limitation, we reformulate the problem directly on G, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We introduce Extended-STC (ESTC), a novel paradigm that extends STC to ensure complete coverage with bounded suboptimality, even when H includes partially obstructed blocks. Furthermore, we present LS-MCPP, a new algorithmic framework that integrates ESTC with three novel types of neighborhood operators within a local search strategy to optimize coverage paths directly on G. Unlike prior grid-based MCPP work, our approach also incorporates a versatile post-processing procedure that applies Multi-Agent Path Finding (MAPF) techniques to MCPP for the first time, enabling a fusion of these two important fields in multi-robot coordination. This procedure effectively resolves inter-robot conflicts and accommodates turning costs by solving a MAPF variant, making our MCPP solutions more practical for real-world applications. Extensive experiments demonstrate that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as 256x256 within minutes of runtime. Validation with physical robots confirms the feasibility of our solutions under real-world conditions.
• Abstract（参考訳）: 従来の手法では,まず4つの粗い格子 H 上の被覆木を計算し,次にSpanning Tree Coverage (STC) パラダイムを用いてG 上の経路を生成することで,部分的に閉塞された2x2ブロックの格子に適用できない。 この制限に対処するため、G 上で問題を直接修正し、グリッドベースの MCPP 解決を革新し、新しい NP-hardness 結果を確立する。 我々は, H が部分的に閉塞されたブロックを含む場合でも, STC を拡張して有界な準最適範囲で完全なカバレッジを確保する新しいパラダイムである Extended-STC (ESTC) を導入する。 従来のグリッドベースMCPPとは違い,本手法では,マルチエージェントパス探索(MAPF)技術を初めてMCPPに適用し,これら2つの重要な分野の融合を実現している。 本手法はロボット間の競合を効果的に解決し,MAPFの変種を解くことにより,実世界のアプリケーションにとってより実用的なMCPPソリューションを実現する。 大規模な実験により、我々のアプローチはソリューションの品質と効率を大幅に改善し、最大100台のロボットを最大256x256まで実行時間内にグリッド上で管理することを示した。 物理的なロボットによる検証は、現実の条件下でのソリューションの実現可能性を確認する。

関連論文リスト

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。 我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
  論文  参考訳（メタデータ） (2025-02-14T15:21:27Z)
• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  複雑な無線環境における経路計画を実現するために,視覚言語モデル(VLM)を用いた新しい手法を提案する。 この目的のために、実世界の無線レイトレーシングデータを用いたデジタルツインからの洞察を探索する。 その結果, SCoTT はDP-WA* と比較して非常に近い平均経路ゲインを実現し, 同時に一貫した経路長が得られることがわかった。
  論文  参考訳（メタデータ） (2024-11-27T10:45:49Z)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。 我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。 古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
  論文  参考訳（メタデータ） (2024-04-25T07:41:47Z)
• Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space [4.678150356894013]
  連続空間におけるMRPP(Multi-Robot Path Planning)の問題点を考察する。 本稿では,低レベルをサンプリングベースとしたSafe Interval RRT* (SI-RRT*) とし,個々のロボットに対して衝突のない軌道を求める2段階のアプローチを提案する。
  論文  参考訳（メタデータ） (2024-04-02T09:07:12Z)
• Multi-Robot Connected Fermat Spiral Coverage [2.8750175877666653]
  我々は,Multi-Robot Connected Fermat Spiral (MCFS)を紹介した。 MCFSはコンピュータグラフィックスコミュニティから、初めてマルチロボットのコーディネーションに適応する。 我々の研究はMCPPにおける重要なステップであり、複雑な環境下でのマルチロボットシステムの能力向上のために、コンピュータグラフィックスと自動計画原則の融合を示す。
  論文  参考訳（メタデータ） (2024-03-20T05:23:24Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• The Parameterized Complexity of Coordinated Motion Planning [28.39902924923273]
  コーディネート・モーション・プランニング(CMP)では、$k$ロボットが異なるスタート・グリッドポイントを$k$で占有し、異なる目的地・グリッドポイントに$k$で到達する必要がある。 目標は、目標目標を最小限に抑えるために、$k$のロボットを目的地に移動するためのスケジュールを計算することだ。 本稿では,CMP-MとCMP-Lのパラメータ化複雑性を2つの基本パラメータについて検討する。
  論文  参考訳（メタデータ） (2023-12-12T10:26:01Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。 本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
  論文  参考訳（メタデータ） (2022-03-26T20:37:14Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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