論文の概要: Large-Scale Multi-Robot Coverage Path Planning via Local Search
- arxiv url: http://arxiv.org/abs/2312.10797v1
- Date: Sun, 17 Dec 2023 19:14:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-19 14:33:22.593847
- Title: Large-Scale Multi-Robot Coverage Path Planning via Local Search
- Title（参考訳）: ローカルサーチによる大規模マルチロボットカバレッジ経路計画
- Authors: Jingtao Tang, Hang Ma
- Abstract要約: 本稿では,複数のロボットのカバレッジパスを計算することを目的とした,グラフベースのマルチロボットカバレッジパス計画(MCPP)について検討する。
我々はLS-MCPPと呼ばれる新しいアルゴリズムフレームワークを導入し、ローカル検索を活用して$D$で直接操作する。
実験ではLS-MCPPの有効性を実証し,初期解法を一貫して改善した。
- 参考スコア（独自算出の注目度）: 3.396452421780085
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to
compute coverage paths for multiple robots to cover all vertices of a given 2D
grid terrain graph $G$. Existing graph-based MCPP algorithms first compute a
tree cover on $G$ -- a forest of multiple trees that cover all vertices -- and
then employ the Spanning Tree Coverage (STC) paradigm to generate coverage
paths on the decomposed graph $D$ of the terrain graph $G$ by circumnavigating
the edges of the computed trees, aiming to optimize the makespan (i.e., the
maximum coverage path cost among all robots). In this paper, we take a
different approach by exploring how to systematically search for good coverage
paths directly on $D$. We introduce a new algorithmic framework, called
LS-MCPP, which leverages a local search to operate directly on $D$. We propose
a novel standalone paradigm, Extended-STC (ESTC), that extends STC to achieve
complete coverage for MCPP on any decomposed graphs, even those resulting from
incomplete terrain graphs. Furthermore, we demonstrate how to integrate ESTC
with three novel types of neighborhood operators into our framework to
effectively guide its search process. Our extensive experiments demonstrate the
effectiveness of LS-MCPP, consistently improving the initial solution returned
by two state-of-the-art baseline algorithms that compute suboptimal tree covers
on $G$, with a notable reduction in makespan by up to 35.7\% and 30.3\%,
respectively. Moreover, LS-MCPP consistently matches or surpasses the results
of optimal tree cover computation, achieving these outcomes with orders of
magnitude faster runtime, thereby showcasing its significant benefits for
large-scale real-world coverage tasks.
- Abstract（参考訳）: グラフベースのマルチロボット被覆経路計画(MCPP)は、与えられた2次元格子地形グラフのすべての頂点をカバーするために、複数のロボットのカバレッジパスを計算することを目的としている。
既存のグラフベースのMCPPアルゴリズムは、まず、すべての頂点をカバーする複数の木の森であるG$でツリーカバーを計算し、次に、分割されたグラフ上のカバレッジパスを生成するためにSpanning Tree Coverage (STC)パラダイムを使用します。
本稿では,$d$ で適切なカバレッジパスを体系的に検索する方法を検討することにより,異なるアプローチをとる。
我々はLS-MCPPと呼ばれる新しいアルゴリズムフレームワークを導入し、ローカル検索を活用して$D$で直接操作する。
本稿では,STCを拡張して,非完全地形グラフであっても,任意の分解グラフ上でMCPPの完全なカバレッジを実現する,新たなスタンドアロンパラダイムであるExtended-STC(ESTC)を提案する。
さらに,ESTCを3種類の新しい近傍演算子と統合し,その探索過程を効果的にガイドする方法を示す。
我々はLS-MCPPの有効性を実証し、それぞれ35.7\%と30.3\%という顕著な減少率で、準最適木被覆をG$で計算する2つの最先端ベースラインアルゴリズムによって得られた初期解を一貫して改善した。
さらに、LS-MCPPは最適な木被覆計算の結果と一貫して一致または上回り、これらの結果を桁違いに高速な実行で達成し、大規模な実世界のカバレッジタスクにおいてその大きな利点を示す。
関連論文リスト
- Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
教師なしの地上距離学習アプローチが導入されました
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
論文 参考訳（メタデータ） (2024-11-11T23:21:01Z) - LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Graph Sparsification via Mixture of Graphs [67.40204130771967]
そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。
MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。
5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
論文 参考訳（メタデータ） (2024-05-23T07:40:21Z) - Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs [7.616556723260849]
本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリング(HC)アルゴリズムを提案する。
明確なクラスタ構造を持つ任意の入力グラフ$G$に対して、我々の設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に実行される。
設計したアルゴリズムは、より少ない実行時間で、より優れたHCツリーを生成する。
論文 参考訳（メタデータ） (2023-06-16T16:31:46Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。
Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
論文 参考訳（メタデータ） (2022-09-28T09:55:47Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳（メタデータ） (2022-02-18T02:54:58Z) - Large-Scale Network Embedding in Apache Spark [1.3769786711365102]
本稿では,Apache Sparkを用いた大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。
提案手法は数時間で数十億のエッジを持つグラフを処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
論文 参考訳（メタデータ） (2021-06-20T04:42:24Z) - Waypoint Planning Networks [66.72790309889432]
本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。
我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。
WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
論文 参考訳（メタデータ） (2021-05-01T18:02:01Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。
textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2020-10-12T17:51:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。