論文の概要: Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding

• arxiv url: http://arxiv.org/abs/2611.07528v1
• Date: Thu, 05 Nov 2026 06:39:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.569755
• Title: Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding
• Title（参考訳）: ゴール分岐型LaCAM:高密度マルチエージェントパスフィニングにおける探索分岐としての一時ゴール
• Abstract要約: 本稿では, ブロックエージェントに一時的目標を付与するゴールブランチを提案し, それぞれがLaCAM検索の分岐として試みる。 Goal-BranchingはLaCAM*の44%に対して89%のインスタンスを解決し、両方のケースにおいて、maze-32-32-2および room-32-32-4では10-14倍高速で、 room-32-32-4では75%密度では200倍高速であることがわかった。
• 参考スコア（独自算出の注目度）: 3.756866987415384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: LaCAM is a search-based solver for multi-agent pathfinding (MAPF) that runs a depth-first search over joint configurations, using PIBT to generate successors and lazily adding single-agent constraints to explore alternatives. Although LaCAM is complete, it can struggle on dense, corridor-heavy instances because extracting blocking agents from deadlocks requires coordinated moves of several agents, often away from their goals, which PIBT's greedy one-step successors rarely propose and which LaCAM can only reach by enumerating constraints one agent at a time. This paper proposes Goal-Branching, where blocking agents are given temporary goals, each tried as an additional branch of LaCAM's search. We examine random and corridor-aware rules for choosing these temporary goals and show that completeness is preserved for any such rule. On dense instances (60-90% of free cells occupied) of three maze and room maps, Goal-Branching solves 89% of instances against 44% for LaCAM*, and, on instances both solve, it finds a first solution 10-14x faster on maze-32-32-2 and room-32-32-4, and nearly 200x faster in median time at 75% density on room-32-32-4. Solution cost increases by 15-22% on instances both solve, while on open maps and the full MovingAI benchmark its solutions cost no more than those of LaCAM* and it is at most 3% slower.
• Abstract（参考訳）: LaCAMはマルチエージェントパスフィンディング(MAPF)のための検索ベースの解決法であり、PIBTを使用して後継を発生させ、代替品を探索するために単一エージェント制約を遅延的に追加する。 LaCAMは完成しているが、デッドロックからブロック剤を抽出するためには、しばしば目標から離れた複数のエージェントの協調的な移動が必要であり、PIBTの一段階の後継者がほとんど提案せず、LaCAMは一度に1つのエージェントを列挙することでのみ到達できる。 本稿では, ブロックエージェントに一時的目標を付与するゴールブランチを提案し, それぞれがLaCAM検索の分岐として試みる。 本稿では,これらの一時的な目標を選択するための無作為かつ回廊対応のルールについて検討し,そのようなルールに対して完全性が保存されていることを示す。 3つの迷路と部屋マップの濃密なインスタンス(60-90%のフリーセルが占有)について、Goal-BranchingはLaCAM*の44%に対して89%のインスタンスを解決し、両方のケースで、maze-32-32-2と室32-32-4では10-14倍、室32-32-4では室32-32-4では中央値で200倍近く高速である。 ソリューションコストは、どちらも解決したインスタンスで15～22%上昇する一方、オープンマップと完全なMovingAIベンチマークでは、ソリューションはLaCAM*よりも高くない。

関連論文リスト

• Local Work, Global Progress: A Convergence Theory of AI Agent Collaboration [53.657104889705856]
  我々はブロック最適化として協調的な問題解決を定式化する。 コーディネータは、グローバルな目的に対して全ての提案をチェックし、干渉しない提案をマージする。 線形収束を誤差フロアまで証明し、補正が正確であれば消滅する。
  論文  参考訳（メタデータ） (2026-10-20T14:37:06Z)
• ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search [13.499784584888902]
  TAPF(Target Assignment and Path Finding)は、衝突のない経路を同時に計画しながらエージェントにターゲットを割り当てることを必要とする。 我々は、LaCAMとITA-CBSにインスパイアされた、完全でスケーラブルなTAPF解決器であるITA-LaCAMを紹介する。
  論文  参考訳（メタデータ） (2026-09-13T00:38:03Z)
• A Lightweight Traffic Map for Efficient Anytime LaCAM* [13.871792180626045]
  MAPF (Multi-Agent Path Finding) は,複数エージェントに対する衝突のない経路の計算を目的とし,幅広い実用性を有する。 LaCAM*は、いつでも構成ベースの解決ツールで、現在、最先端の技術を表現している。 本稿では,LaCAM*の検索中に動的で軽量なトラフィックマップを構築する能力を活用した新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2026-03-09T02:11:07Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Tree Search for Language Model Agents [73.97960454223164]
  対話型Web環境での探索と多段階計画を行うために,LMエージェントの推論時探索アルゴリズムを提案する。 我々のアプローチは、実環境空間内で機能する最優先木探索の一形態である。 現実的なWebタスクにおいて有効性を示すLMエージェントのための最初の木探索アルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-01T17:07:55Z)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。 そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。 提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
  論文  参考訳（メタデータ） (2024-04-30T12:49:54Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding [5.025654873456756]
  マルチエージェントパスフィンディング(MAPF)のための最近開発されたLaCAMアルゴリズムを拡張した。 LaCAMは、遅延後継生成を用いて計画作業を劇的に削減する、サブ最適検索ベースのアルゴリズムである。 我々は、LaCAM*と呼ばれる任意のバージョンを提案し、最終的にはオプティマに収束する。
  論文  参考訳（メタデータ） (2023-05-05T15:43:20Z)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
  MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。 LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。 実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
  論文  参考訳（メタデータ） (2022-11-24T06:27:18Z)

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

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