Pursuit Evasion in Simple Polygons

Abstract

Pursuit evasion in simple polygons is fundamentally searching for an evader in a simple polygon. Popular problems in polygon searching include the room search problem and the two guard problem. Many practical applications, such as search for an evader in a dark house, rescue of a victim in a dangerous building and surveillance with autonomous mobile robots, can be modeled by polygon search problems. In this thesis, we investigate two problems related to polygon searching. The rst problem which we study is searching for a mobile evader in a simple polygonal room with two doors by a boundary 2-searcher. The boundary 2-searcher is a searcher which is equipped with two ashlights with a limited visibility, i.e., only in the direction of ray shots emanating from his position, which can only move on the boundary of polygonal region. We give necessary and su cient conditions for a simple polygonal room to be searchable by a boundary 2-searcher. We propose an algorithm for generating the search schedule, if it exists. We also show that searching a room using a boundary 2-searcher requires at most O(n2) edge traversals. The second problem which we consider is searching for a mobile evader in a simple polygon using a pair of searchers. Each searcher is equipped with a single ashlight and he can see only along the direction of ray emanating from its position. The searchers are allowed to move on the boundary of the simple polygon. The pair of searchers has to detect the evader at least once using any of two ashlights. We present three necessary conditions for a simple polygon to be searchable by a pair of searchers. We also study the capabilities of a boundary and non-boundary pair of searchers.