論文の概要: Heuristically Guided Compilation for Multi-Agent Path Finding
- arxiv url: http://arxiv.org/abs/2212.06940v1
- Date: Tue, 13 Dec 2022 23:19:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-15 15:25:02.320013
- Title: Heuristically Guided Compilation for Multi-Agent Path Finding
- Title(参考訳): マルチエージェントパス探索のためのヒューリスティックガイドコンパイル
- Authors: Pavel Surynek
- Abstract要約: 本稿では,MAPF問題が異なる定式化で表現されるコンパイルベースの解法に着目する。
本研究では,対象SATソルバに対してMAPFエンコーディングを構築し,ドメイン固有の知識を反映させる方法を示す。
実験により, SATベースのMAPFソルバのバニラ変種に対して, ガイドコンパイルの方が優れた性能を示した。
- 参考スコア(独自算出の注目度): 15.99072005190786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-agent path finding (MAPF) is a task of finding non-conflicting paths
connecting agents' specified initial and goal positions in a shared
environment. We focus on compilation-based solvers in which the MAPF problem is
expressed in a different well established formalism such as mixed-integer
linear programming (MILP), Boolean satisfiability (SAT), or constraint
programming (CP). As the target solvers for these formalisms act as black-boxes
it is challenging to integrate MAPF specific heuristics in the MAPF
compilation-based solvers. We show in this work how the build a MAPF encoding
for the target SAT solver in which domain specific heuristic knowledge is
reflected. The heuristic knowledge is transferred to the SAT solver by
selecting candidate paths for each agent and by constructing the encoding only
for these candidate paths instead of constructing the encoding for all possible
paths for an agent. The conducted experiments show that heuristically guided
compilation outperforms the vanilla variants of the SAT-based MAPF solver.
- Abstract(参考訳): マルチエージェントパス探索(MAPF)は、エージェントの指定された初期位置と目標位置を共有環境で接続する非競合パスを見つけるタスクである。
我々は, mapf 問題を混合整数線形計画 (milp), ブール充足可能性 (sat), 制約プログラミング (cp) など, 異なる確立された形式で表現するコンパイル型解法に注目した。
これらのフォーマリズムのターゲットソルバはブラックボックスとして機能するため、MAPFコンパイルベースのソルバにMAPF固有のヒューリスティックを統合することは困難である。
本研究では,対象SATソルバに対してMAPFエンコーディングを構築し,ドメイン固有のヒューリスティック知識を反映させる方法を示す。
このヒューリスティック知識は、各エージェントの候補パスを選択し、エージェントの可能な全てのパスのエンコーディングを構築するのではなく、これらの候補パスのみのエンコーディングを構築することによってSATソルバに転送される。
実験の結果,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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - Semi-DETR: Semi-Supervised Object Detection with Detection Transformers [105.45018934087076]
半教師付き物体検出(SSOD)におけるDETRに基づくフレームワークの解析
本報告では,第1次変圧器を用いたエンド・ツー・エンド半教師対象検出器であるSemi-DETRについて述べる。
我々の手法は、最先端の手法をクリアマージンで上回る。
論文 参考訳(メタデータ) (2023-07-16T16:32:14Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳(メタデータ) (2023-04-01T15:50:18Z) - Counterexample Guided Abstraction Refinement with Non-Refined
Abstractions for Multi-Agent Path Finding [15.99072005190786]
本稿では,SATをベースとしたMAPFのための新しいCEGAR型解法を提案する。
しかし、非精細化は、以前のアプローチよりも桁違いに小さいSATエンコーディングをもたらす。
論文 参考訳(メタデータ) (2023-01-20T17:18:49Z) - Multi-Agent Reinforcement Learning for Microprocessor Design Space
Exploration [71.95914457415624]
マイクロプロセッサアーキテクトは、高性能でエネルギー効率の追求において、ドメイン固有のカスタマイズにますます頼っている。
この問題に対処するために,Multi-Agent RL (MARL) を利用した別の定式化を提案する。
評価の結果,MARLの定式化は単エージェントRLのベースラインよりも一貫して優れていた。
論文 参考訳(メタデータ) (2022-11-29T17:10:24Z) - Conflict-Based Search for Explainable Multi-Agent Path Finding [7.734726150561088]
安全クリティカルなアプリケーションでは、人間の監督者は、この計画が本当に衝突のないものであることを検証したいかもしれない。
MAPF問題は、簡潔な説明を認める非衝突経路のセットを要求する。
従来のMAPFアルゴリズムは、説明可能なMAPFを直接処理するものではない。
我々は、MAPFのためのよく研究されたアルゴリズムである Conflict Based Search (CBS) を適用して、説明可能なMAPFを扱う。
論文 参考訳(メタデータ) (2022-02-20T23:13:14Z) - DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving
Technologies [7.766921168069532]
マルチエージェントパス探索(MAPF)において、タスクは複数のエージェントの非競合パスを見つけることである。
本稿では,決定変数の部分的割り当ての整合性チェックをSATソルバに直接組み込むDPLL(MAPF)という新しいコンパイル方式を提案する。
論文 参考訳(メタデータ) (2021-11-11T23:06:00Z) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。
最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
論文 参考訳(メタデータ) (2021-04-23T20:13:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。