論文の概要: Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement
in Large-Scale Warehouses
- arxiv url: http://arxiv.org/abs/2304.14309v1
- Date: Thu, 27 Apr 2023 16:26:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-28 12:42:08.603076
- Title: Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement
in Large-Scale Warehouses
- Title（参考訳）: 大型倉庫におけるダブルデッキ型マルチエージェントピックアップと配送
- Authors: Baiyu Li, Hang Ma
- Abstract要約: 自動倉庫におけるマルチロボット棚配置問題をモデル化した新しい問題定式化Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD)を導入する。
本稿では,DD-MAPD インスタンスを MAPF インスタンスに分解し,棚の軌道をコーディネートするMAPF-DECOMP と,エージェントの経路を計算するためのMAPD インスタンスを提案する。
実験の結果,MAPF-DECOMPの効率と有効性を示し,1000台以上の棚と数百台のエージェントをほんの数分で大規模インスタンスの高品質なソリューションを計算できることを示した。
- 参考スコア（独自算出の注目度）: 6.852682268049646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a new problem formulation, Double-Deck Multi-Agent Pickup and
Delivery (DD-MAPD), which models the multi-robot shelf rearrangement problem in
automated warehouses. DD-MAPD extends both Multi-Agent Pickup and Delivery
(MAPD) and Multi-Agent Path Finding (MAPF) by allowing agents to move beneath
shelves or lift and deliver a shelf to an arbitrary location, thereby changing
the warehouse layout. We show that solving DD-MAPD is NP-hard. To tackle
DD-MAPD, we propose MAPF-DECOMP, an algorithmic framework that decomposes a
DD-MAPD instance into a MAPF instance for coordinating shelf trajectories and a
subsequent MAPD instance with task dependencies for computing paths for agents.
We also present an optimization technique to improve the performance of
MAPF-DECOMP and demonstrate how to make MAPF-DECOMP complete for well-formed
DD-MAPD instances, a realistic subclass of DD-MAPD instances. Our experimental
results demonstrate the efficiency and effectiveness of MAPF-DECOMP, with the
ability to compute high-quality solutions for large-scale instances with over
one thousand shelves and hundreds of agents in just minutes of runtime.
- Abstract（参考訳）: 自動倉庫におけるマルチロボット棚配置問題をモデル化した新しい問題定式化Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD)を導入する。
DD-MAPDは、Multi-Agent Pickup and Delivery (MAPD) とMulti-Agent Path Finding (MAPF) の両方を拡張し、エージェントが棚の下を移動したり、持ち上げたり、任意の場所に棚を届けることで、倉庫のレイアウトを変更する。
dd-mapdの解決はnp-hardである。
DD-MAPD に対処するため,DD-MAPD インスタンスを MAPF インスタンスに分解するアルゴリズムフレームワーク MAPF-DECOMP を提案する。
また、MAPF-DECOMPの性能向上のための最適化手法を提案し、DD-MAPDインスタンスの現実的なサブクラスであるDD-MAPDインスタンスに対してMAPF-DECOMPを補完する方法を示す。
実験の結果,MAPF-DECOMPの効率と有効性を示し,1000台以上の棚と数百台のエージェントをほんの数分で大規模インスタンスの高品質なソリューションを計算できるようになった。
関連論文リスト
- 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) - Caching-Augmented Lifelong Multi-Agent Path Finding [25.575748142768298]
Lifelong MAPFは、最初のターゲットが完成したらすぐにターゲットをエージェントに割り当てるが、現実の倉庫計画のより正確な近似を提供する。
本稿では,Lifelong MAPFの性能向上を目的としたCaching-Augmented Lifelong MAPF(CAL-MAPF)という新しいメカニズムを提案する。
論文 参考訳（メタデータ） (2024-03-20T09:07:23Z) - 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) - MADiff: Offline Multi-agent Learning with Diffusion Models [79.18130544233794]
拡散モデル(DM)は、最近オフライン強化学習を含む様々なシナリオで大きな成功を収めた。
この問題に対処する新しい生成型マルチエージェント学習フレームワークであるMADiffを提案する。
本実験は,マルチエージェント学習タスクにおけるベースラインアルゴリズムと比較して,MADiffの優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-27T02:14:09Z) - Multi-Robot Coordination and Layout Design for Automated Warehousing [55.150593161240444]
我々は、最先端のMAPFアルゴリズムであっても、人間設計のレイアウトは、多数のロボットを持つ倉庫の混雑を招きかねないことを示す。
倉庫のレイアウトを最適化するために,既存のシナリオ自動生成手法を拡張した。
その結果,(1)交通渋滞の低減とスループットの向上,(2)ロボットの数を2倍にすることで自動倉庫のスケーラビリティの向上,(3)ユーザが特定した多様性対策でレイアウトを生成できることが示唆された。
論文 参考訳（メタデータ） (2023-05-10T20:00:06Z) - Multi-Goal Multi-Agent Pickup and Delivery [25.11387753357413]
我々は、エージェントが常に新しいタスクに取り組み、それらを実行するために衝突のない経路を計画する必要がある、マルチエージェントピックアップ・アンド・デリバリ(MAPD)問題を考える。
我々は、任意のアルゴリズムLNS(Large Neighborhood Search)を用いて各エージェントにタスク列を割り当てるアルゴリズムの2つの変種を提案し、MAPF(Multi-Agent Path Finding)アルゴリズム(PBS)を用いて経路を計画する。
LNS-PBS は MAPD インスタンスの現実的なサブクラスである MAPD インスタンスに対して完全であり、既存の完全 MAPD アルゴリズム CENTRAL よりも経験的に有効である。
LN
論文 参考訳（メタデータ） (2022-08-02T03:20:59Z) - Manifold Topology Divergence: a Framework for Comparing Data Manifolds [109.0784952256104]
本研究では,深部生成モデルの評価を目的としたデータ多様体の比較フレームワークを開発する。
クロスバーコードに基づき,manifold Topology Divergence score(MTop-Divergence)を導入する。
MTop-Divergenceは,様々なモードドロップ,モード内崩壊,モード発明,画像乱れを正確に検出する。
論文 参考訳（メタデータ） (2021-06-08T00:30:43Z) - Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。
そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-05-15T06:07:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。