RRT* (RRT Star) 알고리즘

RRT* 알고리즘은 RRT 알고리즘과 기본 뼈대는 동일하다. 다만 RRT와 두 가지 차이점이 있는데, 첫째는 부모(parent) 노드의 재선정이고 둘째는 트리의 재구성(rewire)이다.

 

 

RRT에서는 \(\mathbf{q}_{new}\)와 가장 가까운 노드 \(\mathbf{q}_{near}\)가 부모(parent) 노드가 되었지만,

 

 

RRT*에서는 \(\mathbf{q}_{new}\)를 중심으로 일정 반경에 있는 노드(그림에서 \(\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3, \mathbf{q}_4, \mathbf{q}_5, \mathbf{q}_{near}\))를 뽑고,

 

 

그 노드들을 \(\mathbf{q}_{near}\)와의 비용(cost) 비교를 통해 가장 적은 비용을 가진 노드(그림에서 \(\mathbf{q}_1\))를 부모로 선정한다.

 

 

트리의 재구성에서는 \(\mathbf{q}_{new}\)를 중심으로 일정 반경에 있는 노드(그림에서 \(\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3, \mathbf{q}_4, \mathbf{q}_5, \mathbf{q}_{near}\))들의 비용과 그 노드들이 \(\mathbf{q}_{new}\)의 자식(child) 노드로 연결되었을 때의 비용을 비교하여,

 

 

만약 자식(child) 노드로 연결되었을 때의 비용이 더 작다면(그림에서 \(\mathbf{q}_4, \mathbf{q}_5\)),

 

 

기존의 부모 노드와의 연결을 끊고, \(\mathbf{q}_{new}\)의 자식 노드로 연결하여 트리를 재구성한다(그림에서 \(\mathbf{q}_4\)의 부모 노드는 \(\mathbf{q}_3\)이었지만 \(\mathbf{q}_{new}\)로, \(\mathbf{q}_5\)의 부모 노드는 \(\mathbf{q}_{near}\)이었지만 \(\mathbf{q}_{new}\)로 재구성되었다).

 

 

RRT*는 Karamann가 제안했는데, 충분하게 많은 수의 샘플점을 발생시킨다면 최적해로 수렴된다는 것이 증명되었다.

RRT*는 고차원 최적 경로계획 문제를 해결하는데 큰 전환점이 되었으며 실제로 많은 문제에 적용되어 그 효용성이 입증되었다. RRT의 변형버전은 사실상 RRT*의 변형버전일 만큼 학계에서도 많은 관심을 불러와 최근 수년간 RRT*에 관련된 논문의 숫자가 폭발적인 증가를 보이고 있다.

RRT*는 형상공간 천제에서 균일한 확률로 샘플점을 발생시켜 형상공간을 탐색한다, 샘플링 수가 충분히 많으면 형상공간 영역에서 균일하게 트리를 구성하는 것이 생성된 경로의 질을 높일 수 있는 방법이겠지만, 경로를 생성하는데 있어서는 시간이 소요될 수 있다. 균일한 샘플링 전략과는 달리 일정 목적으로 편향된(biased) 샘플링 전략을 이용하면 수렴성을 증가시킬 수 있는데 이를 위한 여러 가지 알고리즘이 제안되었다. 대표적으로 지능 샘플링(intelligent sampling), 두 단계 샘플링(two-stage sampling), 포텐셜 필드(potential field)를 이용한 샘플링 전략 등이 있다.

수렴성 증가를 위하여 제안된 방법들은 모두 탐색과 활용(exploration and exploitation)의 균형이라는 문제를 안고 있다. 편향된 샘플링은 목표점까지의 경로를 빨리 찾아주기도 하지만 형상공간 전체를 골고루 탐색하지 못함으로써 최적 경로를 찾지 못할 가능성이 커질 수도 있기 때문이다.