RRT 알고리즘 (Rapidly exploring Random Tree, 예전자료)

 

네이버 블로그에 있는 글들을 하나씩 옮기고 있다. (2008.12월 작성)

대학원에서 로봇동작계획이란 강의를 들을때 숙제했던 내용인데 사실 지금은 기억 나지 않는다.

이런게 있었다 정도...최적경로, 길찾기 알고리즘인데 세월이 지난만큼 더 좋은 알고리즘도 많아졌을것이다.

---

 

1. RRT (Rapidly exploring Random Tree)

 

RRT는 샘플링 기반 Path Planning 알고리즘이다. 상태 공간 전역에 대해 랜덤한 위치에 포인트를 생성하고, 이를 경향 삼아 시작점으로부터 트리(tree)를 신속하게 성장시켜 나가 목적지까지 도달하는 path를 생성하는 알고리즘이다.

 

The fundamental operation used in growing an RRT is the EXTEND operation. Given a target configuration (randomly selected or not), a distance metric defined on the configuration space is used to calculate the node q_near in the existing tree that is nearest to a target configuration q_target.

(RRT 성장에 사용되는 기본 동작은 EXTEND 동작이다. 임의의 목표를 지정하면 공간상에 정의된 거리 메트릭(?)을 사용하여 목표의 q_target과 가장 가까운 기존 트리의 노드 q_near를 계산한다.)

 

(1) select a random target node
(2) calculate nearest node in tree
(3) try to add new collision-free branch

 

If the distance to the target configuration is less than the parameter e (the RRT step size), then the algorithm attempts to grow a new branch connecting directly to q_target. Otherwise, an intermediate node q_new is generated at a distance of e along the straight line between q_near and q_target.

 

If the new branch is collision-free, then it is added to the tree. If an intermediate node was generated, the algorithm continues to attempt to grow the new branch towards q_target (the "CONNECT" operation) until either the configuration is reached, or a collision occurs.

 

Planning queries are solved by incrementally building two Rapidly-Exploring Random Trees (RRTs) of free configurations rooted at the start and the goal. The algorithm attempts to establish a connection between the two trees, which implicitly defines a collision-free path between the start and the goal.

When a new branch is successfully added to one of the trees, the branch terminal node becomes the target configuration for the other tree.

 

(1) one tree grown using random target
(2) new node becomes target for other tree
(3) calculate node "nearest" to target
(4) try to add new collision free branch
(5) If successful, keep extending branch
(6) path found if branch reaches target
(7) return path connecting start and goal

 

 

2. 실행동영상 (Anytime RRT)

 

처음에는 시작지점부터 무작위로 가지를 뻣어나가며 (즉, 그래프탐색에서 노드를 검색하는것과 비슷) 목표지점을 찾게 되며 다음 첫번째로 그려지는 초록색 선은 최적의 속도로 검색된 목표지점까지의 경로이다. 하지만 이 경로는 최단은 아니기 때문에 초록색선을 기준으로 다시 가지를 뻣어나가며 최단경로를 찾게 되며 마지막으로 빨간색 경로가 도출된다.

 

 

RRT는 랜덤 샘플링 방식이기 때문에 다음 동영상과 같이 똑같은 맵이라도 실행될때마다 다른 최적 경로를 찾기도 한다.

 

 

마침.