Daily Arxiv

世界中で発行される人工知能関連の論文をまとめるページです。
このページはGoogle Geminiを活用して要約し、非営利で運営しています。
論文の著作権は著者および関連機関にあり、共有する際は出典を明記してください。

Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds

Created by
  • Haebom

作者

Yimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig

概要

本稿では、マルチエージェントパスファインダー(MAPF)問題の新しい近似アルゴリズムであるDECBSを提案します。 MAPFは、複数のエージェントが衝突なしに目標点に到達する経路を見つけるNPハード問題であり、ECBSやEECBSなどの従来の限られた近似アルゴリズムは、 focal search技術を使用して計算効率と解の質をバランスよく考慮します。しかし、従来の focal search では、初期段階で低域 (LB) 値の増加が遅くなり、ナビゲーション領域が制限されるという問題があります。 DECBSは最初に最大LB値を決定し、それに基づいて最高の検索を実行することによってこの問題を解決します。実験の結果、DECBSはほとんどの場合、ECBSよりも優れており、従来の最適化技術とも互換性があります。特に、エージェント密度が中程度または高い場合、同じサブオプティマリティボーンと最適化の下で、ECBSより平均23.5%の実行時間改善を達成します。高次元CTノードを約30%、低次元 focal searchノードを約50%削減します。

Takeaways、Limitations

Takeaways:
マルチエージェント経路探索問題に対する効率的近似アルゴリズムDECBS提示
従来のアルゴリズムであるECBSと比較して実行時間とナビゲーションノード数の削減効果を確認します(特に高密度環境で効果的)。
既存の最適化手法との互換性により,さらなる性能向上の可能性を提示
Limitations:
提示されたアルゴリズムの性能向上がすべての場合に一貫して現れるわけではない。 (ほとんどの場合には優れていますが、すべてのケースをまとめることはできません)
DECBSの性能向上幅は、エージェント密度によって異なります。 (高密度環境でより大きな効果を示す)
論文で提示された実験結果の一般化の可能性についてのさらなる検証の必要性
👍