本研究が対象とするのは、無向連結グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で動作するエージェント集合 $\mathcal{A}$ によるLifelong MAPD問題である。各タスクはピックアップ地点 $p_j$、デリバリー地点 $d_j$、およびリリース時刻 $r_j$ で定義され、エージェントはタスク完了後に再び自由状態となる。最適化の目的は、タスクのリリースから完了までの平均サービス時間 $S_j = (t_{j, \text{finish}} - r_j)$ を最小化することである。また、実環境の不確実性を考慮し、エージェントが予定された経路を進まずに現在位置に留まる「実行遅延（Delays）」のモデル化も含まれている。
Neural ATTFは、タスク割り当てと経路計画をデカップルした構成により、スケーラビリティ、解の質、計算効率の向上を実現した。第一に、Priority Guided Task Matching (PGTM) により、遅延エージェントを優先しつつタスクへの近接度に基づいた動的な割り当てを可能にした。第二に、Neural STA*を導入することで、時空間ドメインにおける学習済みヒューリスティックを活用し、従来のSTA*と比較して探索ノード数 $iters$ をエージェント数の増加に伴い $10$ から $100$ 倍削減することに成功した。第三に、既存の最先端手法（TPTS, CENTRAL, RMCA, LNS-PBS, LNS-wPBS）と比較して、高いタスク頻度下で平均サービス時間 $st$ を $6\% \sim 33\%$ 改善し、実行時間 $rt$ を平均 $90\%$ 以上削減するという優れた計算効率を示した。
提案手法は、PGTMモジュールとNeural STA*の2段階で構成される。PGTMは、マンハッタン距離を用いた軽量な距離ヒューリスティックに基づき、遅延しているエージェントを優先的にタスクへマッチングさせる。経路計画のNeural STA*は、VGG-16をバックボーンとするU-Net構造のMap Encoderを用いて環境情報をガイダンスマップに変換し、学習ベースのコストマップを利用する。探索においては、到達コスト $g(n)$ と、マンハッタン距離に微小なユークリッド距離を加えたヒューリスティック $h(n)$ を用いる。また、デッドロック回避のために、アイドル状態のエージェントを局所的な空きセルへ移動させるDeadlock Recovery Modeを備えている。
実験では、TPTS, CENTRAL, RMCA, LNS-PBS, LNS-wPBS等の既存手法と比較検証が行われた。Neural STA*の単体評価では、従来のSTA*に対し、平均サービス時間 $st$ を維持しつつ探索ノード数 $iters$ を大幅に削減し、400〜500エージェントの高負荷時において実行時間 $rt$ を大幅に短縮した。スケーラビリティ実験では、200エージェントを超える環境でNeural ATTFが最も優れた $st$ を記録し、RMCAやLNS-PBSが計算量爆発により解を生成できない状況でも安定動作した。さらに、エージェントの実行遅延（$0\%, 1\%, 2\%$）に対する堅牢性評価において、$rt$ は増加するものの $st$ の増加は極めて限定的であることが示された。
Neural ATTFは、LNS系アルゴリズムのような指数関数的な実行時間の増大を回避し、大規模問題において顕著なスケーラビリティを発揮する。小規模なエージェント数においては、エンコーダの推論オーバーヘッドにより改善が限定的となるという限界がある。しかし、大規模環境や不確実性の高い条件下では、再計画コストを効率的に管理することで高い堅牢性とスループットを維持できる。今後の展望として、ロボティクスシミュレータへの展開による現実的な動的シナリオでの評価や、倉庫自動化などの実世界タスクへの適用が挙げられている。
本論文では、Multi-Agent Pickup and Delivery (MAPD) 問題に対し、スケーラビリティと適応性に優れた Neural ATTF (Adaptive Task Token Framework) を提案している。本手法は、Priority Guided Task Matching (PGTM) モジュールと、データ駆動型の経路計画手法である Neural STA* (Space-Time A*) を組み合わせた構成となっている。Neural STA* は、学習されたヒューリスティックを用いることで探索空間の高速な探索を可能にし、動的な制約下での衝突回避を実現する。PGTM は、遅延しているエージェントを優先し、タスクに最も近いエージェントを動的に割り当てることで、システムの継続性とスループットを最適化する。TPTS, CENTRAL, RMCA, LNS-PBS, LNS-wPBS といった既存の最先端アルゴリズムとの比較実験により、Neural ATTF がスケーラビリティ、解の質、および計算効率において優れていることが示されている。
本研究では、タスク割り当てと衝突回避経路計画の双方において計算量的に困難なMulti-Agent Pickup and Delivery (MAPD) 問題に対し、効率性・スケーラビリティ・堅牢性に優れたNeural Adaptive Task Token Framework (Neural ATTF) を提案している。本手法は、タスク割り当てに軽量な距離ヒューリスティックを用いたPriority Guided Task Matching (PGTM) モジュールを、経路計画にはSpace-Time A* の時間的モデリングとNeural A* のデータ駆動型効率性を融合させたNeural STA* を用いるデカップル型アルゴリズムである。PGTMは遅延しているエージェントを優先しつつ、タスクに最も近いエージェントを動的に割り当てることでシステムのスループットを最適化し、Neural STA* は時空間ドメインにおける学習済みヒューリスティックを活用して衝突のない軌道を効率的に計算する。さらに、アイドル状態のエージェントを安全な場所へ再ルーティングするデッドロック回復メカニズムや、実行遅延・不確実性に対応するリアルタイム再計画機能を備えている。広範なシミュレーションの結果、Neural ATTFはTPTS、CENTRAL、HBH-MLA*、RMCA、LNS-PBS、LNS-wPBSといった既存の最先端アルゴリズムと比較して、スケーラビリティと効率性の両面で優れた性能を示すことが確認された。
MAPD（Multi-Agent Pickup and Delivery）問題は、タスク割り当てと経路計画の2つのサブ問題で構成される。タスク割り当てには、二部グラフの最大重みマッチングを解くハンガリアン法や、初期スケジュールを反復的に改善するLarge Neighborhood Search (LNS) などの手法が用いられる。経路計画（MAPF）においては、最適性を保証するConflict-Based Search (CBS) や、計算効率と近似最適性のバランスを取るEnhanced CBS (ECBS)、優先度に基づくPriority-Based Search (PBS) などが提案されている。既存のMAPDアルゴリズムとして、分散型のToken Passing (TP) やその拡張であるTPTS、中央集権的なCENTRAL、タスク割り当てと経路計画を結合したRMCA、さらにLNSとPBSを組み合わせたLNS-PBSや、計算量を削減するために時間窓を用いるLNS-wPBSなどが存在する。本研究で低レベルプランナーとして採用されるNeural A* [11] は、畳み込みエンコーダと微分可能なA*探索を組み合わせたデータ駆動型手法であり、環境マップや始点・終点をガイダンスマップに変換することで、エンドツーエンドの学習を可能にしている。
本セクションでは、無向連結グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上で動作するエージェント集合 $\mathcal{A}$ による、Lifelong Multi-Agent Pickup and Delivery (MAPD) 問題の定式化がなされている。各タスクはピックアップ地点 $p_j$、デリバリー地点 $d_j$、およびリリース時刻 $r_j$ で定義され、エージェントはタスク割り当て後に $p_j$ を経由して $d_j$ へ移動し、完了後に再び自由状態となる。最適化の目的は、タスクのリリースから完了までの平均サービス時間を最小化することであり、タスク $j$ のサービス時間は $S_j = (t_{j, \text{finish}} - r_j)$ と定義される。制約条件として、頂点およびエッジにおける衝突回避、エージェントの移動範囲の制限、タスクの割り当てと実行の整合性、およびエージェントが一度に一つのタスクのみを扱うことなどが数式を用いて厳密に規定されている。また、実環境におけるセンサー誤差や物理的制約に起因する遅延（Delays）を、計画時には予測不可能だが有限な、エージェントが予定された経路を進まずに現在位置に留まる現象としてモデル化している。
Neural ATTFは、タスク割り当てと経路計画の2段階で構成される、スケーラブルで堅牢なマルチエージェント経路計画（MAPD）アルゴリズムである。タスク割り当てには、遅延エージェントを優先し、次にタスク地点への近接度に基づきマンハッタン距離を用いてマッチングを行うPriority Guided Task Matching (PGTM) モジュールが用いられる。経路計画には、VGG-16をバックボーンとするU-Net構造のMap Encoderと、学習ベースのコストマップを利用するNeural Space-Time A*が統合されており、空間と時間の両次元で衝突を回避する。具体的には、エージェントの現在地からタスク開始点、およびタスク開始点からゴール点への2つのガイダンスマップを生成し、それらを基に $g(n)$（到達コスト）と $h(n)$（マンハッタン距離に微小なユークリッド距離を加えたヒューリスティック）を用いて探索を行う。また、従来のアルゴリズムとは異なり、エージェントがゴール地点で待機する制約を緩和し、1タイムステップのみ待機を許容することで、他のエージェントの経路を妨げない設計となっている。デッドロックが発生した場合には、局所的な空きセルへ移動させるDeadlock Recovery Modeを備えており、高密度な環境下でも継続的なタスク実行を可能にしている。
Neural ATTFの実験評価では、提案手法の有効性とスケーラビリティが多角的に検証されている。まず、Neural STA*パスプランナーの評価において、従来のWindowed PBSと比較して、Neural ATTFは500エージェント規模でもリアルタイム性を維持しつつ、wPBSがタイムアウト（80分）する環境下でも高いスループット（$tp$）を達成した。Neural STA*単体の検証では、従来のSTA*と比較して平均サービス時間（$st$）を維持したまま、探索ノード数（$iters$）をエージェント数の増加に伴い $10$ から $100$ 倍削減し、高負荷時（400〜500エージェント）において実行時間（$rt$）を大幅に短縮することを確認した。既存手法（TPTS, CENTRAL, RMCA, LNS-PBS等）との比較では、小規模・大規模倉庫の両環境において、Neural ATTFは高いタスク頻度下で$st$を平均 $6\% \sim 33\%$ 改善し、かつ$rt$を他手法より平均 $90\%$ 以上削減するという優れた計算効率を示した。スケーラビリティ実験では、200エージェント超の環境でNeural ATTFが最も優れた$st$を記録し、RMCAやLNS-PBSが計算量爆発により解を生成できない状況でも安定して動作した。最後に、エージェントの実行遅延（$0\%, 1\%, 2\%$）に対する堅牢性評価では、遅延に伴う再計画コストにより$rt$は増加するものの、$st$の増加は極めて限定的であり、不確実な環境下でも高い性能を維持できることが示された。
Neural ATTFは、サービス時間と計算効率のバランスに優れ、RMCAやLNS-PBS、LNS-wPBSのような指数関数的な実行時間の増大を回避しつつ、多様なシナリオにおいて効率的なスケーラビリティを実現する。HBH-MLA*と比較して、サービス時間の低下を最小限に抑えつつ実用的な実行時間を維持しており、特にNeural STA*を統合することで、エージェント数が多い大規模な問題においてA*の探索反復回数を大幅に削減できる。小規模なエージェント数ではエンコーダの推論オーバーヘッドにより改善が限定的だが、大規模問題ではそのスケーラビリティと適応性が顕著になる。また、遅延確率が高い不確実な条件下でもサービス時間の低下が最小限であり、再計画コストを効率的に管理することで高い堅牢性を示す。今後の展望として、ロボティクスシミュレータへの展開による現実的な動的シナリオでの評価、および倉庫自動化やマルチエージェント協調といった実世界タスクへの適用が挙げられている。