論文の概要: Scalable Multi-Agent Maze Traversal with Local Communication

• arxiv url: http://arxiv.org/abs/2608.11895v1
• Date: Wed, 12 Aug 2026 10:21:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.555326
• Title: Scalable Multi-Agent Maze Traversal with Local Communication
• Title（参考訳）: 局所通信を用いたスケーラブルマルチエージェント迷路トラバース
• Abstract要約: エージェントが未知の、おそらく巡回グラフを一括してトラバースできる分散アルゴリズムを提案する。 エージェントは指定されたスタートノードで順次入力され、ローカライズされ、未公表のゴールに到達する。 いずれにせよ、探査はエージェントの1人のみが行う。
• 参考スコア（独自算出の注目度）: 1.2875771631391097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver.
• Abstract（参考訳）: ケーブネットワーク、パイプシステム、それに類似した迷路のような環境は、通信に制限のある未知の設定において、マルチエージェントナビゲーションに重大な課題をもたらす。 エージェントが未知の、おそらく巡回グラフを一括してトラバースできる分散アルゴリズムを提案する。 エージェントは指定されたスタートノードで順次入力され、衝突を避けながらローカライズされ、未公表のゴールに達する。 リーダとフォロワーの関係とリーダの切り替えを使って、ローカル通信を通じてコーディネートする。 いずれにせよ、探索は1人のエージェントのみが行い、単一のエージェントの迷路ソルバを実行する。 アルゴリズムが完全であること、そのメイスパンが(エージェント数において)最適な全知識戦略と漸近的に等価であること、そしてその時間と空間の複雑さを導出することを証明する。 最大625ドルのエージェントによるシミュレーションでは、エージェントの数が増えるにつれて平均的な総和が減少し、提案手法がすべてのエージェントが独立して単エージェントソルバを実行するナイーブベースラインを上回っていることが示される。

関連論文リスト

• AgentFugue: Agent Scaling for Long-Horizon Tasks through Collective Reasoning [57.72181998599248]
  AgentFugueは、共通の推論ハブを中心に構築された、集合的推論フレームワークである。 ピアエージェントが同じタスクを並列に探索する際、ハブは各エージェントが何を確立、試み、あるいは除外したかを簡潔に記録する。 この結果から,集団推論によってピアエージェントシステムのスケールアウトが実現可能であることが示唆された。
  論文  参考訳（メタデータ） (2026-05-23T09:21:51Z)
• GoAgent: Group-of-Agents Communication Topology Generation for LLM-based Multi-Agent Systems [55.12339141172908]
  GoAgentは、協調グループをMAS構築の原子単位として明示的に扱う通信トポロジ生成手法である。 6つのベンチマークの実験では、GoAgentの最先端のパフォーマンスを93.84%の平均精度で証明し、トークン消費を約17%削減した。
  論文  参考訳（メタデータ） (2026-03-20T06:21:32Z)
• Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time [1.7006003864727406]
  我々は、グリッドのような無向グラフにおけるエージェントの群れのためのミッションを、複数の目標で計画している。 通常のマルチエージェントパスフィニングとは対照的に、ソルバはエージェントに目標の割り当てを独自に見つけて更新する。
  論文  参考訳（メタデータ） (2025-12-17T15:24:20Z)
• Decentralized Multi-Agent Active Search and Tracking when Targets Outnumber Agents [8.692007892160913]
  そこで我々は,DecSTERと呼ばれる分散マルチエージェント,マルチターゲット,同時アクティブ検索・追跡アルゴリズムを提案する。 提案アルゴリズムは,確率仮説密度フィルタの逐次モントカルロ法とトンプソンサンプリングを併用し,分散化マルチエージェント意思決定を行う。 シミュレーションでは,DecSTERは信頼性の低いエージェント間通信に頑健であり,最適サブパターン割り当て(OSPA)の指標で情報グレディベースラインを上回っていることを示す。
  論文  参考訳（メタデータ） (2024-01-06T08:10:58Z)
• 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)
• Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
  本稿では,分解が容易なマルチエージェントスキル発見法を提案する。 我々のキーとなる考え方は、合同状態空間をクロネッカーグラフとして近似することであり、そのフィドラーベクトルを直接見積もることができる。 ラプラシアンスペクトルを直接計算することは、無限大の状態空間を持つタスクには難易度が高いことを考慮し、さらに本手法の深層学習拡張を提案する。
  論文  参考訳（メタデータ） (2023-07-21T14:53:12Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。 また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。 提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
  論文  参考訳（メタデータ） (2022-10-07T00:40:59Z)
• Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs [41.17714498464354]
  エージェント間の協調的な探索行動により,マルチエージェントの選択肢を直接計算できることが示唆された。 提案アルゴリズムは,マルチエージェントオプションの同定に成功し,シングルエージェントオプションや非オプションを用いることで,従来よりも大幅に性能が向上する。
  論文  参考訳（メタデータ） (2022-01-20T15:33:08Z)
• MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding [10.354181009277623]
  監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。 本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。 計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
  論文  参考訳（メタデータ） (2021-03-18T01:57:35Z)

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

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