Approximation Invariant (ε-Approximate Optimality)
- LBR-RRT가 '근사 최적성'을 보장하는 핵심은 Approximation Invariant 때문이다.
- 1. 정의
G_lb는 collision-check없이 추가해 나가는 그래프이다.
2번째 edge삽입에는 충돌검사 안함
- 3. 효과 및 trade-off
- ε을 작게 설정 -> 경로 품질 향상 , 검사빈도 증가 , 속도가 느려짐
- ε을 크게 설정 -> 탐색 속도가 향상 , 품질이 내려감
Lazy Validation
- 기존의 RRT*나 RRG에서는 모든 삽입되는 엣지마다 즉시 충돌 검사를 하지만, LBT-RRT는 필요할때만 검사한다.
- 1. 기본 아이디어
- G_lb에서는 충돌 검사 없이 모든 잠재적 엣지( u , v )를 추가하여, 오직 T_apx에 엣지를 실제로 사용할때만, 해당 edge에 대해서 collision-free검사를 수행한다.
- 즉, 이벤트 드리븐( triggered) 방식으로 필요할때에만 검사하여, 불필요한 충돌 검사를 줄이며, 빠른 초기 확장을 가능하게 한다.
- 그러면 언제 검사하나?
- invariant 위반 복구시에 한다. 즉, 트리 비용 보장을 위함
- 경로 추출 직전
| 방식 |
장점 |
단점 |
| eager |
매 edge에 대해서 즉시 안전 보장 |
검사가 많아서 초기 탐색이 느리다. |
| lazy |
검사 횟수가 줄어들수록, 초기 속도는 증가 |
최종 경로 사용 직전 검사로 약간의 지체 발생 |
LBT-RRT(Local-Best-Tree RRT)
- LBT-RRT는 RRT나 RRT*와 비슷한 맥락에서 출발하지만, 빠르게 경로를 찾되, 최적성( optimality )를 계속 향상시키는 것을 목표로한다.
- 즉, 빠른 초기 경로를 제공하고, 시간이 지남에 따라서 최적 경로로 점진적으로 개선한다.
- 핵심 아이디어
- 1. Approximation Invariant 유지
- 현재 트리의 경로 비용이 최적 비용보다 특정 오차 ε 이내에 있도록 유지합니다. (ε-approximate optimality)
- 2. Lazy Validation
- 트리 확장 과정에서 연결 가능성 여부( collsion-free )를 즉시 검사하지 않고, 필요할때만 검사를 한다.
- ===> 위의 두가지 덕분에, 빠르고 가벼운 트리 탐색과 시간에 따른 최적화를 동시에 달성한다.
| 알고리즘 |
초기 탐색 속도 |
최적성 |
최적화 속도 |
| RRT |
빠름 |
없다. |
없다 |
| RRT* |
느림 |
최적성 보장 |
느림 |
| LBT-RRT |
빠름 |
ε의 설정에 따라서 다르다. |
빠르고 유연 |
- 장점
- 빠른 초기 경로 탐색
- 최적성 보장이 가능하며 실시간 적용이 뛰어남
- 단점
- lazy Validation으로 인해 최종 검증 시 시간이 좀 더 걸릴 수 있음
- 트리의 관리가 복잡
- 기본 루프 구조
- 1. random sampling
- space에서 하나의 점인 q_rand를 샘플링
- 2. 트리 확장
- 트리에서 가장 가까운 점인 q_near을 찾고, q_rand방향으로 새로운 노드인 q_new를 생성
- 3. Near Set 찾기
- q_new 주변의 노드 집합인 Near( q_new )를 찾음
- 4. Best Parent 찾기
- Near( q_new )안에서 가장 좋은 부모 후보를 선택한다. ( 최소 비용 기준으로... )
- 5. Edge를 추가
- q_new를 트리에 추가 ( 일단은 간단히 추가한다. 즉, collision-check는 lazy하게 )
- 6. Approximation Invariant 유지
- 만약에 path가 너무 비효율적이라면, 주변 노드들과의 rewire을 시도한다.
- 비용이 나쁜 경우에 추가로 edge를 바꾸어줌
- 7. collision-check
- 경로를 사용할 거 같을때만 실제로 충돌 검사를 실시한다.
