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$를 완벽히 분석한다.
