A visibility-based pursuit-evasion problem

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.