論文の概要: The Study of Highway for Lifelong Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2304.04217v1
• Date: Sun, 9 Apr 2023 11:21:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-11 17:02:27.833292
• Title: The Study of Highway for Lifelong Multi-Agent Path Finding
• Title（参考訳）: 生涯マルチエージェントパス発見のための道に関する研究
• Authors: Ming-Feng Li and Min Sun
• Abstract要約: 現代のフルフィルメント倉庫では、エージェントが地図を横切り、終りのないタスクを完了し、そこへ到着する。 この課題に対処する目的は、スループットを最大化しながら、有限のランタイムで各エージェントのパスを見つけることである。 我々は,一発MAPFで主に研究されるハイウェイの考え方を探求し,エージェントが同じ方向に移動するように促すことにより,問題の複雑さを低減する。
• 参考スコア（独自算出の注目度）: 30.329065698451902
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In modern fulfillment warehouses, agents traverse the map to complete endless tasks that arrive on the fly, which is formulated as a lifelong Multi-Agent Path Finding (lifelong MAPF) problem. The goal of tackling this challenging problem is to find the path for each agent in a finite runtime while maximizing the throughput. However, existing methods encounter exponential growth of runtime and undesirable phenomena of deadlocks and rerouting as the map size or agent density grows. To address these challenges in lifelong MAPF, we explore the idea of highways mainly studied for one-shot MAPF (i.e., finding paths at once beforehand), which reduces the complexity of the problem by encouraging agents to move in the same direction. We utilize two methods to incorporate the highway idea into the lifelong MAPF framework and discuss the properties that minimize the existing problems of deadlocks and rerouting. The experimental results demonstrate that the runtime is considerably reduced and the decay of throughput is gradually insignificant as the map size enlarges under the settings of the highway. Furthermore, when the density of agents increases, the phenomena of deadlocks and rerouting are significantly reduced by leveraging the highway.
• Abstract（参考訳）: 現代のフルフィルメント倉庫では、エージェントが地図を横切り、終生のマルチエージェントパス発見(ライフロングMAPF)問題として定式化される。 この課題に対処する目的は、スループットを最大化しながら、有限のランタイムで各エージェントのパスを見つけることである。 しかし、既存のメソッドは実行時の指数関数的な成長とデッドロックの望ましくない現象に遭遇し、マップサイズやエージェント密度が増加するにつれて再ルーティングする。 生涯にわたるMAPFにおけるこれらの課題に対処するために、一発MAPF(すなわち、一度に経路を見つける)を主に研究するハイウェイの考え方を探求し、エージェントが同じ方向に進むことを奨励することによって、問題の複雑さを低減させる。 我々は、高速道路のアイデアを生涯のmapfフレームワークに組み込む2つの手法を用いて、デッドロックと再ルーティングの既存の問題を最小化する特性について論じる。 実験の結果,ハイウェイの設定下において地図サイズが大きくなるにつれて,実行時間は大幅に減少し,スループットの低下は徐々に重要視されることがわかった。 さらに,エージェントの密度が大きくなると,高速道路を利用してデッドロック現象やリルート現象が著しく減少する。

関連論文リスト

• 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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。 本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。 我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
  論文  参考訳（メタデータ） (2023-10-02T13:51:32Z)
• 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)
• Long-HOT: A Modular Hierarchical Approach for Long-Horizon Object Transport [83.06265788137443]
  我々は、時間的拡張ナビゲーションのための新しいオブジェクトトランスポートタスクと新しいモジュラーフレームワークを提案することで、長距離探査と航法を具現化する上で重要な課題に対処する。 私たちの最初の貢献は、深層探査と長期計画に焦点を当てた新しいLong-HOT環境の設計である。 重み付けされたフロンティアの助けを借りて探索を行うために,シーンのトポロジカルグラフを構築するモジュラー階層輸送ポリシー(HTP)を提案する。
  論文  参考訳（メタデータ） (2022-10-28T05:30:49Z)
• 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)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  粗いトラフィックからのきめ細かなトラフィックフローの正確な推測は、新たな重要な問題である。 本稿では,道路ネットワークの知識を活かした新しい道路対応交通流磁化器(RATFM)を提案する。 提案手法は,高品質なトラフィックフローマップを作成できる。
  論文  参考訳（メタデータ） (2021-09-29T07:51:49Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。 これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。 提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
  論文  参考訳（メタデータ） (2021-06-03T18:07:26Z)
• Lifelong Multi-Agent Path Finding in Large-Scale Warehouses [26.017429163961328]
  MAPF(Multi-Agent Path Finding)は、エージェントのチームが衝突することなく目標地点に移動する問題である。 そこで本研究では,生涯MAPFの問題をウィンドウ化されたMAPFインスタンスのシーケンスに分解することで,生涯MAPFを解くための新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-05-15T06:07:15Z)

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

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