マルチエージェント経路探索（MAPF）では、全エージェントの経路コストの総和（SOC）または、最も長い経路の長さであるメイクスパン（MKS）を最小化することが求められる。既存のLaCAM*は、任意の解を求めた後に最適解へと収束するanytimeアルゴリズムであるが、SOCの最小化においては大規模な問題で最適解への収束速度が遅いという課題がある。
MKSのヒューリスティック推定値が、大規模かつ疎なマップにおいて非常に正確であるという特性に着目し、LaCAM*をMKSの最適化に適用する有効性を明らかにした。これにより、SOCでは困難であった大規模問題においても、LaCAM*がMKSの最適解を迅速に導出できることを示した。また、探索メカニズムにIDA*を導入したバリアントを提案し、MKS特化型アルゴリズムであるCBSMを上回る性能を実現した。
LaCAM*の探索メカニズムとして、深さ優先の分枝限定法（DFBnB）を用いる手法と、反復深化A*（IDA*）を用いる手法の2種類を検討している。LaCAM*2では、低レベルの探索においてエージェントを密集させず、より分散した配置を選択する空間利用最適化（SUO）を導入している。IDA*を用いたバリアントでは、最小の推定コストを持つノードのみを考慮するため、SUOによってエージェントが分散される一方で、コストが増大する探索を抑制する仕組みとなっている。
4種類のベンチマークマップ（Empty, Warehouse, Game, City）を用い、エージェント数を100から4,000まで変化させたインスタンスに対して、CBSM、LaCAM*-BnB、LaCAM*-IDA*、LaCAM*2-BnB、LaCAM*2-IDA*の5手法を比較した。1インスタンスあたり60秒の制限時間内で、成功率と平均実行時間を評価した。結果として、中規模のWarehouseやGameマップではLaCAM*2-IDA*が優れた性能を示し、大規模なCityマップではLaCAM*2-IDA*が3,500エージェントを含むインスタンスの最適解導出に成功した。
マップの密度によって最適な手法が異なる。小規模で密なマップではCBSMが適しており、中規模から大規模で疎なマップではLaCAM*2-IDA*が推奨される。ただし、非常に疎なマップにおいては、エージェントを分散させるSUOの機能が不要となるため、LaCAM*-IDA*の方が優れた性能を示すというトレードオフがある。
マルチエージェント経路探索（MAPF）では、全エージェントの経路コストの総和であるSOCと、最も長い経路の長さであるメイクスパン（MKS）の最小化が主要な目的関数となる。LaCAMは、エージェントの配置を状態として深さ優先探索を行い、低レベルの探索でPIBTなどの高速なアルゴリズムを用いて衝突のない次状態を生成する手法であり、その拡張であるLaCAM*は、深さ優先の分枝限定法を用いることで最適解への収束を保証する。エージェントの密集を防ぐために配置を分散させる空間利用最適化（SUO）を導入した改良版のLaCAM*2は、SOCの最適化において収束が非常に遅いという課題がある。本研究では、MKSのヒューリスティック推定値は特に大規模で疎なマップにおいて非常に正確であることを利用し、LaCAM*がMKSの最適化において有効であることを示す。実験の結果、疎なマップにおいてLaCAM*はMKS専用のCBSベースの手法であるCBSMを大幅に上回り、さらにIDA*を用いた探索を行うLaCAM*-IDA*は、分枝限定法を用いた手法やCBSMよりも優れた性能を示し、様々なベンチマークマップで最先端の性能を達成した。
LaCAM*は、深さ優先探索を用いて迅速に解を求めるLaCAMを拡張し、深さ優先枝刈り付き探索を用いることで、解の品質を繰り返し改善しながら最終的に最適解を証明することを目指したアルゴリズムです。先行研究では、MAPFベンチマークのインスタンスの99%に対して劣最適解を導出できるスケーラビリティが示された一方で、エージェント数が多い大規模な問題では最適解への収束速度が遅いという課題が報告されていました。本研究では、SOC（衝突回避）とMKS（メイクスパン最小化）における最適解探索の差異を、warehouse-20-40-10-2-1マップ上のエージェント数100から1,000までの50個のインスタンスを用いて実験的に検証しました。その結果、LaCAM*2-BnBはSOCのインスタンスでは最適解を一つも導出できませんでしたが、MKSにおいてはエージェント数が1,000の場合でも32個のインスタンスで最適解を導出しました。この結果は、LaCAM*をMKSにおける最適解探索アルゴリズムとして利用できる可能性を示しています。
Intel Core Ultra 9-185H CPUと16GB RAMの環境において、CBSM、LaCAM*-BnB、LaCAM*-IDA*、LaCAM*2-BnB、LaCAM*2-IDA*の5つの手法を、4種類のベンチマークマップを用いて比較実験した。MAPF-LNS2を用いてエージェント数を100から4,000まで変化させたインスタンスを対象とし、1インスタンスあたりの制限時間を60秒として成功率と平均実行時間を評価した。実験の結果、小規模なEmptyマップではCBSMがLaCAM*系を上回ったが、より大規模な3つのマップではLaCAM*系がCBSMを上回り、特にLaCAM*2-IDA*はCityマップにおいて3,500エージェントを含むインスタンスを最適解として解くことに初めて成功した。手法間の比較では、中規模のWarehouseおよびGameマップにおいて、LaCAM*2-IDA*はLaCAM*2-BnBやLaCAM*-IDA*よりも優れた性能を示した。これは、LaCAM*2の低レベル層がエージェントを疎な領域へ分散させる特性を持ちつつ、IDA*を用いることで最小のコスト値を持つノードを選択し、実行時間を抑制できるためである。一方で、非常に疎なCityマップでは、エージェントを分散させる必要性が低いため、LaCAM*-IDA*がLaCAM*2-IDA*を上回るケースも確認された。