論文の概要: DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies

• arxiv url: http://arxiv.org/abs/2111.06494v1
• Date: Thu, 11 Nov 2021 23:06:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-15 14:17:27.364769
• Title: DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies
• Title（参考訳）: DPLL(MAPF):マルチエージェントパス探索とSATソルビング技術の統合
• Authors: Martin \v{C}apek and Pavel Surynek
• Abstract要約: マルチエージェントパス探索(MAPF)において、タスクは複数のエージェントの非競合パスを見つけることである。 本稿では,決定変数の部分的割り当ての整合性チェックをSATソルバに直接組み込むDPLL(MAPF)という新しいコンパイル方式を提案する。
• 参考スコア（独自算出の注目度）: 7.766921168069532
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In multi-agent path finding (MAPF), the task is to find non-conflicting paths for multiple agents from their initial positions to given individual goal positions. MAPF represents a classical artificial intelligence problem often addressed by heuristic-search. An important alternative to search-based techniques is compilation of MAPF to a different formalism such as Boolean satisfiability (SAT). Contemporary SAT-based approaches to MAPF regard the SAT solver as an external tool whose task is to return an assignment of all decision variables of a Boolean model of input MAPF. We present in this short paper a novel compilation scheme called DPLL(MAPF) in which the consistency checking of partial assignments of decision variables with respect to the MAPF rules is integrated directly into the SAT solver. This scheme allows for far more automated compilation where the SAT solver and the consistency checking procedure work together simultaneously to create the Boolean model and to search for its satisfying assignment.
• Abstract（参考訳）: マルチエージェントパス探索(MAPF)において、タスクは、初期位置から与えられた個々のゴール位置への複数のエージェントの非競合パスを見つけることである。 MAPFは、しばしばヒューリスティック検索によって対処される古典的な人工知能問題である。 検索ベースの手法の重要な代替手段として、MAPFをBoolean satisfiability (SAT)のような異なる形式にコンパイルすることがある。 MAPFに対する現代のSATベースのアプローチは、SATソルバを、入力MAPFのブールモデルのすべての決定変数の代入を返すタスクを持つ外部ツールとみなしている。 本稿では、MAPFルールに対する決定変数の部分的割り当ての整合性チェックをSATソルバに直接組み込む、DPLL(MAPF)と呼ばれる新しいコンパイル方式を提案する。 このスキームは、satソルバと一貫性チェックプロシージャが同時に動作してbooleanモデルを作成し、満足のいく代入を検索する、はるかに自動化されたコンパイルを可能にする。

関連論文リスト

• 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)
• 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)
• 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)
• Heuristically Guided Compilation for Multi-Agent Path Finding [15.99072005190786]
  本稿では,MAPF問題が異なる定式化で表現されるコンパイルベースの解法に着目する。 本研究では,対象SATソルバに対してMAPFエンコーディングを構築し,ドメイン固有の知識を反映させる方法を示す。 実験により, SATベースのMAPFソルバのバニラ変種に対して, ガイドコンパイルの方が優れた性能を示した。
  論文  参考訳（メタデータ） (2022-12-13T23:19:15Z)
• Leveraging Experience in Lifelong Multi-Agent Pathfinding [12.401344261399613]
  Lifelong Multi-Agent Path Finding (L-MAPF) では、エージェントのチームが互いに衝突を避けながらタスクのストリームを実行する。 本稿では,新しいRHCRにインスパイアされたアプローチであるexRHCRを紹介する。 ExRHCRはL-MAPFをRHCRよりも25%高速に解決し、与えられたタスクストリームのスループットを最大で16%向上させる。
  論文  参考訳（メタデータ） (2022-02-09T10:41:35Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• 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)

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

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