알고리즘

Anytime RRT

정지홍 2025. 4. 14. 18:20

Anytime RRT

  • Anytime의 특성 ( 일반 RRT와 다른 점 )
    • initial solution을 빠르게 계산할 수 있어야한다.
    • initial solution을 찾은 후에는, 계속해서 해를 개선해 나가야 한다.
    • 언제든지 중단해도 유효한 해를 제공할 수 있다.
  • 왜 Anytime 특성이 필요한가?
    • 로봇이 움직여야 할 시간이 촉박 or 급변하는 상황에서는 최적해를 못 구할지라도 "괜찮은 해"라도 빠르게 구해야함.
      • ex) UAV가 갑자기 장애물을 탐지 , 드록이 배터리 부족으로 착륙해야할떼
  • 장점
    • 1. 빠르게 feasible한 path를 찾는데 특화됨. ( 초기 경로가 suboptimal할지라도 즉시 실행 가능한 경로를 제공함.)
    • 2. initial solution 이후에도 계속해서 새로운 트리를 생성하거나 기존 트리를 개선하면서 cost를 줄여나감.
    • 3. 매 실행마다 경로가 다를수 있으며, 이는 다양한 환경에서 강건하고 일반화한 path를 찾는데 유리함.
  • 응용 환경
    • 1. 실시간 스스템
    • 2, 시간 제한이 존재하는 로봇의 동작
    • 3. 동적인 환경 
  • RRT와의 차이점
    • 1. RRT는 빠르게 경로를 생성하나 경로의 품질이 보장되지 않는 단점을 개선
    • 2. 시간이 많을수록 품질이 좋아지는 경로 생성
  • 구현 방식
    • 1. RRT-Replan 기반 Anytime RRT : 매 반복마다 새로운 RRT를 생성하며, 더 나은 cost를 가진 경로가 나오면 경로를 업데이트. ( 단, 이전 트리 정보를 재사용 하지 않아서 계산 낭비 )
    • 2. Informed RRT*기반 Anytime RRT : RRT*를 개선한 것이며, 현재 최적 경로의 cost를 기준으로 샘플링 영역을 제한한다. ( 트리는 유지하며 rewiring으로 경로를 점진적으로 개선 )

 

 

 

 

Anytime RRT의 구조

  • Anytime RRT의 기본 개념은 "점진적으로 좋은 경로를 찾자"이다. 그러기 위해서 아래의 것들을 고려해야한다.
    • 1. path optimality
    • 2. real-time constraint
    • 3. memory Cpu의 제한 
    • 4. 환경 변화
  • 아래는 기본적인 anytime rrt의 흐름이다.
Start + Goal 입력
       │
       ▼
최초 RRT 생성 (빠르게 feasible path 탐색)
       │
       ├──→ 최초 경로 저장
       │        └── best_cost ← cost(path)
       │
       ▼
루프 시작: 새로운 트리 생성
       │
       ├──→ 목표 도달? ──┬─> cost 비교 → 더 좋으면 best_path 갱신
       │                 │
       └──── 반복 횟수/시간/개선 여부 체크
                         ↓
                  종료 조건 만족 시 탈출

 

 

 

Anytime RRT의  동작 방식

  • 1. 초기 경로 생성
    • 목적 : 바로 이동할 수 있는 경로를 확보
    • 구현 방식 : RRT , RRT-Connect와 같은 빠른 트리 생성 알고리즘을 사용. 첫번째 경로 생성시 즉시 리턴
    • 경로의 특성 : feasible하지만 보통은 suboptimal하다.
rrt_tree = build_initial_rrt( start , goal )
initial_path = extract_path( rrt_tree )

 

  • 2. 현재까지중에서 가장 좋은 비용을 가진 경로를 추적
    • 목적: 향후 경로 탐섹에서 경로 개션 여부를 판단하기 위한 기준 설정
    • 작동 방식 : best_cost라는 변수를 선언하고, 현재까지 찾은 경로의 cost를 저장. --> 이후에 새로운 경로마다 new_cost < best_cost 인지 확인한다. ( 보통 cost는 경로의 길이,시간,에너지 사용량 등으로 계산 )
best_cost = compute_cost( initial_path )
best_path = initial_patj

 

  • 3. 경로 개선을 반복
    • 전략 A : 트래 새로 생성 방식
      • 매 루프마다 RRT를 새로 생성하는 방식. ( 항상 다른 랜덤 시드 사용해서...)
      • 장점 : local minima에 빠질 확률이 낮다.
      • 단점 : 이전 트리의 정보를 사용하지 않아서 비효율적
    • 전략 B : 기존 트리 rewire 방식
      • RRT*기반인 경우, 기존 트리를 유지하며 rewire을 수행
    • 전략 C : 탐색 범위 제한 방식
      • 이는 informed rrt*완 연계됨

 

 

  • 4. 종료 조건 / 시간 제한 / 실시간 실행 연계
    • 시간 제한 : n초 안에 탐색 종료 
    • 반복 횟수제한 : n번 트리 생성 후에 중단
    • 개선 없는 반복 : n번 반복동안 cost개선이 없다면 중지