論文の概要: Leveraging Experience in Lifelong Multi-Agent Pathfinding
- arxiv url: http://arxiv.org/abs/2202.04382v1
- Date: Wed, 9 Feb 2022 10:41:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-10 20:38:12.008919
- Title: Leveraging Experience in Lifelong Multi-Agent Pathfinding
- Title(参考訳): 生涯マルチエージェントパスフィンディングにおける経験の活用
- Authors: Nitzan Madar, Kiril Solovey and Oren Salzman
- Abstract要約: Lifelong Multi-Agent Path Finding (L-MAPF) では、エージェントのチームが互いに衝突を避けながらタスクのストリームを実行する。
本稿では,新しいRHCRにインスパイアされたアプローチであるexRHCRを紹介する。
ExRHCRはL-MAPFをRHCRよりも25%高速に解決し、与えられたタスクストリームのスループットを最大で16%向上させる。
- 参考スコア(独自算出の注目度): 12.401344261399613
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Lifelong Multi-Agent Path Finding (L-MAPF) a team of agents performs a
stream of tasks consisting of multiple locations to be visited by the agents on
a shared graph while avoiding collisions with one another. L-MAPF is typically
tackled by partitioning it into multiple consecutive, and hence similar,
"one-shot" MAPF queries with a single task assigned to each agent, as in the
Rolling-Horizon Collision Resolution (RHCR) algorithm. Thus, a solution to one
query informs the next query, which leads to similarity with respect to the
agents' start and goal positions, and how collisions need to be resolved from
one query to the next. Thus, experience from solving one MAPF query can
potentially be used to speedup solving the next one. Despite this intuition,
current L-MAPF planners solve consecutive MAPF queries from scratch. In this
paper, we introduce a new RHCR-inspired approach called exRHCR, which exploits
experience in its constituent MAPF queries. In particular, exRHCR employs a new
extension of Priority-Based Search (PBS), a state-of-the-art MAPF solver. Our
extension, called exPBS, allows to warm-start the search with the priorities
between agents used by PBS in the previous MAPF instances. We demonstrate
empirically that exRHCR solves L-MAPF up to 25% faster than RHCR, and allows to
increase throughput for given task streams by as much as 3%-16% by increasing
the number of agents we can cope with for a given time budget.
- Abstract(参考訳): l-mapf(lifelong multi-agent path finding)では、エージェントのチームが、共有グラフ上でエージェントが訪問する複数の場所からなるタスクストリームを実行し、互いに衝突しないようにする。
L-MAPFは通常、ローリング・水平衝突分解(RHCR)アルゴリズムのように、各エージェントに割り当てられた1つのタスクで複数の連続的なMAPFクエリに分割することで取り組まれる。
したがって、あるクエリに対するソリューションは次のクエリに通知し、エージェントの開始位置とゴール位置に関して類似性をもたらし、あるクエリから次のクエリへの衝突をどのように解決する必要があるかを示す。
したがって、1つのMAPFクエリを解く経験は、次のMAPFクエリを高速化するために使用できる。
この直感にもかかわらず、現在のL-MAPFプランナーは連続するMAPFクエリをゼロから解決する。
本稿では,その構成するMAPFクエリの経験を生かしたexRHCRという,RHCRにインスパイアされた新しいアプローチを提案する。
特にexRHCRは、最先端MAPFソルバであるPBS(Preferity-Based Search)を新たに拡張している。
我々の拡張はexPBSと呼ばれ、以前のMAPFインスタンスでPBSが使用するエージェント間の優先順位で検索を温めることができます。
我々は、exRHCRがL-MAPFをRHCRよりも25%高速に解き、与えられた時間予算に対処できるエージェントの数を増やすことで、与えられたタスクストリームのスループットを最大で16%向上できることを示した。
関連論文リスト
- Scalable Mechanism Design for Multi-Agent Path Finding [90.68703851865585]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。
本稿では,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) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳(メタデータ) (2022-10-07T00:40:59Z) - Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
安全クリティカルなアプリケーションでは、人間の監督者は、この計画が本当に衝突のないものであることを検証したいかもしれない。
MAPF問題は、簡潔な説明を認める非衝突経路のセットを要求する。
従来のMAPFアルゴリズムは、説明可能なMAPFを直接処理するものではない。
我々は、MAPFのためのよく研究されたアルゴリズムである Conflict Based Search (CBS) を適用して、説明可能なMAPFを扱う。
論文 参考訳(メタデータ) (2022-02-20T23:13:14Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳(メタデータ) (2021-04-23T20:13:12Z) - Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。
そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
論文 参考訳(メタデータ) (2020-05-15T06:07:15Z) - Scalable Multi-Agent Inverse Reinforcement Learning via
Actor-Attention-Critic [54.2180984002807]
マルチエージェント逆逆強化学習 (MA-AIRL) は, 単エージェントAIRLをマルチエージェント問題に適用する最近の手法である。
本稿では,従来の手法よりもサンプル効率が高く,スケーラブルなマルチエージェント逆RLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-24T20:30:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。