論文の概要: An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
- arxiv url: http://arxiv.org/abs/2511.18604v1
- Date: Sun, 23 Nov 2025 20:11:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-25 18:34:24.922187
- Title: An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
- Title（参考訳）: 制約に基づくマルチエージェントパスフィニングアルゴリズムの解析
- Authors: Hannah Lee, James D. Motes, Marco Morales, Nancy M. Amato,
- Abstract要約: 本研究では,将来のマルチエージェントパスフィンディング(MAPF)およびマルチロボットモーションプランニング(MRMP)アルゴリズムの設計について報告する。
我々は制約を保守的あるいは攻撃的と分類し、彼らの検索行動に関する洞察を提供する。
検索は決定フローチャートで合成され、適切な制約を選択するのに役立つ。
- 参考スコア（独自算出の注目度）: 1.4853650545663049
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study informs the design of future multi-agent pathfinding (MAPF) and multi-robot motion planning (MRMP) algorithms by guiding choices based on constraint classification for constraint-based search algorithms. We categorize constraints as conservative or aggressive and provide insights into their search behavior, focusing specifically on vanilla Conflict-Based Search (CBS) and Conflict-Based Search with Priorities (CBSw/P). Under a hybrid grid-roadmap representation with varying resolution, we observe that aggressive (priority constraint) formulations tend to solve more instances as agent count or resolution increases, whereas conservative (motion constraint) formulations yield stronger solution quality when both succeed. Findings are synthesized in a decision flowchart, aiding users in selecting suitable constraints. Recommendations extend to Multi-Robot Motion Planning (MRMP), emphasizing the importance of considering topological features alongside problem, solution, and representation features. A comprehensive exploration of the study, including raw data and map performance, is available in our public GitHub Repository: https://GitHub.com/hannahjmlee/constraint-mapf-analysis
- Abstract（参考訳）: 本研究では,制約に基づく探索アルゴリズムの制約分類に基づいて,将来のマルチエージェントパスフィンディング (MAPF) とマルチロボットモーションプランニング (MRMP) アルゴリズムの設計について報告する。
我々は、制約を保守的であるか攻撃的であると分類し、バニラ・コンフリクト・ベース・サーチ(CBS)とコンフリクト・ベース・サーチ・ア・プライオリティ(CBSw/P)に焦点を当てて、彼らの検索行動に関する洞察を提供する。
様々な解像度のハイブリッドグリッド-ロードマップ表現の下では、攻撃的(優先度制約)の定式化はエージェント数や解像度が増大するにつれて多くのインスタンスを解決しがちであるが、保守的(動き制約)の定式化はどちらも成功するとより強い解品質が得られる。
検索は決定フローチャートで合成され、適切な制約を選択するのに役立つ。
勧告はMRMP(Multi-Robot Motion Planning)に拡張され、問題、解、表現の特徴とともに位相的特徴を考えることの重要性を強調している。
生のデータやマップのパフォーマンスなど、この研究の包括的な調査は、GitHubリポジトリで公開されています。
関連論文リスト
- Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
SPLIT-RAGは、質問駆動セマンティックグラフ分割と協調サブグラフ検索による制限に対処するマルチエージェントRAGフレームワークである。
革新的なフレームワークは、まずリンク情報のセマンティック分割を作成し、次にタイプ特化知識ベースを使用してマルチエージェントRAGを実現する。
属性対応グラフセグメンテーションは、知識グラフを意味的に一貫性のあるサブグラフに分割し、サブグラフが異なるクエリタイプと整合することを保証する。
階層的なマージモジュールは、論理的検証を通じて、部分グラフ由来の解答間の矛盾を解消する。
論文 参考訳（メタデータ） (2025-05-20T06:44:34Z) - PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
制約,検証,選択という3つの重要な要素を持つモデルに依存しない,スケーラブルなエージェントフレームワークであるPlanGENを提案する。
具体的には、推論時間アルゴリズムの性能を向上させるために、制約誘導反復検証を提案する。
論文 参考訳（メタデータ） (2025-02-22T06:21:56Z) - Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation [0.0]
Constraint Based Tiling Generation (CBTG)アルゴリズムは、一連のタイルと配置制約からレベル実現を自動的に生成するのに役立つ。
Punch Out Model Synthesis (POMS, Constraint Based Tiling Generation algorithm) を提案する。
論文 参考訳（メタデータ） (2025-01-05T21:49:50Z) - Temporal Action Localization with Enhanced Instant Discriminability [66.76095239972094]
時間的行動検出(TAD)は、すべての行動境界とその対応するカテゴリを、トリミングされていないビデオで検出することを目的としている。
本稿では,既存の手法による動作境界の不正確な予測を解決するために,TriDetという一段階のフレームワークを提案する。
実験結果から,複数のTADデータセット上でのTriDetの堅牢性と最先端性能が示された。
論文 参考訳（メタデータ） (2023-09-11T16:17:50Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳（メタデータ） (2022-11-22T10:18:33Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳（メタデータ） (2021-08-11T10:42:11Z) - Regret Analysis in Deterministic Reinforcement Learning [78.31410227443102]
本稿では,最適学習アルゴリズムの分析と設計の中心となる後悔の問題を考察する。
本稿では,システムパラメータに明示的に依存する対数問題固有の後悔の下位境界について述べる。
論文 参考訳（メタデータ） (2021-06-27T23:41:57Z) - Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。
そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
論文 参考訳（メタデータ） (2021-02-17T11:09:33Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。