論文の概要: MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

• arxiv url: http://arxiv.org/abs/2102.12461v2
• Date: Thu, 19 Dec 2024 11:16:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-22 16:38:59.465049
• Title: MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings
• Title（参考訳）: MAPFAST:最短経路埋め込みを用いたマルチエージェント経路探索のためのディープアルゴリズムセレクタ
• Authors: Jingyao Ren, Vikraman Sathiyanarayanan, Eric Ewing, Baskin Senbaslar, Nora Ayanian,
• Abstract要約: MAPF(Multi-Agent Path Finding)問題を最適に解くことは、make-spanと総到着時間最小化の両方においてNP-Hardであることが知られている。 最適なMAPFアルゴリズムは、あらゆる種類の問題でうまく機能し、そのアルゴリズムをいつ使用するかに関する標準ガイドラインは存在しない。 我々は、MAPF問題インスタンスを取り込み、アルゴリズムポートフォリオから最も高速なアルゴリズムを選択しようとする、深層畳み込みネットワークMAPFASTを開発した。
• 参考スコア（独自算出の注目度）: 5.506178421979142
• License:
• Abstract: Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms' strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)問題を最適に解くことは、make-spanと総到着時間最小化の両方においてNP-Hardであることが知られている。 MAPF問題を解決するために多くのアルゴリズムが開発されているが、あらゆる種類の問題でうまく機能する最適なMAPFアルゴリズムは存在しない。 本研究では、MAPF問題インスタンスを抽出し、アルゴリズムポートフォリオから最も高速なアルゴリズムを選択しようとする、深層畳み込みネットワークMAPFAST(Multi-Agent Path Finding Algorithm SelecTor)を開発する。 モデルに与えられたインスタンス埋め込みに単一エージェントのショートパスを組み込んで,分類損失に加えて補足的損失関数を活用することにより,モデルの性能を向上させる。 我々はMAPFインスタンスの大規模かつ多種多様なデータセット上でモデルを評価し、そのポートフォリオにおける個々のアルゴリズムと最先端のMAPFアルゴリズムセレクタよりも優れていることを示す。 また、アルゴリズム設計における様々なヒューリスティックスを活用するために、最適なMAPFアルゴリズムの強みと弱みをより深く理解するために、データセットにおけるアルゴリズムの挙動を分析する。

関連論文リスト

• Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
  多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。 MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。 このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
  論文  参考訳（メタデータ） (2024-06-16T07:41:58Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  我々はロバスト成分分析のためのアルゴリズムを設計する(A) 行列を低主行列とスパース主行列の和に分解する。
  論文  参考訳（メタデータ） (2023-07-12T03:48:26Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。 理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。 本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
  論文  参考訳（メタデータ） (2022-08-02T03:17:29Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Parallel Surrogate-assisted Optimization Using Mesh Adaptive Direct Search [0.0]
  本稿では,メッシュ適応直接探索(MADS)アルゴリズムの探索段階における代理モデルと並列計算を利用する手法を提案する。 我々は、利用可能なCPUリソースに対して、修正MADSアルゴリズムの性能を評価するために数値実験を行う。
  論文  参考訳（メタデータ） (2021-07-26T18:28:56Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization [1.471992435706872]
  CluSPT(Clustered Shortest-Path Tree Problem)は、実生活における様々な最適化問題において重要な役割を果たしている。 近年、CluSPTを扱うためにMFEA(Multifactorial Evolutionary Algorithm)が導入されている。 本稿では,MFEAに基づくCluSPTの解法について述べる。
  論文  参考訳（メタデータ） (2021-02-12T13:36:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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