論文の概要: 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ソルバのバニラ変種よりもヒューリスティックなコンパイルが優れていることがわかった。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• 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)
• 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)
• 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)
• Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding [15.99072005190786]
  本稿では,SATをベースとしたMAPFのための新しいCEGAR型解法を提案する。 しかし、非精細化は、以前のアプローチよりも桁違いに小さいSATエンコーディングをもたらす。
  論文  参考訳（メタデータ） (2023-01-20T17:18:49Z)
• 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)

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

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