日本フィジカルAI新聞

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

群制御arXiv:2507.16874

リアルタイム多エージェント経路探索のための予算配分ポリシー

Budget Allocation Policies for Real-Time Multi-Agent Path Finding

シェア:XThreadsFacebookLINEはてブBluesky

リアルタイム多エージェント経路探索において、限られた計画予算をエージェント間で効果的に配分するポリシーを検討し、共有予算プールよりも優れた性能を示した。

詳しい要約

1. どんなもの?

- Real-time Multi-Agent Path Finding (RT-MAPF) における planning budget の配分問題を扱う研究 - MAPF は各 agent が衝突を避けて目的地へ到達する経路を求める問題 - RT-MAPF では固定の planning period (planning budget) 内で計画し、固定の execution window 分だけ実行する反復プロセスを仮定 - 既存 RT-MAPF 解法は planning budget のサイズを明示的に考慮せず windowed MAPF を毎回呼ぶ - 本研究は windowed 版 MAPF-LNS2 における planning budget の配分ポリシーを探索する

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

- 既存の RT-MAPF 解法は各 planning period で windowed MAPF アルゴリズムを反復呼び出しするが、planning budget のサイズを明示的に考慮していない - このギャップを埋め、planning budget の配分ポリシーを明示的に設計・比較する点が新規 - 全 agent が共有プールから budget を引く baseline は厳しいシナリオで非効率と示す - agent 間で budget を賢く分配するポリシーがより多くの問題をより短時間で解けることを示す

3. 技術・手法の肝は?

- windowed 版 MAPF-LNS2 を対象に、planning budget の配分ポリシーを複数設計・比較 - baseline: 全 agent が共有の planning budget pool から引く方式 - 提案: agent 間で planning budget を知的に分配するポリシー群 - RT-MAPF の反復プロセス (短い計画の実行と次 window の並行計画) の枠組み上で評価 - 各ポリシーが解ける問題数と所要時間に与える影響を比較

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

- 複数の planning budget 配分ポリシーを比較実験で評価 - baseline の共有プール方式が challenging なシナリオで非効率であることを確認 - budget を賢く分配するポリシーがより多くの問題インスタンスをより短時間で解くことを示す - 具体的なベンチマーク名・指標の詳細は要旨からは不明

5. 議論はある?

- baseline の共有 planning budget pool は厳しいシナリオで有効でないと議論 - planning budget を agent 間でどう分配するかが RT-MAPF の性能に影響すると主張 - どの分配ポリシーがどの状況で優れるかの詳細や限界は要旨からは不明 - 他の MAPF アルゴリズムへの一般化可能性は要旨からは不明

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

- MAPF-LNS2 (windowed 版の基盤アルゴリズム) - RT-MAPF の既存解法 (windowed MAPF を反復呼び出す手法群) - MAPF 全般のサーベイや代表的手法 (例: CBS, ECBS, prioritized planning など同分野の定番) - planning budget を考慮したリアルタイム計画に関する関連研究

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

著者: Raz Beck, Roni Stern

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

原文アブストラクト

Multi-Agent Path finding (MAPF) is the problem of finding paths for a set of agents such that each agent reaches its desired destination while avoiding collisions with the other agents. This problem arises in many robotics applications, such as automated warehouses and swarms of drones. Many MAPF solvers are designed to run offline, that is, first generate paths for all agents and then execute them. In real-world scenarios, waiting for a complete solution before allowing any robot to move is often impractical. Real-time MAPF (RT-MAPF) captures this setting by assuming that agents must begin execution after a fixed planning period, referred to as the planning budget, and execute a fixed number of actions, referred to as the execution window. This results in an iterative process in which a short plan is executed, while the next execution window is planned concurrently. Existing solutions to RT-MAPF iteratively call windowed versions of MAPF algorithms in every planning period, without explicitly considering the size of the planning budget. We address this gap and explore different policies for allocating the planning budget in windowed versions of MAPF-LNS2, a state-of-the-art MAPF algorithm. Our exploration shows that the baseline approach in which all agents draw from a shared planning budget pool is ineffective in challenging scenarios. Instead, policies that intelligently distribute the planning budget among agents are able to solve more problem instances in less time.

関連論文

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

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI