論文の概要: Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability

• arxiv url: http://arxiv.org/abs/2410.17160v1
• Date: Tue, 22 Oct 2024 16:34:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:27:48.129527
• Title: Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability
• Title（参考訳）: 層状LA-MAPF: 溶剤MAPFインスタンスを分解し, 可溶性を損なうことなく解法を高速化する
• Authors: Zhuo Yao,
• Abstract要約: 近年,Multi-Agent Path Finding (MAPF) が広く研究されている。 既存のMAPFアルゴリズムの多くは、エージェントがグリッドベースのマップ内の1つのグリッドしか占有していないと仮定している。 textbfLayered LA-MAPFは、幾何学的エージェントを含むMAPFインスタンスをクラスタに分解する手法である。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Multi-Agent Path Finding (MAPF) has been widely studied in recent years. However, most existing MAPF algorithms assume that an agent occupies only a single grid in a grid-based map. This assumption limits their applicability in many real-world domains where agents have geometric shapes, rather than being point-like. Such agents, which can occupy multiple cells simultaneously, are referred to as ``large'' agents. When considering the shape and size of agents in MAPF, the computational complexity increases significantly as the number of agents grows, primarily due to the increased overhead in conflict detection between geometric agents. In this paper, we propose two types of subproblems for the LA-MAPF (Large-Agent MAPF) problem: \textbf{cluster} (which has no constraints on the order of solution) and \textbf{level} (which imposes constraints on the solution order). We introduce \textbf{Layered LA-MAPF}, a method that decomposes a MAPF instance involving geometric agents into clusters, and then further decomposes each cluster into levels. This approach aims to reduce time complexity when solving LA-MAPF problems. Our results demonstrate the performance of our method as the number of agents increases across various maps, and how it accelerates LA-MAPF methods, such as LA-CBS and LA-LaCAM. Experiments show that our LA-MAPF method with instance decomposition \textbf{halves the time cost (reducing from an average of 40s to 20s) and triples the success rate (from an average of 0.27 to 0.80)} in finding a solution within 60 seconds. To facilitate further research, we have made the source code for Layered LA-MAPF publicly available at \url{https://github.com/JoeYao-bit/LayeredMAPF/algorithm/LA-MAPF}.
• Abstract（参考訳）: 近年,Multi-Agent Path Finding (MAPF) が広く研究されている。 しかし、既存のMAPFアルゴリズムの多くは、エージェントがグリッドベースのマップ内の1つのグリッドしか占有していないと仮定している。 この仮定は、エージェントが点のような形ではなく幾何学的形状を持つ多くの実世界の領域で適用性を制限する。 複数の細胞を同時に占有できるこのようなエージェントは ` `large'' エージェントと呼ばれる。 MAPFにおけるエージェントの形状とサイズを考慮すると、主に幾何学的エージェント間の衝突検出のオーバーヘッドが増大するため、エージェントの数が増加するにつれて、計算の複雑さが大幅に増大する。 本稿では,LA-MAPF (Large-Agent MAPF) 問題に対する2種類のサブプロブレムを提案する: \textbf{cluster} (解の順序に制約がない) と \textbf{level} (解の順序に制約を課す)。 我々は、幾何学的エージェントを含むMAPFインスタンスをクラスタに分解し、さらに各クラスタをレベルに分解する方法である、textbf{Layered LA-MAPF}を紹介する。 このアプローチは、LA-MAPF問題を解決する際の時間的複雑さを低減することを目的としている。 本研究はLA-MAPF法,LA-CBS法,LA-LaCAM法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-CBS法,LA-LaCAM法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-MAPF法, LA-MAPF法, LA-MAPF法, LA-MAPAM法, LA-MAPF法, LA-MAPF法, LA-MAPF法, LA-MAPF法, LA-MAPF法, LA-LA-LA-LACAM法, LA-LaCAM法, , LA-MAPF法, LA-MAPF法, LA-MAPF法, LA-MAPF法,LA-MAPF法,LA-MAPF法,LA-MAPF法,LA- 実験により, LA-MAPF法は, 60秒以内で解を求める場合, 時間コスト(平均40秒から20秒まで)を3倍にし, 成功率(平均0.27から0.80まで)を3倍にすることがわかった。 さらなる研究を容易にするため、Layered LA-MAPF のソースコードを \url{https://github.com/JoeYao-bit/LayeredMAPF/algorithm/LA-MAPF} で公開しました。

関連論文リスト

• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  マルチエージェントパスフィンディング(Multi-agent pathfinding)は、共有環境における複数のエージェントの衝突のないパスを見つけることを必要とする、難しい計算問題である。 我々はMAPF-GPTと呼ばれるMAPF問題の基盤モデルを構築した。 擬似学習を用いて、部分観測可能性の条件下での行動を生成するための準最適専門家軌道のセットに関する政策を訓練した。 MAPF-GPTは、様々な問題インスタンスにおいて、現在最も優れた学習可能なMAPF解法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-29T12:55:10Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。 本稿では,MAPFにエージェントを誘導する手法を提案する。 各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
  論文  参考訳（メタデータ） (2023-08-22T07:17:39Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Leveraging Experience in Lifelong Multi-Agent Pathfinding [12.401344261399613]
  Lifelong Multi-Agent Path Finding (L-MAPF) では、エージェントのチームが互いに衝突を避けながらタスクのストリームを実行する。 本稿では,新しいRHCRにインスパイアされたアプローチであるexRHCRを紹介する。 ExRHCRはL-MAPFをRHCRよりも25%高速に解決し、与えられたタスクストリームのスループットを最大で16%向上させる。
  論文  参考訳（メタデータ） (2022-02-09T10:41:35Z)
• Subdimensional Expansion Using Attention-Based Learning For Multi-Agent Path Finding [9.2127262112464]
  MAPF(Multi-Agent Path Finding)は、各開始点から目標地点までの複数のエージェントに対する競合のないパスを見つける。 我々は、この学習に基づくシングルエージェントプランナーをM*に統合することにより、LM*と呼ばれる新しいマルチエージェントプランナーを開発する。 以上の結果から,M* と比較した場合,LM* はコンフリクトが少なく,高速に動作し,高い成功率を享受できることがわかった。
  論文  参考訳（メタデータ） (2021-09-29T20:01:04Z)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  マルチエージェントPPO(MAPPO)は、集中型値関数を採用するマルチエージェントPPOバリアントである。 MAPPOは,3つの一般的なマルチエージェントテストベッドにおいて,最先端技術に匹敵する性能を実現していることを示す。
  論文  参考訳（メタデータ） (2021-03-02T18:59:56Z)
• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
  MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。 そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-05-15T06:07:15Z)

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

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