倉庫自動化における生涯マルチエージェント経路探索のための学習ガイド付き優先順位計画

Abstract

Lifelong Multi-Agent Path Finding (MAPF) は、現代の倉庫自動化にとって重要であり、複数のロボットが対立のない経路を継続的にナビゲートしてシステム全体のスループットを最適化することが求められます。しかし、倉庫環境の複雑さや lifelong MAPF における長期的なダイナミクスは、多くの場合、古典的な探索ベースのソルバに対してコストのかかる適応を要求します。機械学習手法が検討されてきたものの、探索ベース手法に対する優位性は依然として結論が出ていません。本論文では、Reinforcement Learning（RL）により導かれる Rolling Horizon Prioritized Planning（RL-RH-PP）を導入します。これは lifelong MAPF に対して、最初に RL と探索ベース計画を統合する枠組みです。具体的には、その単純さと、学習ベースの優先順位付与ポリシーとの統合における柔軟性を活かし、古典的な Prioritized Planning（PP）をバックボーンとして用います。動的な優先順位付与を Partially Observable Markov Decision Process（POMDP）として定式化することで、RL-RH-PP は lifelong 計画における逐次的な意思決定の性質を活用し、エージェント間の複雑な空間・時間的相互作用を強化学習に委ねます。注意（attention）に基づくニューラルネットワークが優先順位の順序を逐次的にオートレグレッシブにその場で復号し、PP プランナによる効率的な逐次的単一エージェント計画を可能にします。現実的な倉庫シミュレーションでの評価では、RL-RH-PP がベースラインの中で最も高い総スループットを達成し、エージェント密度、計画ホライズン、倉庫レイアウトにわたって効果的に汎化します。解釈に基づく分析により、RL-RH-PP は混雑したエージェントを事前に優先し、混雑から戦略的にエージェントを迂回させることで交通の流れを緩和し、スループットを押し上げることが分かりました。これらの発見は、学習に導かれたアプローチが、現代の倉庫自動化における伝統的なヒューリスティックを補強する可能性を示しています。