Robotics: Science and Systems IV

Approximation Schemes for Two-Player Pursuit Evasion Games with Visibility Constraints

Sourabh Bhattacharya, Seth Hutchinson

Abstract: In this paper, we consider the problem in which a mobile pursuer attempts to maintain visual contact with an evader as it moves through an environment containing obstacles. This surveillance problem is a variation of traditional pursuitevasion games, with the additional condition that the pursuer immediately loses the game if at any time it loses sight of the evader. Since it has been shown that the problem of deciding whether or not the pursuer is able to maintain visibility of the evader is at least NP-complete, we present schemes to approximate the set of initial positions of the pursuer from which it might be able to track the evader. We first consider the case of an environment containing only polygonal obstacles. We prove that in this case the set of initial pursuer configurations from which it does not lose the game is bounded. Moreover, we provide polynomial time approximation schemes to bound this set. We then extend our results to the case of arbitrary obstacles with smooth boundaries.



    AUTHOR    = {Sourabh Bhattacharya, Seth Hutchinson},
    TITLE     = {Approximation Schemes for Two-Player Pursuit Evasion Games with Visibility Constraints},
    BOOKTITLE = {Proceedings of Robotics: Science and Systems IV},
    YEAR      = {2008},
    ADDRESS   = {Zurich, Switzerland},
    MONTH     = {June},
    DOI       = {10.15607/RSS.2008.IV.011}