서지주요정보
Bounded-Curvature motion planning problems = 제한된 곡률을 가지는 로봇이동계획
서명 / 저자 Bounded-Curvature motion planning problems = 제한된 곡률을 가지는 로봇이동계획 / Hyo-Sil Kim.
저자명 Kim, Hyo-Sil ; 김효실
발행사항 [대전 : 한국과학기술원, 2011].
Online Access 원문보기 원문인쇄

등록번호

8022994

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 11032

도서상태

이용가능

반납예정일

#### 초록정보

We study two problems on motion planning for a car-like robot whose turning radius is bounded from below by one and which is allowed to move in the forward direction only (Dubins car model). In the first problem, we consider computing shortest paths visiting a sequence of $n$ points in the plane in a given order. This problem arises naturally in path planning for car-like robots in the presence of polygonal obstacles, and is also a sub-problem of the Dubins Traveling Salesman Problem. Let $F:R^n\rightarrow R$ be the function that maps $(\theta_1,\ldots,\theta_n)$ to the length of a shortest curvature-constrained path that visits the points~$p_1, \ldots, p_n$ in order and whose tangent in $p_i$ makes an angle~$\theta_i$ with the $x$-axis. Let $k$ denote, informally, the number of points~$p_i$ such that the angle~$\angle(p_{i-1}, p_i, p_{i+1})$ is smaller than some given value for $2 < i < n-1$. We show that when consecutive points are distance at least $4$ apart, all minima of $F$ are realized in at most $2^k$ disjoint convex polyhedra where $F$ is strictly convex over each polyhedron and each polyhedron is defined by $4n-1$ linear inequalities. A curvature-constrained shortest path visiting a sequence points can therefore be approximated by standard convex optimization methods, which presents an interesting alternative to the known polynomial-time algorithms that can only compute multiplicative constant-factor approximations. In the second problem, we compare the cost of bounded-curvature shortest paths to the Euclidean distance. Let a configuration of the robot be defined as a pair~$(p, \theta)$, where $p$ and $\theta$ correspond the location and the direction of travel of the robot, respectively. For two given configurations $\sigma$ and $\sigma$, the cost function can be formulated as $dub(d) = \max \{ \ell(\sigma,\sigma) - d \mid \text{$\sigma$,$\sigma$configurations with$d(\sigma,\sigma) = d$}\},$ where $\ell(\sigma, \sigma)$ denotes the length of a shortest curvature-constrained path from~$\sigma$ to~$\sigma$, and $d(\sigma, \sigma)$ denotes the Euclidean distance between $\sigma$ and~$\sigma$. While characterizing $dub$ is a natural and fundamental question (especially, in bounding the approximation ratio of the length of the path with bounded curvature to its Euclidean distance), it is also a relevant question that has repeatedly appeared in the literature, with only partial and unsatisfactory answers so far. We prove that $dub$ has two breakpoints, at $\sqrt{2}$ and at $d_1 \approx 1.59$. For $d \geq d_1$, $\dub(d) = 2\pi$. We give a full characterization of the pairs of configurations realizing $dub(d)$ for a given $d$.

본 논문은 제한된 곡률을 가지는 로봇이동계획과 관련한 두가지 문제를 다룬다. 로봇 이동경로의 최대 곡률은 환경을 적절하게 스케일함으로써 1 로 가정할 수 있으며, 로봇은 앞으로만 움직인다고 가정한다 (두빈스 로봇모델). 첫번째 문제는 $n$개의 점들이 장애물이 없는 환경에서 주어졌을 때, 그 점들을 순서대로 방문하는 가장 짧은 경로를 찾는다. 이 문제는 장애물이 주어진 환경에서 가장 짧은 경로를 찾는 로봇이동계획 문제와 밀접한 관련이 있으며, 또한 두빈스 외판원 문제(Dubins Traveling Salesman Problem)의 부분 문제이다. 곡률이 제한된 경로가 $p_1, \ldots, p_n$개의 점을 순서대로 지날 때 $x$축과 이루는 각도를 $(\theta_1, \ldots, \theta_n)$이라고 하고, $F:R^n \rightarrow R$를 각도~$(\theta_1, \ldots, \theta_n)$이 주어졌을 때, 각각의 점 $p_i$를 $\theta_i$ 방향으로 방문하는 가장 짧은 경로의 길이를 돌려주는 함수라고 하자. 또한 $k$를 $n$개의 점들 중 각도 $\angle{(p_{i-1}, p_i, p_{i+1})}$이 주어진 어떤 값보다 작은 $p_i$의 개수라 하자. 본 논문에서는 두개의 연속된 점이 적어도 거리 $4$만큼 떨어져 있다면 함수~$F$의 모든 최소값은 $n$차원상에 놓여있는 $2^k$개의 볼록 다면체상에서 실현된다는 것을 보여준다. 이때, 각각의 볼록다면체는 $4n-1$개의 선형부등식에 의해서 정의되고 $F$는 그 위에서 항상 순볼록(strictly convex)이다. 이는 $n$개의 점을 순서대로 방문하는 제한된 곡률을 가지는 로봇이동계획 문제가 볼록최적화방법(convex optimization method)를 사용해서 근사치를 구할 수 있다는 것을 보여준다. 지금까지 알려진 방법이 곱의 근사치(multiplicative approximation factor)를 사용한 알고리즘밖에 없다는 것을 감안할 때, 본 논문의 알고리즘은 이 문제에 대한 새로운 대안을 제시한다. 두번째 문제는 제한된 곡률을 가지는 로봇 이동경로의 길이와 유클리드 거리를 비교한다. 로봇의 구성(configuration)을 로봇의 위치와 이동방향의 쌍, 즉 $(p, \theta)$으로 정의하자. 두 구성이 주어졌을 때, 이 비교함수는 다음과 같이 정의될 수 있다: $dub(d) = \max \{ \ell(\sigma,\sigma) - d \mid \text{$\sigma$,$\sigma$configurations with$d(\sigma,\sigma) = d$}\}$. 여기서 $\ell(\sigma,\sigma)$는 두 구성을 연결하는 제한된 곡률을 가지는 경로의 거리 중 가장 짧은 것이고, $d(\sigma,\sigma`)$는 유클리드 거리를 의미한다. 이 함수는 제한된 곡률을 가지는 경로의 길이를 유클리드 거리로 근사할 때, 그 한계를 정하는 매우 자연스럽고 기초적인 문제지만, 많은 문헌에서 이를 부분적으로만 다루었거나, 혹은 만족스럽지 않은 결과만을 돌려주었다. 본 논문은 비교함수~$dub$가 $d_0=\sqrt{2}$와 $d_1 \approx 1.59$에서 중지점(breakpoint)를 가진다는 것을 보인다. 또한 $d$가 $d_1$보다 클 때 $dub(d)=2\pi$임도 보인다. 본 논문에서는 주어진 유클리드 거리 $d$에 주어지는 모든 구성들에 대해서 함수~$dub$를 완벽히 분석한다.

#### 서지기타정보

청구기호 {DCS 11032 v, 112 p. : 삽도 ; 30 cm 영어 저자명의 한글표기 : 김효실 지도교수의 영문표기 : Otfried Cheong 지도교수의 한글표기 : 정지원 학위논문(박사) - 한국과학기술원 : 전산학과, References : p.105-108 Bounded-Curvature Motion Planning Car-like Robot Dubins Path Planning 제한된 곡률 로봇이동계획 자동차 모델 두빈스 길찾기
QR CODE