論文の概要: On the Hardness of Optimal Motion on Trees

• arxiv url: http://arxiv.org/abs/2606.06686v1
• Date: Thu, 04 Jun 2026 20:00:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-08 14:33:29.428963
• Title: On the Hardness of Optimal Motion on Trees
• Title（参考訳）: 樹木の最適運動の硬さについて
• Authors: Tzvika Geft,
• Abstract要約: 本稿では,標準目的木におけるマルチエージェントパス探索の複雑さを解消する枠組みを提案する。 我々は,3つの目的のすべてにおいて,ラベル付きMAPFと2色MAPFの両方に対してNP硬さを証明した。
• 参考スコア（独自算出の注目度）: 0.05076419064097732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives--distance, makespan, and flowtime--for both labeled and colored variants. In MAPF, agents occupy the vertices of a graph and must move to target vertices without collisions while optimizing a given objective. In the labeled case, the agents are distinct and have respective targets; in the colored case, agents of the same color are interchangeable. While many MAPF variants are known to be intractable, several basic cases on trees have remained open. We prove NP-hardness on trees for both labeled and 2-colored MAPF under all three objectives. In particular, we resolve the classical Pebble Motion problem, where one pebble moves at a time to an adjacent empty vertex and the goal is to minimize the total number of moves. Despite being one of the most basic discrete motion models, its complexity on trees had remained open for several decades. Moreover, for colored Pebble Motion, we give the first hardness result on any graph class, already with two colors, which is tight. All of these results are established through the hardness of Stack Rearrangement, itself posed as an open problem, which asks to optimally rearrange items stored in stacks, and which we also prove to be NP-hard. Notably, the connection to stacks yields hardness already on very simple trees--subdivided stars--across all problems. Together, these results reveal a common tractability barrier that permeates several fundamental motion models, thereby unifying and strengthening prior hardness results.
• Abstract（参考訳）: 本稿では,マルチエージェントパスファインディング(MAPF)の標準的な目的(距離,メイスパン,フロータイム)にまたがる複雑さを,ラベル付きおよび色付きの両方で解決するシンプルなフレームワークを提案する。 MAPFでは、エージェントはグラフの頂点を占有し、与えられた目的を最適化しながら衝突することなく目標頂点に移動しなければならない。 ラベル付けされた場合、エージェントは別個のターゲットを持ち、カラーの場合、同じ色のエージェントは交換可能である。 多くのMAPF変異体は難解であることが知られているが、木に関するいくつかの基本的なケースは未解決のままである。 我々は,3つの目的のすべてにおいて,ラベル付きMAPFと2色MAPFの両方に対してNP硬さを証明した。 特に,1小石が隣接する空の頂点に一度に移動するという,従来のPebble Motionの課題を解決し,その目標は,動きの総数を最小限に抑えることである。 もっとも基本的な離散的な運動モデルの一つであったにもかかわらず、木上の複雑さは数十年にわたって開き続けていた。 さらに、色付きPebble Motionでは、すでに2色あるグラフクラスで最初の硬度結果が得られます。 これらの結果はスタック再配置の難しさによって確立され、スタックに格納されたアイテムを最適に並べ替えることを求めるオープンな問題であり、NPハードであることが証明される。 特に、スタックへの接続は、すべての問題において、非常に単純な木の上に既に硬さをもたらす。 これらの結果と合わせて、いくつかの基本運動モデルに浸透する共通のトラクタビリティ障壁が明らかとなり、それによって以前の硬度結果が統一され、強化される。

関連論文リスト

• Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges [8.499685241219366]
  我々は、エッジカラーのハイパーグラフをクラスタリングするためのフレームワークを検討し、そこでは、彼らが参加する主要なマルチウェイインタラクションのタイプに基づいてオブジェクトをクラスタリングすることを目的としている。 よく研究されている1つの目的は、満足できないハイパーエッジの数を最小限に抑えるためにノードを色付けすることである。 最適性は同じだが、近似するよりもはるかに難しい、満足度の高いエッジを最大化する新しいアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2025-02-18T16:20:50Z)
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
  エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。 フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。 この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
  論文  参考訳（メタデータ） (2023-05-25T17:56:24Z)
• Policy Gradient with Tree Expansion [72.10002936187388]
  政策勾配法は、大きなばらつきと高いサンプルの複雑さを持つことで有名である。 我々は、計画を採用するソフトマックスの一般化であるSoftTreeMaxを紹介します。 我々は、SoftTreeMaxが勾配のばらつきを3桁に減らすことを示す。
  論文  参考訳（メタデータ） (2023-01-30T19:03:14Z)
• Graphical House Allocation [18.119269486735245]
  このような問題の鍵となる基準は、うらやましい自由さのような公正な制約を満たすことである。 我々のゴールは、自然公正の目的として、エージェント間の集合的うらやみを最小限にすることである。 同一のバリュエーションが不均一な場合、私たちはこの古典的な問題から脱却する深遠で驚くべき方法をいくつか示します。
  論文  参考訳（メタデータ） (2023-01-03T19:26:15Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。 Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
  論文  参考訳（メタデータ） (2022-09-28T09:55:47Z)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
  論文  参考訳（メタデータ） (2022-06-30T02:33:32Z)
• Learning to Estimate Hidden Motions with Global Motion Aggregation [71.12650817490318]
  閉塞は、局所的な証拠に依存する光学フローアルゴリズムに重大な課題をもたらす。 最初の画像でピクセル間の長距離依存性を見つけるために,グローバルモーションアグリゲーションモジュールを導入する。 遮蔽領域における光流量推定が非遮蔽領域における性能を損なうことなく大幅に改善できることを実証した。
  論文  参考訳（メタデータ） (2021-04-06T10:32:03Z)
• Deep Occlusion-Aware Instance Segmentation with Overlapping BiLayers [72.38919601150175]
  高オーバーラップオブジェクトをセグメント化するBilayer Convolutional Network (BCNet)を提案する。 BCNetはオクルージョンオブジェクト(Occluder)を検出し、ボトムGCN層は部分的にOccludedインスタンス(Occludee)を推論する
  論文  参考訳（メタデータ） (2021-03-23T06:25:42Z)
• Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
  マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。 MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。 対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
  論文  参考訳（メタデータ） (2021-03-12T07:27:35Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)

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

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