論文の概要: Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
- arxiv url: http://arxiv.org/abs/2005.07371v2
- Date: Fri, 12 Mar 2021 18:56:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 23:37:04.248647
- Title: Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
- Title（参考訳）: 大規模倉庫における生涯マルチエージェントパス
- Authors: Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K.
Satish Kumar and Sven Koenig
- Abstract要約: MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。
そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 26.017429163961328
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to
their goal locations without collisions. In this paper, we study the lifelong
variant of MAPF, where agents are constantly engaged with new goal locations,
such as in large-scale automated warehouses. We propose a new framework
Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by
decomposing the problem into a sequence of Windowed MAPF instances, where a
Windowed MAPF solver resolves collisions among the paths of the agents only
within a bounded time horizon and ignores collisions beyond it. RHCR is
particularly well suited to generating pliable plans that adapt to continually
arriving new goal locations. We empirically evaluate RHCR with a variety of
MAPF solvers and show that it can produce high-quality solutions for up to
1,000 agents (= 38.9\% of the empty cells on the map) for simulated warehouse
instances, significantly outperforming existing work.
- Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。
本稿では,大規模自動倉庫などにおいて,エージェントが常に新たな目標地点で作業を行うMAPFの寿命変動について検討する。
本稿では,この問題を窓付きmapfインスタンスの列に分解し,窓付きmapfソルバがエージェントの経路間の衝突を境界時間軸内でのみ解決し,それを超える衝突を無視する,生涯的mapf問題を解決するための新たなフレームワークであるローリング・ホライゾン衝突解決(rhcr)を提案する。
RHCRは、新しいゴール地点に継続的に到着する計画を作成するのに特に適している。
我々は,様々なmapfソルバを用いてrhcrを実証的に評価し,シミュレーションした倉庫インスタンスに対して,最大1,000エージェント(=38.9\%の空セル)に対して高品質なソリューションを作成できることを示した。
関連論文リスト
- 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) - 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) - 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) - Multi-Agent Reinforcement Learning for Microprocessor Design Space
Exploration [71.95914457415624]
マイクロプロセッサアーキテクトは、高性能でエネルギー効率の追求において、ドメイン固有のカスタマイズにますます頼っている。
この問題に対処するために,Multi-Agent RL (MARL) を利用した別の定式化を提案する。
評価の結果,MARLの定式化は単エージェントRLのベースラインよりも一貫して優れていた。
論文 参考訳（メタデータ） (2022-11-29T17:10:24Z) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。
LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。
実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
論文 参考訳（メタデータ） (2022-11-24T06:27:18Z) - Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via
Environment Manipulation [12.401344261399613]
マルチエージェントパスフィニング(Multi-agent pathfinding)は、障害が散らばった環境において、開始時から目標地点まで、エージェントのチームが衝突のない経路を計画することに関心がある。
我々はMAPFの新たな拡張を導入し、Terraforming MAPF (tMAPF) と呼び、いくつかのエージェントが障害を移動して他のエージェントへの道をクリアする役割を担っている。
我々は、tMAPFに取り組むために、CBSとPBSという2つの最先端アルゴリズムを拡張し、静的な障害物設定で可能な限り優れた解を常に上回ることを示す。
論文 参考訳（メタデータ） (2022-03-20T12:18:35Z) - 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) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。