최적 경로 탐색 : RRT (Rapidly Exploring Random Tree) + RRT*

 

RRT는 시작점에서 Goal에 갈 때까지 아래 작업을 반복함

 

1) Xrandom을 만듦
2) 기존 Point 집합에서 Xrandom에 가장 가까운 점과 Xrandom을 Tree로 연결

3) 만약 가장 가까운 점과 Xrandom 사이에 Obstacle이 있다면 버리고 다시 Xrandom 생성
4) Obstacle이 없다면 Xnearest와 Xrandom을 연결하되, 주어진 일정 거리에 Tree 점을 생성

 

근데 RRT는 Optimal이 아니라는 단점이 있어서 아래 절차를 추가해서 RRT *로 개선

 

 

1) 원래였으면 Qnew는 Qnear와 연결되어야 하는데, 일정 반경을 탐색해서 Qnear가 아닌 Cost가 가장 작은 노드 (ex q1)과 연결을 함

 

2) 연결을 한 후에도 자식 노드를 한번 더 탐색해서, Cost가 작아지는 방향이 있다면 연결성을 바꿈

 

 

즉, RRT 대비 RRT*의 차이는 Cost를 고려한다는 점이고, 단순히 Qnear를 선택하는게 아니라 일정 반경에서 비용을 고려하여 최적점을 찾는다는 것