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.
Description:
A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. x, 65 p.