TY - GEN

T1 - Visibility-based pursuit-evasion in a polygonal environment

AU - Guibas, Leonidas J.

AU - Latombe, Jean Claude

AU - LaValle, Steven M.

AU - Lin, David

AU - Motwani, Rajeev

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

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 θ(lg n). For multiply-connected free spaces, the bound is θ(√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 cell complex that is constructed on the basis of critical information changes. It has been implemented and computed examples are shown.

AB - 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 θ(lg n). For multiply-connected free spaces, the bound is θ(√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 cell complex that is constructed on the basis of critical information changes. It has been implemented and computed examples are shown.

UR - http://www.scopus.com/inward/record.url?scp=84947924676&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947924676&partnerID=8YFLogxK

U2 - 10.1007/3-540-63307-3_45

DO - 10.1007/3-540-63307-3_45

M3 - Conference contribution

AN - SCOPUS:84947924676

SN - 3540633073

SN - 9783540633075

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 17

EP - 30

BT - Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Rau-Chaplin, Andrew

A2 - Tamassia, Roberto

PB - Springer

T2 - 5th International Workshop on Algorithms and Data Structures, WADS 1997

Y2 - 6 August 1997 through 8 August 1997

ER -