On Discrete-time Pursuit-evasion Games with Sensing Limitations

We address discrete-time pursuit-evasion games in the plane where every player has identical sensing and motion ranges restricted to closed discs of given sensing and stepping radii. A single evader is initially located inside a bounded subset of the environment and does not move until detected. We propose a Sweep-Pursuit-Capture pursuer strategy to capture the evader and apply it to two variants of the game: the first involves a single pursuer and an evader in a bounded convex environment and the second involves multiple pursuers and an evader in a boundaryless environment. In the first game, we give a sufficient condition on the ratio of sensing to stepping radius of the players that guarantees capture. In the second, we determine the minimum probability of capture, which is a function of a novel pursuer formation and independent of the initial evader location. The Sweep and Pursuit phases reduce both games to previously-studied problems with unlimited range sensing, and capture is achieved using available strategies. We obtain novel upper bounds on the capture time and present simulation studies that address the performance of the strategies under sensing errors, different ratios of sensing to stepping radius, greater evader speed and different number of pursuers