On the Existence of Nash Equilibrium for a Two-player Pursuit—Evasion Game with Visibility Constraints

Abstract

In this paper, we present a game-theoretic analysis of a visibility-based pursuit—evasion game in a planar environment containing obstacles. The pursuer and the evader are holonomic having bounded speeds. Both players have a complete map of the environment. Both players have omnidirectional vision and have knowledge about each other’s current position as long as they are visible to each other. The pursuer wants to maintain visibility of the evader for the maximum possible time and the evader wants to escape the pursuer’s sight as soon as possible. Under this information structure, we present necessary and sufficient conditions for surveillance and escape. We present strategies for the players that are in Nash equilibrium. The strategies are a function of the value of the game. Using these strategies, we construct a value function by integrating the adjoint equations backward in time from the termination situations provided by the corners in the environment. From these value functions we recompute the control strategies for the players to obtain optimal trajectories for the players near the termination situation. This is the first work that presents the necessary and sufficient conditions for tracking for a visibility based pursuit—evasion game and presents the equilibrium strategies for the players.

Keywords

game theory pursuit-evasion

Get full access to this article

View all access options for this article.

References

Alexander, S. , Bishop, R. and Ghrist, R. ( 2006). Pursuit and evasion in non-convex domains of arbitrary dimensions. Proceedings of Robotics: Science and Systems. Philadelphia, PA.

Alexander, S. , Bishop, R. and Ghrist, R. ( 2008). Capture pursuit games on unbounded domains.

Başar, T. and Olsder, G.J. ( 1999). Dynamic Noncooperative Game Theory (2nd edn) (SIAM Series in Classics in Applied Mathematics). Philadelphia, PA, SIAM.

Bandyopadhyay, T. , Li, Y. , Ang, M., Jr , and Hsu, D. ( 2006). A greedy strategy for tracking a locally predicatable target among obstacles. Proceedings IEEE International Conference on Robotics and Automation (ICRA’02), pp. 2342- 2347.

Bhattacharya, S. , Candido, S. and Hutchinson, S. ( 2007). Motion strategies for surviellance. Robotics: Science and Systems-III.

Bhattacharya, S. and Hutchinson, S. ( 2008a). Approximation schemes for two-player pursuit evasion games with visibility constraints. Proceedings of Robotics: Science and Systems IV, Zurich, Switzerland.

Bhattacharya, S. and Hutchinson, S. ( 2008b). From strategies to trajectories. http://www.-cvr.ai.uiuc.edu/∼sbhattac/comp.pdf.

Cheng, L.-T. and Tsai, Y.-H. ( 2005). Visibility optimization using variational approaches , Communication of Mathematical Sciences, 3: 425-451.

Isaacs, R. ( 1965). Differential Games. New York, Wiley.

10.

Kopparty, S. and Ravishankar, C.V. ( 2005). A framework for pursuit evasion games in RN. Information Processing Letters, 96(3): 114-122.

11.

LaValle, S.M. , Gonzalez-Banos, H.H. , Becker, C. and Latombe, J.C. ( 1997). Motion strategies for maintaining visibility of a moving target. Proceedings 1997 IEEE International Conference on Robotics and Automation, Vol. 1, Albuquerque, NM, pp. 731-736.

12.

Lewin, J. ( 1994). Differential Games: Theory and Methods for Solving Game Problems with Singular Surfaces. London, Springer.

13.

Li, T. , Lien, J. , Chiu, S. and Yu, T. ( 1997). Automatically generating virtual guided tours. Computer Animation Conference, pp. 99-106.

14.

Melikyan, A.A. and Hovakimyan, N.V. ( 1991a). A differential game of simple approach in manifolds . Journal of Applied Mathematics and Mechanics, 55(5): 607-618.

15.

Melikyan, A.A. and Hovakimyan, N.V. ( 1991b). Singular trajectories in the game of simple pursuit in the manifold. Journal of Applied Mathematics and Mechanics , 55(1): 42- 48.

16.

Melikyan, A.A. and Hovakimyan, N.V. ( 1993). A differential game of simple approach in manifolds. Journal of Applied Mathematics and Mechanics, 57(1): 47-57.

17.

Parsons, T.D. ( 1976). Pursuit-evasion in a graph. Proceedings of the International Conference on the Theory and Application of Graphs, Kalamazoo, MI.