自動倉庫などの実世界をモデル化した、オンラインかつライフロングなMAPD問題を対象とする。無向グラフ上のエージェントが、随時発生するタスクのピックアップ地点 $p_i$ からデリバリー地点 $d_i$ まで、他エージェントとの衝突を避けながら移動し、タスクを順次実行する必要がある。従来のMAPF（マルチエージェント経路探索）は一度きりのタスク完了を前提としており、継続的なタスク流入やリアルタイムな割り当て・経路計画を同時に行うことには困難が伴う。
既存の分散型手法がデッドロックを引き起こす可能性があったのに対し、本研究は現実的なサブクラスであるwell-formedなMAPDインスタンスのすべてを解けることを理論的に証明した。提案するTPおよびTPTSは、中央集権的な手法に匹敵するタスク完了性能を持ちながら、分散的な動作を可能にする。特にTPTSは、タスクの奪取（Swap）という概念を導入することで、分散型の枠組みでありながら中央集権的な手法に近い効率性を実現している。
提案手法は、同期された共有メモリであるトークンを用いてエージェントが順次経路を更新するデカップリング型アルゴリズムである。TPでは、エージェントは他のエージェントの経路終点と衝突しないタスクを選択して最小コスト経路を計算し、タスクがない場合はデッドロック回避のために特定の待機場所へ移動する。TPTSは、タスクセットに未実行の全タスクを含めることで、より早くピックアップ地点に到達できるエージェントが既存の割り当てを奪取するプロセスを導入している。奪われたエージェントにはトークンが返され、新しいタスクが再割り当てされる再帰的な処理が行われる。
50エージェントを用いた倉庫シミュレーションにおいて、TP、TPTS、および中央集権的なCENTRALを比較した。評価指標としてサービスタイムと実行時間を用い、タスク頻度やエージェント数を変化させて検証した。結果、サービスタイムの短さではCENTRALが最も優れ、次いでTPTS、TPの順となったが、TPTSはTPと比較して最大で約42%の短縮を実現した。実行時間については、TPが10ms未満と最も高速で、TPTSは200ms未満、CENTRALは4,000ms未満であった。また、500エージェント規模の実験では、TPのみが200エージェント時でも500ms未満の実行時間を維持し、リアルタイムな運用が可能であることが示された。
TPTSはCENTRALに近い性能を示すが、特定の条件下ではTPの方が効果的になる場合があり、常に優位とは限らない。また、TPTSが安定して動作するためには、タスク頻度に応じて適切なエージェント数（例：1 task per timestepでは10〜20体）が必要となる。CENTRALやTPTSは大規模環境においてリアルタイムな運用が困難になるという計算コストのトレードオフが存在する。今後の課題として、TPのような高いリアルタイム性を維持しつつ、いかにしてタスク完了性能を向上させるかが挙げられる。
本研究では、自動倉庫などの実世界における継続的なタスク発生をモデル化した、オンライン設定でのマルチエージェント・ピックアップ・アンド・デリバリー（MAPD）問題を扱う。MAPD問題では、エージェントは次々と発生する配送タスクに対し、衝突を回避しながら指定されたピックアップ地点からデリバリー地点まで移動し、各タスクに一人のエージェントを割り当てる必要がある。提案手法として、デカップリングされた2つのアルゴリズムであるToken Passing（TP）と、Task Swapsを導入したToken Passing with Task Swaps（TPTS）を提示する。理論的には、これら2つの手法が現実的なサブクラスであるwell-formedなMAPDインスタンスのすべてを解けることを証明している。実験ではシミュレーション環境を用いた倉庫システムにおいて、中央集権的な手法と比較しており、TPは数百規模のエージェントやタスクに対してもリアルタイム性に優れた効率性を持つ一方、TPTSは限定的な通信によってTPと中央集権的手法のバランスを維持することが示されている。
本研究では、従来のマルチエージェント経路探索（MAPF）が扱う「一度きりのタスク完了」という制約を超え、継続的に新しいタスクが発生する実世界（倉庫ロボットや空港の牽引車など）の状況をモデル化した、Lifelongなマルチエージェント・ピックアップ＆デリバリー（MAPD）問題を扱う。MAPD問題は、無向グラフとしてモデル化された既知の共通環境において、エージェントが外部から随時発生するタスク（ピックアップ地点とデリバリー地点のペアで定義される）を、他エージェントとの衝突を避けながら順次実行していく問題である。提案手法として、既存のMAPFアルゴリズムを基盤とした、分散型の2つのアルゴリズムであるToken Passing（TP）およびToken Passing with Task Swaps（TPTS）を提示する。理論的な解析により、これらの手法は、現実的なタスクのサブクラスであるwell-formedなMAPDインスタンスのすべてを解けることが示されている。実験では、シミュレーション上の倉庫システムにおいて、これらの手法を、解の保証を持たない中央集権的な比較対象のアルゴリズムと比較評価している。
MAPD（Multi-Agent Pickup and Delivery）問題は、オンラインかつライフロングな設定において、エージェントへのタスク割り当てと衝突のない経路計画を同時に行う必要がある。ライフロングな設定では、エージェントはタスク完了後に目的地で待機するのではなく、継続的に流入するタスクに対応し続けなければならず、オンラインな設定ではタスクが随時発生するため、実行中にリアルタイムで割り当てと経路計画を行うことが求められる。既存研究では、分散型のタスク割り当てや、ORCAのような反応型手法、優先度ベースの手法による分散型経路計画が個別に研究されてきたが、これらはデッドロックを引き起こす可能性がある。また、MAPF（Multi-Agent Path Finding）はMAPDのワンショット版として研究されており、全エージェントの移動完了までの総ステップ数であるフロータイムの最小化はNP困難であり、全エージェントが目的地に到達する時刻であるメイクスパンの最小化についても、4/3未満の定数近似がNP困難であることが示されている。MAPFの最適解を得る手法には、Conflict-Based Searchや$M^*$、Enhanced Partial Expansion A*などがあり、非最適解を得る手法としてはWindowed-Hierarchical Cooperative A*やTASSなどが存在するが、これらはいずれもワンショットの設定に基づいている。
MAPD（Multi-Agent Pickup and Delivery）問題は、無向連結グラフ上のエージェントが、タスク集合に含まれる各タスクのピックアップ地点 $p_i$ からデリバリー地点 $d_i$ まで移動する問題である。エージェント $a$ の時刻 $t$ における位置を $L_a(t)$ とすると、エージェントは現在の位置に留まるか隣接する位置へ移動でき、衝突回避条件として、同一時刻における同一地点への滞在 $L_a(t) = L_b(t)$ および、同一エッジを逆方向に移動する $\left(L_a(t), L_a(t+1)\right) = \left(L_b(t+1), L_b(t)\right)$ が禁止される。タスクは、タスク集合に追加されてから完了するまでの平均タイムステップ数であるサービスタイムの最小化を目的とし、すべてのタスクのサービスタイムが有界であることがアルゴリズムの解法条件となる。本研究では、問題の解可能性を保証する「well-formed」なインスタンスを定義しており、これは(a)タスク数が有限であること、(b)非タスク・エンドポイントの集合 $\mathcal{E}_{\text{non-task}}$ の要素数がエージェント数以上であること、(c)任意の2つのエンドポイント間において、他のエンドポイントを経由しないパスが存在すること、の3条件を満たす。エンドポイントとは、エージェントの初期位置、タスクのピックアップ・デリバリー地点、および追加の待機場所を含む集合であり、エージェントが他の経路を妨げずに待機できる場所として機能する。
本セクションでは、各エージェントが自律的にタスク割り当てと衝突回避経路計画を行う、デカップル型MAPDアルゴリズムであるToken Passing (TP) と、その改良版であるToken Passing with Task Swaps (TPTS) を提案している。TPは、同期された共有メモリであるトークンを用いて、エージェントが順次経路を更新する手法であり、エージェントはタスクセットから、他のエージェントの経路の終点と衝突しないタスクを選択して、Path1を用いてピックアップ地点からデリバリー地点への最小コスト経路を計算する。タスクが割り当てられない場合、デッドロック回避のためにPath2を用いて、タスクのデリバリー地点以外の終点へ移動する経路を計算する。TPTSは、タスクセットに「未実行の全タスク」を含めることで、既に他のエージェントが割り当てられているタスクであっても、より早くピックアップ地点に到達できるエージェントがタスクを奪取（Swap）することを可能にしている。このタスクの奪取プロセスでは、奪われた側のエージェントにトークンを返し、新しいタスクを割り当て直す再帰的な処理が行われる。TPTSはTPよりも効率的であることが期待されるが、特定の条件下ではTPの方が効果的になる場合もあり、必ずしも常に優位であるとは限らない。
CENTRALは、提案手法である分散型アルゴリズムの性能を評価するための比較対象として設計された、中央集権的なMAPD（Multi-Agent Pickup and Delivery）アルゴリズムである。各タイムステップにおいて、まずエージェントへの目的地割り当てを行い、次にConflict-Based Searchを用いて全エージェントの衝突のない経路を同時に計画する。目的地割り当てでは、まず未実行タスクの集合から、実行済みタスクの配送先や他の未実行タスクの地点と重複しないタスクの集合 $\mathcal{T}$ を貪欲に抽出する。次に、空きエージェントに対して、ハンガリー法を用いて、タスクのピックアップ地点または待機場所（parking location）を割り当てる。この際、コスト関数 $c'(a, e)$ は、ピックアップ地点への割り当てを優先し、かつ近い地点への割り当てを重視するように、十分大きな定数 $M$ を用いて以下のように修正される。
$$
c'(a, e) =
\begin{cases}
c(a, e) & \text{if } e \text{ is a pickup location of a task in } \mathcal{T} \\
c(a, e) + M & \text{if } e \text{ is a parking location}
\end{cases}
$$
経路計画の効率化のため、まず新たにタスクに従事するエージェントの経路を、他のエージェントの既存経路を時空間障害物として扱いながら計画し、その後に空きエージェントの経路を計画するという2段階の手法が採られている。このアルゴリズムは、定義に基づき、well-formedなMAPDインスタンスにおいて、全エージェントが目的地に到達するための衝突のない経路を必ず生成できることが保証されている。
50エージェントを用いた小規模な倉庫環境において、TP、TPTS、CENTRALの3つのMAPDアルゴリズムを比較する実験が行われた。実験では、タスク頻度を0.2から10の6段階、エージェント数を10から50の5段階で変化させ、500個の配送タスクを生成して評価した。結果として、サービス時間（Service Time）の短さではCENTRALが最も優れ、次いでTPTS、TPの順となり、TPTSはTPと比較して最大で約42%短いサービス時間を実現した。一方で、タイムステップあたりの実行時間（Runtime per Timestep）については、TPが10ms未満と最も高速であり、TPTSは200ms未満、CENTRALは4,000ms未満であったが、TPTSとCENTRALは一部の条件下でTPより2桁大きい実行時間を要した。タスク頻度が1 task per timestepの場合、TPTSにおいて安定した運用を行うには10から20体のエージェントが必要であることが示された。さらに、500エージェント規模の大規模環境におけるスケーラビリティの評価では、TPTSとCENTRALはリアルタイムな運用が困難であったのに対し、TPは200エージェント時でも実行時間が500ms未満であり、リアルタイムなライフロング運用が可能であることが確認された。
本研究では、エージェントが継続的に発生する配送タスクに対し、衝突を回避しながらピックアップ地点から配送地点へと移動する、オンライン設定のマルチエージェント・ピックアップ＆デリバリー（MAPD）問題を扱っている。提案手法として、デカップリングされた2つのアルゴリズムである Token Passing (TP) と Token Passing with Task Swaps (TPTS) を提示し、これらがすべての適切に構成された MAPD インスタンスを解けることを理論的に示した。シミュレーション環境の倉庫システムを用いた実験では、中央集権的な手法である CENTRAL と比較して、メイクスパンおよびサービス時間の短縮において TPTS が TP よりも優れており、中央集権的な手法に次ぐ性能を示すことが確認された。一方で、タイムステップあたりの実行時間については、TP が最も高速であり、次いで TPTS、CENTRAL の順となっている。TP は数百規模のエージェントやタスクに対しても効率的であり、リアルタイム性が最優先される場合の完全分散型アルゴリズムへの拡張に適している。TPTS はエージェント間での限定的な通信を必要とするが、TP の計算効率と CENTRAL の性能のバランスを良好に保つ特性を持つ。