A Visibility-Based Pursuit-Evasion Problem Export

@article{citeulike:3626382, abstract = {This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually \"see \" an evader that is unpredictable, has unknown initial position, and is capable of moving arbitrarily fast. This problem was first introduced by Suzuki and Yamashita. Our study of this problem is motivated in part by robotics applications, such as surveillance with a mobile robot equipped with a camera that must find a moving target in a cluttered workspace. A few bounds are introduced, and a complete algorithm is presented for computing a successful motion strategy for a single pursuer. For simply-connected free spaces, it is shown that the minimum number of pursuers required is \Theta(lg n). For multiplyconnected free spaces, the bound is \Theta( p h+lg n) pursuers for a polygon that has n edges and h holes. A set of problems that are solvable by a single pursuer and require a linear number of recontaminations is shown. The complete algorithm searches a finite graph that is constructed on the basis of critical information changes. It has been implemented and computed examples are shown. 1}, author = {Guibas, Leonidas J. and Latombe, Jean-Claude and Lavalle, Steven M. and Lin, David and Motwani, Rajeev}, citeulike-article-id = {3626382}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.6928}, journal = {International Journal of Computational Geometry and Applications}, keywords = {pursuit\_evasion}, pages = {471--494}, posted-at = {2008-11-30 00:00:12}, priority = {3}, title = {A Visibility-Based Pursuit-Evasion Problem}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.6928}, volume = {9}, year = {1999} }

TY - JOUR ID - citeulike:3626382 L3 - citeulike-article-id:3626382 N2 - This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see " an evader that is unpredictable, has unknown initial position, and is capable of moving arbitrarily fast. This problem was first introduced by Suzuki and Yamashita. Our study of this problem is motivated in part by robotics applications, such as surveillance with a mobile robot equipped with a camera that must find a moving target in a cluttered workspace. A few bounds are introduced, and a complete algorithm is presented for computing a successful motion strategy for a single pursuer. For simply-connected free spaces, it is shown that the minimum number of pursuers required is \Theta(lg n). For multiplyconnected free spaces, the bound is \Theta( p h+lg n) pursuers for a polygon that has n edges and h holes. A set of problems that are solvable by a single pursuer and require a linear number of recontaminations is shown. The complete algorithm searches a finite graph that is constructed on the basis of critical information changes. It has been implemented and computed examples are shown. 1 JF - International Journal of Computational Geometry and Applications EP - 494 TI - A Visibility-Based Pursuit-Evasion Problem VL - 9 SP - 471 KW - pursuit_evasion AU - Guibas, Leonidas AU - Latombe, Jean-Claude AU - Lavalle, Steven AU - Lin, David AU - Motwani, Rajeev PY - 1999/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.6928 ER -