Visibility-based pursuit-evasion in a polygonal environment

Leonidas J. Guibas, Jean Claude Latombe, Steven M. LaValle, David Lin, Rajeev Motwani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 θ(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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings
EditorsAndrew Rau-Chaplin, Frank Dehne, Jorg-Rudiger Sack, Roberto Tamassia
PublisherSpringer-Verlag
Pages17-30
Number of pages14
ISBN (Print)3540633073, 9783540633075
StatePublished - Jan 1 1997
Externally publishedYes
Event5th International Workshop on Algorithms and Data Structures, WADS 1997 - Halifax, Canada
Duration: Aug 6 1997Aug 8 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1272
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Workshop on Algorithms and Data Structures, WADS 1997
CountryCanada
CityHalifax
Period8/6/978/8/97

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Guibas, L. J., Latombe, J. C., LaValle, S. M., Lin, D., & Motwani, R. (1997). Visibility-based pursuit-evasion in a polygonal environment. In A. Rau-Chaplin, F. Dehne, J-R. Sack, & R. Tamassia (Eds.), Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings (pp. 17-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1272). Springer-Verlag.