論文の概要: Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities
- arxiv url: http://arxiv.org/abs/2104.11809v1
- Date: Fri, 23 Apr 2021 20:13:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-27 14:42:17.433011
- Title: Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities
- Title(参考訳): 多元経路探索のためのコンパイル型解法--調査,議論,将来の可能性
- Authors: Pavel Surynek
- Abstract要約: このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
- 参考スコア(独自算出の注目度): 7.766921168069532
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-agent path finding (MAPF) attracts considerable attention in artificial
intelligence community as well as in robotics, and other fields such as
warehouse logistics. The task in the standard MAPF is to find paths through
which agents can navigate from their starting positions to specified individual
goal positions. The combination of two additional requirements makes the
problem computationally challenging: (i) agents must not collide with each
other and (ii) the paths must be optimal with respect to some objective. Two
major approaches to optimal MAPF solving include (1) dedicated search-based
methods, which solve MAPF directly, and (2) compilation-based methods that
reduce a MAPF instance to an instance in a different well established
formalism, for which an efficient solver exists. The compilation-based MAPF
solving can benefit from advancements accumulated during the development of the
target solver often decades long. We summarize and compare contemporary
compilation-based solvers for MAPF using formalisms like ASP, MIP, and SAT. We
show the lessons learned from past developments and current trends in the topic
and discuss its wider impact.
- Abstract(参考訳): マルチエージェントパス探索(MAPF)は、人工知能コミュニティやロボット工学、倉庫の物流などの分野において大きな注目を集めている。
標準的なmapfのタスクは、エージェントが開始位置から特定の個々のゴール位置へナビゲートできるパスを見つけることである。
i)エージェントは互いに衝突してはならないし、(ii)パスは目的に対して最適でなければならない。
最適なmapf解決のための2つの主要なアプローチは、(1)mapfを直接解く専用の検索ベースメソッドと(2)mapfインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベースメソッドである。
コンパイルベースのMAPF解決は、ターゲットソルバの開発時に蓄積された進歩の恩恵を受けることができる。
我々は, ASP, MIP, SAT などの形式を用いて, MAPF のコンテンポラリー・コンピレーション・ベース・ソルバを要約・比較する。
我々は、過去の発展から学んだ教訓と、そのトピックの現在の傾向を示し、その広範な影響について論じる。
関連論文リスト
- Scalable Mechanism Design for Multi-Agent Path Finding [90.68703851865585]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。
本稿では,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) - 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) - Heuristically Guided Compilation for Multi-Agent Path Finding [15.99072005190786]
本稿では,MAPF問題が異なる定式化で表現されるコンパイルベースの解法に着目する。
本研究では,対象SATソルバに対してMAPFエンコーディングを構築し,ドメイン固有の知識を反映させる方法を示す。
実験により, SATベースのMAPFソルバのバニラ変種に対して, ガイドコンパイルの方が優れた性能を示した。
論文 参考訳(メタデータ) (2022-12-13T23:19:15Z) - DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving
Technologies [7.766921168069532]
マルチエージェントパス探索(MAPF)において、タスクは複数のエージェントの非競合パスを見つけることである。
本稿では,決定変数の部分的割り当ての整合性チェックをSATソルバに直接組み込むDPLL(MAPF)という新しいコンパイル方式を提案する。
論文 参考訳(メタデータ) (2021-11-11T23:06:00Z) - Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and
Personalized Federated Learning [56.17603785248675]
モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。
既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。
本稿では,MAMLのメモリベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-09T08:47:58Z) - MALib: A Parallel Framework for Population-based Multi-agent
Reinforcement Learning [61.28547338576706]
人口ベースマルチエージェント強化学習(PB-MARL)は、強化学習(RL)アルゴリズムでネストした一連の手法を指す。
PB-MARLのためのスケーラブルで効率的な計算フレームワークMALibを提案する。
論文 参考訳(メタデータ) (2021-06-05T03:27:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。