[RRT] RRT*-SMART: A Rapid Convergence Implementation of RRT*

RRT*-SMART: A Rapid Convergence Implementation of RRT* - Jauwairia Nasir, Fahad Islam, Usman Malik, Yasar Ayaz, Osman Hasan, Mushtaq Khan, Mannan Saeed Muhammad, 2013

 

 

0. Abstract

• 최근에는 많은 샘플링 기반 알고리즘이 제안되었다.
  • 그중에서 RRT는 확률적 완전성은 보장하나, 최적 경로는 보장 못한다.
  • RRT*는 RRT의 확장 알고리즘이며, 최적해로 수렴함으로써 '점근적 최적성'과 '확률적 완전성'을 동시에 보장한다. 하지만 이론적으로는 수렴 속도가 매우 느리다.
• 본 논문에서는 RRT의 한계를 극복하기 위해서 'RRT-Smart'라는 확장 알고리즘을 제안한다.
  • 제안한 방법은 수렴 속도를 가속화하여 최적 or 준최적의 solution에 훨씬 빠르게 도달한다.
  • 제안할 알고리즘에는 'path optimization'과 'intelligent sampling'이라는 2가지 새로운 기법을 도입한다.
    그리고 실험을 통해서 효율성이 확인되었다.

 

---

1. Introduction

• motion planning은 start에서 goal까지 장애물과 충돌하지 않으면서, 연결 가능한 궤적을 찾는 분야이다.
  • robot과 obstacle의 기하학적 형태는 2d or 3d 구성 공간에서 정의된다.
    robot의 움직임은 구성 공간에서의 path를 나타낸다.
• 지난 40여년간 static , dynamic한 환경에서 동작하는 여러 path planning 알고리즘이 제안되었으며, 여기에는 기하학적 기법, 격자기반 기법 , 퍼텐셜 필드 , 신경망 , 유전 알고리즘 등 다양한 알고리즘이 포함된다. ( 각각의 알고리즘은 저마다의 장단점을 가짐 )
  • 최근에는 sampling 기반 방법이 인기를 얻고있다. 
    이는 collision checking모듈에 의존하며, 장애물이 검출되지 않은 공간에서 샘플링된 점들을 연결해서, 유효한 궤적 roadmap을 구성한다.
• RRT는 최적성을 보장하지 못하여 potential function planner와 densitu avoided sampling planner 및 이들의 변형 기법들이 대표적이다.  
  하지만 RRT*의 등장으로 주요 전환점이 되었다.
  • PRM과 RRT-Connect는 점근적 최적성을 확보하지 못하지만, 시간 복잡도에서 우위를 가진다. (RRT*와 비교했을때)
  • PRM*와 RPG는 점근적 최적성이 있으나, 시간 복잡도는 더 낮다. (RRT*와 비교했을때)
  • 하지만 RRT*는 아래의 단점이 있다.
    • 1. 수렴 속도의 한계. 
• 본 논문은 위의 한계들을 극복하기 위해서 RRT에 정보기반 탐색(informed exploration)을 도입한 RRT*-Smart를 제안한다.
• RRT*-Smart
  • 이는 RRT가 찾아낸 첫번째 path를 지능적 초기 추측(intelligent guess)으로 활용하여, configuration space exploration을 보조하고, 지능형 샘플링(intelligent sampling)을 통해서 매우 빠른 수렴속도로 최적 or 준최적 path를 도출하여 실행 시간을 단축한다.
  • 또한, 생성한 path보다 직선적이며, waypoints가 적어서 robot이 궤적을 추종하기에도 유리하다.
• 본 논문에서는 다양한 실험환경에서 rrt-smart의 성능을 비교 분석하고 증명하고자 한다.
• 논문의 구성...
  • 2장은 RRT
  • 3장은 RRT-Smart
  • 4장은 결과 및 성능 분석
  • 5장은 최적화 파라미터에 대한 설명
  • 6장은 결론 및 향후 연구 과제.

---

2. RRT*

여기는 RRT*에 대한 내용임.

 

RRT*

RRT*

 

---

 

3. RRT*-Smart Algorithm

• 해당 절에서는 RRT*-Smart와 제안된 'intelligent sampling'과 'path optimization'에 대해서 설명한다.
• 먼저 RRT-Smart는 configuration space를 무작위로 탐색하여 초기 경로를 찾는다.
  이렇게 초기 경로가 확보되면, 직접 가시(visible) 가능한 노드들을 서로 연결하여 경로를 최적화한다. ( 이렇게 최적화된 경로로부터 얻은 'biasing points'는 이후에 intelligent sampling의 기준점이 된다. 그리고 이 지점들 주변에서 일정 간격으로 샘플링이 이루어짐. biasing points에 대한 내용은 6장에서 나올것이다.)

알고리즘2. RRT*-Smart 알고리즘 init

• 1~3 , 7~14 : 기존의 RRT와 동일
• 15 : InitialPathFound가 최초 경로를 찾은 반복횟수 n을 반환한다. 그리고 이 n을 기준으로 bias샘플링을 시작한다.
• 16 : n이 갱신된다면, 이후부터 매 b번 반복마다 intelligent sampling을 수행한다.
• 17 : PathOptimization( T , z_init , z_goal )은 경로 상에서, 서로 직접 볼수 있는 노드들을 연결해서 최적화된 path를 만들고, 해당 비용을 directCost로 반환한다.
• 18 ~ 19 : 새로 계산한 비용인 directCost_new가 이전 비용보다 작다면, bias point인 z_beacons를 갱신해서, 다음 intelligent sampling기준으로 사용한다. ( 그렇지 않다면, 당연 기존 bias point를 사용 )
• 4 ~ 5 : Sample( i , z_beacons )는 반경 R_beacons이내에서 bias point주변으로 sample을 생성한다.

 

---

 

3.1  Path Optimzation

• RRT*가 초기 경로를 생성하면, 경로 상의 노드 집합 "x : [ z_init , z_goal ] -> X"에서 서로 간에 가시(visible) 가능한 노드들을 직접 연결해서 경로를 단축한다.
  이 과정은 z_goal에서 시작해서, z_init방향으로 진행된다. ( 즉, 부모 노드를 차례로 따라가며... )
  각 단계마다, "부모의 부모노드(parent-to-parent)"까지 직선으로 연결해서 충돌이 없다면, 그 부모를 한단계 더 뛰어넘어 연결함으로써 노드 수를 줄인다.
  그리고 이러한 과정을 가능한 쌍이 없을때까지 반복한다.
  • 위의 기법은 삼각 부등식( triangular inequality )에 기반한다.

알고리즘3( 위 알고리즘 17라인 ). ( T , directcost ) <--- PathOptimization( T , z_init , z_goal )

 

• 1 : 더 이상 가시(visible) 가능한 노드 쌍이 없을때까지 반복.
• 2 : 탐색 시작 지점을 z_goal로 설정
• 3~6 : 현재 노드인 z_vc가 시작노드( z_init )가 될때까지, parent의 parent 노드까지 직접 연결이 가능하다면 부모를 건너뛰어서 연결하고, 그렇지 않다면 한 단계 위의 부모로 이동한다.
• ==> 위의 과정을 거치며, RRT*가 찾아낸 초기 경로보다 훨씬 적은 수의 노드로 구성된 최적화된 경로가 생성된다.
  • ==> 이때 최적화된 경로 상의 노드들을 beacons라고 부르며, 이후에 intelligent sampling에 사용된다.
• 경로 최적화가 수행될 때마다, '새롭게 계산된 경로 비용'과 '이전 최적화 경로 비용'을 비교하고, '새로 계산된 경로 비용'이 더 짧다면, 해당 경로의 노드 집합으로 beacons를 갱신한다.
  • 충돌 검사시에는, 두 노드 사이 직신을 따라서 일정 간격으로 점은 보간( interpolation )하여, 각 점이 free space에 속하는지 확인한다. 이러한 기법은 장애물의 구체적 형상을 알 필요가 없으며, 간단한 선형 보간만으로 collision-check이 가능하니 계산비용이 낮다.

 

---

3.2  Intelligent Sampling

• intelligent sampling의 아이디어는 visibility graph기법의 기본 개념을 따라서, 장애물 꼭짓점( obstacle vertices ) 근처에 노드를 최대한 가깝게 생성함으로써, 최적성에 접근하는 것이다.
  • 그러나 visibility 기법은 '복잡한 환경의 모델링'과 '장애물에 대한 명시적 정보'가 필요하며, [ concave , polygonal , circulur ]와 같은 복잡한 형태의 장애물 환경에서는 해를 못찾을수있다.
  • 반면에 샘플링 기반의 RRT*-Smart는 최적 or 중간 경로 상에 놓인 장애물의 외곽( periphery)만을 따라 경로를 최적화한다.
    • ==> RRT*-Smart는 초기 경로가 확보되면, 알고리즘2의 4~5라인에서 설명한것 처럼, 반경 R_beacons를 중심으로 비콘(z_beacons)주변에 일정 수의 샘플을 직접 생성하기 시작한다.
      이러한 샘플링은 beacon방향으로 편향(bias)되는데, 이는 beacon이 장애물 꼭짓점(혹은 원형 장애물의 외곽 )에 대한 유의미한 단서를 제공하기 때문이다. 이러한 회전(turn)지점 주변에 더 많은 노드를 집중시킴으로써, 알고리즘은 RRT*보다 더 적은 반복(iteration)만으로 최적 해에 도달할수 있다.
    • 비콘(z_beacons)들은 매번 알고리즘이 반복될때 마다, 새로운 RRT* 경로가 발견되며, 이를 최적화 시킨후의 비용이 더 낮은 비용을 가진다면, z_beacons는 갱신이되며 다음 샘플링의 기준점이 된다.
      ==> 그리고 반복을 거듭할 수록 beacons은 꼭짓점에 더 가까워지며, 이러한 과정은 설정된 반복 횟수만큼 계속된다.
    • 장애물의 형태를 명시적으로 정의하지 않으면서도, 'intelligent guessing'과 'biasing beacons'를 통해 트리가 꼭짓점 근처로 생성되도록 유도하니, 최적 또는 준최적 경로를 탐색하게 된다.
      x : [ z_init , z_goal ] --> X-optimal
      • ==> 이러한 과정에서 생성되는 샘플수는 적으며, 결과적으로 RRT*-Smart는 빠른 수렴속도로 우수한 해를 제공한다. 또한 waypoint의 수가 적어서 로봇이 따라가기에 단순한 경로를 생성한다.
  •  

figure2. RRT*-Smart의 동작 예시

• a : n= 650 에서 초기 경로를 발견
• b : 경로 최적화후, 파란색으로 표시된 최적화 경로, 초록색 점은 해당 경로의 비콘
• c : n=2500 이후 비콘 주변에 클러스터 된 샘플들
• d : 최종적으로 n=4200에서 장애물 환경에 대한 죄적화 경로가 생성됨
• ==> RRT*-Smart는 RRT의 공간 및 시간 복잡도와 동일하다. 하지만 유의미하게 작은 n으로 작동하니 실질적인 성능이 크게 향상된다.
  • 다만, bias비율이 높아질수록 무작위성은 줄어들며, intelligent sampling과 전역 탐색간에는 trade-off관계이다.

 

---

figure3

4. Results and Performance Comparison

• 본 절에서는 서로 다른 장애물 배치를 가진 4가지 환경에서의 RRT*-Smart의 결과를 보여준다.
  또한 RRT와 RRT*-Smart간의 통계적,분석적 비교를 제시하고 두 방법의 평균 차이에 대한 t-검정도 수행했다.
• 위의 figure3에서 빈 빨간 상자는 goal region을, 채워진 빨간 블록은 장애물을, 검은 실선은 생성된 궤적을 나타낸다.
• RRT*-Smart 알고리즘은 원형 장애물 환경, 로컬 최소(local minima) 환경, 그리고 복잡하게 배치된(cluttered) 환경 모두에서 최적 또는 준최적 경로를 찾아내었다.
  이 알고리즘이 사용하는 경로 최적화 및 지능형 샘플링 기법은 장애물의 형태에 독립적으로 적용되므로, 직선형 장애물뿐만 아니라 둥근 외곽을 가진 장애물에서도 효과적으로 경로를 최적화함을 Fig. 3(a)에서 확인할 수 있다.
• 각 장애물 환경에서 경로 최적화에 사용되는 비콘(beacons)의 수는 환경에 따라 다를 수 있다.
  특히 Fig. 3(a)와 같은 원형 장애물 환경의 경우, 장애물 외곽을 충분히 커버하기 위해 더 많은 비콘이 필요하므로 비콘 수가 직선형 장애물 환경보다 크게 증가한다.
  이는 가능한 한 최적의 경로를 확보하기 위해 원형 외곽을 보다 세밀히 탐색해야 하기 때문이다.

 

---

figure4

 

4.1 statistical analysis

• 본 절에서는 다양한 관점에서 RRT*-Smart와 RRT*의 성능을 실험적으로 비교 분석한다.
  먼저, 두 알고리즘의 결과를 Fig. 4에서 나타난다.
  • Fig. 4(d)를 보면, RRT*-Smart는 반복 횟수 n=800에서 RRT가 찾은 초기 경로 비용 630.18(그림 4(a))를 가져와 경로 최적화 기법만으로 비용을 584.02로 낮춘 것을 확인할 수 있다.
  • 이어서 intelligence sampling과 추가 경로 최적화를 적용한 결과, n=1200에서 비용이 557.478로 더욱 감소한 반면, RRT는 동일한 반복 횟수에서 624.95의 비용으로 수렴하였다(그림 4(b)).
  • 마지막으로 RRT*-Smart는 n=4200에서 540.12의 최적/준최적 해를 얻었으며(그림 4(f)), 같은 반복 횟수에서 RRT는 574.009의 경로로 수렴하였다(그림 4(c)).
  • ==>이 비교로 볼 때, 경로 비용 측면에서 RRT-Smart의 효율성이 명확히 드러난다.

 

figure5

• Fig. 5는 두 알고리즘의 비용 수렴 패턴을 그래프로 비교한 것이다.
  • 여기서도 RRT*-Smart가 훨씬 빠른 수렴 속도를 보이며 유한 반복 후 최적 비용에 근접하는 반면, RRT*는 상대적으로 느린 속도로 여전히 최적 해를 향해 진행 중임을 알 수 있다.

 

figure6

• Fig. 6은 고정된 여러 비용 수준에 도달하기까지 필요한 반복 횟수를 비교한 그래프로, 동일한 비용(예: 540)에 이르는 데 RRT는 훨씬 많은 반복을 요구한다.
  • RRT-Smart는 540 비용에 n=4200반복에서 도달했으나, RRT*는 매우 큰 반복 횟수에서도 이 비용에 도달하지 못했다.

 

figure7

• Fig. 7은 두 알고리즘의 경로 비용 대비 소요 시간을 비교한 그래프로, 동일한 비용에 도달하는 데 RRT가 RRT-Smart보다 훨씬 많은 시간을 필요로 함을 보여준다.
• 이 실험은 2.1 GHz Intel Core i3 프로세서와 4 GB RAM 환경에서 수행되었다.

 

 

 

figure8

• Fig. 8은 RRT와 RRT-Smart의 실행 시간 비율을 보여준다.
• 그래프에서 두 알고리즘의 비율이 항상 1보다 크게 나타나는데, 이는 동일한 작업을 수행할 때 RRT*-Smart가 RRT*보다 항상 빠르다는 것을 의미한다.

 

 

 

figure9

• Fig. 9는 서로 다른 50개의 장애물 환경에서 두 알고리즘의 동작을 비교한 것이다.
• 각 환경마다 고정된 반복 횟수 n에서의 경로 비용을 플롯했을 때, RRT*-Smart의 그래프가 항상 RRT보다 아래에 위치함을 볼 수 있다.
  • 이는 모든 환경에서 RRT-Smart가 RRT보다 더 낮은 비용의 경로를 찾아낸다는 것을 보여주어, RRT-Smart의 효율성을 다시 한 번 입증한다.
• 이상의 성능 비교 결과를 종합해 보면, RRT*-Smart는 경로 최적화 측면뿐만 아니라 계산 시간 면에서도 RRT*보다 월등히 우수하다.

 

Comparative Statistical Analysis using t-Student test

• 세 가지 서로 다른 환경(미로, 좁은 통로, 장애물이 점점 늘어나는 복잡한 환경)에서 각각 최소 5회씩 실험을 수행하여 두 알고리즘을 비교하였다.
  • Fig. 10은 미로와 좁은 통로 환경에서 수행한 다섯 번의 실험 중 한 사례를, Fig. 11은 복잡한 환경에서의 한 사례를 보여준다.
    • 그림에서 빨간색 빈 상자는 목표 영역, S와 G는 각각 시작점과 목표 위치를, 빨간 블록은 장애물을, 검은 선은 경로를 나타낸다.
    • 모든 비교 사례에서 RRT*-Smart의 t-값이 기준치(2.31∼5.04)보다 높게 나타났다.
      즉, 두 집단의 평균 차이가 통계적으로 매우 유의미함을 의미하며, 동일한 반복 횟수 내에서 RRT*-Smart가 RRT*보다 경로 비용 측면에서 확연히 우수하다는 결론을 내릴 수 있다.
• 실험 결과는 표 1에 요약되어 있다.
• 이어서, 두 방법의 평균이 같은지를 검정하기 위해 unpaired t-검정(t-Student test)을 수행하였다.
  • 각 환경에서 얻은 5개의 경로 비용 값을 하나의 표본 집단으로 보고, RRT*-Smart와 RRT* 두 집단 간의 t-값을 계산했다
  • 표 1에는 각 환경별 최소값, 최대값, 평균, 표준편차, 그리고 자유도 8에서의 t-값과 95% 신뢰수준(p=0.05 시 기준 t₀.₀₅=2.31, p=0.001 시 기준 t₀.₀₀₁=5.04)이 정리되어 있다.

 

 

 

---

4.2 complexity analysis

• RRT의 공간 및 시간 복잡도는 [10]에서 각각 O(n)과 O(nlog⁡n)으로 제시되었다.
• RRT-Smart도 기본적으로 같은 복잡도를 가지지만, 최적 해에 도달하기 위해 요구되는 반복 횟수 n이 현저히 줄어들어 실질적인 성능이 향상된다.

---

4.2 complexity analysis - 공간 복잡도

• 공간 복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리의 양을 나타낸다.
• RRT*-Smart는 n회의 반복에 걸쳐 n개의 노드(메모리 구성)를 유지하므로, RRT*와 마찬가지로 선형 공간 복잡도 O(n)를 가진다.

 

---

4.2 complexity analysis - 시간 복잡도

• 시간 복잡도는 문제 크기 n에 대한 알고리즘 실행 시간을 나타낸다.
• RRT*-Smart에 추가된 path optimization, intelligence sampling , 그리고 보간(interpolation) 기반 충돌 검사 단계는 모두 상수에 비례하거나, 반복 횟수 n에 크게 영향을 주지 않으므로 전체 복잡도 O(nlogn)는 변하지 않는다.
  • 다만, 실제 n이 줄어들어 실행 시간은 단축된다.

 

---

4.2 complexity analysis - 시간 복잡도 - 경로 최적화 단계 복잡도

•  새로 개선된 경로가 발견된 횟수를 Δ라 하면, 이 단계의 계산 비용은 Δ  ×  (Direct cost)이다.
  • Direct cost = f x ( y_f/2 )​ ​× (충돌 검사당 비용)이다.
    • y_f는 각 반복 f에서 RRT*가 찾은 경로의 노드 수이다.
    • f는 visible한 모든 노드가 직접 연결될때 까지의 반복된 횟수이다.
    • 충돌 검사당 비용은 상수이며, 경로가 최적화될 수록 Direct cost는 감소한다.

 

---

4.2 complexity analysis - 시간 복잡도 - intelligent sampling 단계 복잡도

• 비콘에 직접 샘플을 생성하는 횟수를 p라 하면, 이 단계의 비용은p×c이다. ( c는 한 번 샘플을 놓는 데 드는 상수 시간)
• 바이어싱 비율(biasing ratio)이 커질수록 p도 증가하지만, p 역시 전체 반복 수 n에 비해 작은 값으로 유지된다.

 

 

 

---

5. Algorithm Characteristics - bisaing radius

• biasing radius(바이어싱 반경)은 beacon(z_beacon)을 중심으로 biasing이 이루어지는 구(球)의 반경이다.
• 반경 R_beacon​은 플래너의 요구에 따라 선택할 수 있다.
  • 같은 구성 공간에서 R_beacon​이 상대적으로 클수록, 궤적이 최적 경로 쪽으로 빠르게 이동할 가능성이 높아지며, 이후 반복이 계속될수록 수렴 속도는 다소 느려진다.
  • 반면 반경이 작으면 최적 경로로 수렴하는 속도는 느리지만, 한 번 충분히 최적화된 경로가 발견되면 그 이후로는 더 빠르게 최적값에 도달할 수 있다.
  • 이는 계획(planning) 시간과 내비게이션(navigation) 시간 간의 trade-off로 볼 수 있다.
    • 예를 들어, 내비게이션 시간보다 계획 시간을 줄이는 것이 더 중요한 문제라면 큰 반경을, 반대로 내비게이션 정확도가 더 중요하다면 작은 반경을 선택하는 것이 바람직하다.
    • 다만 반경을 무한히 크게 늘리면 알고리즘의 동작이 결국 RRT와 거의 동일해진다.
    • Fig. 2 환경에서, 같은 비용에 도달하기 위해 필요한 반복 횟수를 반경별로 비교한 실험 결과가 표 III에 정리되어 있다.
      • 반경이 일정 수준 이상 커지면 최적 비용에 도달하는 데 필요한 반복 횟수가 급격히 늘어나 RRT 경향에 가까워지는 것을 확인할 수 있다(표 III에서 반경 25의 경우).
      • 본 논문의 모든 실험에서는 동일 크기의 구성 공간에 대해 반경을 10∼15 범위에서 사용하였다.
      • 구성 공간 크기에 비례해 반경을 정하는 것이 좋은 근사법이다.

 

---

5-1. Algorithm Characteristics - biasing radio

• biasing ratio는 일반 샘플링 대신 beacons에서 직접 샘플을 생성하는 횟수의 비율을 결정한다.
  • 이 값은 전체 계획 과정에서 일정하게 유지되며, 플래너의 요구에 따라 조정할 수 있다.
    다만 비율 변화는 최적해 수렴 경향에 영향을 미친다.
  • 같은 장애물 환경에서 서로 다른 고정 바이어싱 비율을 적용했을 때의 결과가 표 IV에 나와 있다(환경은 Fig. 3(c) 사용).
    • 표 IV를 보면, 특정 환경에서 편향과 탐색 탐사(exploration)의 균형을 맞추어 최적/준최적 비용을 최소 반복 횟수로 달성할 수 있는 최적의 비율이 존재함을 알 수 있다.
    • 이 최적 비율보다 크거나 작으면 모두 더 많은 반복이 필요하다.
• 본 논문에서는 모든 실험에 대해 고정 바이어싱 비율을 사용하였으나, 이를 극복하기 위한 동적 바이어싱 비율(dynamic biasing ratio) 기법도 제안한다.

 

---

5-2. Algorithm Characteristics - Generic Dynamic Biasing Ratio Scheme

• intelligent sampling도입으로 수렴 속도와 탐색 속도 간의 trade-off가 발생한다.
• 빠른 수렴을 위해 강한 편향이 필요하지만, 충분한 탐색 없이 단순히 편향만 강화하면 국소 최적해에 갇힐 위험이 있다.
• 환경 복잡도에 따라 적절한 ratio을 선택하는 것은 어려운 문제이므로, '반복 횟수 n'과 '장애물 없는 공간인  X_free'​에 따라 바이어싱 비율을 동적으로 조정하는 방안을 제안한다.

biasing ratio를 동적으로 조정하는 방법

• 위의 식에서 ( n/X_free )는 시점별 공간 밀도를 나타낸다.
• 탐색 초기에는 밀도가 낮아 편향이 적게 이루어지고, 반복이 진행될수록 공간 밀도가 높아지므로 편향 비율이 증가한다.
  • 결국 탐색이 충분히 이루어진 뒤에는 강한 편향으로 최종 최적화에 집중하게 된다.
  • Fig. 12의 대표 환경 네 가지 모두 이 동적 비율을 적용해 최적화에 성공함을 확인할 수 있다.
    • 반복이 늘어날수록 노드를 비콘에 배치하는 속도가 빨라져 수렴이 가속화된다. 이 기법은 대부분의 환경에서 편향과 탐색 간 균형을 자동으로 맞추도록 도와준다.

 

 

 

---

5-3. Algorithm Characteristics -  다른 알고리즘과 비교 

 

 

 

 

---

6. 결론

• 증분적 샘플링 기반 알고리즘은 다른 모션 플래너에 비해 여러 장점을 지니고 있어 널리 사용되고 있다.
  • RRT*는 RRT와 달리 확률적 완전성뿐만 아니라 점근적 최적성도 보장하지만, 최적 해에 근접하는 수렴 속도는 느리다.
  • 향후 연구로는 제안 알고리즘을 더 고차원 공간으로 일반화하는 작업이 자연스러운 확장 방향이 될 것이다.
• 본 논문에서는 지능형 샘플링(Intelligent Sampling)과 경로 최적화(Path Optimization) 기법을 도입하여 RRT의 수렴 속도를 획기적으로 개선한 RRT-Smart를 제안하였다.
  • 시뮬레이션 결과, RRT*-Smart는 매우 적은 반복만으로도 최적 또는 준최적 해에 빠르게 수렴함을 보였다. 또한 성능 비교를 통해 실행 시간과 경로 비용 면에서 RRT*-Smart의 효율성이 입증되었다.