論文の概要: Multi-Goal Multi-Agent Pickup and Delivery
- arxiv url: http://arxiv.org/abs/2208.01223v1
- Date: Tue, 2 Aug 2022 03:20:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-03 13:36:58.553297
- Title: Multi-Goal Multi-Agent Pickup and Delivery
- Title（参考訳）: マルチゴールマルチエージェントピックアップとデリバリー
- Authors: Qinghong Xu, Jiaoyang Li, Sven Koenig, Hang Ma
- Abstract要約: 我々は、エージェントが常に新しいタスクに取り組み、それらを実行するために衝突のない経路を計画する必要がある、マルチエージェントピックアップ・アンド・デリバリ(MAPD)問題を考える。
我々は、任意のアルゴリズムLNS(Large Neighborhood Search)を用いて各エージェントにタスク列を割り当てるアルゴリズムの2つの変種を提案し、MAPF(Multi-Agent Path Finding)アルゴリズム(PBS)を用いて経路を計画する。
LNS-PBS は MAPD インスタンスの現実的なサブクラスである MAPD インスタンスに対して完全であり、既存の完全 MAPD アルゴリズム CENTRAL よりも経験的に有効である。
LN
- 参考スコア（独自算出の注目度）: 25.11387753357413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we consider the Multi-Agent Pickup-and-Delivery (MAPD) problem,
where agents constantly engage with new tasks and need to plan collision-free
paths to execute them. To execute a task, an agent needs to visit a pair of
goal locations, consisting of a pickup location and a delivery location. We
propose two variants of an algorithm that assigns a sequence of tasks to each
agent using the anytime algorithm Large Neighborhood Search (LNS) and plans
paths using the Multi-Agent Path Finding (MAPF) algorithm Priority-Based Search
(PBS). LNS-PBS is complete for well-formed MAPD instances, a realistic subclass
of MAPD instances, and empirically more effective than the existing complete
MAPD algorithm CENTRAL. LNS-wPBS provides no completeness guarantee but is
empirically more efficient and stable than LNS-PBS. It scales to thousands of
agents and thousands of tasks in a large warehouse and is empirically more
effective than the existing scalable MAPD algorithm HBH+MLA*. LNS-PBS and
LNS-wPBS also apply to a more general variant of MAPD, namely the Multi-Goal
MAPD (MG-MAPD) problem, where tasks can have different numbers of goal
locations.
- Abstract（参考訳）: 本研究では,エージェントが常に新しいタスクに取り組み,衝突のない経路を計画する必要があるMAPD(Multi-Agent Pickup-and-Delivery)問題を考える。
タスクを実行するには、エージェントはピックアップロケーションと配送ロケーションからなる2つのゴールロケーションを訪問する必要がある。
本研究では,各エージェントにタスクのシーケンスを割り当てるアルゴリズムの2つの変種を,anytimeアルゴリズム large neighborhood search (lns) と plan paths using the multi-agent path find (mapf) algorithm priority-based search (pbs) を用いて提案する。
LNS-PBS は MAPD インスタンスの現実的なサブクラスである MAPD インスタンスに対して完全であり、既存の完全 MAPD アルゴリズム CENTRAL よりも経験的に有効である。
LNS-wPBSは完全性を保証するものではないが、LSS-PBSよりも実験的に効率的で安定である。
大規模な倉庫で数千のエージェントと数千のタスクにスケールし、既存のスケーラブルなMAPDアルゴリズムHBH+MLA*よりも経験的に効果的です。
LNS-PBS と LNS-wPBS はより一般的な MAPD の変種である Multi-Goal MAPD (MG-MAPD) にも適用される。
関連論文リスト
- Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large
Neighborhood Search [30.364955687049292]
MAPFはLarge Neborhood Search(LNS)に基づいている
探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。
大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
論文 参考訳（メタデータ） (2023-12-28T01:24:42Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - 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) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。
MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。
本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文 参考訳（メタデータ） (2023-03-30T14:42:41Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳（メタデータ） (2022-10-07T00:40:59Z) - Optimal Multi-Agent Path Finding for Precedence Constrained Planning
Tasks [0.7742297876120561]
我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。
そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。
本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
論文 参考訳（メタデータ） (2022-02-08T07:26:45Z) - MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal
Sequencing and Path Finding [10.354181009277623]
監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。
本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。
計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
論文 参考訳（メタデータ） (2021-03-18T01:57:35Z) - The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
マルチエージェントPPO(MAPPO)は、集中型値関数を採用するマルチエージェントPPOバリアントである。
MAPPOは,3つの一般的なマルチエージェントテストベッドにおいて,最先端技術に匹敵する性能を実現していることを示す。
論文 参考訳（メタデータ） (2021-03-02T18:59:56Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。