論文の概要: Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard

• arxiv url: http://arxiv.org/abs/2608.28658v1
• Date: Fri, 21 Aug 2026 05:31:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-08 15:29:38.139473
• Title: Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard
• Title（参考訳）: Goal Stayingは、NPハードを見つける匿名のマルチエージェントパスを作る
• Abstract要約: 標準目標設定型AMAPFは根本的に異なることを示す。 ゴールステイリングの最小化は 3SAT からの還元により NP-hard であることが証明された。
• 参考スコア（独自算出の注目度）: 1.9589337121790473
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.
• Abstract（参考訳）: AMAPF (Anonymous Multi-Agent Path Finding, AMAPF) は、エージェントが目標に達すると消滅すると、メイスパン、全距離、総コスト(SoC)など、いくつかの目的に対して多項式時間ネットワークフローアルゴリズムを認める。 標準目標設定型AMAPFは根本的に異なることを示す。 まず,目標設定制約付き標準時間拡張フローモデルを拡張することで,SoCの最小化を定式化し,線形プログラミング緩和が非積分であることを示す。 次に,ゴールステイリング AMAPF における SoC の最小化は 3SAT からの還元により NP-hard であることが証明された。 消失する変種に対する多項式時間結果とともに、完成エージェントがその目的に留まっているかどうかによって決定される鋭い複雑性境界を確立する。

関連論文リスト

• Alternating Target-Path Planning for Scalable Multi-Agent Coordination [11.193867567895353]
  並列ターゲット割り当てとパスフィンディング問題は、マルチエージェントパスフィンディングを拡張する。 本稿では,パスフィニングから目的の割り当てを分離する反復的精錬フレームワークを提案する。 これは現実のセットアップに適した実用的で大規模なTAPFに向けた確かなステップである。
  論文  参考訳（メタデータ） (2026-05-08T13:50:51Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  本稿では,安価な拡散サンプリング推論をステップレベル候補の再利用プールに変換する自己整合性フレームワークを提案する。 ステップレベルの再結合は、難しい問題に対して最も有益であることがわかった。 トレーニング不要のフレームワークは、6つの数学およびコーディングタスクの平均精度を最大2倍改善します。
  論文  参考訳（メタデータ） (2026-02-26T11:08:39Z)
• Multi-Agent Route Planning as a QUBO Problem [0.39325957466009204]
  本稿では、形式的な問題定義を与え、重み付き集合パッケージ問題から減算してNP硬度を証明し、二次的非制約二項最適化の定式化を導出する。 単一のペナルティパラメータがカバレッジオーバーラップトレードオフを制御する。 バルセロナでの最大10万台の車両による実験では、カバーオーバーラップの明確な膝が明らかになった。
  論文  参考訳（メタデータ） (2026-02-08T11:18:45Z)
• Do Latent-CoT Models Think Step-by-Step? A Mechanistic Study on Sequential Reasoning Tasks [37.23113613155819]
  Latent Chain-of-Thought (Latent-CoT) は、長い論理を出力することなくステップバイステップの計算を可能にすることを目的としている。 本研究では, 連続的思考型教師学生蒸留モデルであるCODIについて, 厳密なシーケンシャル・イット・タスクについて検討する。
  論文  参考訳（メタデータ） (2026-01-31T01:48:23Z)
• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。 我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。 従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
  論文  参考訳（メタデータ） (2025-12-04T14:11:52Z)
• Visual Multi-Object Tracking with Re-Identification and Occlusion Handling using Labeled Random Finite Sets [10.618186767487993]
  本稿では、オブジェクトの出現と隠蔽を解消するオンライン視覚多目的追跡(MOT)アルゴリズムを提案する。 我々の解は、ラベル付きランダム有限集合 (LRFS) フィルタリングアプローチに基づいている。 本稿では,トラックの重なり合う部分とそのサイズを考慮したファジィ検出モデルを提案する。
  論文  参考訳（メタデータ） (2024-07-11T21:15:21Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメトリした線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• 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)
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic [59.94347858883343]
  本稿では,マルコフ決定過程(MDP)をモデルとした自律動的システムの運動計画について検討する。 LDGBA と MDP の間に組込み製品 MDP (EP-MDP) を設計することである。 モデルフリー強化学習(RL)のためのLDGBAベースの報酬形成と割引スキームは、EP-MDP状態にのみ依存する。
  論文  参考訳（メタデータ） (2021-02-24T01:11:25Z)
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient [62.24615324523435]
  本稿では,スパース線形関数近似を用いた高次元バッチ強化学習(RL)の統計的解析を行う。 候補となる機能が多数存在する場合,提案手法がバッチRLをより効率的にサンプリングできるという事実に光を当てる。
  論文  参考訳（メタデータ） (2020-11-08T16:48:02Z)

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

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