Heuristically Guided RRT

Heuristically Guided RRT

• RRT (Rapidly-Exploring Random Tree)알고리즘에 "휴리스틱"을 도입해서 경로 탐색 효율을 높인 변형 알고리즘이다.
  • 이름에서 알수 있듯이, 목표지점에 더 빠르게 도달할 수 있게 RRT의 node sampling을 "지능적으로"유도하는게 핵심
• 핵심 아이디어
  • RRT (Rapidly-Exploring Random Tree)에 목표 기반 휴리스틱을 추가해서, node sampling or select를 더 "똑똑하게"만듬
    • 기존의 RRT는 목표를 향하는 능력이 약하며, 불필요한 노드를 많이 생성한다.
  • 다음의 방식으로 동작한다.
    • 1. Biasing the Sampling
      • Random sampling대신에, "목표에 가까운 방향" or "cost가 낮은 방향쪽"으로 sampling할 확률을 높임.
      • ex) [ Random Sampling 90% , 목표 방향 sampling 10% ]으로 목표 지향성을 상승시킴.
    • 2. Heuristic Cost Function 사용
      • 각 node에서 goal까지의 추정 비용( ex. 유클리드 거리 )을 고려해서 탐색 우선순위를 정한다.
      • f( n ) = g( n ) + h( n )과 같은 방식으로.... ==> 마치 a star처럼 동작하는 느낌
    • 3. Best-first node 확장
      • 기존 RRT는 단순히 가까운 노드를 선택하지만, Heuristic RRT는 F( n )이 낮은 노드를 우선적으로 확장.
• 장점
  • 불필요한 공간 탐색을 줄여주며, 빠르게 목표에 도달할 가능성이 높아짐.
  • 장애물이 많은 복잡한 환경에서 유리
• 단점
  • 당연 계산 복잡도 증가
  • 휴리스틱 비율을 잘 조정해야함