論文の概要: Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering

• arxiv url: http://arxiv.org/abs/2009.05161v1
• Date: Thu, 10 Sep 2020 22:27:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-20 03:37:34.948825
• Title: Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
• Title（参考訳）: decoupled と integrated goal vertex order によるマルチゴールマルチエージェントパス探索
• Authors: Pavel Surynek
• Abstract要約: 本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。 我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
• 参考スコア（独自算出の注目度）: 15.99072005190786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from their starting vertices to one individual goal vertex per agent, MAPF$^{MG}$ assigns each agent multiple goal vertices and the task is to visit each of them at least once. Solving MAPF$^{MG}$ not only requires finding collision free paths for individual agents but also determining the order of visiting agent's goal vertices so that common objectives like the sum-of-costs are optimized. We suggest two novel algorithms using different paradigms to address MAPF$^{MG}$: a heuristic search-based search algorithm called Hamiltonian-CBS (HCBS) and a compilation-based algorithm built using the SMT paradigm, called SMT-Hamiltonian-CBS (SMT-HCBS). Experimental comparison suggests limitations of compilation-based approach.
• Abstract（参考訳）: 本稿では,標準離散型マルチエージェントパス探索(mapf)問題を一般化したマルチエージェントパス探索(mapf$^{mg}$)を導入する。 mapfのタスクは、開始頂点から1つの個々の目標頂点まで、無指示のグラフでエージェントをナビゲートすることであるが、mapf$^{mg}$は、各エージェントに複数のゴール頂点を割り当て、タスクは、少なくとも1度は各エージェントを訪問することである。 MAPF$^{MG}$を解くには、個々のエージェントの衝突のない経路を見つけるだけでなく、エージェントのゴール頂点の順序を決定することでコストの和のような共通の目的が最適化される。 我々は、MAPF$^{MG}$に対処するために異なるパラダイムを用いる2つの新しいアルゴリズムを提案する:Hachian-CBS (HCBS) と呼ばれるヒューリスティック検索ベースのアルゴリズムと、SMTパラダイムを用いて構築されたコンパイルベースのアルゴリズム、SMT-Hamiltonian-CBS (SMT-HCBS) である。 実験的比較はコンパイルベースのアプローチの限界を示唆する。

関連論文リスト

• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。 そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。 提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
  論文  参考訳（メタデータ） (2024-04-30T12:49:54Z)
• 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)
• DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding [25.756524895372454]
  Multi-Agent Combinatorial Path Finding (MCPF)は、初期から目標地点までの複数のエージェントの衝突のない経路を求める。 最近の研究は、目標における個々の到着時間の総和を最小化しながら、MPPFに対処する方法を開発している。 本稿では,MCPF の min-max 変種である MCPF-max を提案する。
  論文  参考訳（メタデータ） (2023-12-11T11:53:31Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
  MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。 LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。 実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
  論文  参考訳（メタデータ） (2022-11-24T06:27:18Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
  論文  参考訳（メタデータ） (2021-11-23T17:59:50Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)

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

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