論文の概要: 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%向上できることを示した。

関連論文リスト

• MM-Embed: Universal Multimodal Retrieval with Multimodal LLMs [78.5013630951288]
  本稿では,マルチモーダル大言語モデル(MLLM)を用いた情報検索手法を提案する。 まず,16個の検索タスクを持つ10個のデータセットに対して,MLLMをバイエンコーダレトリバーとして微調整する。 我々は,MLLMレトリバーが提示するモダリティバイアスを軽減するために,モダリティを考慮したハードネガティブマイニングを提案する。
  論文  参考訳（メタデータ） (2024-11-04T20:06:34Z)
• 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)
• 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 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。