非同期行動に対応したスケーラブルなマルチエージェント経路計画LSRP*
LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions
非同期行動を扱うマルチエージェント経路計画において、初期解を得た後も時間予算内で解品質を改善し続けるanytimeプランナLSRP*を提案し、最大1000エージェントで評価した。
詳しい要約
1. どんなもの？
2. 先行研究と比べてどこがすごい？
3. 技術・手法の肝は？
4. どうやって有効だと検証した？
5. 議論はある？
6. 次に読むべき論文は？
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Dachuan Liu, Shuai Zhou, Shizhe Zhao, Zhongqiang Ren
分類: cs.RO, cs.AI, cs.MA
原文アブストラクト
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.