論文の概要: Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments

• arxiv url: http://arxiv.org/abs/2412.04256v1
• Date: Thu, 05 Dec 2024 15:37:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-06 14:39:28.584670
• Title: Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments
• Title（参考訳）: 高密度環境における生涯ナビゲーションのための過渡的マルチエージェント経路探索
• Authors: Jonathan Morag, Noy Gabay, Daniel koyfman, Roni Stern,
• Abstract要約: ライフロングMAPF(英: Lifelong MAPF、LMAPF)は、エージェントが現在のターゲットに到達すると新たなターゲットを受信するMAPFのオンライン版である。 そこで本研究では,LMAPF問題に対して,各エージェントが最終的にターゲットを訪問することを目的とした修正MAPF問題の系列を解くことで,LMAPF問題を解くことを提案する。 本稿では、このMAPF変種をTransient MAPF (TMAPF) と呼び、既存のMAPFアルゴリズムに基づいたいくつかのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 9.000023855628958
• License:
• Abstract: Multi-Agent Path Finding (MAPF) deals with finding conflict-free paths for a set of agents from an initial configuration to a given target configuration. The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. The common approach for solving LMAPF is to treat it as a sequence of MAPF problems, periodically replanning from the agents' current configurations to their current targets. A significant drawback in this approach is that in MAPF the agents must reach a configuration in which all agents are at their targets simultaneously, which is needlessly restrictive for LMAPF. Techniques have been proposed to indirectly mitigate this drawback. We describe cases where these mitigation techniques fail. As an alternative, we propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target, but not necessarily for all agents to do so simultaneously. We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms. A limited experimental evaluation identifies some cases where using a TMAPF algorithm instead of a MAPF algorithm with an LMAPF framework can improve the system throughput significantly.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、初期設定から所定のターゲット設定へのエージェントセットの競合のないパスを見つけることを扱う。 ライフロングMAPF(英: Lifelong MAPF、LMAPF)は、エージェントが現在のターゲットに到達すると新たなターゲットを受信するMAPFのオンライン版である。 LMAPFを解く一般的なアプローチは、エージェントの現在の設定から現在のターゲットへ定期的に変更するMAPF問題の系列として扱うことである。 このアプローチの重大な欠点は、MAPFにおいてエージェントは、LMAPFに不必要に制限されるすべてのエージェントが同時にターゲットに置かれる構成に到達しなければならないことである。 この欠点を間接的に緩和する技術が提案されている。 これらの緩和技術が失敗する事例を述べる。 代案として,LMAPF問題を改良したMAPF問題の列を解くことで,各エージェントが最終的にターゲットを訪問することが目的であるが,必ずしもすべてのエージェントが同時に実施するとは限らない,という課題を解決し,LMAPFの問題を解決することを提案する。 本稿では、このMAPF変種をTransient MAPF (TMAPF) と呼び、既存のMAPFアルゴリズムに基づいたいくつかのアルゴリズムを提案する。 LMAPF フレームワークを用いた MAPF アルゴリズムの代わりに TMAPF アルゴリズムを使用すれば,システムスループットが大幅に向上することを示す。

関連論文リスト

• Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability [0.0]
  近年,Multi-Agent Path Finding (MAPF) が広く研究されている。 既存のMAPFアルゴリズムの多くは、エージェントがグリッドベースのマップ内の1つのグリッドしか占有していないと仮定している。 textbfLayered LA-MAPFは、幾何学的エージェントを含むMAPFインスタンスをクラスタに分解する手法である。
  論文  参考訳（メタデータ） (2024-10-22T16:34:24Z)
• 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)
• Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities [44.292720085661585]
  我々は2023年のLMAPFコンペティションに勝利のアプローチを提示する。 最初の課題は、限られた計画時間内で高品質なLMAPFソリューションを探すことである。 第2の課題は、LMAPFアルゴリズムにおける筋萎縮と行動の影響を緩和することである。 第3の課題は、文学と現実世界の応用で使用されるLMAPFモデルのギャップを埋めることである。
  論文  参考訳（メタデータ） (2024-04-24T19:37:18Z)
• 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)
• 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)
• Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learning [135.64775986546505]
  我々はマルチエージェント強化学習(MARL)におけるエージェントの対称性を利用する 我々は,平均場MARLを解くMF-FQIアルゴリズムを提案し,MF-FQIアルゴリズムの非漸近解析を確立する。 MF-FQIアルゴリズムは、多くの観測エージェントがMF-FQIアルゴリズムの性能を向上させるという意味で、「多くのエージェントの恵み」を享受する。
  論文  参考訳（メタデータ） (2020-06-21T21:45:50Z)

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

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