격자 지도의 골격화를 이용한 Informed RRT^* 기반 경로 계획 기법의 개선

1. 서 론

경로 계획은 로봇을 목적지까지 안전한 경로로 신속하게 이동시키는 것으로, 지금까지 많은 연구가 이루어져 왔다. 그 러나 고차원 환경에서의 적용 문제나 국소 최저점(local-minima) 문제로 인해 그 사용이 제한되어 왔다[1]. 국소 최저점에 빠지 지 않고 고차원 환경에도 적용이 가능한 샘플링 기반 알고리 즘인 RRT (Rapidly exploring Random Tree)[2]가 제안되었다. RRT는 상태 공간 전역에 대해 임의의 위치에 포인트(point)를 생성하고, 시작점부터 트리(tree)를 성장시켜 나가 목적지까지 신속하게 경로를 생성하는 알고리즘이다. 하지만 기본적인 RRT 알고리즘은 이미 생성된 트리를 수정하지 않기 때문에, 경로의 거리 상 최적 비용을 갖는 경로 생성이 보장되지 않는다.

이를 개선하기 위해 제안된 RRT*[3]는, 상태 공간 상에서 생 성된 임의의 포인트가 트리를 구성하는 노드(node)를 대체하 여 비용을 줄일 수 있는 경우, 기존 노드를 대신하여 트리를 구 성하게 된다. 이 과정을 재귀적으로 거치면 트리 상의 경로가 최적 비용 경로로 수렴하게 된다.

하지만, Iram Noreen[4]은 RRT* 기반 알고리즘들의 한계로 느린 수렴 속도와 큰 메모리 요구성, 좁은 통로에서의 경로 생 성 지연 문제를 지적한다. RRT*는 상태 공간 전역에 걸쳐 트 리가 확장된다. 따라서, 최적의 비용을 갖는 경로와 상관없는 영역에 많은 샘플링 시간을 투자하게 되어 최적 비용 경로로 의 수렴이 느리고, 생성되는 노드의 수가 증가함에 따라 큰 메 모리가 요구된다. 또한, 복도나 문과 같은 좁은 통로를 지나는 경로 생성이 필요한 경우, 좁은 통로 부근에 노드가 생성될 확 률이 적기 때문에 최적 경로 생성이 지연될 수 있다. 위 문제를 부분적으로 해결한 기법들[5, 10-14]이 존재하지만, 세 부분에서 모두 개선하지는 못하였다. 이 내용에 대해서는 2장에서 다룰 예정이다.

본 논문에서는 느린 수렴 속도, 큰 메모리 요구성, 좁은 통로 에서의 경로 생성 지연 문제를 모두 개선할 수 있는 Informed RRT*[5] 기반 경로 계획 기법을 제안한다. 제안된 기법은 수렴 속도와 메모리 요구성을 개선한 Informed RRT*를 이용하여 경로 최적화를 진행한다. 이때, 초기 경로 생성을 위해 RRT* 가 아닌 골격화(skeletonization) 알고리즘을 이용한다. 골격화 알고리즘으로 생성된 경로는 RRT*와 달리 좁은 통로에 의해 경로 생성이 지연되지 않고 신속한 경로를 생성한다. 하지만, 골격화 알고리즘으로 생성된 경로는 최적 비용 경로보다 더 큰 비용을 갖게 되어 경로 개선이 필요하다. 따라서, 제안된 기 법을 이용하면 복잡한 환경 및 좁은 통로가 존재하는 환경에 서 보다 최적 비용에 근사한 초기 경로를 얻으므로 경로 탐색 시간을 줄여 신속한 경로 계획이 가능하다.본 논문의 구성은 다음과 같다. 2장에서는 기존 경로 계획 알고리즘들을 살펴보고 본 논문에서 제안하는 알고리즘과의 차이점을 비교한다. 3장에서는 골격화를 이용한 초기 경로 생 성 방법 및 Informed RRT*에 의한 경로 최적화 방법에 대해 설 명한다. 4장에서는 시뮬레이션을 통해 제안된 알고리즘의 성 능 및 타당성을 검증한다. 5장에서는 결론을 맺는다.

2. 기존 경로 계획 알고리즘의 분석

이 장에서는 기존 경로 계획 알고리즘들을 비샘플링 기반 기법과 샘플링 기반 기법으로 분류한다. 샘플링 기반 기법들 은, ‘샘플링 기반을 대표하는 기법’, ‘골격화를 이용하는 RRT 기반 기법’, ‘서론에서 언급한 세 가지 문제(수렴 속도, 메모리 효율성, 좁은 통로 문제)를 개선하기 위한 RRT* 기반 기법’들 로 재분류하여 각각에 대한 특징 및 장단점을 살펴보고, 제안 기법과 비교를 수행한다.

경로 계획 시, 널리 이용되는 대표적인 비샘플링 기반 기법 들로 A*[6], 포텐셜 필드 방법(Potential field method)[7], GVG (Generalized Voronoi Graph)[8]들이 존재한다. A*는 휴리스틱 (Hueristic) 방식을 이용하는 기법으로, 시작점부터 목적지까 지 경로를 생성하여 최적 비용 경로에 근접한 경로를 생성할 수 있는 장점이 존재한다. 하지만, 한번 생성된 경로는 경로 개 선이 어렵고, 경로 생성을 위해 많은 노드를 탐색해야하므로 많은 연산 시간이 소요된다. 포텐셜 필드 방법은 로봇과 도착 점 사이 작용하는 인력장과 로봇과 기존 장애물 사이에 작용 하는 척력장의 관계를 이용하여 경로를 추출한다. 수학적 분 석이 간편하지만, 국소 최저점에 빠질 수 있는 확률이 존재하 는 단점이 있다. GVG는 지도 상에서 장애물들과 거리를 최대 화 하는 지점에 경로를 생성한다. 국소 최저점에 빠지지 않는 경로 생성이 가능하지만, 경로 개선이 어려우므로 경로 비용 을 줄이는데 한계가 있다. 제안 기법은 위 방식들과 달리 경로 개선이 수월하고 국소 최저점에 빠지지 않으며 신속하게 최적 비용 경로로의 수렴이 가능하다.

샘플링 기반 경로 계획 기법 중 하나인 PRM (Probabilistic RoadMap)[9]은 경로 탐색 이전에 지도 상에 임의로 노드들을 배치한 후, 가시성이 확보되는 근접한 노드끼리 모두 연결하 여 그래프를 생성한다. 이후, 사용자가 시작점과 도착점만 지 정하면 사전 작업을 통해 생성한 그래프를 이용하여 신속한 경로 생성이 가능하다. 하지만, 최적 비용 경로가 좁은 통로를 지나는 경우 최적 비용 경로에 근사한 경로를 생성할 확률이 낮다. 이에 반해, 골격화를 이용하는 제안 기법은 좁은 통로에 의한 영향을 받지 않는다.

샘플링 기법들 중, 지도에 골격화를 적용한 후, RRT 샘플링 을 이용하여 좁은 통로에 영향을 받지 않고 신속한 경로 생성 을 진행할 수 있는 기법으로 MARRT[10]와 Skilled-RRT[11] 가 존재한다. MARRT는 지도에 골격화를 적용하여 중심축 (medial axis)을 생성한다. 이후, 생성된 중심축 상에 RRT 트리 를 성장시켜 경로를 생성한다. 이때, 트리의 성장은 RRT 샘플 링을 이용한다. Skilled-RRT는 골격화를 이용하여 생성한 경 로 부근에 샘플링을 편향시켜 경로를 생성한다. 두 경로 계획 기법 모두 골격화를 이용하기 때문에, 좁은 통로에 의해 경로 생성이 지연되지 않고 신속한 경로 생성이 가능한 장점이 있 지만, 경로 개선이 어려운 단점이 존재한다. 제안 기법도 골격 화를 이용하기 때문에 좁은 통로에 영향을 받지 않는 장점이 있다. 그러나, 위의 두 기법과 달리, 골격화로 생성된 경로에 Informed RRT* 샘플링을 적용하기 때문에 쉽게 경로 개선이 가능하다.

샘플링을 기반으로 하는 RRT* 기반 기법들 중, 수렴 속도, 메모리 효율, 좁은 통로 지연 문제 중 일부분을 개선한 기법들 로는 RRT*FN[12], RRT*-SMART[13], Cloud RRT*[14], Informed RRT*[5]가 존재한다. RRT*FN은 트리에 포함된 노드의 수를 사용자가 지정한 최대 노드의 수 까지만 유지되게 하여 메모 리 효율을 높였다. 하지만, 경로 개선 시, 최적 비용 경로로의 수렴 속도가 느린 단점이 존재한다. RRT*-SMART는 RRT*를 이용하여 생성된 초기 경로를 삼각부등식(triangular inequality) 을 이용하여 최적화 시키고, 트리를 구성하는 노드 부근에 샘 플링을 편향 시킨다. 따라서, 최적 비용 경로로의 수렴 속도가 빠르고, 메모리를 보다 효율적으로 이용할 수 있다. 그러나, 초 기 경로가 최적 비용 경로와 다른 경로로 생성된 경우, 최적 비 용 경로로의 수렴 가능성이 낮아진다[5]. Cloud RRT*는 GVG 를 이용하여 샘플링 영역을 부분적으로 편향시킨다. 이산적으 로 분할된 원 형태의 샘플링 영역을 줄이는 방식으로 수렴 속 도를 개선하였다. 하지만, 샘플링이 진행됨에 따라 최적 비용 경로로의 수렴 시, 최적 비용 경로 부근으로 편향된 샘플링 원 들은 주변 샘플링 영역의 일부 확률만 가져오므로 수렴 속도 에 한계가 존재한다. Informed RRT*는 RRT*를 이용하여 초 기 경로를 생성한 후, 시작점과 도착점, 경로의 길이를 이용한 타원을 구성하여 최적 비용 경로가 생성될 수 있는 영역에 한 정하여 샘플링을 진행한다. 따라서, 최적 비용 경로로의 수렴 속도와 메모리 요구성을 개선시키며 좁은 통로 환경에서도 보 다 빠른 경로 생성이 가능하다. 하지만, 경로 개선 시, 경로의 비용이 최적 비용에 근접할수록 샘플링 영역이 감소하므로 수 렴 속도가 증가하는데, 생성된 초기 경로의 비용이 최적 비용 과 차이가 많을수록 수렴 속도가 감소한다. 따라서, 초기 경로 의 비용에 따라 최종 경로 생성 시간과 메모리 효율이 크게 좌 우되는 단점이 존재한다. 위에 언급된 RRT* 기반 기법들은 수 렴 속도, 메모리 효율, 좁은 통로 지연 문제에 대해 부분적으로 개선은 있었지만 모든 부분을 동시에 개선하지는 못하였다. 특히, 위 기법들 모두 초기 경로 생성 시, 좁은 통로에서 경로 생성 지연이 발생하는 문제점이 존재한다. 이에 반해, 제안 기 법은 초기 경로 생성 시, 골격화를 이용함으로써 좁은 통로에 의한 경로 생성 지연이 발생하지 않는다. 또한, 골격화를 이용 하여 생성된 초기 경로의 비용이 최적 경로의 비용과 큰 차이 가 나지 않아 Informed RRT* 샘플링 수행 시, 빠른 수렴이 진 행된다. 빠른 수렴이 진행됨에 따라 생성되는 노드의 수도 적 어지므로 메모리 효율도 증가한다.

3. 격자 지도의 골격화를 이용한 Informed RRT* 기반 경로 계획 기법

이 장에서는 격자 지도 이미지 골격화를 이용한 초기 경로 생성 방법과 Informed RRT*에 의한 경로 최적화 방법에 대해 설명한다.

3.1 초기 경로 생성

3.1.1 격자 지도 골격화

이미지 골격화 알고리즘은 이진화된 이미지에서 물체의 두 께를 1 pixel 단위로 만들어 물체의 형태학적 특성을 최대한 압 축하여 나타내는 기법이다[17]. 골격화 알고리즘을 경로 계획 에 적용하면 국소 최저점에 빠지지 않는 초기 경로를 신속하 게 얻을 수 있다. 또한, 골격화로 생성한 경로는 우회하지 않고 최적 비용 경로 방향으로 빠르게 수렴할 수 있는 초기 경로를 생성할 수 있다. 이와 비슷한 결과를 도출하는 기법으로 GVG (Generalized Voronoi Graph)[8]를 이용한 방법이 존재한다. 하 지만, GVG는 격자 지도와 같은 복잡한 환경에서 골격 이미지 를 생성하기 위해 정점[15]이나 형상[16]과 같은 특징 추출이 필 요한 반면, 골격화는 특징 추출이 필요하지 않아 보다 간단하 게 수행이 가능하므로 제안 기법에서는 골격화를 이용하였다. 골격화 알고리즘에는 대표적으로 형태적(morphological) 방식 [17]과 zhang-suen 방식[18], guo-hall 방식[19]이 존재한다. 제안된 기법에서 골격화 알고리즘은 빠른 초기 경로 생성을 위해 사 용되므로, 위 세 방식 중에서 연산 시간이 가장 빠른 방법을 선 정하였다. Gulshan Goyal은 zhang-suen 방식과 guo-hall 방식 의 성능 비교를 실시하였는데, zhang-suen 방식이 연산 시간과 최대 신호 대 잡음 비 방면에서 guo-hall에 비해 우수함을 입증 하였다[20]. [Table 1]은 형태적 방식과 zhang-suen 방식의 연산 시간 비교 결과로 ‘Intel Lab.’[21] 격자 지도에 대해서 알고리즘 마다 10회씩 수행한 결과의 연산 시간 평균값이다. 형태적 방 식의 평균 연산 속도가 약 2배정도 더 빠른 것을 확인하였고, 따라서 Informed RRT* 개선 기법을 위해 형태적 골격화 알고 리즘을 적용하기로 하였다.

Table 1

Computational time of Morphological skeletonization and Zhang-Suen skeletonization for Intel Lab. grid map

3.1.2 노드 검출

3.1.1에서 격자 지도 이미지의 골격화를 수행한 이후 얻은 이미지에서는 RRT 기반 알고리즘에서 사용될 노드 정보를 얻 을 수 없다. 따라서, 본 논문에서는 Harris Corner Detector[22]를 이용하여 골격 이미지로부터 노드 정보를 추출한다. 그러나 Harris Corner Detector를 이용하여 노드를 추출하면, 한 코너 에서 중복으로 노드가 검출되는 경우가 발생한다. 중복으로 생성된 노드는 초기 최단 경로 산출 시에 연산 시간을 지연시 키는 요인이 되므로, 코너 검출 후 사용자가 지정한 반경 안에 속하는 노드들은 경로 생성에서 제외한다.

3.1.3 초기 최단 경로 산출

3.1.2에서 Harris Corner Detector를 이용하여 얻은 노드들의 좌표만으로는 초기 경로를 산출할 수 없으므로, 최소 신장 트 리(Minimal Spanning Tree) 알고리즘을 이용한다. 최소 신장 트리 알고리즘은 대표적으로 Prim 알고리즘[23]과 Kruskal 알 고리즘[24]이 존재한다. Kruskal 알고리즘은 노드 간의 거리가 가장 가까운 부분부터 연결하여 트리를 생성하기 때문에 모든 노드들 간의 거리를 계산해야 하므로 연산량이 많다. 반면, Prim 알고리즘은 경로의 출발 지점부터 트리 생성을 시작하 고, 트리에 등록된 노드는 연산에서 제외하기 때문에 연산량 이 훨씬 적어 신속한 초기 경로 생성이 가능하다. 따라서, 초기 경로 생성을 위해 Prim 알고리즘을 이용하였다.

제안된 기법에서 Prim 알고리즘은 사용자가 지정한 시작점 을 설정하여 시작점에서 가장 가까운 노드를 찾아 트리를 확 장하게 된다. 트리의 노드들에서 아직 연결되지 않은 노드 중 가장 가까운 노드를 찾아 연결하는 과정을 모든 노드가 트리 에 연결될 때까지 진행하게 된다.

3.2 경로 개선

제안된 기법에서는, 초기 경로 생성 후 보다 신속한 경로 최 적화를 위해서 Informed RRT*[5]의 샘플링 기법을 이용한다. Informed RRT*는 지도 전역에서 샘플링을 진행하는 RRT*와 달리, 최적 비용을 갖게 될 것으로 예상되는 영역 내에서만 샘 플링을 진행하므로 연산 시간 면에서 우수한 성능을 보인다.

Informed RRT*는 초기 경로 생성을 위해 RRT*를 이용 하지만, 경로 최적화 과정에서 샘플링 영역을 타원 형태로 제한한다. 이때, 타원의 형태는 [Fig. 1]과 같다. [Fig. 1]에 서 $$ P_{start}$$ 는 시작점, $$ P_{goal}$$ 은 도착점, $$ C_{\min }$$ 은 시작점과 도착점 의 거리, $$ C_{best}$$ 는 트리의 경로 비용이다. 타원의 높이는 $$ \sqrt{C_{best}^2-C_{\min }^2}$$ 로 정의되는데, 타원의 두 초점에서 타원 위 의 한 점까지 거리의 합이 타원의 장축과 같다는 성질을 이용한다. 따라서, 타원 내부에는 $$ C_{best}$$ 의 비용을 갖는 경로 보다 적은 비용을 갖는 경로가 생성 될 수 있는 경우의 수 를 모두 포함하게 된다[25]. 또한, 경로가 개선 됨에 따라 $$ C_{best}$$ 가 점차 최적 비용으로 수렴하고 타원의 크기 또한 작 아지므로 샘플링의 효율도 높아져 보다 신속한 경로의 최 적화가 가능하다.

Fig. 1

Ellipse-shaped sampling region of Informed RRT*[5]

3.3 골격화를 이용한 Informed RRT* 기반 경로 계획 알고리즘

제안된 격자 지도의 골격화를 이용한 경로 계획 알고리즘 은 [Fig. 3]과 [Table 2]의 Algorithm 1과 같다. 알고리즘 입력은 격자 지도 이미지 $$ Imag{e}_{input}$$ , 시작점 $$ P_{start}$$ , 도착점 $$ P_{goal}$$ , 중복 노드 삭제 반경 $$ r$$ 이다. 먼저, $$ Tree$$ 및 경로 개선에 사용될 변 수를 초기화 하고(line 1), 격자 지도 이미지를 골격화한다(line 2). 이때 얻어진 골격 이미지의 예는 [Fig. 2 (a)]와 같다. 골격 이미지에서 Harris corner를 추출하고, 중복 노드 삭제 반경 $$ r$$ 을 적용하여, 초기 경로 생성을 위한 노드의 위치를 획득한다 (line 3). 획득된 노드의 위치는 [Fig. 2 (b)]와 같다. 이 노드들을 Prim 알고리즘을 이용해 최적 비용 경로에 근접하도록 연결하 여 초기 경로를 얻는다(line 4, [Fig. 2 (c)]). 생성된 초기 경로와 [Fig. 1]의 타원 제한 조건을 적용하여 Informed RRT* 샘플링 을 진행한다(line 6, [Fig. 2 (d)]). Informed RRT* 샘플링을 통해 생성된 point를 $$ Tree$$ 에 노드로 등록하며, 이 과정은 RRT*를 따른다 (line 7~14). 경로 개선 과정(line 5-14)은 사용자가 지정 한 횟수 혹은 비용이 될 때까지 반복된다. 경로 개선이 완료되 면 $$ Tree$$ 를 반환한다(line 15, [Fig. 2 (e)]).

Fig. 2

Procedure of the proposed path planning algorithm using a gridmap image skeletonization: (a) Skeletonization of the gridmap (b) Node extraction (c) the initial path calculation (d) Sampling using Informed RRT* (e) the final optimized path

Fig. 3

Proposed algorithm using gridmap skeletionization

Table 2

Pseudocode of the proposed algorithm using gridmap skeletonization

4. 시뮬레이션

4.2 시뮬레이션 결과 및 분석

[Fig. 4] ~ [Fig. 6]는 시작점과 도착점이 다른 세 가지 시뮬레 이션 결과의 예이다. 파란색 선은 RRT*의 트리, 녹색 선은 Informed RRT*의 타원, 붉은색 선은 최종 경로를 나타낸다. Informed RRT*는 RRT*를 이용한 초기 경로 생성 시 샘플링이 진행됨에 따라 지도 전역에 걸쳐 트리가 생성되었다. 하지만, 제안 알고리즘은 골격화를 이용하여 생성된 초기 경로 부근의 영역에만 트리를 생성하여 경로의 비용 최적화를 진행하였다. 이는, 골격화로 생성한 초기 경로의 비용이 최적 경로의 비용 에 근접하기 때문이다. 따라서, 최적 경로로의 수렴 시간을 단 축시키고, 낭비되는 노드를 줄여 메모리 효율을 높일 수 있다.

Fig. 4

Path planning results - Simulation 1, starting position (538, 511), goal position (323, 273), termination threshold < 460 pixels (a) Informed RRT*, (b) Informed RRT* with initial path generated by A*, (c) the proposed method

Fig. 5

Path planning results - Simulation 2, starting position (63, 66), goal position (143, 274), termination threshold < 290 pixels (a) Informed RRT*, (b) Informed RRT* with initial path generated by A*, (c) the proposed method

Fig. 6

Path planning results - Simulation 3, starting position (63, 66), goal position (176, 561), termination threshold < 520 pixels (a) Informed RRT*, (b) Informed RRT* with initial path generated by A*, (c) the proposed method

[Table 3] ~ [Table 5]에서 볼 수 있는 바와 같이, 제안된 알 고리즘의 초기 경로 생성 시간이 A* 초기 경로를 이용한 Informed RRT*에 비해 약 3.6배에서 43배까지 감소되었다. 이 는 A*의 경로 생성 시간이 시작점과 도착점의 위치, 장애물의 위치에 대해 큰 영향을 받기 때문이다. Informed RRT*에 비해 제안 알고리즘의 초기 경로 생성 시간은 최소 약 4배에서 최대 29배 감소되었다. 또한, 골격화를 이용한 알고리즘의 초기 경 로 생성 시간 표준 편차는 0.04 이하로 작은 값을 보여, 초기 경 로 생성 시간 차이가 적음을 입증하였다. 반면에, Informed RRT*의 표준 편차는 최소 약 11에서 최대 약 150이므로 매 시 행 마다 큰 차이를 보인다. 이는 초기 경로 생성을 위해 사용되 는 RRT*가 좁은 통로에 효율적으로 대처하지 못하기 때문이 다. 이로써, 제안된 알고리즘은 골격화를 이용하여 좁은 통로 와 상관 없이 신속한 초기 경로 생성이 가능함을 입증할 수 있 다. A*와 골격화는 같은 조건에서 항상 같은 경로를 생성하기 때문에 초기 경로 비용의 표준 편차가 0으로 일정하다. 골격화 를 이용하여 생성된 초기 경로의 비용은 RRT*를 이용하여 생 성된 초기 경로에 비해 시뮬레이션 1에서는 약 250 pixel, 시뮬 레이션 3에서는 약 130 pixel 단축된 것을 확인할 수 있다. 시뮬 레이션 2에서는 Informed RRT*의 RRT* 의한 초기 경로가 약 50 pixel 짧게 생성되었지만, 초기 경로 생성을 위해 29배 정도 더 긴 시간이 소요되었다. 초기 경로 비용의 표준 편차는 Informed RRT*의 경우 경로에 따라 큰 차이를 보였다. 시뮬레 이션 1에서 395.42, 시뮬레이션 2에서 88.56, 시뮬레이션 3에 서 232.87이다. 제안된 알고리즘은 모든 시뮬레이션에서 0이 며, 이는 골격화를 이용한 알고리즘이 훨씬 안정적인 초기 경 로를 생성하는 것을 의미한다. A*를 이용한 Informed RRT*는 제안 알고리즘에 비해 초기 경로의 비용이 모든 시뮬레이션에 서 더 적지만, 초기 경로 연산 시간이 최소 약 3.6배 이상 더 소 요된다. 총 연산 시간은 세 시뮬레이션 모두 제안된 알고리즘 을 사용한 결과가 Informed RRT*에 비해 약 3~10배, A*를 이 용한 Informed RRT*에 비해 약 1.7~2.4배 덜 소요되었다. RRT*를 이용하여 초기 경로를 생성하는 Informed RRT*에 비 해, 제안된 알고리즘은 초기 경로 생성 시 좁은 통로에 영향을 받지 않고 최적 비용 경로에 근접하여 빠르게 진행하였기 때 문이다. 전체 노드 수를 비교해 보면, 제안 알고리즘에 의해 생 성된 노드 수가 Informed RRT*에 비해 평균적으로 약 900 ~ 2,800개 더 적고 편차가 약 1,000이상 적다. 따라서 생성된 노 드의 수가 더 적다는 것은 메모리 사용량이 더 적다는 것을 의 미하기 때문에, 제안된 알고리즘이 Informed RRT*에 비해 메 모리 효율성이 더 높다는 것을 입증할 수 있다. 제안된 알고리 즘의 생성된 노드 수가 A*를 이용한 Informed RRT*에 비해 약 1.5~4배정도 더 많다. 이는 A* 알고리즘 수행 시 트리에 포함 되지 않은 노드의 수는 고려되지 않았기 때문이다.[Table 4]

Table 3

Path planning results - Simulation 1

Table 4

Path planning results - Simulation 2

Table 5

Path planning results - Simulation 3

5. 결 론

본 논문에서는 최적 비용 경로로의 수렴 속도, 메모리 요구 성, 좁은 통로 문제에 대응하기 위해 골격화를 이용한 Informed RRT* 개선 알고리즘을 제안하였으며, 그 성능을 잘 알려진 환 경의 격자 지도를 이용하여 검증하였다. 초기 경로 생성을 위 해 RRT*가 아닌 격자 지도의 골격화를 이용하면, 복잡한 구조 및 좁은 통로가 존재하는 환경에서 최적 비용에 근사한 초기 경로를 얻을 수 있다. 따라서, 전체적인 경로 탐색 시간을 줄여 신속한 경로 계획이 가능하다. 또한, 실행할 때마다 생성된 경 로의 비용 및 연산 시간 면에서 큰 편차를 보인 기존의 Informed RRT*와 달리 제안된 골격화를 이용한 방법은 편차가 작은 안 정된 결과를 보여주었다. 또한, 초기 경로 생성 시, 제안된 골 격화 대신 A*를 적용한 결과에서는 골격화를 이용한 방법이 연산 시간면에서 더 우수함을 입증하였다. RRT 기반 알고리 즘들은 2차원 공간뿐만 아니라 고차원 공간에서도 많이 활용 되고 있다. 3차원 공간의 경우, 3차원 골격화 기법[26]과 3차원 Harris Corner Detector[27]를 이용하여 초기 경로 생성이 가능하 다. 따라서, 이와 같은 방법을 이용하여 제안 기법의 고차원 공 간으로의 확장이 가능할 것이다. 제안 기법을 이용하여 격자 지도 상에서 경로 계획 시, 로봇은 크기가 없는 점으로 표현되 므로, 실제 로봇의 크기에 따라 장애물과 충돌할 수 있는 위험 이 존재한다. 로봇의 크기에 따른 충돌을 방지하기 위해, 제안 기법으로 경로 계획을 진행하기 이전에 다음과 같은 사전 작 업을 진행할 수 있다. 사전 작업은 격자 지도에 로봇 반지름 길 이 이상의 값만큼 골격화를 수행하는 방식으로 진행된다. 사 전 작업을 진행하면 격자 지도의 장애물들은 장애물 크기 정 보와 더불어 로봇 반지름의 정보까지 보유하게 된다. 따라서, 사전 작업을 진행한 격자 지도로 제안 기법을 이용한 경로 계 획 시, 로봇을 크기가 없는 점으로 표현하더라도 보다 실제 주 행에 적합한 경로 생성이 가능하다. 위 부분은 향후 추가적인 연구를 통해 수행될 예정이다.

Acknowledgments

This study is supported by 2017 Research Grant from Kangwon National University and is partly supported by a project of Korean government (10073166).

References

• M. Elbanhawi, M. Simic, Sampling-Based Robot Motion Planning: A Review., IEEE Access, (2014), 2, p56-77. [https://doi.org/10.1109/access.2014.2302442]
• S.M. LaValle, J.J. Kuffner, Randomized Kinodynamic Planning., Int. J. Robot. Res., (2001), 20(5), p378-400. [https://doi.org/10.1177/02783640122067453]
• S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning., Int. J. Robot. Res., (2011), 30(7), p846-894. [https://doi.org/10.1177/0278364911406761]
• I. Noreen, A. Khan, Z. Habib, Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions., International Journal of Advanced Computer Science and Applications, (2016), 7(11). [https://doi.org/10.14569/ijacsa.2016.071114]
• J.D. Gammell, S.S. Srinivasa, T.D. Barfoot, Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, USA, p2997-3004, (2014). [https://doi.org/10.1109/iros.2014.6942976]
• P.E. Hart, N.J. Nilsson, B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths., IEEE Transactions on Systems Science and Cybernetics, (1968), 4(2), p100-107. [https://doi.org/10.1109/tssc.1968.300136]
• J. Borenstein, Y. Koren, Real-time obstacle avoidance for fast mobile robots., IEEE Trans. Syst. Man Cybern., (1989), 19(5), p1179-1187. [https://doi.org/10.1109/21.44033]
• H. Choset, J. Burdick, Sensor based planning. I. The generalized Voronoi graph, 1995 IEEE International Conference on Robotics and Automation, Nagoya, Japan, p1649-1655, (1995). [https://doi.org/10.1109/robot.1995.525511]
• L.E. Kavraki, P. Svestka, J-C. Latombe, M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces., IEEE Trans. Robot. Autom., (1996), 12(4), p566-580. [https://doi.org/10.1109/70.508439]
• J. Denny, E. Greco, S. Thomas, N.M. Amato, MARRT: Medial Axis biased rapidly-exploring random trees, 2014 IEEE International Conference on Robotics and Automation, Hong Kong, China, p90-97, (2014). [https://doi.org/10.1109/icra.2014.6906594]
• Y. Dong, E. Camci, E. Kayacan, Faster RRT-based Nonholonomic Path Planning in 2D Building Environments Using Skeleton-constrained Path Biasing., J. Intell. Robot. Syst., (2017), 89(3-4), p387-401.
• O. Adiyatov, H.A. Varol, Rapidly-exploring random tree based memory efficient motion planning, 2013 IEEE International Conference on Mechatronics and Automation, Takamatsu, Japan, p354-359, (2013). [https://doi.org/10.1109/icma.2013.6617944]
• J. Nasir, F. Islam, U. Malik, Y. Ayaz, O. Hasan, M. Khan, M.S. Muhammad, RRT*-SMART: A Rapid Convergence Implementation of RRT*., Int. J. Adv. Robot. Syst., (2013), 10(7), p299. [https://doi.org/10.5772/56718]
• D. Kim, J. Lee, S. Yoon, Cloud RRT*: Sampling Cloud based RRT, 2014 IEEE International Conference on Robotics and Automation, Hong Kong, p2519-2526, China, (2014).
• N. Amenta, M. Bern, D. Eppstein, The Crust and the I -Skeleton: Combinatorial Curve Reconstruction., Graph. Models Image Proc., (1998), 60(2), p125-135.
• O. Sharma, D. Mioc, F. Anton, Voronoi Diagram Based Automated Skeleton Extraction from Colour Scanned Maps, 2006 3rd International Symposium on Voronoi Diagrams in Science and Engineering, Banff, Alberta, BC, Canada, (2006), p186-195. [https://doi.org/10.1109/isvd.2006.39]
• P. Maragos, R. Schafer, Morphological skeleton representation and coding of binary images., IEEE Trans. Acoust. Speech Signal Process., (1986), 34(5), p1228-1244. [https://doi.org/10.1109/tassp.1986.1164959]
• T.Y. Zhang, C.Y. Suen, A fast parallel algorithm for thinning digital patterns., Commun. ACM, (1984), 27(3), p236-239. [https://doi.org/10.1145/357994.358023]
• Z. Guo, R.W. Hall, Parallel thinning with two-subiteration algorithms., Commun. ACM, (1989), 32(3), p359-373. [https://doi.org/10.1145/62065.62074]
• G. Goyal, R. Luthra, Skeleton Generation for Digital Images Based on Performance Evaluation Parameters., International Journal of Signal Processing, Image Processing and Pattern Recognition, (2016), 9(2), p47-58. [https://doi.org/10.14257/ijsip.2016.9.2.05]
• A. Howard, N. Roy, Radish: The robotics data set repository, [Online], http://radish.sourceforge.net (2018).
• C. Harris, M. Stephens, A Combined Corner and Edge Detector, 1988 Alvey Vision Conference, p23.1-23.6, (1988). [https://doi.org/10.5244/c.2.23]
• R.C. Prim, Shortest Connection Networks And Some Generalizations., Bell Syst. Tech. J., (1957), 36(6), p1389-1401. [https://doi.org/10.1002/j.1538-7305.1957.tb01515.x]
• J.B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem., American Mathematical Society, (1956), 7(1), p48-50. [https://doi.org/10.1090/s0002-9939-1956-0078686-7]
• H.B. Lee, H. Kwak, J. Kim, C. Lee, H.J. Kim, Improvement of Online Motion Planning based on RRT* by Modification of the Sampling Method., Journal of Institute of Control, Robotics and Systems, (2016), 22(3), p192-198. [https://doi.org/10.5302/j.icros.2016.15.0135]
• T.C. Lee, R.L. Kashyap, C.N. Chu, Building Skeleton Models via 3-D Medial Surface Axis Thinning Algorithms., CVGIP Graph. Models Image Process., (1994), 56(6), p462-478. [https://doi.org/10.1006/cgip.1994.1042]
• I. Sipiran, B. Bustos, Harris 3D: a robust extension of the Harris operator for interest point detection on 3D meshes., Vis. Comput., (2011), 27(11), p963-976. [https://doi.org/10.1007/s00371-011-0610-y]