本研究が扱うのは、グラフ $G=(V, E)$ 上で、任意の異なるエージェントのペアの距離が指定された値 $r$ 以上であることを要求する Distance-Independent Unlabeled Multi-Agent Pathfinding (IUMAPF) である。各時刻の配置（configuration） $c$ が、距離独立集合（distance-independent set）となることが制約として課される。これは、エージェントの形状、幾何学的な干渉、あるいは安全マージンを抽象化した問題である。従来のUnlabeled MAPFでは頂点衝突のみを考慮するが、IUMAPFでは $d(u, v) > r$ という広範な制約を扱うため、計算量が大幅に増大する。
第一に、IUMAPFという新しい問題設定を定義し、その解の存在判定が $\textsf{NP}$-complete であることを示した。第二に、最適解を保証するために、問題を整数線形計画法 (ILP) へ帰着させる手法と、グラフのサイズを $O(k^2 d^2)$ まで縮小するカーネル化（圧縮）アルゴリズムを提案した。第三に、大規模な群れ（swarm）に対応するため、ルールベースの IU-PIBT と LaCAM を組み合わせた IU-LaCAM を提案し、ライブロック検出技術によって完全性を確保した。これにより、計画の質を重視するアプローチと、スケーラビリティを重視するアプローチの両面から体系的な研究基盤を構築した。
最適化アプローチとして、Bounded IUMAPF を ILP で定式化し、変数 $x_{i,v,t}$（エージェント $i$ が時刻 $t$ に頂点 $v$ に位置する）と $y_{i,u,v,t}$（エッジ $(u, v)$ を移動する）を用いて、距離独立制約 $\forall t, \forall u, v \in V: d(u, v) \le r \implies (x_{i,u,t} + x_{j,v,t} \le 1)$ を課す。圧縮手法では、問題を Galactic IUMAPF (GMAPF) へ帰着させ、Reduction rule 1 および 2 を用いて、頂点数を $O(k^2)$ または $O(k^2 d^2)$ まで削減する。大規模向けには、IU-PIBT を構成生成器として採用し、再帰的なプロセスで距離独立性と距離回転（distance-rotations）を回避する。さらに、LaCAM の探索スキームにターゲット割り当て関数を統合し、ライブロック検知時にターゲットを再割り当てすることで、IU-LaCAM を構築している。
Intel Core i9-13900H を用いた実験において、`empty-16-16` や `random-64-64-20` などのマップで評価を行った。ILP（Gurobi使用）は単純なマップでは高速だが、大規模な $k$ に対してはスケーラビリティに限界がある。一方、IU-LaCAM は `empty-16-16` で少なくとも $2\times$、`random-64-64-20` では $k=10$ の場合に $0.056\text{s}$ と $0.231\text{s}$ を記録し、既存手法に対し約 $10\times$ の高速化を実現した。また、$d=2$ の Unlabeled MAPF において、IU-PIBT は既存の TSWAP と同等の実行時間でありながら、ボトネックマッチングの下限に近い優れた劣最適性（suboptimality）を示した。
提案手法は、計画の質とスケーラビリティの両立において高い成果を上げたが、いくつかの限界も明らかになった。ILP ベースの手法は、変数の増加に伴い大規模なインスタンスでの成功率が低下する。IU-PIBT は、中程度の密度を持つマップにおいてライブロックにより解を見つけられない傾向があり、これを IU-LaCAM のターゲット再割り当てによって補完している。しかし、`warehouse-10-20-10-2-2` のような狭い通路が多いマップでは、ライブロック対策の優位性が顕著には現れなかった。今後の課題として、エージェントの匿名性をより効率的に扱うための、ラベルなし設定に特化した新しい探索スキームの開発が挙げられている。
本研究では、エージェント間の距離を常に一定以上に保つ制約を持つ「Distance-Independent Unlabeled Multi-Agent Pathfinding (DI-UMAPF)」という、古典的なMAPFを一般化したグラフ上の経路探索問題を扱う。この追加制約により、標準的な（ラベルなし）MAPFでは多項式時間で決定可能であった解の存在判定（feasibility）が、本問題では $\textsfsf{NP}$-complete になるという困難さが生じる。著者らはこの課題に対し、解の存在を維持する圧縮手順を用いた帰着ベースの最適アルゴリズムと、構成生成器（configuration generator）に基づく探索という2つの補完的なアプローチを提案している。実験結果では、この問題の困難性にもかかわらず、提案手法によって数百規模のエージェントを実用的な時間内で扱うことが可能であることが示されている。
本研究では、エージェントが同一の頂点を同時に占有することを衝突と定義する Unlabeled MAPF を拡張し、グラフ上の任意のペアのエージェント間の距離を一定以上に保つ制約を課した Distance-Independent Unlabeled Multi-Agent Pathfinding (IUMAPF) を提案する。IUMAPF において、各時刻の配置が距離独立集合（distance-independent set）となることを要求するこの問題は、幾何学的な干渉や安全マージン、遅延許容性を抽象化したものであり、既存の Unlabeled MAPF とは異なり、一般の $d$ に対しては未踏の課題である。著者らは、計画の質を保証するために整数線形計画法 (ILP) への帰着を用いた最適アルゴリズムと、エージェント数が少ない場合に有効な実行可能性を維持する圧縮手法を提案しているが、これらはスケーラビリティに限界がある。一方で、大規模なインスタンスに対応するため、ルールベースの IU-PIBT と、これに LaCAM の探索手法およびライブロック検出技術を組み合わせた IU-LaCAM を提案しており、後者は大規模な群れ（swarm）の解決を可能にする。これにより、計画の質を重視するアプローチと、大規模なエージェント数を扱うアプローチの両面から IUMAPF の体系的な研究基盤を構築している。
グラフ $G=(V, E)$ において、頂点 $u, v$ 間の最短経路の長さを $d(u, v)$ と定義し、頂点 $v$ の閉近傍を $N[v]$、次数を $\text{deg}(v)$ とする。IUMAPF（Unlabeled Multi-Agent Pathfinding）では、エージェントの集合 $\mathcal{A}$ に対する各エージェントの頂点への割り当てである構成（configuration） $c$ を扱う。構成 $c$ が距離独立（distance-independent）であるとは、任意の異なるエージェントのペアについて $d(u, v) > r$ が成立することを指す。初期構成 $c_{start}$ と目標構成 $c_{target}$ が与えられたとき、IUMAPFの目的は、各ステップでエージェントが現在の頂点の閉近傍 $N[v]$ 内に移動し、かつ全ての構成 $c_t$ が距離独立性を維持するような有限の構成列 $c_0, c_1, \dots, c_T$ を見つけることである。なお、構成が常に距離独立であり、かつエージェントが区別されない（anonymous）設定であるため、従来のMAPFで用いられる頂点衝突やスワップ衝突の制約は考慮不要となる。
本研究は、従来の点エージェントによるMAPFの抽象化を超え、エージェントの形状や実行の不確実性を考慮した拡張MAPFの文脈に位置付けられる。既存のLarge-agent MAPF研究では、連続的なユークリッド距離制約や明示的な幾何学的形状、あるいはConflict-Based Search (CBS) の適応が検討されているが、本研究は実行可能な構成を「距離に依存しない集合（distance-independent sets）」として定式化することで、グラフ理論や組合せ論的手法を用いた計算可能なアルゴリズムの導出を可能にしている。また、エージェントの識別を必要としないunlabeled MAPFに焦点を当てており、これはターゲット割り当てを伴うlabeled MAPFのアルゴリズムを直接適用するよりも、計算量やスケーラビリティの観点で有利である。手法の分類としては、SATベースやフローベースの手法のように問題の性質を利用して保証を与える「帰着ベースのアプローチ」と、現在の状態から後続の構成を高速に生成する「構成生成器ベースのアプローチ」が挙げられ、本研究は後者のLaCAMなどの先行研究から着想を得つつ、unlabeled設定における効率的なプランニングを目指している。
本研究では、距離独立制約を柔軟に扱うために、IUMAPFを整数線形計画法（ILP）へ帰着させる手法を提案している。まず、グラフ $G=(V, E)$、頂点部分集合の集合 $\mathcal{S}$、および時間境界 $T$ が与えられた際に、長さ $T$ 以下の計画が存在するかを判定する Bounded IUMAPF を定義する。ILPの定式化では、エージェント $i$ が時刻 $t$ に頂点 $v$ にいることを示す変数 $x_{i,v,t} \in \{0, 1\}$ および、エージェント $i$ が時刻 $t$ にエッジ $(u, v) \in E$ を移動することを示す変数 $y_{i,u,v,t} \in \{0, 1\}$ を用いる。制約条件として、初期・終了状態の整合性、各時刻における各エージェントの移動の唯一性、および距離独立性のための制約 $\forall t, \forall S \in \mathcal{S}, \forall u, v \in V: \text{dist}(u, v) \le d \implies (x_{i,u,t} + x_{i,v,t} \le 1 \text{ if } S \text{ is distance-independent})$ 等が課される。目的関数を定数とすることで、充足可能な割り当ての有無を判定し、YES-instanceの探索範囲は $\binom{|V|}{|\mathcal{S}|}$ で抑えられるため、この手法は最適解を保証する。
本セクションでは、エージェント数 $k$ と距離制約 $d$ に基づいてグラフのサイズを縮小するカーネル化（kernelization）アルゴリズムを提案している。提案手法は、グラフを惑星（planets）$P$ とブラックホール（black holes）$B$ の和集合として扱うGalactic IUMAPF（GMAPF）フレームワークへ問題を帰着させ、エージェントを吸収可能な頂点としてブラックホールを定義することで、計算量を削減する。具体的には、頂点 $v$ のレイヤー $L(v)$ が一定の閾値を超えた場合に、その周辺のコンポーネントを単一のブラックホールに集約する「Reduction rule 2」と、隣接するブラックホールを統合する「Reduction rule 1」を繰り返し適用する。これにより、GMAPFは $|V| = O(k^2)$ のサイズを持つカーネルを持つことが証明されており（Theorem 1）、さらに誘導グリッドグラフ（induced grid graph）が与えられた場合には、より小さな頂点数でのカーネル化が可能である（Theorem 2）。この手法を距離制約 $d$ のバリアントへ拡張することで、距離制約を考慮したカーネル化も実現しており、最終的に $O(k^2 d^2)$ のサイズにグラフを縮小できる。
本セクションでは、大規模なインスタンスに対してスケーラブルな構成生成器ベースのアルゴリズムであるIU-LaCAMを提案している。IU-LaCAMは、距離独立性（distance-independence）を維持しつつ距離回転（distance-rotations）を回避する構成生成器IU-PIBTと、ラベルなし設定向けに調整されたLaCAM探索スキームで構成される。IU-PIBTは、優先度順にエージェントの次位置を決定するPIBTを拡張したもので、再帰的なプロセスを通じて、あるエージェント $a$ の移動が他のエージェント $a' \in \mathcal{W}_a$ の距離独立性を損なわないか、あるいは距離回転（$d(s_a, g_a) < d(s_{a'}, g_{a'})$ かつ $d(s_{a'}, g_{a'}) < d(s_a, g_a)$ となるようなエージェントの連鎖）を引き起こさないかを検証する。また、デッドロック時にはターゲットの回転（rotation of targets）を行い、局所的な衝突時には一時的なターゲットの入れ替え（target swapping）を行うことで、探索の効率化を図っている。IU-PIBT単体では、同時移動が必要なケースや、エージェント同士がすれ違う際に発生するライブロック（livelock）により不完全性が生じるが、IU-LaCAMはLaCAMの探索状態にターゲット割り当て関数を含め、ライブロックを検知した際にターゲットを再割り当てする手法を導入することで、IUMAPFにおける完全性（completeness）を保証している。
本実験では、Intel Core i9-13900H搭載のMini PCを用い、`empty-16-16`、`random-64-64-20`、`lak303d`、`warehouse-10-20-10-2-2`のマップを用いて、ILP手法および構成生成器ベースの手法の評価を行っている。ILP手法（Gurobi使用）は、`empty-16-16`のような単純なマップでは1秒以内に最適解を見つけるが、`random-64-64-20`のような大規模インスタンスではエージェント数 $k$ の増加に伴い成功率が低下し、変数の増加がスケーラビリティの限界となっている。これに対し、提案手法であるIU-LaCAMは、`empty-16-16`で少なくとも $2\times$、`random-64-64-20`では約 $10\times$（例：$k=10$ で $0.056\text{s}$ 対 $0.231\text{s}$）の高速化を実現している。大規模設定における評価では、IU-PIBTは疎な設定では動作するものの、中程度の密度ではライブロックにより解を見つけられない傾向があるが、LaCAMはエージェントの動きを明示的に指定することでこれを解決し、成功率を大幅に向上させている。ただし、狭い通路が多いマップ（`warehouse-10-20-10-2-2`等）では、ライブロック対策による明確な利点は得られていない。また、特殊ケースである $d=2$ のUnlabeled MAPFにおいて、IU-PIBTは既存のTSWAPと比較して、実行時間は同程度でありながら、より柔軟な移動を許容することで、ボトネックマッチングの値を下限とした劣最適性（suboptimality）においてより優れた結果を示している。
本研究では、標準的なラベルなしマルチエージェント経路計画（Unlabeled MAPF）に対し、距離に基づく拡張された衝突定義を導入した IUMAPF を提案・検討している。この拡張により従来の MAPF アルゴリズムは適用不可能となるため、著者らは品質とスケーラビリティの観点から、圧縮を用いた帰着ベースの手法と、構成生成器（configuration generator）に基づく探索という2つのアプローチを提案した。今後の課題として、エージェントの匿名性を効率的に扱うための、ラベルなし変種に特化した探索スキームの開発がオープンな問題として残されている。