$L \times L$ の2次元グリッド上で、$m$ 台のエージェントが次々と発生するタスク集合 $\mathcal{T}$ を処理するMulti-Agent Pickup and Delivery (MAPD) 問題を対象とする。各タスクはピックアップ地点 $s_j$ とデリバリー地点 $g_j$ を持つ。従来のMAPFを繰り返す手法では、エージェントの動きを離散的な移動と仮定するため、連続的な速度や旋回といった実環境の運動学的制約を考慮した最適解を得ることが困難である。
離散的なセルと時刻のペアを扱う従来の時空間 $A^*$ に代わり、セルと安全な時間間隔のペアを扱うSIPPの概念を拡張し、運動学的制約を直接組み込んだTP-SIPPwRTを提案する。また、動的な障害物による安全な時間間隔を効率的に管理するために、予約テーブル（reservation table）という新しいデータ構造を導入した。これにより、従来のSIPPにおける計算コストの課題を解決し、連続的な前進移動および旋回を考慮した経路計画を実現している。
各エージェントが共有メモリ上のトークンを用いてタスクを貪欲に割り当て、他のエージェントを動的障害物と見なして経路を計画する。エージェントは半径 $L/2$ 以下のディスクとしてモデル化され、指定された回転速度による $\pi/2$ rad の点旋回、および指定された並進速度による隣接セルへの前進移動というアクションを選択する。予約テーブルでは、各セルのエントリを、そのセルを占有する動的障害物の最大連続区間を下限値の昇順で保持する優先度付きキューとして構成する。この構造を用いて、安全な時間間隔の算出、予約エントリの追加、および不要なエントリの削除を効率的に行う。
2.50 GHz Intel Core i5-2450Mおよび6 GB RAMの環境において、最大250エージェントおよび2,000タスクの条件下で評価を行った。その結果、TP-SIPPwRTの計画時間は16秒未満であった。また、モデル化されていない運動学的制約や運動ノイズが存在するロボットシミュレータを用いた実験においても、すべてのロボットが計画された経路を安全に追従できることが確認された。
本手法は、指定された速度に基づく連続的な前進移動および旋回を計算するが、ロボットシミュレータにおけるモデル化されていない運動学的制約やノイズが存在する場合でも、安全な追従が可能であることを示している。今後の課題として、より複雑な運動特性や、さらなる大規模なタスク環境への適応が考えられる。
Multi-Agent Pickup and Delivery (MAPD) 問題は、$L \times L$ のサイズを持つ 2 次元 4 近傍グリッド上で、$m$ 台のエージェントが次々と発生するタスク集合 $\mathcal{T}$ を処理する問題であり、各タスク $\tau_j$ はピックアップ地点 $s_j$ とデリバリー地点 $g_j$ を持ちます。従来の MAPD アルゴリズムは、エージェントの動きを離散的な移動と仮定して衝突のない経路を計算する Multi-Agent Pathfinding (MAPF) を繰り返し解く手法が一般的ですが、これは最適解を求めることが NP 困難な問題です。本研究では、離散的な移動を前提とする Token Passing (TP) アルゴリズムを拡張し、後処理として連続的な速度を用いた移動を適応させる手法に代わり、TP と Safe Interval Path Planning with Reservation Table (SIPPwRT) を組み合わせた新しいアルゴリズム TP-SIPPwRT を提案します。この手法は、与えられた速度に基づく連続的な前進移動および旋回を直接計算し、エージェント間の安全距離を保証しながら、自動倉庫などの実環境をモデル化した well-formed な MAPD インスタンスのすべてを解くことが可能です。
TP手法は、各エージェントが共有メモリ上のトークンを用いてタスク集合 $\mathcal{T}$ からタスク $\tau_j$ を貪欲に割り当て、他のエージェントの経路を動的障害物と見なして時空間 $A^*$ を用いて衝突回避経路を計画する手法である。本研究では、この時空間 $A^*$ を、与えられた速度に基づき連続的な前進移動と点旋回を計算する SIPPwRT に置き換えることを提案している。エージェントは半径 $L/2$ 以下のディスクとしてモデル化され、待機以外に、指定された回転速度による $\pi/2$ rad の点旋回、および指定された並進速度による隣接する空きセルへの前進移動というアクションを選択する。従来の時空間 $A^*$ がセルと離散的な時刻のペアを扱うのに対し、SIPP はセルと安全な時間間隔（あるセルが占有されていない連続した時刻の範囲）のペアを扱う。SIPPwRT は、この安全な時間間隔の概念を拡張し、エージェントの運動学的制約を考慮しながら経路を計算する。
SIPPwRTは、動的な障害物による安全な時間間隔（safe interval）を効率的に扱うために、予約テーブル（reservation table）という新しいデータ構造を導入した手法である。この予約テーブルにおいて、各セルのエントリは、そのセルを占有する動的障害物の最大連続区間を、下限値の昇順で保持する優先度付きキューとして構成される。この構造により、特定のセルの全安全間隔の算出、新しい経路計算後の予約エントリの追加、および過去の無関係なエントリの削除が効率的に行えるようになり、従来のSIPPにおける計算コストの課題を解決している。実験では、2.50 GHz Intel Core i5-2450Mおよび6 GB RAMの環境において、エージェントシミュレータを用いた評価が行われ、最大250エージェントおよび2,000タスクの条件下で、TP-SIPPwRTの計画時間が16秒未満であることが示された。また、モデル化されていない運動学的制約や運動ノイズが存在するロボットシミュレータにおいても、すべてのロボットが経路を安全に追従できることが確認されている。