対象は、グラフ上を移動する複数エージェントに、時間とともに解放されるピックアップ・デリバリー課題を割り当てるオンライン多エージェント・ピックアップ・アンド・デリバリー問題（MAPD）である。各エージェントは現在位置からピックアップ地点へ移動し、その後に対応するデリバリー地点へ移動する必要があり、エージェント同士の衝突は禁止される。衝突には、同時に同じ頂点を占有する場合と、同時に同じ辺を逆方向へ通過する場合が含まれる。課題は逐次的に現れ、空いているエージェントへ割り当てられるため、単一の固定目標への通常のMAPFよりも、将来の経路と割当を考慮する必要がある。
第一の貢献は、順序付けられた複数目標を一つの探索で扱うマルチラベルA*（MLA*）を提案したことである。第二の貢献は、エージェントと未割当課題をh値で並べ、MLA*による実現可能性判定と経路生成を反復する集中型ヒューリスティックHBHである。従来のTPやTPTSでは、ピックアップまでのA*とピックアップからデリバリーまでのA*を分けて実行していたのに対し、本手法はその分割による過剰な制約を避ける。提示された実験では、既存手法に対して解品質と計算効率の双方を改善できることが示される。
MLA*は古典的A*の探索構造を保ちながら、探索ノードに現在の目標段階を表すラベルを付ける。ラベル1ではエージェントはピックアップ地点を目指し、ピックアップ地点に到達すると同じ状態をラベル2へ進め、以後はデリバリー地点を目指す。探索キューから最小f値のノードを選び、許容される時間条件を満たさないノードを棄却し、デリバリー到着時に経路を返す。これにより、エージェントがピックアップ地点で計画終了まで待機すると仮定する必要がなくなり、他エージェントの将来経路との干渉を避けながら地点を通過して先へ進める。HBHは各時刻に利用可能なエージェントと未割当の公開課題を取得し、エージェント・課題対をh値の昇順に調べ、MLA*で実行可能な対を採用して経路と割当を更新する。
評価には、先行研究で用いられた倉庫インスタンスが使われた。小規模集合は、時間とともに解放される500課題、10〜50エージェント、解放頻度0.2〜10課題/時刻の30インスタンスで構成され、大規模集合は、1000課題、解放頻度50課題/時刻、100〜500エージェントの5インスタンスで構成される。比較対象はTP、TPにMLA*を組み込んだ構成、HBHとMLA*の組合せ、そして先行研究のCentral法であり、メイクスパン、平均サービス時間、1時刻あたりの計算時間、探索状態数を比較した。実装はC++で、2.7GHz Intel Core i5、16GB RAM、1コアの環境で実行されたが、Central法の結果は先行研究から取得された。
MLA*の中心的な利点は、ピックアップ地点に到着した時点で経路を分割せず、デリバリーまでを見通して探索できることである。これにより、ピックアップ地点が別エージェントの将来のデリバリー地点である場合や、別エージェントが近い将来にその地点を通過する場合に、実際には可能な経路を不可能または遅延した経路として扱う問題を緩和できる。一方、HBHは集中型であり、利用可能なエージェントと課題の対を繰り返し検査するため、問題全体の最適解を保証する方法として説明されているわけではない。抜粋には、理論的な最適性保証、一般の地図への移植性、課題解放規則の変更に対する頑健性は確立されていない。将来課題として、MLA*を複数注文のスケジューリングへ拡張する方向が示されている。
MAPFは、複数エージェントについて、開始位置から目標位置まで衝突のない経路を求める計画問題であり、倉庫物流、ゲーム、捜索救助などに応用される。研究では期限、運動学的制約、匿名エージェントへの課題割当、複数目標などの拡張が扱われてきた。MAPDはその一つで、課題が時間とともに現れ、各課題がピックアップとデリバリーの目標を含む。
エージェントはグラフの頂点と辺に沿って、待機または隣接頂点への移動を行う。各時刻に新しい課題が追加され、空いているエージェントへ課題が割り当てられ、経路は全期間にわたって衝突を起こしてはならない。抜粋では、すべての動的課題に対する大域的最適解を求めることが問題の要求なのか、実行可能な高品質解を求めるのかは明示されていない。
MLA*の探索ノードは、位置、時間、コスト、目標段階を持つラベル付き状態として扱われる。ピックアップ到着時にラベルを1から2へ変更することで、二つの順序付き目標を単一探索に統合する。HBHはh値に基づくエージェント・課題対の順序付けと、MLA*による経路実現可能性の確認を組み合わせる。
小規模実験は30インスタンス、大規模実験は5インスタンスで行われた。小規模では500課題と10〜50エージェント、大規模では1000課題と100〜500エージェントが使われた。評価環境はC++、2.7GHz Intel Core i5、16GB RAM、1コアである。
大規模事例では、HBH+MLA*はTPに対して平均メイクスパンを30%、平均サービス時間を43%、計算時間を98%削減した。500エージェントの場合、最大でメイクスパン30%、平均サービス時間43%の削減が報告され、1時刻あたりの計算時間は最大74ミリ秒だった。小規模事例では、HBH+MLA*はサービス時間を一貫して改善し、50エージェント時にCentral法と同程度の解品質を、0.84ミリ秒/時刻対2085ミリ秒/時刻で得たと報告されている。
MLA*は、ピックアップとデリバリーという順序付き目標を見通して探索することで、逐次A*が生む不要な制約を避ける。HBHと組み合わせると、MAPDの大規模倉庫事例で解品質と計算効率の双方が改善された。抜粋が示す結論は経験的なものであり、すべてのMAPD設定で同じ改善が得られることまでは確立していない。
実験は先行研究の倉庫インスタンスに基づいており、他の地図、障害物構造、課題分布、エージェント能力への一般化は抜粋から判断できない。Central法との比較は大規模事例では行われていないため、その規模での相対性能は確立されていない。最適性、完全性、最悪時計算量、動的環境の予測誤差に関する説明も、供給された抜粋には十分に含まれていない。
MAPDでは、課題割当と衝突回避経路計画を別々に扱うと、局所的に妥当な選択が将来の経路を不必要に制限しうる。本論文は、順序付き目標を一つの探索で扱うという比較的明確な機構により、その制約を減らし、大規模なオンライン物流に適用可能な計算効率を示した点で重要である。特に、解品質だけでなく1時刻あたりの処理時間を同時に評価している点が実運用志向の研究に有用である。
MAPFやMAPD、倉庫ロボットのオンライン課題割当、衝突回避経路計画を研究する読者に適している。通常のA*を複数の順序付き目標へ拡張する設計や、経路生成を利用した集中型ヒューリスティックの実験的効果を知りたい場合に特に有用である。厳密最適化の理論保証や多様な環境での頑健性を主目的とする読者は、抜粋だけでは情報が不足している点に注意すべきである。