まとめ

マルチゴール：「同じ棚を複数のワークステーションに順番に持っていく」

複数のワークステーションの巡回順は固定

1タスクがk個のゴール列（例：s → g1 → g2 → … → gk）を持つ

各エージェントは容量1

提案アルゴリズム：

どのエージェントがどのタスクをどの順に担当するか（タスク間の並び）をLNSで最適化
固定されたタスク内ゴール列を辿る衝突回避経路をPBS/wPBSで計画

Abstract

本研究では、新たなタスクが継続的に到着し、それらを実行するためにエージェントが衝突のない経路を計画し続ける必要がある Multi-Agent Pickup-and-Delivery（MAPD）問題を扱う。タスクを実行するには、エージェントはピックアップ地点とデリバリ地点からなる一対のゴール地点を順に訪れる必要がある。私たちは、任意時（anytime）アルゴリズムである Large Neighborhood Search（LNS）を用いて各エージェントにタスク列を割り当て、Multi-Agent Path Finding（MAPF）アルゴリズムの Priority-Based Search（PBS）で経路を計画するアルゴリズムの2つの変種を提案する。LNS-PBS は、現実的な MAPD の部分クラスである well-formed な MAPD インスタンスに対して完全性を備え、既存の完全な MAPD アルゴリズム CENTRAL より経験的に高い有効性を示す。LNS-wPBS は完全性の保証はないが、経験的には LNS-PBS よりも効率的で安定している。大規模倉庫において数千のエージェントと数千のタスクにまでスケールし、既存のスケーラブルな MAPD アルゴリズム HBH+MLA* よりも経験的に有効である。さらに、LNS-PBS と LNS-wPBS は、タスクが異なる数のゴール地点を持ち得る、より一般的な MAPD の変種である Multi-Goal MAPD（MG-MAPD）にも適用可能である。