Pursuit-Evasion Games under Lack of Common Knowledge

Pursuit-Evasion Games under Lack of Common Knowledge

Pursuit-evasion games have traditionally been studied under the assumption that both player have an identical understanding of the environment in which they operate. However this is rarely true in practice. Instead, players form their own understanding of the dynamics of the world. This discrepancy in the understanding of the evolution of the system may arise due to sensing limitations or because of the agent's prior experience or may also be due to deception, measurement capability of the agent or erroneous modeling assumptions of the environment. A motivating example of such a situation is a pursuit-evasion game between two unmanned air vehicles (UAVs) in the presence of a wind-field. The presence of this wind-field will undoubtedly influence the outcome of the game, and the ability of each player to understand the effect of this wind-field (that is, understand the true system dynamics) will influence the strategy it decides to employ when playing the game.

Figure 1: Grid for pursuit evasion game: start, goal and obstacle cells are indicated.

Motivated by this view, we seek to establish the existence of equilibria solutions under this new set of relaxed assumptions. We prove that under these new conditions there exist (Nash) equilibria solutions and utilize methods for finding correlated equilibria in order to arrive at tractable solutions. A two-player game is constructed on the grid-world shown in Figure 1, where then each of the players is given a (possibly) different understanding of the world dynamics. In order to provide for meaningful comparisons, we solve for correlated equilibria under a common understanding of each players environment - sample paths are shown in Figure 2.

(a)

(b)

Figure 2: Sample trajectories given the stochastic game. Case (a) is game under common knowledge (stochastic environment). Case (b) represents case where the evading player is captured, assuming the evader's environment is correct.

We observe that in the case where the environment is stochastic, and the pursuing player in unaware of this, it takes risks such as passing directly next to the obstacles in the environment - for which crashing into them is a considered to be a loss to the crashing player. We also see the pursuing player, who is aware of the stochastic environment, be more cautious, staying further away from obstacles in their attempt to escape.

For more information, see our publication here.

Sponsors

This project has been sponsored by the office of naval research (ONR) and the National Science Foundation (NSF).

Selected Publications

Larsson, Daniel T., Georgios Kotsalis, and Panagiotis Tsiotras. "Nash and Correlated Equilibria for Pursuit-Evasion Games Under Lack of Common Knowledge." 2018 IEEE Conference on Decision and Control (CDC). IEEE, 2018.