論文の概要: Caching-Augmented Lifelong Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2403.13421v1
- Date: Wed, 20 Mar 2024 09:07:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 17:28:32.130170
- Title: Caching-Augmented Lifelong Multi-Agent Path Finding
- Title（参考訳）: キャッシングによる長寿命マルチエージェントパスの探索
- Authors: Yimin Tang, Zhenghong Yu, Yi Zheng, T. K. Satish Kumar, Jiaoyang Li, Sven Koenig,
- Abstract要約: Lifelong MAPFは、最初の目標を達成すればすぐにターゲットをエージェントに割り当てるが、現実の倉庫計画のより正確な近似を提供する。
本稿では,Lifelong MAPFの性能向上を目的とした,Caching-Augmented Lifelong MAPF (CAL-MAPF) という新しいメカニズムを提案する。
- 参考スコア（独自算出の注目度）: 25.575748142768298
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-Agent Path Finding (MAPF), which involves finding collision-free paths for multiple robots, is crucial in various applications. Lifelong MAPF, where targets are reassigned to agents as soon as they complete their initial objectives, offers a more accurate approximation of real-world warehouse planning. In this paper, we present a novel mechanism named Caching-Augmented Lifelong MAPF (CAL-MAPF), designed to improve the performance of Lifelong MAPF. We have developed a new map grid type called cache for temporary item storage and replacement and designed a lock mechanism for it to improve the stability of the planning solution. This cache mechanism was evaluated using various cache replacement policies and a spectrum of input task distributions. We identified three main factors significantly impacting CAL-MAPF performance through experimentation: suitable input task distribution, high cache hit rate, and smooth traffic. Overall, CAL-MAPF has demonstrated potential for performance improvements in certain task distributions, maps and agent configurations.
- Abstract（参考訳）: マルチエージェントパス探索(MAPF: Multi-Agent Path Finding)は、複数のロボットの衝突のない経路を見つけることを含む、様々な用途において重要である。
Lifelong MAPFは、最初の目標を達成すればすぐにターゲットをエージェントに割り当てるが、現実の倉庫計画のより正確な近似を提供する。
本稿では,ライフロングMAPFの性能向上を目的とした,Caching-Augmented Lifelong MAPF (CAL-MAPF) という新しいメカニズムを提案する。
我々は、一時的アイテム記憶と交換のためのキャッシュと呼ばれる新しいマップグリッドタイプを開発し、計画ソリューションの安定性を改善するためのロック機構を設計した。
このキャッシュ機構は、様々なキャッシュ置換ポリシーと入力タスク分布のスペクトルを用いて評価された。
実験によりCAL-MAPFの性能に顕著な3つの要因を同定した: 適切な入力タスク分布、高いキャッシュヒット率、スムーズなトラフィック。
全体として、CAL-MAPFは特定のタスク分布、マップ、エージェント設定のパフォーマンス改善の可能性を実証している。
関連論文リスト
- Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability [0.0]
近年,Multi-Agent Path Finding (MAPF) が広く研究されている。
既存のMAPFアルゴリズムの多くは、エージェントがグリッドベースのマップ内の1つのグリッドしか占有していないと仮定している。
textbfLayered LA-MAPFは、幾何学的エージェントを含むMAPFインスタンスをクラスタに分解する手法である。
論文 参考訳（メタデータ） (2024-10-22T16:34:24Z) - 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) - DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding [25.756524895372454]
Multi-Agent Combinatorial Path Finding (MCPF)は、初期から目標地点までの複数のエージェントの衝突のない経路を求める。
最近の研究は、目標における個々の到着時間の総和を最小化しながら、MPPFに対処する方法を開発している。
本稿では,MCPF の min-max 変種である MCPF-max を提案する。
論文 参考訳（メタデータ） (2023-12-11T11:53:31Z) - SQLNet: Scale-Modulated Query and Localization Network for Few-Shot
Class-Agnostic Counting [71.38754976584009]
CAC(class-agnostic counting)タスクは、最近、任意のクラスの全てのオブジェクトを、入力画像にいくつかの例を付与してカウントする問題を解くために提案されている。
我々は、スケール変調クエリーおよびローカライズネットワーク(Net)と呼ばれる、新しいローカライズベースのCACアプローチを提案する。
クエリとローカライゼーションの段階において、模範者のスケールを完全に探求し、各オブジェクトを正確に位置付けし、その近似サイズを予測することで、効果的なカウントを実現している。
論文 参考訳（メタデータ） (2023-11-16T16:50:56Z) - 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) - Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement
in Large-Scale Warehouses [6.852682268049646]
自動倉庫におけるマルチロボット棚配置問題をモデル化した新しい問題定式化Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD)を導入する。
本稿では,DD-MAPD インスタンスを MAPF インスタンスに分解し,棚の軌道をコーディネートするMAPF-DECOMP と,エージェントの経路を計算するためのMAPD インスタンスを提案する。
実験の結果,MAPF-DECOMPの効率と有効性を示し,1000台以上の棚と数百台のエージェントをほんの数分で大規模インスタンスの高品質なソリューションを計算できることを示した。
論文 参考訳（メタデータ） (2023-04-27T16:26:05Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳（メタデータ） (2022-11-04T16:10:50Z) - POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
POGEMAは、部分的に観測可能なマルチエージェントパスフィンディング(PO-MAPF)問題に挑戦するためのサンドボックスである。
様々なPO-MAPFに合わせることができ、プランニングと学習のための優れた試験場として機能する。
論文 参考訳（メタデータ） (2022-06-22T09:39:50Z) - Learning Space Partitions for Path Planning [54.475949279050596]
PlaLaMは2次元ナビゲーションタスクにおける既存の経路計画手法よりも優れており、特に難解な局所最適化の存在下では優れている。
これらは高マルチモーダルな実世界のタスクに移行し、コンパイラフェーズでは最大245%、分子設計では最大0.4の強いベースラインを0-1スケールで上回ります。
論文 参考訳（メタデータ） (2021-06-19T18:06:11Z) - Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。
そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-05-15T06:07:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。