グラフ上で複数のエージェントが、複数のコスト関数からなるコストベクトルを考慮しながら、衝突を回避して始点から終点へ移動する経路を求める問題である。従来の多目的マルチエージェント経路探索では、パレート境界（非劣解の集合）をすべて算出するか、目的関数を重み付けによって単一のコストに統合する手法が主流であった。しかし、これらは目的関数の数が増えると計算コストが膨大になるか、あるいは適切な重みの設定が困難であるという課題があった。
パレート境界の計算や目的関数のスカラー化を必要とせず、ユーザーが定義した優先順位に従って直接的に単一の解を導出するフレームワークを提案した点に新規性がある。既存手法が目的関数の増加に伴い計算負荷が急増するのに対し、提案手法は計算量が目的関数の数に対して線形にスケールする。
Conflict-Based Search (CBS) の二層構造を拡張した手法である。高レベル探索では制約木を用いてエージェント間の衝突を解消し、各ノードが保持する結合コストベクトルを辞書式順序で最小化するように探索を進める。低レベル探索にはLexicographic A* (LA*) を採用しており、時間拡張された状態空間において、優先度の高い目的関数から順に最適化することで、個々のエージェントの辞書式最適経路を計算する。
10種類のベンチマークマップを用い、5つのベースライン手法と比較評価を行った。評価指標は、2分間の制限時間内に有効な共同計画を見つけられる成功率と、解の最適性である。実験の結果、3つの目的関数を持つ標準的なシナリオで高い成功率を示した。また、目的関数が4つ以上に増える設定においても、既存手法が失敗する中でLCBSは成功を収め、最大10個の目的関数を持つ設定までスケーラビリティを実証した。さらに、パレート最適解を算出する手法と比較して、LCBSが同一の最適コストベクトルを導出することも確認した。
本手法は、目的の優先順位が既に定義されている設定に焦点を当てたモデリングに基づくものであり、優先順位が不明な場合に用いられるパレート境界探索手法の代替ではない。提案手法は辞書式順序においてパレート境界上の解を得ることを理論的に保証しているが、計算量の線形性は目的関数の数に基づくものであり、高レベルおよび低レベルの各探索におけるヒープ操作やベクトル演算のコスト自体は目的関数の次元数に依存する。
本研究は、複数の目的関数に対して優先順位（辞書式順序）が定義されているマルチエージェント経路探索（MO-MAPF）を効率的に解くための、Lexicographic Conflict-Based Search (LCBS) というフレームワークを提案している。従来のMO-MAPF手法は、パレート最適解の集合をすべて算出してから優先順位に沿った解を選択する手法や、重み付けによって目的関数を単一のコストに統合するスカラー化手法が主流であったが、これらは目的関数の数が増えると計算コストが膨大になる、あるいは適切な重みの設定が困難であるといった課題があった。提案手法であるLCBSは、パレートフロントの計算や重みの決定を必要とせず、優先順位の高い目的から順に逐次的に最適化を行うことで、直接的に優先順位に適合した単一の解を導出する。具体的には、下位レベルの探索において辞書式A*（LA*）を用いることで、制約を満たしつつ優先順位に従った最短経路を計算し、上位レベルではConflict-Based Search（CBS）の枠組みに基づき、エージェント間の衝突を制約として分岐させながら解消していく。標準的なベンチマークおよびランダムなMO-MAPFの設定を用いた評価実験では、最大で10個の目的関数と35個のエージェントが存在する条件下においても、既存の最先端手法を上回る成功率を達成し、高いスケーラビリティを示すことが確認されている。
Multi-Objective MAPF (MO-MAPF)は、グラフ上で各エージェントが始点から終点へ移動する際、複数のコスト関数に基づくコストベクトルを考慮し、頂点やエッジの衝突を回避する経路を求める問題である。従来のMO-MAPFはパレート境界上の非支配的な解を生成するが、目的間の優先順位を計画プロセスに直接組み込むことができず、解の生成後に事後的に適用されるという課題がある。これに対し、Lexicographic MO-MAPFは、目的間に厳格な優先順位を定義することで、最も優先度の高い目的から順に最適化を行う。ある計画が最適であるとは、そのコストベクトルが、優先度の高い次元から順に他のすべての有効な計画と比較して、辞書式順序において最小となることを指す。この手法は、人間とロボットの相互作用においてエネルギー消費よりも安全性を優先するといった、実用的な優先順位を計画段階から直接反映できる。
LCBSは、複数の目的関数に対して辞書式順序による優先順位付けを行うConflict-Based Search (CBS) を拡張した手法です。高レベル探索では制約木を用いてエージェント間の衝突を解消し、各ノードが保持する結合コストベクトルを辞書式順序で最小化するように探索を進めます。低レベル探索にはLexicographic A* (LA*)が用いられ、時間拡張された状態空間において、優先度の高い目的関数から順に最適化することで、個々のエージェントの辞書式最適経路を計算します。この手法は、得られる解がパレートフロント上に存在することを理論的に保証しています。また、計算量は目的関数の数に対して線形にスケールし、高レベルおよび低レベルの各探索におけるヒープ操作やベクトル演算のコストは、目的関数の次元数に対して線形な依存関係に留まります。
本実験では、提案手法であるLCBSを、標準的およびランダムなシナリオを含む10種類のMAPFベンチマークを用いて、5つのベースライン手法と比較評価しています。比較対象には、低レベル探索の異なる手法を用いる4つのバリエーション（計算負荷を抑えた単一解の提示、5解または10解の提示によるパレート解の網羅性評価、および重複する衝突を統合して計算量を削減する手法）と、非支配的な経路を枝刈りして高速化を図る手法が含まれます。評価指標として、エージェント数の増加に伴う成功率、目的関数の数が増加した際の性能推移、および最適性を測定しています。実験はC++を用いて実装され、Apple M3 Proチップを搭載したmacOS上で実施されました。また、パレート支配の粒度を制御するパラメータについても、先行研究に基づいた設定を用いています。
提案手法であるLCBSの性能を、エージェント数や目的関数の数が増加する条件下で、パレート最適解に基づく既存手法と比較して評価しました。2分間の制限時間内に有効な共同計画を見つけられる割合を成功率として定義し、標準的なシナリオおよびランダムなシナリオを用いた10種類のベンチマークマップで実験を行いました。その結果、3つの目的関数を持つ標準的なシナリオにおいて、LCBSは他の手法よりも高い成功率を示しました。目的関数が4つ以上に増える設定では、パレート境界の近似に伴う計算負荷の増大により既存手法は失敗しますが、LCBSは成功を収めており、目的関数の数に対するスケーラビリティの高さが示されています。また、パレート最適解を求める手法と比較した解の最適性評価において、LCBSはパレート境界全体を計算することなく、辞書式順序において同一の最小コストベクトルを算出できることが確認されました。
多目的経路計画では、パレート境界全体を計算する手法が存在するが、目的関数の数が増えるとスケーラビリティが低下し、近似手法ではパレート最適性が保証されないという課題がある。多目的マルチエージェント経路探索（MO-MAPF）においては、低レベル探索で各エージェントのパレート最適経路を求め、高レベルプランナーで衝突を解決する手法が一般的である。MO-CBSは制約木を用いて非支配経路を列挙することでパレート境界を構築し、BB-MO-CBSはその衝突解決を改善している。また、近似的な支配関係を用いて計算コストを削減する手法や、複数の目的を単一のコストに統合するスカラー化手法も存在する。これに対し、本研究が採用する辞書式順序（Lexicographic）フレームワークは、優先度の高い順に目的を逐次的に最適化することで、ユーザーの好みを直感的に反映しつつスケーラブルな計画を可能にする。本研究は、目的の優先順位が指定されているMO-MAPFの設定に焦点を当てており、優先順位が不明な場合に用いられるパレート境界探索手法の代替ではなく、特定のモデリング選択に基づくものである。
本研究では、優先順位付けされた目的関数に対して最適解を計画できる、辞書式順序を用いた多目的マルチエージェント経路探索（MO-MAPF）の定式化と、辞書式CBS（LCBS）アルゴリズムを提案している。LCBSは、低レベルの探索プロセスに優先順位を考慮したLA*を統合することで、パレート境界の計算やスカラー化を行うことなく、目的の優先順位に従った効率的な計画を実現する。ベンチマークを用いた評価の結果、LCBSは既存のベースライン手法と比較して一貫して高い成功率を示した。また、エージェント数の増加や目的関数の増加に対しても、性能を維持できることが確認された。