論文の概要: Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
- arxiv url: http://arxiv.org/abs/2608.24585v1
- Date: Tue, 25 Aug 2026 14:10:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-26 14:09:35.022287
- Title: Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
- Title（参考訳）: Pivot-and-Station Multi-Agent Path Findinging: Solvability, Complexity, Algorithms
- Abstract要約: Pivot-and-Station Multi-Agent Path Finding (PS-MAPF)を紹介する。
2辺連結グラフ上のすべてのインスタンスは可解である。
ステーションメークスパンやステーションフロータイムの最小化はすでにNPハードであり、1つのピボットが存在することを証明している。
- 参考スコア（独自算出の注目度）: 3.1418230465261625
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.
- Abstract（参考訳）: 自動高密度ストレージシステム(倉庫、ロボット駐車場、プラントの物流など)では、エージェントが不足するタスククリティカルなリソースを移動し、将来の運用を妨げることなく駐車する必要がある。
MAPFの亜種であるPivot-and-Station Multi-Agent Path Finding (PS-MAPF)を導入し、各エージェントのサブセットは、各ノードが匿名のステーションで終了する前に、一組の交換可能なピボット(ワークステーションなど)を訪問しなければならない。
2辺連結グラフ上のすべてのインスタンスは可解であり、任意の連結グラフ上では、占有されていない頂点の数に対する構造的有効距離測度は必要十分条件を与える。
ステーションメークスパンやステーションフロータイムの最小化はすでにNPハードであり、1つのピボットが存在することを証明している。
そこで本研究では, ベンチマークインスタンスの74～89%をベースライン以下で解く, 完全ベースライン, SATベース最適解法, Pivot-Prioritized Planning (PPP) の3つのアルゴリズムを提案する。
関連論文リスト
- Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints [3.7347677698423536]
先行制約付きマルチエージェントパス探索(MAPF-PC)は衝突のない計画計算のためのよく研究されたフレームワークである。
本研究では,MAPF-PCシードから始まる大規模な地域探索手法を開発し,再割り当てによる地区修復を反復的に改善する。
実験により、最も優れた構成は、固定割り当てシードソリューションよりも89.1%のインスタンスを改善していることが示された。
論文 参考訳（メタデータ） (2026-03-30T20:12:26Z) - TP-MDDN: Task-Preferenced Multi-Demand-Driven Navigation with Autonomous Decision-Making [90.18833928208333]
Task-Preferenced Multi-Demand-Driven Navigation (TP-MDDN)は、複数のサブオンデマンドと明示的なタスク嗜好を含む長距離ナビゲーションのための新しいベンチマークである。
空間記憶のために,3次元点雲蓄積と2次元意味マッピングを組み合わせたMASMapを設計した。
本手法は,認識精度とナビゲーションの堅牢性の両方において,最先端のベースラインを上回っている。
論文 参考訳（メタデータ） (2025-11-21T13:12:13Z) - Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
本稿では,新しい無人航空機(UAV)による協調移動エッジコンピューティング(MEC)フレームワークを提案する。
システムコストを最小限に抑え、タスク消費とエネルギー消費のトレードオフを改善することを目的としている。
提案手法はシステムコストを大幅に削減し,タスク消費とエネルギー消費のトレードオフの改善を実現する。
論文 参考訳（メタデータ） (2025-10-23T02:55:40Z) - Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
任意のOTコスト関数に対して連続的エントロピーOT(EOT)バリセンタを近似する新しいアルゴリズムを提案する。
本手法は、弱いOTに基づくEOT問題の二重再構成に基づいている。
論文 参考訳（メタデータ） (2023-10-02T11:24:36Z) - Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
論文 参考訳（メタデータ） (2023-05-25T17:56:24Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - An Efficient Approach to the Online Multi-Agent Path Finding Problem by
Using Sustainable Information [10.367412630626834]
多エージェント経路探索(MAPF)は、衝突せずにエージェントをゴールへ移動させる問題である。
本稿では,持続可能な情報を活用したオンラインMAPFの3段階的解決手法を提案する。
我々のアルゴリズムは、エージェント数の設定が異なる場合、平均1.48倍の速度でSOTAより高速である。
論文 参考訳（メタデータ） (2023-01-11T13:04:35Z) - Optimal Multi-Agent Path Finding for Precedence Constrained Planning
Tasks [0.7742297876120561]
我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。
そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。
本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
論文 参考訳（メタデータ） (2022-02-08T07:26:45Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。