RRT스타알고리즘 (RRT* (RRT-star))
한 줄 정의: RRT의 트리 확장 과정에 재연결(rewiring) 단계를 추가하여 표본 수가 늘어남에 따라 점근적으로 최적 경로에 수렴하도록 개선한 알고리즘.
쉽게 풀면
기본 RRT처럼 가지를 뻗어가되, 새 가지가 생길 때마다 주변 가지들을 더 짧은 길로 다시 연결할 수 있는지 확인해서 점점 더 좋은 길을 만드는 방법입니다.
논문에서는 이렇게 쓰입니다
RRT*는 새 노드 추가 시 인근 노드들의 비용을 비교하여 부모를 재선택하고, 인근 노드들도 재연결함으로써 표본 수가 무한대로 갈 때 최적해에 점근적으로 수렴함을 보장한다.
새로 추가된 점을 기준으로 주변 가지들을 다시 살펴보고, 더 짧게 갈 수 있는 길이 있으면 연결을 바꿔준다는 뜻으로, 이 과정이 반복될수록 경로가 점점 최적에 가까워집니다.
주의할 점
점근적 최적성을 위해 재연결 계산이 추가되어 기본 RRT보다 계산 비용이 더 크다는 단점이 있습니다.