A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents

A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents

Fan Xie, Adi Botea, Akihiro Kishimoto

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4470-4476. https://doi.org/10.24963/ijcai.2017/624

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.
Keywords:
Planning and Scheduling: Search in Planning and Scheduling
Combinatorial & Heuristic Search: Heuristic Search
Agent-based and Multi-agent Systems: Multi-agent Planning