informed sampler
- 샘플링 기반의 경로 계획에서, 목표지점까지의 경로를 최적화 하기 위해서 특정 정보(휴리스틱)를 사용하여 샘플링을 효율적으로 수행하는 기법
- 즉, '어떻게 샘플링을 최적으로 할까' 이다.
- 기존의 random sampling은 탐색이 너무 광범위하게 이루어진다. 그래서 최적을 찾기 위해서는 좀 더 정제된 탐색이 필요. 이때 informed sampler를 사용하면 탐색공간을 줄이면서 성능을 향상 시킬수 있다.
- 기존의 uniform sampling에 비해서 좋은점( uniform sampling은 기본의 RRT*등에서 사용된다 .)
- sampling 공간을 줄여서 계산량이 감소한다. 그래서 더 빠르게 해를 찾을수있으며 불필요한 탐색을 최소화 시킨다.
- 핵심원리
- 기존 sampling공간 전체에서 최적화된 sampling 공간인 subset을 추출.
- 현재까지의 경로 비용보다 낮은 비용을 가질 가능성이 있는 영역만 sampling을 한다.
- 장점
- 샘플링 공간을 줄여서 탐색 속도의 상승 및 메모리 효율 증가
- 최적 경로를 더 빠르게 찾을수있다.
- 단점
- 초기에 좋은 해를 찾지못하면 비효율적
- 장애물이 많은 환경에서는 비효율적일수 있음
- 확장
- 비용 기반 가중치를 적용한 샘플링
- 머신러닝을 활용해서 좋은 샘플링 공간을 학습
- 실제 로봇이 가지는 동적 제약을 고려해서 샘플링
기존 샘플링 공간 vs Informed Sampling 공간
- 기존 RRT*: 전체 공간을 균일하게 샘플링
- Informed RRT*: 현재까지 찾은 경로보다 더 좋은 경로가 존재할 가능성이 높은 공간만 샘플링
타원 샘플링 ellipsoid sampling
- informed sampling중에서 많이 사용되는 방법중 하나이다.
- 현재까지 찾은 해보다 나은 경로가 존재하는 공간을 타원 형태로 제한하는 방식이다.
- 과정
- 1. 초기 탐색 후 경로 발견. 그리고 해당 경로의 비용을 C best라고 한다.
- 2. 최적 비용을 가질 가능성이 존재하는 공간을 정의한다.
- 2-1. 시작 지점과 목표 지점을 초점으로 하는 타원 공간 생성
- 2-2. 타원의 장축은 현재까지의 최적 경로 비용인 C best이다.
- 2-3. 장축의 길이가 줄어들수록 탐색 공간이 좁아진다.
- 3. 타원 내부에서만 샘플링을 한다. ( 더 나은 해를 효율적으로 찾기 위함 )
인자들
타원 샘플링 수식. 탐색공간이 줄어들수록 원 모양에 가까워짐