論文の概要: Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time
- arxiv url: http://arxiv.org/abs/2512.22171v1
- Date: Wed, 17 Dec 2025 15:24:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-04 08:45:17.091388
- Title: Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time
- Title（参考訳）: 多項式時間におけるマルチエージェント多目的経路探索問題の解法
- Authors: Stefan Edelkamp,
- Abstract要約: 我々は、グリッドのような無向グラフにおけるエージェントの群れのためのミッションを、複数の目標で計画している。
通常のマルチエージェントパスフィニングとは対照的に、ソルバはエージェントに目標の割り当てを独自に見つけて更新する。
- 参考スコア（独自算出の注目度）: 1.7006003864727406
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we plan missions for a fleet of agents in undirected graphs, such as grids, with multiple goals. In contrast to regular multi-agent path-finding, the solver finds and updates the assignment of goals to the agents on its own. In the continuous case for a point agent with motions in the Euclidean plane, the problem can be solved arbitrarily close to optimal. For discrete variants that incur node and edge conflicts, we show that it can be solved in polynomial time, which is unexpected, since traditional vehicle routing on general graphs is NP-hard. We implement a corresponding planner that finds conflict-free optimized routes for the agents. Global assignment strategies greatly reduce the number of conflicts, with the remaining ones resolved by elaborating on the concept of ants-on-the-stick, by solving local assignment problems, by interleaving agent paths, and by kicking agents that have already arrived out of their destinations
- Abstract（参考訳）: 本稿では,グリッドなどの非方向グラフにおけるエージェント群のミッションを,複数の目標で計画する。
通常のマルチエージェントパスフィニングとは対照的に、ソルバはエージェントに目標の割り当てを独自に見つけて更新する。
ユークリッド平面上での運動を伴う点エージェントの連続の場合、問題は任意に最適に解くことができる。
ノードとエッジが衝突する離散変種に対しては、一般グラフ上の従来の車両ルーティングはNPハードであるため、多項式時間で解けることを示す。
エージェントの競合のない最適化ルートを見つけるための,対応するプランナを実装した。
地球規模の割当て戦略は紛争の数を大幅に減らし、残りはアリという概念を解明し、ローカルな割当て問題を解決し、エージェントパスをインターリーブし、既に目的地から到着したエージェントを蹴ることによって解決する。
関連論文リスト
- When Disagreements Elicit Robustness: Investigating Self-Repair Capabilities under LLM Multi-Agent Disagreements [56.29265568399648]
我々は、不一致が早期のコンセンサスを防ぎ、探索されたソリューション空間を拡張することを主張する。
タスククリティカルなステップの相違は、ソリューションパスのトポロジによってコラボレーションを損なう可能性がある。
論文 参考訳（メタデータ） (2025-02-21T02:24:43Z) - A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳（メタデータ） (2025-02-14T15:21:27Z) - Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。
我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。
古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
論文 参考訳（メタデータ） (2024-04-25T07:41:47Z) - 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) - Fault-Tolerant Offline Multi-Agent Path Planning [5.025654873456756]
本研究では,複数のエージェントが実行時にクラッシュする可能性のある新しいグラフパス計画問題について検討し,ワークスペースの一部をブロックする。
我々の設定では、エージェントは隣のクラッシュしたエージェントを検出し、実行時に後続のパスを変更することができる。その目的は、各エージェントに対して一連のパスを作成し、ルールを切り替えることであり、すべての正しいエージェントが衝突やデッドロックなしで目的地に到達することを保証することである。
論文 参考訳（メタデータ） (2022-11-25T05:58:32Z) - Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure
of Costs [65.23158435596518]
チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。
我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
論文 参考訳（メタデータ） (2022-06-13T09:17:40Z) - Subdimensional Expansion Using Attention-Based Learning For Multi-Agent
Path Finding [9.2127262112464]
MAPF(Multi-Agent Path Finding)は、各開始点から目標地点までの複数のエージェントに対する競合のないパスを見つける。
我々は、この学習に基づくシングルエージェントプランナーをM*に統合することにより、LM*と呼ばれる新しいマルチエージェントプランナーを開発する。
以上の結果から,M* と比較した場合,LM* はコンフリクトが少なく,高速に動作し,高い成功率を享受できることがわかった。
論文 参考訳（メタデータ） (2021-09-29T20:01:04Z) - Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。
これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。
提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
論文 参考訳（メタデータ） (2021-06-03T18:07:26Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。