マルチエージェント経路探索（MAPF）において、エージェントの集合 $\mathcal{A}$ がグラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で衝突を回避しながら目標地点へ移動する経路を計画する。既存の学習ベースの手法は、計算速度に優れる一方で、衝突やデッドロック、あるいは不要な往復運動といった軌跡の質の低さが課題となっている。本研究は、既存のソルバーが生成した実行可能なスケジュールに対し、軌跡レベルでの後処理を行うことを目的とする。
エージェントの軌跡内の閉じた部分的な歩行を崩壊させるタスクを、MAPF-Collapseという新たな最適化問題として定式化し、そのNP困難性を証明した。従来の学習ベースの手法は次の一手レベルの衝突回避に留まっていたが、本研究は軌跡全体を対象とした事後最適化を導入している。これにより、ソルバーの種類に依存せず、解の品質を一貫して向上させるフレームワークを実現した。
エージェント $a$ の時刻 $t_1$ から $t_2$ までの位置が $x_{a, t_1} = x_{a, t_2}$ を満たす場合に、その区間を単一の地点で待機するアクションに置き換える。この問題を、候補となる崩壊操作の集合 $\mathcal{C}$ に対し、コスト削減量 $w_c$ と実行有無を示すバイナリ変数 $z_c$ を用いて、$\text{maximize} \sum_{c \in \mathcal{C}} w_c z_c$ となる整数線形計画法（ILP）として定式化する。制約条件には、同一エージェント内での時間重複の禁止、エージェント間の頂点衝突の回避、および特定の崩壊操作を選択した際に生じる衝突を回避するための依存関係の維持が含まれる。
POGEMAベンチマークを用い、SCRIMP、DCC、RAILGUN、MAMBA、Followerなどの学習ベースの手法およびLaCAMという探索ベースの手法を対象に評価した。評価指標として、成功率（ISR）、総移動コストの減少量（Saved SoC）、および減少率（SoC Saving Ratio）を用いた。実験の結果、エージェント密度が高まるほど冗長な動きが増えるため、平均して約20%から40%のSoC削減を達成した。実行時間は、LaCAMでは100ms未満、多くの学習ベースの手法でもほとんどのケースで1秒未満を実現している。
Judgelightはソルバーに依存しない汎用的な手法であるが、計算量はILPの制約条件の数に大きく依存する。今後の課題として、他のマルチエージェント計画設定への拡張や、冗長な移動の除去だけでなく、不要な待機アクションの除去へと機能を強化することが挙げられる。
本研究では、学習ベースのMAPFソルバーが生成する実行可能だが冗長または振動的な軌跡を改善するため、事後最適化レイヤーであるJudgelightを提案している。この手法は、エージェントの軌跡内にある閉じた部分的な歩行（closed subwalks）を崩壊させることで、すべての実行可能性制約を維持したまま不要な動きを除去する。このプロセスはMAPF-Collapseとして定式化され、その計算量がNP困難であることが証明されている。著者らは、この問題を整数線形計画法（ILP）として定式化することで、厳密な最適化アプローチを提示している。実験の結果、Judgelightは特に学習ベースのソルバーにおいて、解のコストを約20%一貫して削減し、実世界への導入に適した軌跡を生成することを示した。
Multi-Agent Path Finding (MAPF) は、既知のグラフ上で複数のエージェントが衝突を回避しながら始点から終点へ移動する経路を計画する NP-hard な問題であり、倉庫自動化などの分野で重要視されている。既存の探索ベースの手法は高い解の質を保証する一方で、エージェント数や混雑度の増加に伴い実行時間が大幅に増大する課題があり、これに対し深層学習を用いた手法が提案されているが、学習ベースの手法は衝突やデッドロックを招く安全性への懸念や、不要な往復運動などの軌跡の質の低さが課題となっている。本研究では、学習ベースまたは探索ベースのソルバーが生成した実行可能なスケジュールに対し、軌跡レベルでの後処理を行う手法 Judgelight を提案する。Judgelight は、エージェントの軌跡に含まれる閉じた部分的な歩行（closed subwalks）を圧縮することで冗長な動きを削減することを目的としており、このタスクを、実行可能性制約の下で移動アクションの総数を最小化する（待機は低コストとして扱う）新たな最適化問題 MAPF-Collapse として定式化する。MAPF-Collapse は NP-hard であることが証明されており、提案する厳密な最適化アプローチである Judgelight は、特に学習ベースのソルバーが生成した軌跡の品質を、実世界の倉庫運用に適した形へと一貫して改善する。
Multi-Agent Path Finding (MAPF) 問題は、エージェントの集合 $\mathcal{A}$ が、頂点と単位コストの辺からなる無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で、各エージェント $a \in \mathcal{A}$ の開始地点 $s_a$ から目標地点 $g_a$ まで、衝突を回避しながら移動する経路を計画する問題である。各エージェントの時刻 $t$ における位置を $x_a(t)$ とすると、移動またはその場での待機（自己ループ）の各アクションは $1$ 単位時間で実行され、経路 $\pi_a$ は $x_a(0) = s_a$ および $x_a(T_a) = g_a$ を満たし、目標到達後は $x_a(t) = g_a$ ($t > T_a$) となる。衝突は、時刻 $t$ において $x_a(t) = x_b(t)$ となる頂点衝突 $\text{coll}(a, b, t)$ と、時刻 $t$ から $t+1$ にかけてエージェント $a$ と $b$ が同じ辺を逆方向に移動する辺衝突 $\text{coll}(a, b, t, t+1)$ の2種類が定義される。MAPF アルゴリズムの目的は、すべてのエージェントの経路集合 $\Pi = \{\pi_a \mid a \in \mathcal{A}\}$ を、各経路がグラフの辺に沿っており、かつすべての衝突 $\text{coll}(a, b, \cdot)$ を回避するように、総フロータイム（SoC）を最小化することである。
マルチエージェント経路探索（MAPF）は最適性を求める場合にNP困難な問題であり、各エージェントの経路を個別に計画する分離型、全エージェントの計画を同時に策定する結合型、および衝突時のみ結合する動的結合型の戦略が存在する。Conflict-Based Search（CBS）に代表される探索ベースの手法は、ECBSやEECBSといった限定的な劣最適解を許容するバリアントを含む中央集権的かつ最適解を得る手法であるが、問題規模の増大に伴う探索空間の次元の爆発という課題を抱えている。これに対し、深層学習を用いた手法は、模倣学習（IL）や強化学習（RL）を用いることで、ヒューリスティック関数を自動的に学習し、探索ベースよりも短時間で計画を生成できる利点がある。具体的には、局所的な視野に基づくPRIMAL、GPTモデルを用いたMAPF-GPT、グラフニューラルネットワークやTransformerによる通信機構を組み込んだMAGATやSCRIMP、さらには中央集権的なILを用いるRAILGUNなどが提案されている。しかし、CS-PIBTのように学習済み局所方策をPIBTと組み合わせる手法であっても、その修正は主に次の一手レベルの衝突回避に留まっており、エージェントが目標に向かって進展しているか、あるいは単に振動運動を繰り返しているかを検知することはできない。また、エージェントに次々と新しい目標が割り当てられるLifelong MAPF（LMAPF）においても、既存のPIBT等の手法と同様に、不要な動きや振動運動が発生する可能性があり、提案手法であるJudgelightはこれらに対しても拡張適用が可能である。
MAPF-Collapseは、既存のMAPF解の軌跡に対して、閉じた部分歩行（closed subwalk）を定数シーケンス（待機行動）に置き換えることで総コストを最小化する事後最適化問題である。具体的には、エージェント $a$ の時刻 $t_1$ から $t_2$ までの位置の列 $x_{a, t_1:t_2}$ が $x_{a, t_1} = x_{a, t_2}$ を満たすとき、この区間を $x_{a, t_1}$ で固定する「collapse」操作を適用する。この問題の決定版はNP完全であり、独立集合問題（Independent Set）からの多項式時間還元によってその困難性が証明されている。提案手法であるJudgelightは、この問題を整数線形計画法（ILP）として定式化し、以下の目的関数を最大化することでコスト削減を実現する。
$$\text{maximize} \sum_{c \in \mathcal{C}} w_c z_c$$
ここで、$\mathcal{C}$ は候補となるcollapseの集合、$w_c$ はその操作によるコスト削減量、$z_c \in \{0, 1\}$ は操作の実行有無を示すバイナリ変数である。制約条件として、同一エージェント内での時間重複の禁止、異なるエージェント間での頂点衝突の回避、およびあるcollapseを選択した際に生じる衝突を回避するために他のエージェントに特定のcollapseを強制する依存関係の維持が含まれる。実用上の計算量削減のため、同一地点が連続する区間を最初と最後の出現のみに絞る最適化や、振動的な動き（例：$ABAB\dots$）に対して長さ3のフィルタリングを適用する前処理が導入されている。
本研究では、POGEMAベンチマークを用い、SCRIMP、DCC、RAILGUN、MAMBA、Followerといった学習ベースの手法およびLaCAMという探索ベースの手法を対象に、提案手法であるJudgelightの有効性を評価している。評価指標には、エージェントが目標地点に到達した割合を示す個別の成功率（ISR）、元の解と最適化後の解の間の総移動コスト（SoC）の減少量であるSaved SoC、および元のSoCに対する減少率であるSoC Saving Ratioが用いられている。実験の結果、エージェント数が増加して密度が高まると、衝突回避のための冗長な動き（振動的な動き）が増えるため、Saved SoCおよびSoC Saving Ratioの両方が増加する傾向が確認され、平均して約20%から40%のSoC削減が達成された。特に、MAPFを完全には解決できないMAMBAやFollowerのような手法において、Judgelightは不要な動きを抑制し、目標に到達できないエージェントを静止させることで高い削減率を示す。実行時間に関しては、エージェント密度と元のアルゴリズムの性能に依存し、特にILPの制約条件の数が変数よりも実行時間に大きな影響を与えるが、LaCAMでは100ms未満、多くの学習ベースの手法でもほとんどのケースで1秒未満の実行時間を実現している。
学習ベースのMAPFソルバーは、次アクション単位の意思決定を行うため、混雑時や部分的な失敗時に不要な動きや振動を含む解を生成しやすい。本研究では、このような冗長な動きの除去を軌跡レベルの事後処理問題として定式化し、これを MAPF-Collapse と定義して、その問題が NP困難であることを証明した。この問題に対し、整数線形計画法を用いた厳密解法を開発し、それに基づく事後最適化フレームワークとして Judgelight を提案している。POGEMA ベンチマークを用いた実験では、Judgelight は実行時間の実用性を維持しつつ、解のコストを継続的に $20\%$ から $40\%$ 削減し、解決したテストケースの $90\%$ 以上が $1$ 秒以内に完了することを示した。Judgelight はソルバーに依存しない事後処理手法として有効であるが、今後の課題として、他のマルチエージェント計画設定への拡張や、冗長な移動だけでなく不要な待機アクションの除去へと機能を強化することが挙げられる。