論文の概要: Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF
- arxiv url: http://arxiv.org/abs/2608.06702v1
- Date: Fri, 07 Aug 2026 01:56:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-10 16:21:25.325907
- Title: Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF
- Title（参考訳）: 長寿命MAPFのための拡張型長期計画法
- Abstract要約: LMAPF (Lifelong Multi-Agent Path Finding) は、リアルタイムの厳しい制約の下で大型エージェントの衝突のない経路を生成する必要がある。
我々は,数千のエージェントを1秒以下で調整できるLMAPFプランナであるPass Updates over Staggered Horizons (PUSH)を提案する。
- 参考スコア（独自算出の注目度）: 5.199189722211842
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Reactive frameworks such as PIBT and Enhanced PIBT (EPIBT) scale effortlessly to thousands of agents through rule-based, step-by-step coordination but suffer from severe temporal myopia, making them ineffective in scenarios where long-horizon reasoning is essential. RHCR plans windowed paths over multi-step horizons but incurs substantial planning overheads that hinder scalability. TP tackles both challenges by planning only subsets of agents at each timestep, yet its applicability is restricted to highly structured maps. To achieve long-horizon planning at scale across general maps, we propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second while planning over multi-step horizons. PUSH combines the key advantages of PIBT, RHCR, and TP. Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. Unlike TP, however, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. To maintain high throughput in congested environments, PUSH further integrates EPIBT-inspired priority inheritance, backtracking, and anytime improvements into its windowed planning. Empirical evaluations across two realistic MAPF scenarios requiring long-horizon reasoning show that PUSH scales to the same massive agent loads as EPIBT (e.g., 10k agents) while achieving significantly higher system throughput than all baselines.
- Abstract（参考訳）: LMAPF (Lifelong Multi-Agent Path Finding) は、リアルタイムの厳しい制約の下で大型エージェントの衝突のない経路を生成する必要がある。
PIBT や Enhanced PIBT (EPIBT) のようなリアクティブなフレームワークは、ルールベースのステップバイステップ調整を通じて数千のエージェントに対して努力的にスケールするが、深刻な側頭筋症に苦しむため、長期水平推論が不可欠であるシナリオでは効果がない。
RHCRは、マルチステップの地平線を越えてウィンドウ化されたパスを計画するが、スケーラビリティを妨げるかなりの計画上のオーバーヘッドを引き起こす。
TPは各タイミングでエージェントのサブセットだけを計画することで両方の課題に取り組むが、その適用性は高度に構造化された地図に制限される。
多段地平線を計画しながら、数千のエージェントを1秒以下で調整できるLMAPFプランナーであるPUSH(Path Updates over Staggered Horizons)を提案する。
PUSHはPIBT、RHCR、TPの重要な利点を組み合わせたものである。
TPと同様に、PUSHは、停滞した計画ウィンドウを使用して、各タイムステップにエージェントのサブセットだけを計画することで、計算の複雑さを低減する。
しかし TP とは異なり、PUSH は制限的な写像の仮定に頼ることなく、一般地図における RHCR スタイルの窓付きパスを計画している。
混み合った環境で高いスループットを維持するため、PUSHはさらに、EPIBTにインスパイアされた優先度継承、バックトラック、およびいつでも改善されたウィンドウプランニングを統合する。
長期的な推論を必要とする2つの現実的MAPFシナリオに対する実証的な評価は、PUSHがEPIBT(例えば10kエージェント)と同じ巨大なエージェント負荷にスケールし、全てのベースラインよりもシステムスループットを著しく向上することを示している。
関連論文リスト
- HIPIF: Hierarchical Planning and Information Folding for Long-Horizon LLM Agent Learning [51.95194664412812]
大規模言語モデル(LLM)は、幅広いタスクにまたがる自律エージェントとして強力な能力を示している。
長期LLMエージェント学習のための階層的計画と情報フォールディング(HIPIF)を提案する。
HIPIFはエージェントをエンドツーエンドにトレーニングし、明示的なサブゴールの周りに長い水平実行を組織すると同時に、完了したサブゴール履歴を折り畳み、長いコンテキスト干渉を減らす。
論文 参考訳（メタデータ） (2026-06-09T07:35:14Z) - Planning over MAPF Agent Dependencies via Multi-Dependency PIBT [26.73382486796029]
MAPF(Multi-Agent Path Finding)アルゴリズムは、密集した環境で数百から数千のエージェントを1秒以内に計画する必要がある。
PIBTはそのような状況下で効果的に計画できる一般的なアルゴリズムである。
エージェント依存を検索する多依存PIBT(MD-PIBT)を提案する。
論文 参考訳（メタデータ） (2026-03-24T16:38:12Z) - HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel [17.262462566213244]
提案する階層型マルチエージェントフレームワークであるHiMAP-Travelは,計画を戦略的コーディネートと並列日次実行に分割する。
TravelPlannerでは、Qwen3-8Bを用いたHiMAP-Travelが52.78%の検証と52.65%のテストファイナルパスレート(FPR)を達成した。
論文 参考訳（メタデータ） (2026-03-05T02:55:53Z) - Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
時間に敏感なアプリケーションのための実行インフォームドMAPF計画フレームワークであるREMAPを提案する。
我々のフレームワークは提案したExecTimeNetを統合し、計画されたパスに基づいて実行時間を正確に推定する。
実験の結果、REMAPはベースライン法よりもソリューション品質を最大20%改善することがわかった。
論文 参考訳（メタデータ） (2025-11-26T20:08:52Z) - Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
リアルタイムMAPFは、計画と実行がインターリーブされる現実的なMAPFセットアップを具現化する。
RT-MAPFの既存のソリューションは、計画期間毎にMAPFアルゴリズムのウィンドウバージョンを反復的に呼び出す。
標準MAPFアルゴリズムのウィンドウ化バージョンにおける計画予算の配分について検討する。
論文 参考訳（メタデータ） (2025-07-22T08:32:55Z) - Wide-Horizon Thinking and Simulation-Based Evaluation for Real-World LLM Planning with Multifaceted Constraints [39.01715254437105]
本稿では,多面制約による計画課題を解決するための多面計画(MAoP)について紹介する。
MAoPは直接計画するのではなく、ストラテジストを活用して、さまざまな側面から事前計画を行い、プランナーのための計画青写真を提供する。
論文 参考訳（メタデータ） (2025-06-14T09:37:59Z) - HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking [109.09735490692202]
提案するHyperTree Planning(HTP)は,高木構造プランニングアウトラインを構成する新しい推論パラダイムである。
実験ではHTPの有効性を実証し、Gemini-1.5-ProによるTravelPlannerベンチマークで最先端の精度を実現し、o1-previewよりも3.6倍の性能向上を実現した。
論文 参考訳（メタデータ） (2025-05-05T02:38:58Z) - Extendable Long-Horizon Planning via Hierarchical Multiscale Diffusion [62.91968752955649]
本稿では,学習データよりも長い軌道計画を行うための,拡張可能な長期計画支援エージェントの課題に対処する。
より短いものを縫い合わせることで、より長い軌跡を反復的に生成する拡張法を提案する。
HM-ディフューザーは階層構造を用いてこれらの拡張軌道を訓練し、複数の時間スケールにわたるタスクを効率的に処理する。
論文 参考訳（メタデータ） (2025-03-25T22:52:46Z) - SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
無線対応経路計画フレームワークであるSCoTTを提案する。
SCoTT は DP-WA* の2% 以内で経路ゲインを達成し, 連続的に短い軌道を生成できることを示す。
また,ガゼボシミュレーションにおいて,SCoTTをROSノードとして配置することにより,本手法の実用性を示す。
論文 参考訳（メタデータ） (2024-11-27T10:45:49Z) - Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。
我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。
ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
論文 参考訳（メタデータ） (2024-02-29T15:36:01Z) - Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders
for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
BTPG(Bidirectional Temporal Plan Graph)と呼ばれる新しいグラフィカルな表現を導入し,実行中の注文を切り替えることで,不要な待ち時間を回避する。
実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。
論文 参考訳（メタデータ） (2023-12-30T20:23:27Z) - LLM-Assist: Enhancing Closed-Loop Planning with Language-Based Reasoning [65.86754998249224]
従来のルールベースプランナとLCMベースのプランナを併用した,新しいハイブリッドプランナを開発した。
当社のアプローチでは,既存のプランナが苦労する複雑なシナリオをナビゲートし,合理的なアウトプットを生成すると同時に,ルールベースのアプローチと連携して作業する。
論文 参考訳（メタデータ） (2023-12-30T02:53:45Z) - Differentiable Spatial Planning using Transformers [87.90709874369192]
本研究では、長距離空間依存を計画して行動を生成する障害マップを与えられた空間計画変換器(SPT)を提案する。
エージェントが地上の真理マップを知らない環境では、エンド・ツー・エンドのフレームワークで事前訓練されたSPTを利用する。
SPTは、操作タスクとナビゲーションタスクの両方のすべてのセットアップにおいて、最先端の差別化可能なプランナーよりも優れています。
論文 参考訳（メタデータ） (2021-12-02T06:48:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。