A visibility-based pursuit-evasion problem

Citation
Lj. Guibas et al., A visibility-based pursuit-evasion problem, INT J C GEO, 9(4-5), 1999, pp. 471-493
Citations number
25
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
9
Issue
4-5
Year of publication
1999
Pages
471 - 493
Database
ISI
SICI code
0218-1959(199908/10)9:4-5<471:AVPP>2.0.ZU;2-#
Abstract
This paper addresses the problem of planning the motion of one or more purs uers in a polygonal environment to eventually "see" an evader that is unpre dictable, has unknown initial position, and is capable of moving arbitraril y fast. This problem was first introduced by Suzuki and Yamashita. Our stud y of this problem is motivated in part by robotics applications, such as su rveillance with a mobile robot equipped with a camera that must find a movi ng target in a cluttered workspace. A few bounds are introduced, and a complete algorithm is presented for comp uting a successful motion strategy for a single pursuer. For simply-connect ed free spaces, it is shown that the minimum number of pursuers required is theta(lg n). For multiply-connected free spaces, the bound is theta(root h + lg n) pursuers for a polygon that has n edges and h holes. A set of prob lems that are solvable by a single pursuer and require a linear number of r econtaminations is shown. The complete algorithm searches a finite graph th at is constructed on the basis of critical information changes. It has been implemented and computed examples are shown.