群制御2026/9/13arXiv:2609.14208

ITA-LaCAM: 割当を考慮した構成空間探索による完全かつスケーラブルなTAPFソルバ

ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search

エージェントの目標割当と衝突回避経路計画を同時に行うTAPF問題に対し、割当を構成空間探索に統合した完全ソルバを提案し、大規模ベンチマークで高い成功率と効率を示した。

詳しい要約

1. どんなもの？

- Combined Target Assignment and Path Finding (TAPF) を解く完全かつスケーラブルなソルバ ITA-LaCAM を提案。 - LaCAM と ITA-CBS に着想を得て、joint-configuration ノードに agent-to-target matching を持たせる。 - 後継生成時に移動した agent の matching を漸進的に修復し、targets を PIBT の後継生成のガイドに使う。 - 組合せ的 assignment 空間を明示的に列挙せず適応的再割当てを可能にし、LaCAM の完全性とスケーラビリティを保つ。

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

- 8 マップ・5–200 agents の 9,760 benchmark instances で ITA-LaCAM は 100% 解決。 - DBS-Hungarian を構成した IR-TAPF は 95.6% の解決に留まる。 - 初期解を 84.0% の比較でより速く発見。 - 両手法が解いた instance のうち 65.0% で sum of costs がより低い。

3. 技術・手法の肝は？

- 各 joint-configuration ノードが agent-to-target matching を保持。 - 後継生成時に、移動した agents の matching を漸進的に修復 (incremental repair)。 - その targets を用いて PIBT successor generation をガイド。 - これにより assignment 空間の明示的列挙を避けつつ適応的再割当てを実現。 - LaCAM の完全性とスケーラビリティを維持。

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

- 8 マップ、5–200 agents の 9,760 benchmark instances で評価。 - ITA-LaCAM は 100% 解決、IR-TAPF (DBS-Hungarian) は 95.6% 解決。 - 初期解発見速度は 84.0% の比較で優位。 - 両手法が解いた instance の 65.0% で sum of costs が低い。

5. 議論はある？

- 要旨からは不明。 - 制限や失敗ケース、計算コストの詳細な議論は要旨に記載なし。

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

- LaCAM - ITA-CBS - IR-TAPF - DBS-Hungarian - PIBT

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

著者: Yimin Tang, Han Zhang, Shao-Hung Chan, Junsoo Kim, Erdem Bıyık, Sven Koenig, Jingkai Chen

分類: cs.RO

原文アブストラクト

Combined Target Assignment and Path Finding (TAPF) requires assigning targets for agents while simultaneously planning collision-free paths. We present ITA-LaCAM, a complete and scalable TAPF solver inspired by LaCAM and ITA-CBS. In ITA-LaCAM, each joint-configuration node carries an agent-to-target matching. When a successor is generated, ITA-LaCAM incrementally repairs the matching for the agents that moved and uses the targets to guide PIBT successor generation. This design enables adaptive reassignment without explicitly enumerating the combinatorial assignment space, while preserving LaCAM's completeness and scalability. Across 9,760 benchmark instances on eight maps with 5--200 agents, ITA-LaCAM solved 100% of the instances, compared with 95.6% for IR-TAPF configured with DBS-Hungarian. ITA-LaCAM found an initial solution faster in 84.0% of the comparisons and achieved a lower sum of costs in 65.0% of the instances solved by both methods.

arXivで原文を読む →arXiv概要ページ