探索・救助現場や建設現場のような、回避経路や待機場所が限られた迷路状の環境におけるMAPD問題を対象とする。従来のアルゴリズムは、グリッド状の倉庫環境のように豊富な迂回路や終端ノードが存在することを前提としており、ピックアップ・デリバリー地点の不足や不均衡が生じる環境ではエージェントが滞留し、デッドロックが発生しやすい。本研究では、このような制約の多い環境下でのエージェントの衝突回避と効率的なタスク遂行を目的とする。
既存のPIBTが環境の2連結性を要求することや、HTEやRDPが豊富な回避経路を前提としていることに対し、SBDAは迷路状の環境でも動作する。グラフ理論における関節点探索アルゴリズムを用いて、環境の連結性を損なわない待機ノードをリアルタイムに特定する点が新規である。これにより、従来のToken Passing手法などで課題となっていた、端点の重複による効率低下やデッドロックの問題を解決し、輸送効率と完全性の両立を実現している。
Status Management Token（SMT）と呼ばれる共有メモリ領域を用い、予約テーブル、タスク実行状態テーブル、待機ノード状態テーブルを通じてエージェントと計画の状態を管理する。待機ノードとして、Tarjanのアルゴリズムを用いて計算量 $O(|V|+|E|)$ で抽出された、関節点でもなくタスク終点でもなく行き止まりでもない潜在的待機ノード $\mathcal{P}_s$ を利用する。タスク選択時には、現在地からの距離が閾値 $\delta(e_j)$ 以内であることや、待機ノードの予約状況に基づく特定の条件（Cond. 1）を考慮してタスクを選択する。目的地決定プロセスでは、目的地の終点が開放されていない場合に、潜在的待機ノードを一時的な目的地として選択することで、エージェントが終点付近で塞ぎ合うのを防ぐ。
タスク端点が共通するタスクを同時に実行できないHTEをベースラインとし、タスク端点が少ない迷路状環境（Env. 1）と、荷積み・荷降ろし地点が偏っている環境（Env. 2）で評価を行った。評価指標には全タスク完了時間であるmakespanと、計算時間であるruntimeを用いた。エージェント数 $N=10$ の実験において、SBDAはEnv. 1でmakespanを約39%、Env. 2で約53%削減した。また、待機ノードと端点間の最大距離 $d_{\text{max}}$ に関する分析や、タスク選択条件の有効性を検証するアブレーションスタディも実施されている。
SBDAは輸送効率の観点では劣最適（suboptimal）なアルゴリズムである。パラメータ $d_{\text{max}}$ については、値が大きすぎると経路の迂回や局所的な混雑を招き、効率が低下するというトレードオフが存在する。また、タスク選択における制約（Cond. 1）は、作業エリアへの過度な流入や混雑を防ぐために重要である。今後の課題として、実世界のアプリケーションへの適用性を高めるため、グラフ構造からパラメータ $\alpha$ の適切な値を自動的に決定する手法の研究が挙げられている。
本研究では、迷路のような制約の多い環境下でのマルチエージェント・ピックアップ＆デリバリー（MAPD）問題において、エージェントの集中によるデッドロックを防ぐための待機ノードに基づくデッドロック回避手法（SBDA）を提案している。従来のMAPDアルゴリズムはグリッド状の倉庫環境を想定しており、回避経路や待機場所が豊富にあることを前提としているが、探索・救助や建設現場のような迷路状の環境では、ピックアップ・デリバリー地点の不足や不均衡によりエージェントが滞留し、デッドロックが発生しやすい。SBDAは、関節点検出アルゴリズムを用いてリアルタイムに決定された待機ノードを活用し、エージェントがその地点に有限時間留まることを保証することで、効率的な運用を実現する。実験の結果、提案手法は従来手法よりも高い輸送効率を示すことが確認されており、待機ノードの選択に関するパラメータが性能に与える影響についても分析が行われている。
本研究は、迷路のような制約のある環境下でのマルチエージェント・ピックアップ＆デリバリー（MAPD）問題において、デッドロックを回避しつつ輸送効率を向上させる待機ベースのデッドロック回避（SBDA）手法を提案している。従来のPIBTは環境の2連結性を要求し、HTEやRDPはグリッド状の環境や豊富な終端・迂回路を前提とするが、これらは探索・救助現場のようなアドホックで迷路状の環境では適用が困難である。提案するSBDAは、グラフ理論における関節点探索アルゴリズム（APFアルゴリズム）を用いて、目的地付近の待機ノードをリアルタイムに決定し、エージェントが目的地付近で停滞したりデッドロックに陥ったりするのを防ぐために、これらのノードで一時的に待機することを可能にする。SBDAは輸送効率の観点では劣最適（suboptimal）なアルゴリズムであるが、待機ノードを利用することで完全性（completeness）を保証している。実験では、HTEをベースラインとして、迷路状の制限環境において提案手法がベースラインを上回る性能を示すことを確認し、パラメータ設定やアブレーションスタディを通じてその特性を分析している。
MAPFおよびMAPD問題の研究は、中央集権的な計画手法と分散的な手法に大別される。中央集権的な手法として、各エージェントが独立して経路を生成する低レベル探索と、衝突のない最適経路を生成する高レベル探索からなるConflict-based Search (CBS) があるが、エージェント数の増加に伴い計算コストが急増するという課題がある。一方、分散的な手法はスケーラビリティと堅牢性に優れるが、個別に計画を生成するため、完全性の確保や衝突解決の能力が求められる。例えば、優先度に基づき隣接エージェントと通信して次ノードを決定するPIBTは、二連結グラフの環境でのみ完全性が保証される。また、トークンを用いてタスクの終端予約を確認する手法も存在するが、これらは回避経路や退避ノードが豊富なグリッド状の環境を想定していることが多い。これに対し、迷路のような環境では、終端ノードや迂回路の数が少なく、かつそれらの経路長が大きく異なるため、既存のデッドロック回避手法（例えば、エージェントが待機できる終端ノードを多数想定するHTEや、各エージェントに専用の駐車場所を確保するRDPなど）を適用すると、輸送効率や計画効率が著しく低下するという限界がある。
MAPD問題は、エージェント集合 $\mathcal{A}$、タスク集合 $\mathcal{T}$、および2次元ユークリッド空間に埋め込み可能な無向連結グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ で定義され、各タスクは荷物の積み込み位置と向き $(p_i, o_i)$ および荷下ろし位置と向き $(d_i, o_i)$ のタプルとして指定される。エージェントは離散時間 $t \in \mathbb{Z}_{>0}$ において、移動、回転、待機、積み込み、荷下ろしの各アクションを実行し、各アクションの所要時間は、エッジの長さ $l_{uv}$、回転角 $\Delta \theta$、待機時間 $\Delta t$ に基づいて $T_{\text{move}}, T_{\text{rot}}, T_{\text{wait}}, T_{\text{load}}, T_{\text{unload}}$ として定式化される。既存のToken Passing (TP) アルゴリズムでは、全エージェントの経路やタスク割り当てを共有メモリであるトークンで管理し、タスクの端点集合 $\mathcal{E}_{\text{task}}$ と、初期位置を含む非タスク端点集合 $\mathcal{E}_{\text{non-task}}$ を用いて衝突回避を行う。TPが解ける「well-formed」なインスタンスの条件は、タスク数が有限であること、非タスク端点の数がエージェント数以上であること、および任意の端点間に他の端点を経由しない経路が存在することの3点である。しかし、TPでは端点が重複する場合にエージェントが同時にタスクを実行できず、迷路のような環境では効率が著しく低下するという限界がある。
SBDA（Standby-Based Deadlock Avoidance）は、迷路のような環境下でエージェントが同じ終点を持つタスクを実行してもデッドロックを回避し、輸送効率を向上させる手法である。本手法では、予約テーブル（RT）、タスク実行状態テーブル（TEST）、待機ノード状態テーブル（SST）を含む共有メモリ領域であるStatus Management Token（SMT）を用いて、エージェント、計画、待機ノードの状態を管理し、衝突を検知する。待機ノードとして、グラフ $G$ において関節点（AP）でもなく、タスクの終点でもなく、行き止まりでもないノードである潜在的待機ノード $\mathcal{P}_s$ を動的に特定する。この $\mathcal{P}_s$ は、Tarjanのアルゴリズムを用いて計算量 $O(|V|+|E|)$ で効率的に抽出され、エージェントが特定のノードを予約すると、そのノードと接続するエッジを除去した一時的なグラフ $G'$ が構成されるが、$\mathcal{P}_s$ の定義により他のエージェントの経路確保は保証される。タスク選択プロセスでは、現在の位置 $x_i$ からの距離 $d(x_i, e_j)$ が閾値 $\delta(e_j)$ 以内であることや、待機ノードの予約状況を考慮した条件（Cond. 1）に基づき、最も近いタスクを選択する。目的地決定プロセス（DecideDest）では、目的地の終点が開放されていない場合に、潜在的待機ノードを一時的な目的地として選択することで、エージェントが終点付近で互いに塞ぎ合うデッドロックを回避し、環境の混雑状況に応じて待機またはパーキングノードへの帰還を行う。
提案手法であるSBDA（Standby-Based Deadlock Avoidance）の性能を評価するため、タスクの端点が共通するタスクを同時に実行できないベースライン手法HTEと比較する実験が行われた。実験は、タスク端点が少ない迷路状の環境（Env. 1）と、荷積み・荷降ろし地点が偏っている環境（Env. 2）の2種類で実施され、評価指標として全タスク完了時間であるmakespanと、計画に要したCPU時間であるruntimeが用いられた。Env. 1において、エージェント数 $N=10$ のとき、SBDAはHTEと比較してmakespanを約39%削減し、Env. 2では約53%もの削減を実現した。これは、SBDAが待機ノード（standby nodes）を効果的に活用することで、HTEよりも高い並列性を実現できるためである。パラメータ $d_{\text{max}}$（待機ノードと端点間の最大距離）については、値が0から8に増加するにつれてmakespanが減少する傾向が見られたが、$d_{\text{max}}=12$ のように大きすぎると、経路の迂回や局所的な混雑により効率が低下することが示された。アブレーション研究の結果、タスク選択条件であるCond. 1の各制約は、作業エリアへの過度な流入防止や、荷積み・荷降ろしノードの混雑回避、およびタスク実行の中断防止において、makespanの最適化に重要な役割を果たしていることが確認された。
本研究では、迷路のような環境下での輸送効率を向上させるため、MAPD問題に対するデッドロック回避手法であるSBDAを提案している。SBDAの核心は、エージェントが待機しても環境の連結性が維持される待機ノードを活用することにあり、グラフ理論における関節点探索アルゴリズムを用いることで、計算コストを抑えつつリアルタイムにこれらのノードを特定できる。SBDAは、任意の有限時間待機が保証される待機ノードを効果的に利用することで、適切に構成されたMAPDインスタンスに対して完全性を保証する。迷路のような制限された環境におけるHTEを用いた比較実験の結果、SBDAは従来手法を大幅に上回る性能を示した。また、待機ノードの選択に使用するパラメータ $\alpha$ の値を調整することで、タスク実行の並列性を制御でき、適切な設定により輸送効率を著しく向上させられることが明らかになった。今後の課題として、実世界のアプリケーションへの柔軟性と利便性を高めるため、グラフ構造から $\alpha$ の適切な値を決定する手法の研究が挙げられている。