混雑回避経路による多エージェント経路計画の交通流最適化
Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
多数のエージェントが共有マップ上を移動する際、混雑を避ける経路へ誘導することで経路計画の品質とスループットを改善する手法を提案した。
著者: Zhe Chen, Daniel Harabor, Jiaoyang Li, Peter J. Stuckey
分類: cs.AI, cs.MA, cs.RO
原文アブストラクト
Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics that asks us to compute collision-free paths for a team of agents, all moving across a shared map. Although many works appear on this topic, all current algorithms struggle as the number of agents grows. The principal reason is that existing approaches typically plan free-flow optimal paths, which creates congestion. To tackle this issue, we propose a new approach for MAPF where agents are guided to their destination by following congestion-avoiding paths. We evaluate the idea in two large-scale settings: one-shot MAPF, where each agent has a single destination, and lifelong MAPF, where agents are continuously assigned new destinations. Empirically, we report large improvements in solution quality for one-short MAPF and in overall throughput for lifelong MAPF.
