정의

RRT* (Rapidly-exploring Random Trees Star) 알고리즘은 확률 기반의 경로 탐색 알고리즘 중 하나로, 주어진 공간 내에서 빠르게 경로를 탐색하고 확장하는데 사용됩니다.

기존의 RRT에서 부모(Parent) 노드의 재선정과 트리의 재구성(rewire)을 통해 성능을 향상 시킨 모델입니다.

먼저 RRT에서는 q_new와 가장 가까운 q_near를 부모 노드로 설정하였습니다.

RRT* 에서는 q_new를 중심으로 일정 반경에 있는 모든 노드를 선택하여 비용(cost)을 계산한 후 가장 적은 비용을 가진 노드를 부모로 선정합니다.(아래 그림에서는 q1)

부모 노드를 결정한 이후에는 q_new의 반경에 있는 노드들의 비용과 q_new와 연결 되었을 때의 비용을 비교하여 만약 q_new에 연결하였을 때의 비용이 더 적다면 아래와 같이 트리를 재구성한다.

---

코드 구현

아래 코드는 시작점과 출발점을 변경할 수 있으며 랜덤한 장애물을 생성하고 Tree길이를 수정하여 RRT* 의 작동 방식을 확인 할 수 있다.
첨부한 코드는 실행 파일의 내용만을 포함하고 있다.

import numpy as np

from rrt_star import RRTStar
from search_space import SearchSpace
from obstacle_generation import generate_random_obstacles
from plotting import Plot

X_dimensions = np.array([(0, 100), (0, 100)])  # dimensions of Search Space
x_init = (0, 0)  # starting location
x_goal = (100, 100)  # goal location

Q = np.array([(8, 4)])  # length of tree edges
r = 1  # length of smallest edge to check for intersection with obstacles
max_samples = 1024  # max number of samples to take before timing out
rewire_count = 32  # optional, number of nearby branches to rewire
prc = 0.1  # probability of checking for a connection to goal

# create Search Space
X = SearchSpace(X_dimensions)
n = 10
Obstacles = generate_random_obstacles(X, x_init, x_goal, n)
# create rrt_search
rrt = RRTStar(X, Q, x_init, x_goal, max_samples, r, prc, rewire_count)
path = rrt.rrt_star()

# plot
plot = Plot("rrt_star_2d_with_random_obstacles")
plot.plot_tree(X, rrt.trees)
if path is not None:
    plot.plot_path(X, path)
plot.plot_obstacles(X, Obstacles)
plot.plot_start(X, x_init)
plot.plot_goal(X, x_goal)
plot.draw(auto_open=True)

---

실행 결과

---

출처

https://github.com/motion-planning/rrt-algorithms/tree/master
https://pasus.tistory.com/77