本研究は、エージェントが動的にリリースされるタスクを順次処理するMulti-Agent Pickup and Delivery (MAPD) 問題、および各タスクが複数の目標地点を持つMulti-Goal MAPD (MG-MAPD) 問題を対象とする。タスクにはリリース時刻 $r_\tau$ と、一連の目標地点（ピックアップ地点およびデリバリー地点）が設定されている。既存手法の多くはタスク割り当てと経路計画を分離しているが、経路コストの推定精度やスケーラビリティに課題があった。本研究では、タスクの割り当て（どのエージェントがどの順序でタスクをこなすか）と、衝突のない経路計画（どのように移動するか）を効率的に統合する枠組みを構築している。
第一に、well-formedなMAPDインスタンスにおいて完全性を保証する $LNS\text{-}PBS$ を提案し、既存の完全解法である CENTRAL よりも高い性能を示すことを明らかにした。第二に、実用的な大規模環境向けに、windowed PBS を採用した $LNS\text{-}wPBS$ を提案し、数千のエージェントとタスクを扱うスケーラビリティと、既存の HBH+MLA* を上回るサービス時間の短縮を実現した。第三に、タスクが複数の目標地点を持つ MG-MAPD への拡張性と、将来のタスクを一部把握できるセミオンライン設定への適用可能性を示した。さらに、実行時間の分散が小さい安定したアルゴリズムであることを実証した。
提案手法は、LNS によるタスクシーケンスの最適化と、PBS による衝突回避経路計画の二段階で構成される。LNS プロセスでは、Hungarian algorithm による初期割り当て後、Shaw removal によるタスク削除と Regret-based re-insertion による再挿入を繰り返し、推定サービス時間を最小化する。経路計画では、PBS を拡張し、高優先度エージェントの新しいパスと、低優先度エージェントの既存パス（old paths）の両方を回避する探索を行う。$LNS\text{-}wPBS$ では、計算負荷を抑えるために windowed PBS (wPBS) を採用し、最初の $w$ ステップのみを計画するが、これにより完全性は失われる。また、セミオンライン設定では look-ahead horizon を導入し、事前に把握可能なタスクバッチを利用してエージェントの事前配置を行う。
4近傍グリッドマップを用いた倉庫環境（small, medium, large）において、CENTRAL, RMCA, HBH+MLA* と比較実験を行った。実験の結果、$LNS\text{-}wPBS$ は medium 環境で 10% 以上、large 環境でも継続的なサービス時間の改善を示し、HBH+MLA* を上回る性能を達成した。また、タイムステップあたりの実行時間 $rt$ の分散が小さく、高い安定性を示した。タスク割り当ての比較では、greedy-LNS よりも Hungarian 法を用いた LNS が優れた結果となった。ルックアヘッド・ホライゾン $LA$ に関しては、$LA=5$ まではサービス時間の短縮に寄与するが、それ以上に拡大するとタスクシーケンスの長期化により逆にサービス時間が増加する傾向が確認された。
提案手法は、大規模な倉庫環境において数千のエージェントとタスクを扱うことが可能であり、実用的なスケーラビリティを備えている。$LNS\text{-}PBS$ は well-formed な設定において完全性を維持できる点が強みであるが、$LNS\text{-}wPBS$ は効率性と安定性を優先した設計となっている。今後の課題として、現在の推定コストではなく、実際の経路コストに基づいたより精緻なタスク割り当てへの改善が挙げられる。また、理論的なシミュレーションから、より現実的なロボットの挙動を反映したロボットシミュレータを用いた検証への移行が必要である。
本研究では、エージェントが継続的に新しいタスク（ピックアップ地点とデリバリー地点のペア）を受け取り、衝突のない経路を計画する必要がある Multi-Agent Pickup-and-Delivery (MAPD) 問題を扱う。提案手法は、Large Neighborhood Search (LNS) を用いて各エージェントにタスクのシーケンスを割り当て、Priority-Based Search (PBS) を用いて経路計画を行う LNS-PBS と、その効率化版である LNS-wPBS の2つのバリアントで構成される。LNS-PBS は、現実的なサブクラスである well-formed MAPD インスタンスに対して完全性を持ち、既存の完全解法である CENTRAL よりも高い性能を示す。一方、完全性の保証はないものの、LNS-wPBS は LNS-PBS よりも効率的かつ安定しており、大規模な倉庫環境において数千のエージェントと数千のタスクを扱うスケーラビリティを備え、既存のスケーラブルな手法である HBH+MLA* を上回る性能を示す。さらに、これらの手法は、タスクごとに目標地点の数が異なるより一般的な Multi-Goal MAPD (MG-MAPD) 問題にも適用可能である。
本研究は、各タスクがリリース時刻と一連の目標地点（ピックアップ地点およびデリバリー地点）を持つMulti-Agent Pickup and Delivery (MAPD) 問題を対象としている。既存手法の多くはタスク割り当てと経路計画を分離しており、一度に一つのタスクのみを割り当てる手法や、経路をセグメントごとに計画する手法が存在するが、これらはタスク割り当ての質や経路の効率性に課題がある。提案手法は、anytimeアルゴリズムであるLarge Neighborhood Search (LNS) を用いてエージェントにタスク列を割り当て、Priority-Based Search (PBS) を用いて一連の目標地点を通る経路を計画する分離型アルゴリズムであり、完備性と効率性に焦点を当てた $LNS\text{-}PBS$ と $LNS\text{-}wPBS$ の2つのバリアントを提案している。$LNS\text{-}PBS$ は「dummy paths」の概念を導入することで、well-formedなMAPDインスタンスにおいて完備性を保証し、$LNS\text{-}wPBS$ はRHCRのwindowed MAPFを採用することで、ユーザー指定の実行時間制限やウィンドウサイズに基づいた高いスケーラビリティを実現している。実験の結果、提案手法は既存のMAPDアルゴリズムよりもサービス時間が短縮される傾向にあり、$LNS\text{-}wPBS$ は大規模な倉庫環境において数千のエージェントとタスクを扱うことが可能である。さらに、本研究はタスクが複数の目標地点を持つMulti-Goal MAPD (MG-MAPD) への拡張や、オンライン、オフライン、および新たに定義したセミオンライン設定への適用についても検討している。
MAPD（Multi-Agent Pickup and Delivery）問題は、タスク割り当てと経路計画の2つの要素で構成される。タスク割り当てに関しては、二部グラフの最大重みマッチングを多項式時間で解く Hungarian algorithm や、VRP（Vehicle Routing Problem）のスケジューリングに用いられる Large Neighborhood Search (LNS) などの組合せ最適化手法が関連している。経路計画については、完全かつ最適解を保証する Conflict-Based Search (CBS) やその改良版の ICBS、効率的だが優先順位に基づき不完全性を持つ prioritized planning、さらに優先順位の探索を行う Priority-Based Search (PBS) や、ピックアップ・デリバリー地点間の経路を扱う Multi-Label A* (MLA*) が存在する。既存の MAPD アルゴリズムは、タスク割り当てと経路計画を分離して解く手法（CENTRAL, TA-Hybrid, HBH など）が主流であるが、これらは経路コストの推定値に基づいてタスクを割り当てる。これに対し、RMCA はタスク割り当てと経路計画を同時に行う結合型（coupled）の手法であり、LNS を用いてタスクシーケンスを決定し、prioritized planning と sequential A* を用いて衝突のない経路を計画することで、実際の経路コストをタスク割り当てに反映させている。
本セクションでは、従来のMAPDを一般化したMulti-Goal MAPD (MG-MAPD) 問題を定義している。MG-MAPDは、エージェントの集合と無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ で構成され、各タスク $\tau$ は一連のゴール地点のシーケンスとリリース時刻 $r_\tau$ を持ち、エージェントはこれらを順に訪問する必要がある。衝突条件として、時刻 $t$ における頂点衝突（$x_i(t) = x_j(t)$）およびエッジ衝突（$\{x_i(t), x_i(t+1)\} = \{x_j(t), x_j(t+1)\}$）が定義されている。本研究では、エージェントの開始地点がタスクのゴール地点と重複せず、任意の2つのエンドポイント間に他のエンドポイントを経由しないパスが存在するという「well-formed」なインスタンスを対象とする。問題の目的は、タスクの割り当てと衝突のない経路計画を行い、タスクの完了時刻とリリース時刻の差であるサービス時間の平均を最小化することである。また、アルゴリズムの評価指標として、タイムステップあたりの平均実行時間（効率性）および実行時間の予測可能性（安定性）が用いられる。
LNS-PBSおよびLNS-wPBSは、Multi-Goal Multi-Agent Pickup and Delivery (MG-MAPD) 問題を解くための手法であり、各エージェントはダミー・エンドポイント、タスク列、ゴール列、および衝突のないパスを保持する。LNS（Large Neighborhood Search）を用いて未実行タスク $\mathcal{T}_{un}$ をエージェントに再割り当てし、ハンガリアン法による初期割り当て、Shaw removalによる関連タスクの削除、およびRegret-based re-insertionによる再挿入のプロセスを経て、推定サービス時間を最小化する。パス計画にはPBS（Priority-Based Search）を拡張した手法を用い、各エージェントが以前のパス（old paths）を回避しながら新しいゴール列を巡回できるよう設計することで、well-formedなインスタンスにおける完全性（completeness）を保証している。具体的には、PBSの低レベル計画において、高優先度エージェントの新しいパスと、それ以外の全エージェントの旧パスを回避する経路を探索する。一方、LNS-wPBSは、計算効率向上のためにwindowed PBS（wPBS）を採用しており、最初の $w$ ステップのみを計画して再計画を繰り返すが、旧パスの考慮やタスクの保留を行わないため、完全性は失われている。
本セクションでは、将来のタスクを部分的に把握できるセミオンライン設定における「look-ahead horizon」を定義している。タスクはバッチ単位でリリースされ、look-ahead horizon は事前に把握可能なバッチの数を指し、オフライン設定ではこの値は無限大となる。例えば、5タイムステップごとにタスクがリリースされる環境で horizon が 1 の場合、タイムステップ 0 において、時刻 0 と時刻 5 にリリースされるタスクの両方が既知となる。この先行知識を利用することで、エージェントをタスクのリリース前にあらかじめ目的地へ移動させて待機させることが可能となり、タスク完了時間の短縮が期待できる。具体例として、タスクが時刻 0 と 2 にリリースされる場合、horizon が 0 では平均サービス時間が $\frac{5+11}{2} = 8$ となるのに対し、horizon が 1 であればエージェントを事前に配置することで平均サービス時間を $\frac{4+8}{2} = 6$ まで削減できることが示されている。
本実験では、提案手法であるLNS-PBSおよびLNS-wPBSを、既存のMAPDアルゴリズム（CENTRAL, RMCA, HBH+MLA*）と比較し、オンライン、オフライン、およびセミオンライン設定での性能を評価している。実験環境は、4近傍グリッドマップからなる倉庫環境（small, medium, largeの3サイズ）を用い、MG-MAPDインスタンスでは各タスクのゴール地点を1〜5個の範囲でランダムに設定している。LNS-wPBSは、small環境のオンライン設定ではRMCAと混合的な結果となったが、mediumおよびlarge環境では、HBH+MLA*よりも実行時間は長いものの、サービス時間（$st$）において常に優位性（例：mediumで$10\%$以上、largeでも継続的な改善）を示した。また、LNS-wPBSはLNS-PBSやCENTRALと比較して、タイムステップごとの実行時間（$rt$）の分散が小さく、より安定した動作を実現している。タスク割り当てアルゴリズムの比較では、Hungarian法に基づく挿入法を用いたLNSが、greedy heuristicを用いたgreedy-LNSよりも優れたサービス時間を達成した。さらに、ルックアヘッド・ホライゾン（$LA$）の影響については、$LA=5$まではサービス時間の短縮に寄与するものの、それ以上に拡大すると、タスクシーケンスの長期化や頻繁な変更により、逆にサービス時間が増加する傾向が確認された。
本研究では、エージェントへのタスクシーケンスの割り当てと、目標地点のシーケンスに基づく衝突回避経路計画を分離して行う、2つのデカップリング型MAPDアルゴリズムを提案している。第1のバリアントである LNS-PBS は、well-formed な MAPD インスタンスに対して完全性（completeness）を持ち、第2の LNS-wPBS はより高い効率性と安定性を備えている。実験の結果、両手法とも既存の最先端 MAPD アルゴリズムと比較してサービス時間を短縮しており、特に LNS-wPBS は大規模な倉庫環境において数千のタスクと 1,000 エージェント規模までスケール可能であることが示された。本手法は、タスクごとに目標地点の数が異なる Multi-Goal MAPD へと拡張可能であり、近未来のタスクが既知であるセミオンライン設定にも対応している。今後の課題として、実際の経路コストに基づいたタスク割り当てへの改善や、実機ロボットへの適用を見据えたより現実的なロボットシミュレータを用いた検証が挙げられている。