[RRT] RRG(Rapidly-exploring Random Graph)

RRG(Rapidly-exploring Random Graph)

• RRT의 확장 버전으로, 비최적해를 탐색하는 RRT의 한계를 극복하고, 최적해로 수렴하기 위한 방법중 하나이다.
  • RRT처럼 무작위 표본을 이용해서 confoguration space를 탐색하지만, Tree구조가 아니라 Graph구조를 만든다.
    • 즉, 노드간의 연결이 다수가 가능해서, 좀 더 촘촘한 경로망을 구축할 수 있다.
• 특징
  • 구조 : 비사이클 Graph구조
  • 탐색 방식 : 무작위 샘플링 기반
  • 연결성 : 기존 노드 중 여러개의 가까운 노드에 연결이 가능
  • 장점 : 다양한 경로의 생성 , 탐색영역이 빠르게 넓어짐
  • 목적 : 경로의 다양성 확보 , 최적화 기반 구조 형성 

 

• 알고리즘 절차
  • 1. initialize
    • start node를 x_init으로 하여 그래프 G를 초기화.
    • 그래프 G는 정점 집합 V와 간선 집합 E로 구성된다.
    • 초기 : V={ x_init} , E=None
  • 2. Random Sampling
    • 상태 공간 X에서 임의의 샘픔인 x_rand를 추출
  • 3. Nearest Vertex
    • 현재 그래프 V에서 x_rand와 가장 가까운 노드인 x_nearest를 찾는다.
  • 4. Steer
    • x_nearest에서 x_rand방향으로 일정거리만큼 이동해서 x_new를 생성.
  • 5. Collision Check
  • 6. Add Vertex
    • x_new를 그래프 V에 추가한다. 즉,   V ← V ∪ {x_new}
  • 7. Add Edge
    • x_nearest와 x_new를 연결하는 edge를 추가한다. 즉, E ← E ∪ {(x_nearest, x_new)}  
  • 8. Nearby Vertices ( r-connection )
    • x_new 주변의 반지름 r( n )내에 있는 노드 집합인 X_near을 찾는다. ( 식1 참고 )
  • 9. connect to Near
    • 각 x_near ∈ X_near에 대해서, x_new와 충돌이 없는 경로이면 edfe를 추가한다. 즉, E ← E ∪ {(x_near, x_new)} 
      •  ( x_near는 X_near의 원소를 의미 )
  • 10. 반복

식1. r(n)에 대한 정의

 

 

	RRT	RRG
구조	Tree	Graph
연결 방식	하나의 노드만 연결	여러 노드와 연결
경로의 다양성	낮음	높음
최적성 보장	없음	없다( 하지만 최적 구조 가능 )
연산량	적음	많음 ( 가까운 노드 다수 탐색이 필요 )