Pursuit-evasion games in the presence of obstacles

摘要

This paper studies planar pursuit-evasion games in the presence of obstacles that inhibit the motions of the players. The goal is to construct the dominance regions, where a point in the plane is said to be dominated by one of the players if that player is able to reach the point before the opposing players, regardless of the opposing players' actions. The key achievements of the paper are to provide the dominance regions and to show that an analysis of dominance provides a complete solution to the game. This paper also presents a study of the effects of obstacles by comparing the dominance regions in the presence and absence of obstacles. The obstacles considered include line segments and polygons as well as obstacles that have asymmetric effects on the players. As part of the discussion, a novel, multiplayer pursuit-evasion game is also presented. It features three players on two teams, and it can be used to model rescue scenarios and biological behaviors. The solution of this game cannot be determined from the previous literature, but the methods provided in this paper are used to determine dominance and solve the game. (C) 2015 Elsevier Ltd. All rights reserved.