日本フィジカルAI新聞

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

群制御arXiv:2603.28968

優先順位制約付きマルチエージェントタスク割り当てと経路探索のための大規模近傍探索

Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints

シェア:XThreadsFacebookLINEはてブBluesky

タスクの順序制約を考慮しつつ、エージェントへのタスク割り当てと経路を同時に最適化する問題(TAPF-PC)に対し、大規模近傍探索を用いて解を反復改善する手法を提案した。

詳しい要約

1. どんなもの?

- 複数ロボットのタスク割当と経路計画を同時に最適化する問題(TAPF-PC)を扱う研究。 - 従来のMAPF-PCはタスク順序が固定だが、本論文は「誰がどのタスクを行うか」も最適化する。 - 優先順序制約を満たしつつ、衝突回避と経路コスト最小化を目指す。 - 大規模近傍探索(Large Neighborhood Search)による解法を提案。

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

- 従来のMAPF-PCはタスク順序が事前に固定されており、割当の自由度がなかった。 - 本論文はTAPF-PCへ拡張し、割当・優先順序・経路コストを統合最適化する点が新しい。 - 固定割当の初期解と比較して、89.1%のインスタンスで改善を達成。 - 柔軟な再割当による利得を大規模近傍探索で効果的に捉えられることを示した。

3. 技術・手法の肝は?

- 実行可能なMAPF-PCの初期解(seed)から出発する大規模近傍探索。 - 選択した近傍内で再割当に基づく近傍修復を行い、実行可能性を回復する。 - 反復的に改善を繰り返すことで、割当と経路の結合探索空間を効率的に探索。 - 優先順序制約を維持しながら再割当を可能にする点が肝。

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

- 複数のベンチマークファミリーとスケーリング条件で実験。 - 最良の構成が固定割当の初期解に対して89.1%のインスタンスで改善。 - 大規模近傍探索が優先順序制約下での柔軟な再割当の利得を捉えることを実証。

5. 議論はある?

- 大規模近傍探索がTAPF-PCの結合探索空間に対して有効であることを示唆。 - ただし、特定の近傍サイズや修復戦略の影響、計算時間などの詳細は要旨からは不明。 - 他の手法との比較や限界については要旨からは不明。

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

- MAPF-PC(Multi-Agent Path Finding with Precedence Constraints)の既存研究。 - TAPF(Task Assignment and Path Finding)の関連研究。 - Large Neighborhood Search(LNS)を用いた組合せ最適化の一般手法。 - 要旨で参照されている具体的な論文は不明。

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

著者: Viraj Parimi, Brian C. Williams

分類: cs.RO, cs.MA

原文アブストラクト

Many multi-robot applications require tasks to be completed efficiently and in the correct order, so that downstream operations can proceed at the right time. Multi-agent path finding with precedence constraints (MAPF-PC) is a well-studied framework for computing collision-free plans that satisfy ordering relations when task sequences are fixed in advance. In many applications, however, solution quality depends not only on how agents move, but also on which agent performs which task. This motivates the lifted problem of task assignment and path finding with precedence constraints (TAPF-PC), which extends MAPF-PC by jointly optimizing assignment, precedence satisfaction, and routing cost. To address the resulting coupled TAPF-PC search space, we develop a large neighborhood search approach that starts from a feasible MAPF-PC seed and iteratively improves it through reassignment-based neighborhood repair, restoring feasibility within each selected neighborhood. Experiments across multiple benchmark families and scaling regimes show that the best-performing configuration improves 89.1% of instances over fixed-assignment seed solutions, demonstrating that large neighborhood search effectively captures the gains from flexible reassignment under precedence constraints.

関連論文

  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