論文の概要: Improved Anonymous Multi-Agent Path Finding Algorithm
- arxiv url: http://arxiv.org/abs/2312.10572v4
- Date: Sat, 27 Jan 2024 22:57:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-30 20:58:36.591607
- Title: Improved Anonymous Multi-Agent Path Finding Algorithm
- Title（参考訳）: 匿名マルチエージェントパス探索アルゴリズムの改良
- Authors: Zain Alabedeen Ali and Konstantin Yakovlev
- Abstract要約: エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。
我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。
その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
- 参考スコア（独自算出の注目度）: 3.694001372535405
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider an Anonymous Multi-Agent Path-Finding (AMAPF) problem where the
set of agents is confined to a graph, a set of goal vertices is given and each
of these vertices has to be reached by some agent. The problem is to find an
assignment of the goals to the agents as well as the collision-free paths, and
we are interested in finding the solution with the optimal makespan. A
well-established approach to solve this problem is to reduce it to a special
type of a graph search problem, i.e. to the problem of finding a maximum flow
on an auxiliary graph induced by the input one. The size of the former graph
may be very large and the search on it may become a bottleneck. To this end, we
suggest a specific search algorithm that leverages the idea of exploring the
search space not through considering separate search states but rather bulks of
them simultaneously. That is, we implicitly compress, store and expand bulks of
the search states as single states, which results in high reduction in runtime
and memory. Empirically, the resultant AMAPF solver demonstrates superior
performance compared to the state-of-the-art competitor and is able to solve
all publicly available MAPF instances from the well-known MovingAI benchmark in
less than 30 seconds.
- Abstract（参考訳）: 我々は、エージェントの集合がグラフに制限され、ゴール頂点の集合が与えられ、これらの頂点のそれぞれがあるエージェントによって到達されなければならない匿名のマルチエージェントパス探索(amapf)問題を考える。
問題となるのは、エージェントへの目標の割り当てと衝突のない経路を見つけることであり、我々は最適メイスパンによる解を見つけることに興味を持っている。
この問題を解決するための確立されたアプローチは、グラフ探索問題の特別なタイプ、すなわち入力されたグラフによって誘導される補助グラフ上の最大フローを見つける問題に還元することである。
前のグラフのサイズは非常に大きくなり、検索がボトルネックになる可能性がある。
そこで本研究では,検索空間を探索するアイデアを,個別の検索状態ではなく,同時にバルク化する,特定の検索アルゴリズムを提案する。
つまり、検索状態の大部分を単一の状態として暗黙的に圧縮し、保存し、拡張することで、ランタイムとメモリの大幅な削減を実現します。
実証的に、結果のAMAPFソルバは最先端の競合と比較して優れたパフォーマンスを示し、よく知られた movingAIベンチマークから利用可能なMAPFインスタンスを30秒未満で解決することができる。
関連論文リスト
- Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
多エージェント経路探索(MAPF)は、衝突しない複数のエージェントの経路を見つける問題である。
MAPFの最適解を見つけることはNP-Hardであるが、現代の最適解法は数百のエージェントにスケールでき、場合によっては数千までスケールできる。
このエンコーディングが既存のエンコーディングと効果的に結合できることを示し、その結果、グラフ埋め込みによるMAPFアルゴリズム選択と呼ばれる新しいASメソッドが実現された。
論文 参考訳（メタデータ） (2024-06-16T07:41:58Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。
本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。
MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
論文 参考訳（メタデータ） (2023-12-26T06:57:22Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
論文 参考訳（メタデータ） (2023-05-25T17:56:24Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。
グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。
低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文 参考訳（メタデータ） (2023-03-10T21:18:34Z) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。
Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。
わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
論文 参考訳（メタデータ） (2022-04-12T16:46:06Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal
Vertex Ordering [15.99072005190786]
本稿では,MAPF問題を一般化したマルチゴールマルチエージェントパス探索法(MAPF$MG$)を提案する。
我々は,MAPF$MG$に対処するために,異なるパラダイムを用いた2つの新しいアルゴリズムを提案する。Hamiltonian-CBS (HCBS) と呼ばれる検索ベース検索アルゴリズムと,SMTパラダイムを用いたコンパイルベースアルゴリズムであるSMT-Hamiltonian-CBS (SMT-HCBS) を提案する。
論文 参考訳（メタデータ） (2020-09-10T22:27:18Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。