An autonomous mobile robot equipped with cameras or sensors can perform vision tasks such as model building, target tracking, or target finding. In this thesis we investigate a target finding problem that is known as the visibility-based pursuit-evasion problem. The goal of this problem is to plan the motion for a robot guard in a 2D workspace so as to guarantee that an evasive target will eventually be detected. The target is assumed to have an unknown initial position and to move unpredictably at an arbitrary speed. A robot guard moving with bounded speed should explore the workspace so that the target is driven into a corner. What makes this problem challenging is the issue of recontamination. It occurs when the target sneaks back to places already explored, which may allow the target to evade detection forever. We discuss motion strategies of robots to ensure the detection of the target regardless of how the target moves.
The visibility-based pursuit-evasion problem is an interesting variant of the well-known art-gallery problem and watchman route problem: the former deals with stationary guards, and the latter with stationary targets. Our setting is dynamic, as both guard and target are moving. It models many practical applications such as military operations, toxic cleanup, surveillance systems, and architectural design of secure buildings. For example, suppose a security system of a building that involves autonomous mobile robots with vision. Any motion strategy for the robots to detect an unpredictable target provides a patrolling route that guarantees any intruder to be detected. Motion strategies can also be used for locating another mobile robot that is malfunctioning or locating people in a search-rescue effort. With these diverse applications, the visibility-based pursuit-evasion problem has attracted much attention and produced many variations for the last decade.
To detect a target, a robot is equipped with omnidirectional vision or carries a number of rotating beams. In this thesis, we consider three kinds of robot searchers: the ∞-searcher who can see in all directions simultaneously, the 1-searcher who carries one rotating beam, and the 2-searcher with two beams. We also consider two guards which have additional constraints: they should move along the boundary of workspace and always be guarded by each other. Although their movements are rather restricted, they have some merits: hardware is less expensive and communication between robots is easier.
The polygonal workspaces we consider are basically simple polygons. We also consider two variants: a corridor has two doors on its polygonal boundary, and two guards walk on the two boundary chains separated by the two doors. The other variant, called a room, has one door, and the searcher should find the target in such a way that the target cannot escape through the door. The problem of searching a simple polygon without any door has also been an important topic of research. In these three types of polygons, the capabilities of searchers having different degrees of visibility were investigated[4,11,14,18,21,37].
In this thesis we first consider two guards searching a room. We give a characterization of the class of rooms searchable by two guards, and a searching algorithm for the two guards. Secondly, for a polygon without a door, we suggest the class of polygons searchable by a 1-searcher, and an O(nlogn)-time algorithm to test if a given polygon is searchable. Finally, we consider the ∞-searcher. For the ∞-searcher, the problem of characterizing the searchable polygons has been open for a long time[37]. The first algorithm to search a polygon by an ∞-searcher was proposed in [10], but no tight bound is known. We present a characterization of the class of polygons searchable by the ∞-searcher. We also show that every polygon searchable by the ∞-searcher is searchable by the 2-searcher, which proves a conjecture suggested in 1992[37]. It means that the $O(n^2)$-time algorithm for the 2-searcher[23] is also complete for the ∞-searcher, where n is the number of edges of a given polygon.
시각 장치나 센서를 갖추고 자율적으로 이동하는 로봇은 이차원 작업 공간에서 지도 작성, 목표물 추적, 목표물 탐색 등의 작업을 수행할 수 있다. 본 논문에서는 가시성 기반 회피 및 탐색 문제로 알려져 있는 목표물 탐색 문제를 연구한다. 이 문제의 목적은, 움직이는 목표물이 반드시 발견되도록 로봇의 동작을 계획하는 것이다. 목표물의 초기 위치는 알 수 없고, 목표물은 임의의 속도로 예측 불가능하게 움직인다고 가정한다. 반면에 로봇은 제한된 속도로 움직이면서 작업 공간을 탐색하며 목표물을 찾게 된다. 이 문제를 어렵게 만드는 요인은 재오염이라고 할 수 있다. 재오염이란 로봇이 이미 탐색했던 영역에 목표물이 다시 숨어들어가는 것을 말하며, 이것이 계속 반복되면 목표물을 영영 찾지 못하는 경우도 발생한다. 우리는 주어진 로봇이 성공적인 탐색을 수행할 수 있는 지형과 그렇지 못한 지형을 기하학적으로 분석하고, 로봇의 효율적인 탐색 전략을 제시한다.
로봇과 목표물이 동시에 움직이는 이러한 동적인 세팅은 감시 및 경비 시스템이나 군사 작전, 보안 중심의 건물 설계 등의 실용적인 응용들에 적용할 수 있다. 예를 들어서 자율적으로 이동하는 로봇들을 이용하는 건물의 감시 시스템에서, 위와 같이 계산된 탐색 전략은 침입자를 찾아내는 순찰 경로로 이용될 수 있다. 목표물을 탐지하기 위해서 로봇은 기본적으로 전방위 시각을 가지거나 몇 개의 회전가능한 광선을 소지하도록 구현된다. 본 논문에서는 전방위 시각을 가지는 전방위-탐색자와 한 개의 회전하는 광선을 가진 1-탐색자, 그리고 두 개의 광선을 각기 회전시키는 2-탐색자를 다룬다. 또한 작업 공간의 가장자리를 따라 이동하는 제한적인 모델인 2-가드를 이용하는 탐색 전략도 소개한다. 2-가드는 가장자리를 따라 이동할 뿐 아니라 두 명의 가드가 항상 서로에 의해서 감시된다는 제약 조건을 가진다. 이러한 조건들은 가드의 움직임을 제한하는 반면에, 하드웨어 비용을 감소시키고 로봇 간의 커뮤니케이션을 용이하게 한다는 장점을 가진다.
본 논문에서는 한 개의 출구를 가지는 방에서 2-가드를 이용하여 탐색하는 문제에서 탐색 가능한 종류의 방들을 규명하고, 2-가드의 탐색 전략을 제시하였다. 주어진 방의 탐색 가능 여부를 검사하는 것은 O(n log n) 시간에, 그리고 실제로 탐색 알고리즘을 수행하는 것은 O($n^2$ log n) 시간에 가능하다. 일반적인 단순 다각형을 탐색하는 문제에서는 1-탐색자가 탐색할 수 있는 다각형의 종류를 제시하고, 주어진 다각형이 탐색 가능한지를 테스트하는 O(n log n) 시간의 알고리즘을 제안하였다. 또한 전방위-탐색자가 탐색할 수 있는 다각형의 필요충분 조건을 제시함은 물론, 전방위-탐색자가 탐색할 수 있는 다각형 클래스와 2-탐색자가 탐색할 수 있는 다각형 클래스가 같다는 것을 증명하였다. 이로써 2-탐색자에 대한 $O(n^2)$ 시간 알고리즘을 전방위-탐색자에게 그대로 적용할 수 있게 되므로, 전방위-탐색자에 대한 효율적인 알고리즘이 제공되었다.
