RRT스타알고리즘 (RRT* (RRT-star))
쉽게 풀면
기본 RRT처럼 가지를 뻗어가되, 새 가지가 생길 때마다 주변 가지들을 더 짧은 길로 다시 연결할 수 있는지 확인해서 점점 더 좋은 길을 만드는 방법입니다.
왜 중요한가
재연결 단계를 통해 표본 수가 늘어날수록 점근적으로 최적 경로에 수렴하는 성질이 있어, 경로의 품질이 중요한 매니퓰레이터 및 이동로봇 경로계획 연구에서 널리 사용됩니다. 물류로봇처럼 같은 창고에서 수천 번 반복 주행하는 응용에서는 경로 길이 몇 퍼센트의 차이가 누적되어 큰 운영비 절감으로 이어지므로, 단순 RRT보다 품질이 보장되는 RRT*가 선호된다.
논문에서는 이렇게 쓰입니다
새로 추가된 점을 기준으로 주변 가지들을 다시 살펴보고, 더 짧게 갈 수 있는 길이 있으면 연결을 바꿔준다는 뜻으로, 이 과정이 반복될수록 경로가 점점 최적에 가까워집니다.
이 문장은 앞의 예문이 RRT*의 기본 원리와 이론적 최적성을 다뤘다면, 이 예문은 그 계산 비용 문제를 실시간 응용에 맞게 완화하려는 개선 연구를 보여줍니다.
조금 더 깊게 보면
점근적 최적성은 표본 수가 충분히 많아질 때 보장되는 이론적 성질이라, 실시간 응용에서는 계산 시간 제약으로 인해 완전한 최적해에 도달하지 못하는 경우가 많습니다. 새 노드를 추가할 때 단순히 가장 가까운 노드에 연결하는 대신, 일정 반경 안의 이웃 노드들 중 시작점까지의 누적 비용이 가장 작아지는 노드를 부모로 다시 선택하고, 나아가 그 이웃들도 새 노드를 거치면 더 짧아지는지 확인해 연결을 다시 잇는 재연결 과정을 거친다. 이 재연결 반경을 이론적으로 정해진 값보다 좁게 제한하면 계산은 빨라지지만 점근적 최적성 보장이 약해지는 실용적 절충이 존재한다.
주의할 점
점근적 최적성을 위해 재연결 계산이 추가되어 기본 RRT보다 계산 비용이 더 크다는 단점이 있습니다.
표본 수가 무한대로 갈 때만 최적해에 수렴한다는 점근적 보장이므로, 계산 시간이 제한된 실시간 응용에서는 실제로 얻는 경로가 최적과 상당히 차이 날 수 있다.