半径 $1$ の円盤としてモデル化される $m$ 個のエージェントが、障害物を含む連続空間 $W \subseteq \mathbb{R}^2$ 内で、個別の目標指定なしに目標地点の集合 $T$ へ衝突を避けながら到達する問題を扱う。従来の連続空間におけるAMAPFアルゴリズムは、アルゴリズムの正当性を保証するために、任意の2つのエージェントの開始・目標位置間の距離を $\|v-v'\|_2 \ge 4$、および開始・目標位置と障害物との距離を $\|v-x\|_2 \ge \sqrt{5}$ とするという非常に厳しい制約を課していた。この制約により、エージェントの密度が高い実世界のシナリオへの適用が困難であった。
先行研究のアルゴリズムが保持していた「すべてのエージェントが衝突することなく最終的に目標を達成する」という理論的性質を損なうことなく、開始・目標位置間の最小分離距離の制約を $4$ から $2\sqrt{3}$ へと緩和した点が新規性である。これにより、従来の制約下では解の存在が保証できなかった、より高密度なエージェント配置においても解を導出することが可能となった。
まず、全エージェント間の最短経路に基づき、総経路長を最小化する目標割り当てを行う。次に、他の経路を妨げない「スタンドアロンな目標」を順次選択してエージェントを移動させる。移動中にエージェント $i$ が目標 $\tau$ への経路を妨げる衝突点 $\gamma_j(t)$ が発生した場合、その衝突点と目標 $\tau$ の距離が $2$ 以上であれば、開始位置から衝突点までの直線と残りの経路を組み合わせた経路を割り当てる。距離が $2$ 未満である場合には、$\|\gamma_j(t') - \tau\|_2 = 2$ を満たす一意な点 $\gamma_j(t')$ を選択し、開始位置から $\gamma_j(t')$ までの直線と、$\gamma_j(t')$ から $\tau$ までの直線で構成される経路を割り当てる。
本研究では、提案手法が緩和された制約条件下においても、エージェントの移動が他のエージェントとの衝突を引き起こさないことを幾何学的な証明を通じて示した。理論的な解析により、制約を $4$ から $2\sqrt{3}$ へ緩和しても、元のアルゴリズムが持つ目標到達性の性質が維持されることが確認されている。
本研究の主な貢献は理論的な制約の緩和と正当性の証明であるが、提案手法の実験的な検証および既存手法との詳細な比較は今後の課題として残されている。また、入力データに対する制約のさらなる緩和についても、今後の検討事項として挙げられている。
本研究は、どのエージェントがどの目標に到達するかを問わない、匿名マルチエージェント経路計画（AMAPF）における制約の緩和を扱っている。既存のMAPFアルゴリズムの多くは格子状の離散空間を前提とし、エージェントの大きさを考慮していないため、倉庫内の移動ロボットのような実世界のシナリオへの適用が困難である。一方で、連続空間で動作する手法は、初期位置・目標位置・障害物間の距離に対して厳しい制約を課す傾向がある。本論文では、エージェントを等しい半径を持つ円盤としてモデル化し、開始・目標位置間にエージェント半径の4倍という厳格な最小分離距離を要求する既存の連続空間AMAPFアルゴリズムに着目している。この制約を $2\sqrt{3}$ まで緩和する修正手法を提案しており、この変更によって、すべてのエージェントが衝突することなく安全に最終的に目標を達成するという元の理論的性質が維持されることを理論的に証明している。
本研究は、エージェントのサイズを考慮した連続空間における匿名マルチエージェント経路探索（AMAPF-LA）において、従来手法が課していた厳格な制約を緩和する手法を提案している。既存のAMAPF-LAアルゴリズムでは、障害物を多角形、エージェントを半径 $1$ の円盤としてモデル化しており、アルゴリズムの正当性を保証するために、任意の2つのエージェントの開始・目標位置間の距離を $4$ 以上、および開始・目標位置と障害物との距離を $\sqrt{5}$ 以上に保つという制約が存在する。本論文では、この第一の制約を $4$ から $2\sqrt{3}$ へと緩和することを提案している。理論的な検証を通じて、この制約緩和を行っても、すべてのエージェントが割り当てられた目標に到達するという元のアルゴリズムの根本的な性質が維持されることを証明している。
マルチエージェント経路計画（MAPF）は、各エージェントに特定の目標が割り当てられる古典的な定式化と、目標の割り当てが限定されない匿名マルチエージェント経路計画（AMAPF）に分類される。エージェントの物理的なサイズを考慮する場合、(Anonymous) Multi-Agent Path Finding for Large Agents と呼ばれ、古典的な MAPF において特定の目標への到達を保証する最適解の探索は NP困難であることが示されている。AMAPF において、メイクスパンを指標とした場合にはグラフにおける最大流アルゴリズムを用いることで多項式時間での最適解の導出が可能であるが、大規模な問題への直接的な適用は困難である。既存の AMAPF アルゴリズムには、連続空間で動作するものの障害物やエージェントのサイズを無視するものや、障害物の構造に特殊な制約を課すもの、あるいは開始地点と目標地点の距離に制限を設けるものなどが存在する。また、強化学習や模倣学習を用いた学習ベースの手法も提案されているが、これらは経験的な性能は有望であるものの、安全性や目標到達性に関する理論的な保証を欠いているという限界がある。
共通の作業空間 $W \subseteq \mathbb{R}^2$ において、半径 $1$ の開円盤として表される $m$ 個のエージェントの集合 $M = \{1, 2, \dots, m\}$ を考える。各エージェントの状態は円盤の中心位置で定義され、初期位置の集合 $S = \{s_1, \dots, s_m\}$ と目標地点の集合 $T = \{\tau_1, \dots, \tau_m\}$ が与えられる。障害物領域を $O \subset W$ とすると、エージェントが障害物と衝突しない自由空間 $F$ は、中心位置 $p$ に対して半径 $1$ の開円盤 $B_1(p)$ が $O$ と交わらない条件 $F = \{x \in W \setminus O \mid B_1(x) \cap O = \emptyset\}$ によって定義される。各エージェントの経路 $\pi_i$ は連続時間 $T = \mathbb{R}^+ \cup \{0\}$ 上の連続写像であり、すべての経路の集合 $\Pi = \{\pi_1, \dots, \pi_m\}$ が解となるためには、任意の時刻 $t \in T$ においてエージェント同士が衝突しない条件 $\nexists t \in T : B_1(\pi_i(t)) \cap B_1(\pi_j(t)) \neq \emptyset$ を満たし、かつ各経路が初期位置 $s_i$ から開始して目標地点の集合 $T$ のいずれか一意の点に到達する必要がある。本問題のコストは各経路の長さの総和 $\sum_{i=1}^{m} |\pi_i|$ として定義されるが、本研究ではコストの最適化を必須条件とはせず、より低いコストを持つ解を優先的に扱う。
本手法は、大規模なエージェントを扱う匿名マルチエージェント経路探索（Anonymous MAPF）において、従来のアルゴリズムが課していた初期配置および目標配置に関する制約を緩和するものである。ベースとなるアルゴリズムは、まず全エージェント間の最短経路を計算してハンガリー法等で総経路長を最小化する目標割り当てを行い、次に他の経路を妨げない「スタンドアロンな目標」 $\tau$ を順次選択してエージェントを移動させる。従来のアルゴリズムでは、開始位置または目標位置間の距離が $\|v-v'\|_2 \ge 4$、および障害物との距離が $\|v-x\|_2 \ge \sqrt{5}$ であることが要求されていた。提案手法では、衝突を回避するエージェント $i$ が目標 $\tau$ への経路を妨げている場合、その衝突点 $\gamma_j(t)$ と $\tau$ の距離が $2$ 以上であれば、開始位置から衝突点までの直線と残りの経路を組み合わせた経路を割り当てる。一方で、距離が $2$ 未満である場合には、$\|\gamma_j(t') - \tau\|_2 = 2$ を満たす一意な点 $\gamma_j(t')$ を選択し、開始位置から $\gamma_j(t')$ までの直線と、$\gamma_j(t')$ から $\tau$ までの直線で構成される経路を割り当てる。理論的解析により、この緩和された条件下においても、エージェントの移動が他のエージェントとの衝突を引き起こさないことが幾何学的な証明（Lemma 2, 4等）を通じて示されている。
本研究では、エージェントの個体識別を必要とせず、初期位置から目標位置の集合へ衝突のない経路を構築する、匿名マルチエージェント経路計画（Anonymous Multi-Agent Path Finding）におけるエージェントのサイズを考慮した問題を扱っている。先行研究で提案された、平面上でエージェントの大きさを考慮しつつ解を求めるアルゴリズムは、初期位置と目標位置の相対的な配置に対して特定の制約を課していた。本論文では、元のアルゴリズムが持つ理論的特性を維持したまま、これらの制約を $13\%$ 緩和する修正手法を提案している。この緩和により、エージェントの密度が高い問題において解を見つけやすくなり、元のアルゴリズムでは制約により適用不可能であったケースにおいても、提案手法は解を導出できることが示された。今後の課題として、提案手法の実験的な検証および既存手法との比較、さらには入力データに対する制約のさらなる緩和が挙げられている。