日本フィジカルAI新聞

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

群制御arXiv:2609.39559

分割して崩壊:独立部分問題への厳密分解によるMAPF-Collapse

Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances

シェア:XThreadsFacebookLINEはてブBluesky

マルチエージェント経路計画の冗長動作除去問題を、協調不要な部分問題に分解して高速に解く厳密解法を提案した。

詳しい要約

1. どんなもの?

本論文は MAPF-Collapse (MAPFC) を扱う。MAPFC は、現代の MAPF solver が生成した feasible な plan から、除去可能な冗長 move を削除して feasibility を保つ post-optimization 問題である。NP-hard であり、learning-based SOTA solver が冗長 move を含む plan を作る際に自然に生じる。

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

先行研究の Judgelight は全 agent を jointly に ILP で解くため、コストが full instance に支配される。本研究は MAPFC が独立 sub-problem に分解でき、多くは単一 agent で inter-agent reasoning 不要という洞察に基づく。結果として、coordination 不要な場合に約 1,900 倍高速な lightweight solver を導入し、全体で Judgelight の品質を維持しつつ median 10.5 倍の per-instance speedup を達成した。

3. 技術・手法の肝は?

まず協調が必要な agent を特定し、instance を sub-problem に分割する。協調不要な場合は極めて軽量な solver を適用する。協調が必要な場合は Judgelight も使えるが、より効率的な CBS-like solver を導入する。提案 framework は exact で、商用 ILP solver を使わない。coordination-heavy な instance には Judgelight に fallback する regime-aware hybrid planner を提案する。

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

要旨からは不明。ただし、coordination 不要な場合の lightweight solver が Judgelight より約 1,900 倍高速であること、全 benchmark で median 10.5 倍の per-instance speedup を達成し、Judgelight の品質に匹敵することが述べられている。

5. 議論はある?

要旨からは不明。ただし、MAPFC が独立 sub-problem に分解でき、多くが単一 agent で解けるという洞察が議論の中心である。coordination-heavy な instance では Judgelight に fallback する hybrid planner が提案されている。

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

Tang et al. による Judgelight (ILP ベースの MAPFC solver) が直接の比較対象として挙げられている。また、CBS-like solver や learning-based SOTA MAPF solver も関連する。

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

著者: Oren Salzman

分類: cs.AI, cs.RO

原文アブストラクト

In this work we study the problem of MAPFC, a post-optimization step for Multi-Agent Path Finding (MAPF) plans where we are given a feasible plan produced by a modern MAPF solver and are tasked with removing avoidable moves while preserving feasibility. This NP-hard problem naturally arises when using learning-based state-of-the-art (SOTA) solvers which construct plans that contain redundant moves that can be removed. Recently, Tang et al. presented Judgelight, which uses Integer Linear Programming (ILP) to solve MAPFC. Importantly, the ILP is constructed over all agents jointly, so its cost is governed by the full instance rather than by the small coupled residue that actually requires joint reasoning. Our key insight, motivating this work, is that MAPFC instances naturally decompose into independent sub-problems, most of which involve a single agent and can be solved without any inter-agent reasoning. To this end, we first identify which agents need to coordinate their motion and partition the instance into sub-problems accordingly. For the cases where no coordination is required, we introduce an extremely lightweight solver that is $\approx\!1{,}900\times$ faster than Judgelight. For cases where coordination is required, Judgelight can be used but we introduce an alternative CBS-like solver which is more efficient on easier problems. The resulting framework is exact, uses no commercial ILP solver, and matches Judgelight's quality while running substantially faster on the coordination-light majority of instances; on the coordination-heavy instances we propose a regime-aware hybrid planner that falls back to Judgelight. Over all benchmarks tested, this planner achieves a median $10.5\times$ per-instance speedup over Judgelight.

関連論文

  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・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

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