Thompson Sampling for Pursuit-Evasion Problems

Pursuit-evasion is a multi-agent sequential decision problem in which a group of agents coordinate their traversal of a spatial domain to locate an agent trying to evade them. Pursuit-evasion problems arise in a number of important application domains including defense and route planning. Learning to coordinate pursuer behaviors so as to minimize the time to capture of the evader is challenging because of a large action space and sparse noisy state information; consequently, previous approaches have relied primarily on heuristics. We propose a variant of Thompson Sampling for pursuit-evasion that allows for the application of existing model-based planning algorithms. The proposed approach is general that it allows for an arbitrary number of pursuers, a general spatial domain and the integration of side information. We derive posterior convergence rates and regret bounds for the proposed method, which are the first of their kind in this context. Through a suite of simulation experiments, we find that Thompson Sampling for pursuit-evasion significantly reduces time-to-capture and increases capture rate by at least 9% relative to competing algorithms.