23. RRT 알고리즘 기초
1. RRT 알고리즘의 개념 및 원리
1) 무작위 샘플링을 사용하여 고차원의 구성 공간을 탐색하는 경로계획 알고리즘
2) 시작지점에서 계속적으로 랜덤 포인트들을 뿌리면서 근접한 포인트들과 이어나가는 과정
-> 주행할 수 있는 경로들의 후보를 확장해 나가는 기술 -> 랜덤 특성을 지닌 경로 후보의 다발을 만들어주는 방식으로 Path Generation이 가능해짐
3) RRT 원리
1. X_init : 시작지점, X_rand : 경로 후보 확장을 위해 뿌리는 샘플링 포인트로 확장하는 점
2. X_rand를 뿌려서 확장하고 기존의 점과 가장 가까운 점을 연결하게 되는데, 여기서 기존 트리에서 가장 가까운 점이 X_near
3. X_near와 연결이 되면서 새로운 포인트는 X_new
4. X_new를 기준으로 다시 X_rand를 뿌리면서 계속적으로 확장
5. 확장 트리가 목적지 도달 시, 목적지부터 시작점까지 재귀적으로 트리 검색 -> 실시간 경로 선택
4) 랜덤 포인트를 효과적으로 뿌리는 법
- 공간 내에서 균등 분포와 같은 것을 사용하여 샘플링 개념으로 점을 확장 및 선택
- X_rand가 목적지에 치우치게 하는 분포 형태 or 차량과 같은 이동체의 특성에 맞는 형태
- ex) 차량은 횡방향 이동에 한계 -> 직진성을 고려한 타원 분포가 효과적
5) 장애물이 있는 자리에 회피하여 랜덤 포인트 생성할 수 있으므로 장애물 회피 경로 생성 가능
6) RRT 알고리즘은 랜덤특성 지님
장점 : 구현 용이
단점 : 경로생성의 최적성(optimality)고려 필요
퀴즈)
1. RRT 알고리즘 설명으로 틀린 것? 답 1(RRT는 학습이 아니라 샘플링 기반)
1. 학습 기반 방식
2. 샘플링 기반 방식
3. 계속적인 확장을 해나가는 방식
4. optimality 부족
2. RRT는 무슨 용어의 약자? 답 2
1. Redundant Escape Transform
2. Rapidly Exploring Random Tree
3. Residual Escape Transform
4. Roll Exploring Random Tree
24. RRT 알고리즘 이해
1. RRT 알고리즘의 원리 이해
1) RRT 알고리즘은 어느 특정시점에 1번만 실행되는 것이 아니라 실시간으로 반복적인 수행이 필요함
- 자차와 주변차량의 환경은 매우 빠르게 변하기 때문
2) 차로 변경 및 추월 시나리오
1. 시작/목적지 설정
2. RRT 알고리즘을 통해 경로후보들을 생성할 탐색 영역 설정
3. 영역 안에 RRT 알고리즘을 통해 경로후보들을 만들 점을 뿌려 트리 확장
( 전방 차량이 있는 위치는 경로후보 X -> 랜덤 포인트 X // 만약 탐색 영역의 차선들에 모두 장애물이 있다면 갈 수 있는 경로 후보 X -> 다른 길 모색 )
퀴즈)
1. RRT 알고리즘 기반 경로생성에 대해 틀린 것? 답 2
1. 샘플링 기반 방식
2. 격자 활용
3. 범용적 적용 가능
4. 반복적 수행 필요
2. 자율주행 경로생성에서 RRT알고리즘이 반복적으로 수행되어야하는 이유? 답 2
1. 격자 기반 방식
2. 자차와 주변 차량 변함
3. 학습 기반 방식
4. 불완전한 방식
댓글