論文の概要: Multi-Agent Path Finding For Large Agents Is Intractable

• arxiv url: http://arxiv.org/abs/2505.10387v1
• Date: Thu, 15 May 2025 15:07:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-16 22:29:06.372908
• Title: Multi-Agent Path Finding For Large Agents Is Intractable
• Title（参考訳）: 大規模エージェントを見つけるためのマルチエージェントパス
• Authors: Artem Agafonov, Konstantin Yakovlev,
• Abstract要約: マルチエージェントパス探索(MAPF)問題は、これらのパスを同期的に追従する場合、エージェントが衝突に遭遇しないようなグラフ上の一連のパスを見つけるように要求する。 この論文では、まず最初に、後者の問題がNPハードであることを確認し、P!=NPがなければ、残念ながらそのアルゴリズムは提示できない。
• 参考スコア（独自算出の注目度）: 1.0550841723235613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict. In the most widespread MAPF formulation, the so-called Classical MAPF, the agents sizes are neglected and two types of conflicts are considered: occupying the same vertex or using the same edge at the same time step. Meanwhile in numerous practical applications, e.g. in robotics, taking into account the agents' sizes is vital to ensure that the MAPF solutions can be safely executed. Introducing large agents yields an additional type of conflict arising when one agent follows an edge and its body overlaps with the body of another agent that is actually not using this same edge (e.g. staying still at some distinct vertex of the graph). Until now it was not clear how harder the problem gets when such conflicts are to be considered while planning. Specifically, it was known that Classical MAPF problem on an undirected graph can be solved in polynomial time, however no complete polynomial-time algorithm was presented to solve MAPF with large agents. In this paper we, for the first time, establish that the latter problem is NP-hard and, thus, if P!=NP no polynomial algorithm for it can, unfortunately, be presented. Our proof is based on the prevalent in the field technique of reducing the seminal 3SAT problem (which is known to be an NP-complete problem) to the problem at hand. In particular, for an arbitrary 3SAT formula we procedurally construct a dedicated graph with specific start and goal vertices and show that the given 3SAT formula is satisfiable iff the corresponding path finding instance has a solution.
• Abstract（参考訳）: マルチエージェントパス探索(MAPF)問題は、これらのパスを同期的に追従する場合、エージェントが衝突に遭遇しないようなグラフ上の一連のパスを見つけるように要求する。 最も広く使われているMAPF(Classical MAPF)の定式化では、エージェントのサイズは無視され、同じ頂点を占有するか、同じエッジを同時に使用するかの2種類の競合が考慮される。 一方、ロボット工学などの多くの応用では、MAPFソリューションを安全に実行できるように、エージェントのサイズを考慮することが不可欠である。 大きなエージェントの導入は、あるエージェントがエッジに従い、そのエージェントが実際に同じエッジを使用していない別のエージェントのボディと重なるときに生じる、新たなタイプの衝突を引き起こす(例えば、グラフの別の頂点に留まる)。 これまでのところ、このような対立が計画中に考慮される場合、問題がどの程度難しくなるかは明確ではなかった。 具体的には、非方向グラフ上の古典的MAPF問題は多項式時間で解けることが知られているが、大きなエージェントでMAPFを解くための完全多項式時間アルゴリズムは提示されなかった。 この論文では、まず最初に、後者の問題はNPハードであり、従って、P! 残念ながら、NP の多項式アルゴリズムは提示できない。 本証明は, 素数3SAT問題(NP完全問題として知られる)を手前の問題に還元するフィールド技術において広く用いられている手法に基づくものである。 特に、任意の 3SAT の公式に対して、特定の開始点と目標頂点を持つ専用グラフを手続き的に構築し、与えられた 3SAT の公式が、対応する経路探索インスタンスが解を持つことを証明した。

関連論文リスト

• 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)
• Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
  エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。 我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。 その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
  論文  参考訳（メタデータ） (2023-12-17T00:49:30Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。 フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。 この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
  論文  参考訳（メタデータ） (2023-05-25T17:56:24Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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