本研究は、タスク割り当てと衝突回避経路計画を組み合わせたMAPD問題に、エージェントが一時停止する「遅延」を導入した MAPD with delays (MAPD-d) を扱う。従来のMAPDは動的なタスク投入を想定しているが、本研究では実行中にエージェントが現在の頂点に留まることで経路が妨げられる不確実性をモデル化している。遅延は時刻 $t$ における集合 $\mathcal{D}_t$ で表され、問題の整合性を保つため、エージェントが無限に遅延することはないという条件 $\forall a, \forall t, \exists t' > t \text{ s.t. } a \notin \mathcal{D}_{t'}$ が課される。既存の分散型手法である Token Passing (TP) をベースラインとし、遅延による衝突を検知してから再計画を行う手法と比較を行う。
決定論的な堅牢性（$\delta$-robustness）を保証する $\delta\text{-TP}$ と、確率的な堅牢性（$\epsilon$-robustness）を保証する $\epsilon\text{-TP}$ という2つの新しいアルゴリズムを提案した。$\delta\text{-TP}$ は、最大 $\delta$ ステップの連続遅延が発生しても衝突を回避する $\delta\text{-extension}$ 制約を経路計画に組み込む。一方、$\epsilon\text{-TP}$ は、遅延をマルコフ連鎖モデルとして扱い、衝突確率を閾値 $\epsilon$ 以下に抑える計画を行う。これらの手法により、オンラインでの再計画（replanning）の頻度を大幅に削減しつつ、実用的な解のコストを維持できることを示した。
$\delta\text{-TP}$ では、エージェント $i$ の経路 $\pi_i$ の時刻 $t$ における頂点 $v \in \pi_i(t)$ を、後続のエージェントが時刻 $t+1, \dots, t+\delta$ において障害物として扱う制約を課す。$\epsilon\text{-TP}$ では、各エージェントの遅延確率 $p$ に基づき、遷移行列 $M$ を用いて時刻 $t$ における所在分布 $\mathbf{x}_t = \mathbf{x}_0 M^t$ を算出する。経路の衝突確率は、各時刻における「エージェントがその頂点にいる確率」と「他のエージェントがその頂点にいない確率」の積を全頂点にわたって合計することで計算される。両手法とも、設定した $\delta$ または $\epsilon$ の閾値を超える遅延が発生した場合には、従来のTPと同様に再計画を実行する。
$10 \times 10$ および $20 \times 20$ の4連結グリッド環境を用い、タスク到着がポアソン分布に従う（到着頻度 $\lambda \in \{0.1, 0.2, 0.5\}$）条件下でシミュレーションを行った。評価指標としてメイクスパン、再計画回数、総実行時間を測定し、再計画を行うベースラインのTPと比較した。実験の結果、提案手法はいずれの環境でも再計画回数を劇的に減少させることが確認された。特に $\epsilon\text{-TP}$ は $\delta\text{-TP}$ よりも同等のメイクスパンにおいて高い堅牢性を示す傾向があり、$\delta\text{-TP}$ がベースラインに対して大幅な実行時間の増加を伴うのに対し、$\epsilon\text{-TP}$ は $\epsilon$ の値に応じてベースラインと同等から増加までの範囲で変動することが示された。
提案手法には、堅牢性のレベルと解のコスト（メイクスパン）との間に明確なトレードオフが存在する。$\epsilon\text{-TP}$ において、閾値 $\epsilon$ を大きくするか $\delta$ を小さくすることで再計画回数は減少するが、堅牢性を過度に高めすぎるとメイクスパンが著しく増大する。また、エージェントあたりの遅延回数を $1$ から $2$ に増やした困難な設定においても、提案手法の有効性は一貫して示された。今後の課題として、$\epsilon\text{-TP}$ のさらなる強化と、シミュレーションを超えた実環境での実験的検証が挙げられている。
本研究は、実行時の遅延や失敗といった実環境の不確実性を考慮した、ロバストなMulti-Agent Pickup and Delivery (MAPD) 問題を扱う。提案手法は、分散型アルゴリズムであるToken Passing (TP) をベースとした2つのアルゴリズム、$\text{robust-TP}$ と $\text{prob-TP}$ であり、それぞれ決定論的および確率的なロバスト性の保証を提供する。これらの手法は、不完全な実行による影響を制限するように経路を計画することで、オンラインでの再計画（replanning）の頻度を大幅に削減することを目指している。実験では、オンライン再計画を組み込んだ従来のTPと比較検証が行われ、$\text{robust-TP}$ と $\text{prob-TP}$ は、解のコストや計算時間をほとんど増加させることなく、遅延に起因する再計画回数を劇的に減少させることを示した。
Multi-Agent Pickup and Delivery (MAPD) は、タスク割り当て問題と衝突回避経路計画（MAPF）を組み合わせた問題であり、実行時に動的にタスクが投入される環境を想定している。本研究では、経路実行中にエージェントが一時停止する「遅延（delays）」が発生する状況を考慮した新しい問題設定である MAPD with delays (MAPD-d) を導入する。提案手法として、遅延による衝突を検知した際に再計画を行う分散型アルゴリズム Token Passing (TP) をベースラインとし、これに対し、遅延による衝突リスクを事前に抑制する堅牢な計画手法である $\delta$-TP および $\epsilon$-TP を提案する。$\delta$-TP は遅延に対して決定論的な堅牢性（$\delta$-robustness）を保証し、$\epsilon$-TP は確率的な堅牢性（$\epsilon$-robustness）を保証する。シミュレーション実験を通じて、提案アルゴリズムが提供する堅牢性のレベルと、解のコスト（solution cost）とのトレードオフを評価している。
本セクションでは、MAPF（Multi-Agent Path Finding）を拡張したMAPD（Multi-Agent Pickup and Delivery）の定義と、遅延に対する堅牢性（Robustness）の概念が整理されている。MAPDは、グラフ上のエージェントに対し、実行時に動的に追加されるタスク集合 $\mathcal{T}$ から、ピックアップ地点 $p_i$ とデリバリー地点 $d_i$ を持つタスク $t_i$ を割り当て、衝突を回避しながら最小コスト（サービス時間またはメイクスパン）で完了させる問題である。遅延への対策として、各エージェントの遅延が最大 $\Delta$ ステップである場合に衝突を回避する $\Delta$-robustnessと、遅延発生確率に基づき衝突確率を $1-\epsilon$ 以下に抑える $\epsilon$-robustnessの2つの概念が導入されている。また、MAPDにおける長期的な実行可能性を保証する「long-term robustness」の条件として、タスク数が有限であることや、エージェントが干渉せずに待機できるエンドポイント（rest locations）の存在などが挙げられている。本研究では、オンラインかつ分散的な手法であるToken Passing (TP) アルゴリズムをベースとしており、これは共有メモリであるトークンを用いて、空いているエージェントが最も近いタスクを自身に割り当て、衝突のない経路を逐次計算するものである。
本セクションでは、実行時に遅延が発生するMAPD問題（MAPD–d）を定義している。遅延は、時刻 $t$ における遅延エージェントの集合 $\mathcal{D}_t$ によって表され、エージェント $a$ は現在の頂点に留まることで経路の実行が妨げられる。エージェント $a$ の経路 $\pi_a$ に対する実行トレース $\tau_a$ は、遅延を考慮した実際の頂点遷移の列として定義され、$\tau_a(t)$ は時刻 $t$ においてエージェント $a$ が占有する頂点を示す。問題の「well-formedness（整合性）」を維持するため、エージェントが無限に遅延することはない（$\forall a, \forall t, \exists t' > t$ s.t. $a \notin \mathcal{D}_{t'}$）という条件 (iv) が追加されており、これにより遅延が環境のトポロジーを恒久的に変化させて解の存在を失わせることを防いでいる。比較用のベースラインとして、衝突を検知した際にトークンを衝突エージェントに割り当てて経路を再計画する「TP with replanning」が提案されている。このアルゴリズムでは、衝突が発生した場合に `PathPlanner` を用いて他のエージェントの現在の経路を制約条件としつつ新しい経路を計算し、デッドロック時にはランダムウォークによる回避を試みる。
本セクションでは、遅延に対して異なる堅牢性（robustness）を提供する2つのMAPDアルゴリズム、$\delta$-TPおよび$\epsilon$-TPが提案されている。$\delta$-TPは決定論的な堅牢性を提供し、各エージェントが最大 $\delta$ 回の連続した遅延が発生しても衝突を回避できるよう、計画中の経路に対して $\delta$-extension制約を課す。具体的には、エージェント $i$ の経路 $\pi_i$ に対して、時刻 $t$ における頂点 $v \in \pi_i(t)$ を、後続のエージェントが時刻 $t+1, \dots, t+\delta$ において障害物として扱う制約を生成する。一方、$\epsilon$-TPは確率的な堅牢性を提供し、各経路の衝突確率が閾値 $\epsilon$ を下回ることを保証する。$\epsilon$-TPでは、各エージェントの遅延確率を $p$ としたマルコフ連鎖モデルを採用しており、時刻 $t$ におけるエージェントの所在分布を遷移行列 $M$ を用いて $\mathbf{x}_t = \mathbf{x}_0 M^t$ と計算する。経路 $\pi$ の衝突確率は、各時刻における「エージェントがその頂点にいる確率」と「他のエージェントがその頂点にいない確率」の積を全頂点にわたって合計することで算出される。両アルゴリズムとも、$\delta$ 回または $\epsilon$ 閾値を超える遅延が発生した場合には再計画（replanning）が必要となる。
本実験では、遅延の影響が顕著な2種類の4連結グリッド環境（小規模：$10 \times 10$、大規模：$20 \times 20$）を用い、提案手法である $\epsilon\text{-TP}$ および $\delta\text{-TP}$ を、再計画を行うベースラインの $\text{TP}$ と比較評価している。タスクの到着はポアソン分布に従い、到着頻度 $\lambda \in \{0.1, 0.2, 0.5\}$ の条件下で、エージェントごとの遅延が発生するシナリオにおいて、評価指標としてメイクスパン（makespan）、再計画回数、および総実行時間を測定した。実験結果から、提案手法はいずれの環境においてもベースラインと比較して再計画回数を大幅に削減できることが示され、特に $\epsilon\text{-TP}$ は $\delta\text{-TP}$ よりも同等のメイクスパンにおいて高い堅牢性（robustness）を示す傾向がある。$\epsilon\text{-TP}$ においては、閾値 $\epsilon$ を大きくするか $\delta$ を小さくすることで再計画回数は減少するが、堅牢性を高めすぎるとメイクスパンが著しく増大するトレードオフが確認された。また、計算量に関しては、$\delta\text{-TP}$ はベースラインに対して大幅な実行時間の増加を伴う一方、$\epsilon\text{-TP}$ の実行時間は $\epsilon$ の値に依存してベースラインと同等から大幅な増加まで変動する。さらに、エージェントあたりの遅延回数を $1$ から $2$ に増やしたより困難な設定においても、提案手法は再計画回数の削減において一貫した有効性を示した。
本論文では、実行中の未知かつ有限な遅延を考慮した、実用的なマルチエージェント・ピックアップ＆デリバリー問題の拡張版である MAPD with delays (MAPD–d) を提案している。MAPD–d において、エージェントは各タスクのピックアップ地点からデリバリー地点への移動を完了させる必要があるが、本研究では決定論的な頑健性を保証する $\text{MAPD--TP}_{\text{det}}$ と、確率的な頑健性を保証する $\text{MAPD--TP}_{\text{prob}}$ という2つのアルゴリズムを提案した。実験では、遅延に対してリアクティブに対処するベースライン手法と比較を行い、提案手法がいずれもメイクスパンのわずかな増加で再計画（replanning）の回数を大幅に削減できることを示した。特に $\text{MAPD--TP}_{\text{prob}}$ は頑健性とコストのトレードオフにおいて最良の結果を示したが、依然として改善の余地が残されている。今後の展望として、Section 5.2 で述べた $\text{MAPD--TP}_{\text{prob}}$ の強化および実環境での実験的検証が挙げられている。