Path planning in an environment cluttered with obstacles is a basic problem in computational geometry and robotics. Recently, researches on the visibility-based path planning algorithms have attracted much attention, where the robot (or a person) has visibility. These researches divides into two categories: online navigations and pursuit-evasions. In online navigation problems, the robot has to find a target or explore the environment without knowing the geometry of the obstacles. In pursuit-evasions, the robot with visibility has to find a mobile target. In this thesis, we deal with various versions of the visibility-based path planning problems. These problems are natural extensions of the well-known geometric problems including the shortest path problem and watchman route problem and the art gallery problems.
In the first part, we consider an online navigation problem, called online kernel-search problem. The online kernel-search problem is for a mobile robot with 360° visibility to move from a starting point s to the closest kernel point κ within an unknown star-shaped polygon. The goal is to minimize the ratio of the distance traveled by the robot to the length of the shortest s-t path. Icking and Klein first introduced this problem and presented a very intuitive strategy and showed that their strategy is 5.331-competitive. We show that their strategy is, in fact, π+1(?4.14)-competiive. Since it is known that their strategy is no better than (π+1)-competitive, our new analysis is tight. Next, we present a new simple strategy that is $1+2\sqrt{2};(＜ 3.829)$-competitive.
In the second part, we consider visibility-based pursuit-evasion problems stated as follows: given a polygonal region, a searcher with visibility, and an {\em unpredictable} intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In particular, we mainly discuss about the following question. Given a simple polygon with a door (i.e., penetrable vertex) d, can the searcher find the intruder within the polygon in such a way that the intruder couldn't make a dash for the door? We give a characterization of the class of regions that admits a 'search strategy' and present an $O(n^2)$-time algorithm for constructing a search schedule, if one exists, for an n-sided region. We also consider several variants and present a characterization of each region that is searchable. Interestingly, our characterizations imply that each of the above regions searchable by the searcher with omnidirectional visibility (i.e. 360° visibility) is also searchable by the searcher having two flashlights (i.e. ray visibility). As a by-product, we improves the previous time complexity of the corridor search problem, by a factor of log n.
장애물이 있는 지형에서 경로계획 알고리즘은 계산기하학과 로보틱스에서 많이 연구되어 왔다. 최근 들어서는 경로를 찾는 로봇(또는 사람)이 가시능력을 가지고 있는 경우를 다루는 가시기반 경로계획 알고리즘에 관한 연구가 활발하다. 대표적인 예로 미지의 지형에서 목표물을 찾거나 지형의 지도를 그리는 온라인 경로계획 알고리즘(online navigation)과 움직이는 목표물을 찾는 가시기반 탐색 알고리즘(visibility-based pursuit evasion) 등이 있다. 본 논문에서는 다각형 모양의 장애물 내부에서 가시기반 경로계획 문제를 다룬다.
본 논문은 크게 두 부분으로 구성되어 있다. 첫번째 부분에서는 제한된 모양의 별형 다각형 내에서의 온라인 경로 계획 문제를 다룬다. 별형 다각형은 내부의 어떤 점에서 다각형의 모든 경계가 보이는 것을 말한다. 로봇은 다각형의 모양을 알지 못하고 대신 가시능력을 이용하여 주위에 관한 정보를 얻으면서 경로를 결정하여 모든 경계가 보이는 부분으로 움직여야 한다. 로봇은 짧은 경로를 통해 목표에 도달하여야 하는데, 로봇이 움직인 거리와 최단 거리 (지형을 알고 있는 로봇이 움직이는 경로) 사이의 비를 최소화하는 것이 목표이다. 본 논문에서는 기존에 알려진 가장 좋은 알고리즘의 성능 분석을 개선하여 이 알고리즘이 최단 경로의 π+1(＜4.15)배의 경로를 보장하는 것을 보였다. 또한 이보다 개선된 성능을 가지는 새로운 알고리즘을 제시하였는데 이 알고리즘은 $2\sqrt{2}+1(＜3.829)$배의 경로를 보장한다.
두 번째 부분에서는 다각형 내부에서 움직이는 목표물을 찾는 가시기반 탐색문제를 다룬다. 특히 다각형 경계에 한 점이 주어질 때, 그 점을 출발한 탐색자가 다각형 내부의 목표물이 그 점에 도착하기 전에 목표물을 찾아낼 수 있는가를 검사하고 그때의 경로를 생성하는 방 탐색 문제를 고려한다. 본 논문에서는 탐색 가능한 다각형의 필요충분 조건을 제시하고 탐색 가능한지를 검사하는 $O(n^2)$ 시간 알고리즘을 제시하였다. 또한 탐색 가능한 다각형에 대한 탐색 경로를 찾는 $O(n^2)$ 시간 알고리즘도 제시하였고 이는 최적 알고리즘이다. 이 결과들은 제한된 다각형만을 다룬 기존의 연구 결과들을 일반화하였고 알고리즘의 성능도 개선하였다. 마지막으로 여러 가지 탐색 문제의 변형을 고려하고 필요충분 조건과 효율적인 알고리즘을 제시하였다.
