論文の概要: Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2301.08687v1
• Date: Fri, 20 Jan 2023 17:18:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-23 12:54:27.304016
• Title: Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding
• Title（参考訳）: マルチエージェント経路探索のための非補間抽象化を用いた逆例
• Authors: Pavel Surynek
• Abstract要約: 本稿では,SATをベースとしたMAPFのための新しいCEGAR型解法を提案する。 しかし、非精細化は、以前のアプローチよりも桁違いに小さいSATエンコーディングをもたらす。
• 参考スコア（独自算出の注目度）: 15.99072005190786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counterexample guided abstraction refinement (CEGAR) represents a powerful symbolic technique for various tasks such as model checking and reachability analysis. Recently, CEGAR combined with Boolean satisfiability (SAT) has been applied for multi-agent path finding (MAPF), a problem where the task is to navigate agents from their start positions to given individual goal positions so that the agents do not collide with each other. The recent CEGAR approach used the initial abstraction of the MAPF problem where collisions between agents were omitted and were eliminated in subsequent abstraction refinements. We propose in this work a novel CEGAR-style solver for MAPF based on SAT in which some abstractions are deliberately left non-refined. This adds the necessity to post-process the answers obtained from the underlying SAT solver as these answers slightly differ from the correct MAPF solutions. Non-refining however yields order-of-magnitude smaller SAT encodings than those of the previous approach and speeds up the overall solving process making the SAT-based solver for MAPF competitive again in relevant benchmarks.
• Abstract（参考訳）: Counterexample guided abstract refinement (CEGAR) は、モデルチェックや到達可能性分析などの様々なタスクにおいて、強力なシンボル技術である。 近年,マルチエージェントパス探索 (MAPF) において, CEGAR と Boolean satisfiability (SAT) を組み合わせた CEGAR が適用されている。 最近の CEGAR アプローチでは、MAPF 問題の初期の抽象化を用いて、エージェント間の衝突を省略し、その後の抽象化改良で排除した。 本研究では,SATをベースとしたMAPFのための新しいCEGAR型解法を提案する。 これにより、下層の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)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Heuristically Guided Compilation for Multi-Agent Path Finding [15.99072005190786]
  本稿では,MAPF問題が異なる定式化で表現されるコンパイルベースの解法に着目する。 本研究では,対象SATソルバに対してMAPFエンコーディングを構築し,ドメイン固有の知識を反映させる方法を示す。 実験により, SATベースのMAPFソルバのバニラ変種に対して, ガイドコンパイルの方が優れた性能を示した。
  論文  参考訳（メタデータ） (2022-12-13T23:19:15Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies [7.766921168069532]
  マルチエージェントパス探索(MAPF)において、タスクは複数のエージェントの非競合パスを見つけることである。 本稿では,決定変数の部分的割り当ての整合性チェックをSATソルバに直接組み込むDPLL(MAPF)という新しいコンパイル方式を提案する。
  論文  参考訳（メタデータ） (2021-11-11T23:06:00Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• 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)
• Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions [10.354181009277623]
  マルチエージェントパス検索(MAPF)は、各開始位置と目標位置の間の複数のエージェントの衝突のないパスのアンサンブルを決定する。 この記事では、エージェントが必ずしも同時に起動および停止しない非同期アクションによるMAPFの自然な一般化を紹介します。
  論文  参考訳（メタデータ） (2021-03-08T02:34:17Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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