Learn all about Multi-Agent Path Finding (MAPF)
F. Xie, A. Botea and A. Kishimoto. A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 4470-4476, 2017.
Abstract: Chasing multiple mobile targets with multiple agents is important in several applications, such as computer games and police chasing scenarios. Existing approaches can compute optimal policies. However, they have a limited scalability, as they implement expensive minimax searches. We introduce a sub-optimal but scalable approach that assigns individual agents to individual targets and that can dynamically re-compute such assignments. We provide a theoretical analysis, including upper bounds on the number of time steps required to solve an instance. In a detailed empirical evaluation on grid maps, our algorithm scales up very convincingly beyond the limits of previous methods. On small problems, where a comparison to a minimax approach is possible, the results demonstrate a good solution quality for our method.