日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:2608.06702

段階的更新による大規模長期計画:生涯MAPFのためのスケーラブルな手法

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

シェア:XThreadsFacebookLINEはてブBluesky

生涯マルチエージェント経路探索(LMAPF)において、数千エージェントを1秒未満で調整しつつ、複数ステップ先を見据えた計画を可能にする新しいプランナーPUSHを提案した。PIBT、RHCR、TPの利点を組み合わせ、一般のマップでスケーラブルな長期計画を実現する。

詳しい要約

1. どんなもの?

Lifelong Multi-Agent Path Finding (LMAPF) のための新しいプランナー 'Path Updates over Staggered Horizons (PUSH)' を提案する。PUSH は、PIBT や EPIBT のようなリアクティブな手法のスケーラビリティと、RHCR のようなウィンドウベースの長期的計画の利点を組み合わせ、一般的なマップ上で数千エージェントを1秒未満で調整しつつ、マルチステップの地平線で計画することを目指す。

2. 先行研究と比べてどこがすごい?

既存の LMAPF 手法は、PIBT/EPIBT はスケールするが時間的近視に悩み、RHCR は長期的計画が可能だが計算オーバーヘッドが大きくスケーラビリティに欠け、TP は長期的計画とスケーラビリティを両立するが高度に構造化されたマップに限定される。PUSH は、TP のように各タイムステップで一部のエージェントのみを計画するスタッガードな計画ウィンドウを用いるが、TP と異なり一般的なマップで RHCR スタイルのウィンドウ計画を実現し、制限的なマップ仮定に依存しない点が新しい。

3. 技術・手法の肝は?

PUSH は、各タイムステップで一部のエージェントのみを計画するスタッガードな計画ウィンドウを採用し、計算複雑性を削減する。さらに、EPIBT から着想を得た priority inheritance、backtracking、anytime improvements をウィンドウ計画に統合し、混雑環境での高スループットを維持する。これにより、PIBT のスケーラビリティ、RHCR の長期的計画、TP の部分計画の利点を組み合わせる。

4. どうやって有効だと検証した?

長期的推論を必要とする2つの現実的な MAPF シナリオで実験を行い、PUSH が EPIBT と同じ大規模なエージェント負荷(例:10kエージェント)にスケールし、全ベースラインよりも有意に高いシステムスループットを達成することを示した。

5. 議論はある?

要旨からは、PUSH の限界や特定の条件下での性能低下などについての議論は不明。また、実験シナリオの詳細や比較したベースラインの具体的な設定も要旨からは不明。

6. 次に読むべき論文は?

要旨で参照されている関連手法として、PIBT、Enhanced PIBT (EPIBT)、RHCR、TP が挙げられる。次に読むべき論文としては、これらの元論文が適切である。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Vaibhav Sanjay, Jiaoyang Li

分類: cs.MA, cs.AI, cs.RO

原文アブストラクト

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.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI