論文の概要: 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まで実行時間内にグリッド上で管理することを示した。
物理的なロボットによる検証は、現実の条件下でのソリューションの実現可能性を確認する。
関連論文リスト
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming [36.13745722329505]
本稿では,大規模線形計画問題の解法として PDHG-Net と呼ばれる FOM-Unrolled Neural Network (NN) を提案する。
提案手法は,大規模LP問題に対するFOMと比較して,最大3ドル以上の高速化を実現することができることを示す。
論文 参考訳（メタデータ） (2024-06-04T02:39:42Z) - 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) - Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。
本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。
メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
論文 参考訳（メタデータ） (2024-04-03T05:32:10Z) - 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) - Large-Scale Multi-Robot Coverage Path Planning via Local Search [3.396452421780085]
本稿では,複数のロボットのカバレッジパスを計算することを目的とした,グラフベースのマルチロボットカバレッジパス計画(MCPP)について検討する。
我々はLS-MCPPと呼ばれる新しいアルゴリズムフレームワークを導入し、ローカル検索を活用して$D$で直接操作する。
実験ではLS-MCPPの有効性を実証し,初期解法を一貫して改善した。
論文 参考訳（メタデータ） (2023-12-17T19:14:07Z) - 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) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。