TY - GEN
T1 - A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader
AU - Murrieta-Cid, Rafael
AU - Monroy, Raul
AU - Hutchinson, Seth
AU - Laumond, Jean Paul
PY - 2008
Y1 - 2008
N2 - In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [11], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k - Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.
AB - In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [11], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k - Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.
UR - http://www.scopus.com/inward/record.url?scp=51649086720&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51649086720&partnerID=8YFLogxK
U2 - 10.1109/ROBOT.2008.4543613
DO - 10.1109/ROBOT.2008.4543613
M3 - Conference contribution
AN - SCOPUS:51649086720
SN - 9781424416479
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 2657
EP - 2664
BT - 2008 IEEE International Conference on Robotics and Automation, ICRA 2008
T2 - 2008 IEEE International Conference on Robotics and Automation, ICRA 2008
Y2 - 19 May 2008 through 23 May 2008
ER -