論文の概要: Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding

• arxiv url: http://arxiv.org/abs/2406.10827v1
• Date: Sun, 16 Jun 2024 07:41:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-18 20:41:29.307025
• Title: Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding
• Title（参考訳）: グラフ埋め込みによる最適マルチエージェントパス探索のためのアルゴリズム選択
• Authors: Carmel Shabalin, Omri Kaduri, Roni Stern,
• Abstract要約: 多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。 MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。 このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
• 参考スコア（独自算出の注目度）: 9.831879504969224
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. This problem manifests in numerous real-world applications such as controlling transportation robots in automated warehouses, moving characters in video games, and coordinating self-driving cars in intersections. Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases. Different solvers employ different approaches, and there is no single state-of-the-art approach for all problems. Furthermore, there are no clear, provable, guidelines for choosing when each optimal MAPF solver to use. Prior work employed Algorithm Selection (AS) techniques to learn such guidelines from past data. A major challenge when employing AS for choosing an optimal MAPF algorithm is how to encode the given MAPF problem. Prior work either used hand-crafted features or an image representation of the problem. We explore graph-based encodings of the MAPF problem and show how they can be used on-the-fly with a modern graph embedding algorithm called FEATHER. Then, we show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding (MAG). An extensive experimental evaluation of MAG on several MAPF algorithm selection tasks reveals that it is either on-par or significantly better than existing methods.
• Abstract（参考訳）: 多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。 この問題は、自動倉庫における輸送ロボットの制御、ビデオゲームにおけるキャラクターの移動、交差点での自動運転車の調整など、現実の多くの応用に現れている。 MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。 異なる解法は異なるアプローチを採用しており、すべての問題に対して単一の最先端のアプローチは存在しない。 さらに、各MAPFソルバがいつ使用するかを選択するための明確な、証明可能なガイドラインは存在しない。 以前はアルゴリズム選択(AS)技術を使用して過去のデータからそのようなガイドラインを学習していた。 最適なMAPFアルゴリズムを選択するためにASを用いる場合の大きな課題は、与えられたMAPF問題をエンコードする方法である。 以前の作業では手作りの機能を使ったり、問題のイメージを表現したりしていた。 MAPF問題のグラフベースの符号化について検討し、FEATHERと呼ばれる最新のグラフ埋め込みアルゴリズムを用いて、どのようにそれをオンザフライで使用できるかを示す。 そして、このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込み(MAG)によるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。 いくつかのMAPFアルゴリズム選択タスクにおけるMAGの広範囲な実験的評価により、既存の手法よりもかなり優れていることが判明した。

関連論文リスト

• 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)
• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。 我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。 古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
  論文  参考訳（メタデータ） (2024-04-25T07:41:47Z)
• Guidance Graph Optimization for Lifelong Multi-Agent Path Finding [47.51678151084153]
  MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用法について検討する。 本稿では、生涯MAPFのためのガイダンスの多目的表現としてガイダンスグラフを紹介する。 任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T14:38:04Z)
• 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)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
  MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。 LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。 実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
  論文  参考訳（メタデータ） (2022-11-24T06:27:18Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings [6.223269541026908]
  マルチエージェントパス探索(mapf)問題を最適に解くことは、メイクスパンと全到着時間の最小化の両方においてnpハードであることが知られている。 あらゆる種類の問題でうまく機能する最適なMAPFアルゴリズムは存在せず、どのアルゴリズムを使用するかの標準ガイドラインも存在しない。 私たちは、MAPF問題インスタンスを取り、アルゴリズムのポートフォリオから使用する最速のアルゴリズムを選択しようとする深い畳み込みネットワークMAPFASTを開発しました。
  論文  参考訳（メタデータ） (2021-02-24T18:41:37Z)

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

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