Computer Science – Computer Science and Game Theory
Scientific paper
2011-10-21
K. Klein and S. Suri. Complete information pursuit evasion in polygonal environments. In 25th Conference on Artificial Intelli
Computer Science
Computer Science and Game Theory
17 pages, 12 figures
Scientific paper
Suppose an unpredictable evader is free to move around in a polygonal environment of arbitrary complexity that is under full camera surveillance. How many pursuers, each with the same maximum speed as the evader, are necessary and sufficient to guarantee a successful capture of the evader? The pursuers always know the evader's current position through the camera network, but need to physically reach the evader to capture it. We allow the evader the knowledge of the current positions of all the pursuers as well---this accords with the standard worst-case analysis model, but also models a practical situation where the evader has "hacked" into the surveillance system. Our main result is to prove that three pursuers are always sufficient and sometimes necessary to capture the evader. The bound is independent of the number of vertices or holes in the polygonal environment. The result should be contrasted with the incomplete information pursuit-evasion where at least {\Omega}(\surd h + log n) pursuers are required just for detecting the evader in an environment with n vertices and h holes.
Klein Kyle
Suri Subhash
No associations
LandOfFree
Capturing an Evader in Polygonal Environments: A Complete Information Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Capturing an Evader in Polygonal Environments: A Complete Information Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capturing an Evader in Polygonal Environments: A Complete Information Game will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-85692