RRT 알고리즘

RRT (Rapidly Exploring Random Tree)

• 무작위 샘플링을 사용하여 고차원의 구성 공간을 탐색하는 경로 계획 알고리즘
• 랜덤하게 근접한 포인트들을 이어나가는 과정 -> 주행할 수 있는 경로들의 후보를 확장해 나가는 기술
• 랜덤 특성을 지닌 경로 후보의 다발을 만들어주는 방식으로 Path Generation이 가능해짐
• 중앙 시작지점에서 경로의 후보들이 확장되면서 탐색 공간 전체에 대한 경로 후보들을 확보
• 계속적으로 랜덤 포인트를 주변에 뿌려야 해 확장 탐색하는 랜덤포인트 증가로 계산량이 증가
• (Pros) 랜덤적인 특성으로 구현이 용이함
• (Cons) 경로 생성의 최적성(Optimality) 고려 필요

---

1. 시작지점 설정

Xinit : 시작지점
Xrand : 공간확장 :경로 후보 확장을 위해 뿌리는 샘플링 포인트로 확장하는 점
Xnear : Xrand를 뿌려서 확장하고 기존의 점과 가장 가까운 점을 연결할 때 기존 트리에서 가장 가까운 점

확장하는 트리 T가 목적지에 도달하면 목적지부터 시작점까지 재귀적으로 트리를 검색하여 실시간 경로 선택

2. 탐색 영역 (Searching Region) 설정

---

효과적 확장 방법

균등 분포 - 공간 내에서 균등 분포와 같은 것을 사용하여 샘플링 개념으로 점을 확장 및 선택

직진성을 고려하여 타원 분포 사용

---

Sudo code

Generator__RRT(Xinit, K, deltaT)
T.init(Xinit);
for k = 1 to K do
Xrand <- RANDOM_STATE();
Xnear <- NEAREST_NEIGHBOR(Xrand,T);
u <- SELECT_INPUT(Xrand,Xnear);
Xnew <- NEW_STATE(Xnear,u,deltaT);
T.add_vertex(Xnew);
T.add_edge(Xnear,Xnew,u);
Return T

---

차로 변경 및 추월 시나리오

장애물까지 고려한 경로 후보들 생성 -> 최적의 후보 찾음

---

RRT 알고리즘

시작지점에서 샘플링포인트들을 지속적으로 공간 탐색으로 확장함

시작지점과 도착지점이 정해지면 반복적으로 구성 공간 내에서 임의의 한 점 Xrand를 확장하면서 초기의 시작점으로만 구성된 검색트리 T를 확장하는 방식

---

편리함

포인트를 뿌리는 방식 조절 가능
장애물 부분에 샘플링 포인트 확장 X

장애물 인식 범위를 좀 더 크게 키워주는 작업 필요
장애물 인식 영역을 너무 딱 맞게 설정할 경우, 차량의 크기 등으로 장애물과 충돌할 가능성

---

샘플링 포인터

최대화 시 섬세한 경로 획득 가능, 계산량 많아짐
최소화 시 섬세한 경로 획득 불가, 계산량이 적어져 실시간성

이동체 대상 및 환경 특성을 고려하여 합리적인 설계 방법이 필요함

---

RRT* 알고리즘

랜덤한 샘플링 포인트로 optimal 함이 태생적으로 불가능함
RRT 알고리즘 + optimality 측면의 개선한 형태

최적 이동을 위한 비용함수 도입
new state의 neighbor들을 optimal path로 rewiring 작업 추가

1. Random sampling
2. Include the node
3. Find near neighbor (only RRT*)
4. Select best parent (only RRT*)
5. Check cost for rewiring (only RRT*)
6. Rewired tree (only RRT*)