RRT & RRT* 알고리즘: 복잡한 환경에서 빠른 경로 탐색의 비밀 > 경로 계획 및 자율 주행 알고리즘

• 목록

지난 시간에는 다익스트라 알고리즘을 통해 단일 시작점에서 모든 노드까지의 최단 경로를 구하는 방법을 알아보았습니다. 다익스트라나 A*와 같은 탐색 기반 알고리즘은 격자형 지도나 그래프로 잘 표현되는 환경에서는 효율적이지만, 로봇 팔과 같이 복잡하고 연속적인 움직임을 가지는 **고차원 공간(Configuration Space)**이나, 장애물이 복잡하게 분포된 환경에서는 탐색 공간이 너무 커져 계산 효율성이 현저히 떨어집니다. 이때 복잡한 환경에서 빠르고 효율적으로 경로를 탐색하는 비밀이 바로 RRT (Rapidly-exploring Random Tree) 및 RRT* (RRT-star) 알고리즘입니다.

RRT 계열 알고리즘은 샘플링 기반(Sampling-based) 경로 계획의 대표적인 방법으로, 미지의 공간에서 무작위로 지점을 샘플링하여 '탐색 트리(Tree)'를 빠르게 확장해 나가는 방식으로 경로를 찾습니다. 이는 정해진 규칙이나 그래프를 따르기보다, 불확실성이 높은 환경에서 마치 '감을 잡는' 것처럼 작동합니다. RRT는 목표 지점까지의 경로를 빠르게 찾아내지만 최적성은 보장하지 않으며, RRT*는 RRT의 빠른 탐색 능력에 최적성까지 추가한 발전된 형태입니다. 자율 이동 로봇의 경로 계획, 로봇 팔의 작업 공간 계획 등 복잡하고 동적인 환경에서 로봇에게 "빠른 의사 결정 능력"을 부여하는 RRT 및 RRT* 알고리즘이 무엇이며, 어떻게 복잡한 환경에서 경로를 탐색하는지, 그 원리와 작동 방식, 그리고 로봇 개발에서의 활용은 무엇인지 자세히 파헤쳐 보겠습니다. 

로봇이 "수많은 장애물이 있는 공간에서 로봇 팔이 컵을 잡기 위해 관절을 움직여야 하는데, 이 과정에서 주변 장비나 다른 로봇 팔과 충돌하지 않도록 경로를 찾아야 하는" 상황이라면, RRT 알고리즘은 고차원적인 로봇 팔의 관절 공간에서 빠르고 효율적인 충돌 회피 경로를 찾아줍니다.

1. RRT (Rapidly-exploring Random Tree) 알고리즘이란 무엇인가?

RRT 알고리즘은 샘플링 기반(Sampling-based) 경로 계획 알고리즘의 일종으로, 미지의 환경이나 복잡한 고차원 공간에서 경로를 효율적으로 탐색하는 데 사용됩니다.  

배경: 고전적인 탐색 기반 알고리즘(A*, Dijkstra)은 탐색 공간이 커지면 계산 복잡도가 기하급수적으로 증가하는 한계가 있습니다. RRT는 이 한계를 극복하기 위해 무작위성을 도입했습니다.

핵심 아이디어: "시작점에서부터 무작위 샘플링을 통해 점차적으로 탐색 트리(Tree)를 확장"하여 목표 지점까지 경로를 찾아나가는 방식입니다.

2. RRT 알고리즘의 작동 방식: 트리 확장으로 길 찾기

RRT 알고리즘은 다음과 같은 과정을 반복하며 탐색 트리를 확장합니다.

시작점 설정: 시작 노드를 트리 T에 추가합니다.

무작위 샘플링 (Random Sampling): 탐색 공간(환경) 내에서 무작위 지점(q_rand) 하나를 샘플링합니다. (장애물 내부에 샘플링될 수도 있습니다.)

가장 가까운 노드 탐색 (Nearest Node): 트리 T에서 q_rand에 **가장 가까운 노드(q_nearest)**를 찾습니다.

새로운 노드 생성 (New Node): q_nearest에서 q_rand 방향으로 일정 거리(step size)만큼 이동하여 **새로운 노드(q_new)**를 생성합니다. 이때 q_nearest에서 q_new까지의 경로가 장애물과 충돌하지 않는지 확인합니다.

충돌하지 않는다면 q_new를 트리 T에 추가하고 q_nearest를 q_new의 부모 노드로 설정합니다.

목표 지점 확인: q_new가 목표 지점(또는 목표 지점 근처)에 도달했는지 확인합니다. 도달했다면 탐색을 종료하고 시작 노드부터 q_new까지의 경로를 역추적하여 반환합니다.

반복: 목표 지점에 도달할 때까지 2단계부터 5단계까지를 반복합니다.

특징: 무작위 샘플링 덕분에 "복잡한 장애물이나 고차원 공간에서도 비교적 빠르게 경로를 찾을 수 있습니다."

3. RRT의 한계: 최적 경로 미보장 (Optimality)

RRT 알고리즘은 경로를 "빠르게" 찾아낸다는 장점이 있지만, 다음과 같은 한계가 있습니다.

최단 경로 미보장: 무작위 샘플링 방식이므로, 찾아낸 경로가 항상 최단 경로나 최적의 경로(예: 가장 매끄러운 경로)는 아닐 수 있습니다. 경로가 매우 비효율적일 수도 있습니다.

불안정한 결과: 무작위 샘플링 때문에 실행할 때마다 다른 경로를 생성할 수 있습니다.

4. RRT* (RRT-star) 알고리즘: 최적성을 향한 발전

RRT의 최적성 문제를 해결하기 위해 2011년에 발표된 RRT* 알고리즘은 RRT의 장점(빠른 탐색)을 유지하면서 **최단 경로에 수렴하는 특성(Probabilistically Optimal)**을 추가했습니다. 

RRT*의 핵심 개선점: RRT*는 q_new를 트리에 추가하는 과정과, 트리에 q_new가 추가된 이후의 과정에서 두 가지 추가 단계를 수행하여 최적성을 확보합니다.

가장 좋은 부모 노드 재선택 (Rewire Parent - chooseParent()):

q_new를 생성할 때, q_nearest뿐만 아니라 q_new 주변의 일정 반경 내에 있는 다른 모든 노드(q_in_radius)들을 탐색합니다.

이 q_in_radius 노드들 중에서 q_new까지 연결할 때 "총 비용(시작 노드에서 q_new까지의 경로 비용)"이 가장 작아지는 노드를 q_new의 부모 노드로 선택합니다. 이는 기존 RRT보다 더 효율적인 경로를 찾을 수 있게 합니다.

트리 재연결 (Rewire Tree - rewire()):

q_new가 트리에 추가된 후, q_new 주변의 일정 반경 내에 있는 다른 노드(q_in_radius)들을 다시 검토합니다.

만약 q_new를 경유하여 q_in_radius 노드로 가는 경로가 기존 경로보다 짧다면, q_in_radius 노드의 부모를 q_new로 변경하여 트리의 기존 가지를 더 짧은 경로로 재연결합니다.

결과: RRT*는 RRT보다 초기에는 경로를 찾는 속도가 느릴 수 있지만, 시간이 지남에 따라 더 효율적이고 최적에 가까운 경로로 수렴합니다.

5. RRT 및 RRT* 알고리즘의 주요 특징

확률적 완성도 (Probabilistic Completeness): 충분한 시간 동안 실행하면 경로가 존재할 경우 반드시 찾아냅니다.

확률적 최적성 (Probabilistically Optimal, RRT*): 충분한 시간 동안 실행하면 찾아낸 경로가 최적 경로에 수렴합니다.

고차원 공간 탐색: 로봇 팔의 다관절(Joint) 움직임과 같이 고차원적인 관절 공간에서의 충돌 없는 경로 계획에 매우 효과적입니다.

복잡한 장애물 회피: 불규칙하고 복잡한 형태의 장애물이 있는 환경에서도 경로를 쉽게 찾습니다.

6. 로봇 개발에서 RRT 및 RRT* 알고리즘의 활용

RRT 및 RRT* 알고리즘은 복잡하고 고차원적인 공간에서의 경로 계획 문제에 특히 강점을 보이며, 현대 로봇 개발에서 널리 활용됩니다.

6.1. 로봇 팔의 충돌 없는 경로 계획 (Collision-Free Motion Planning):

가장 대표적인 활용 분야입니다. 로봇 팔이 작업 공간 내의 장애물이나 로봇 자체의 다른 부분과의 충돌 없이 물체를 잡거나 조립하는 최적의 관절 각도 시퀀스(경로)를 찾는 데 RRT 계열 알고리즘이 사용됩니다.

MoveIt!: ROS 기반 로봇 팔 모션 플래닝 프레임워크인 MoveIt!의 내부에서도 RRT 계열 알고리즘이 기본 플래너로 사용됩니다.

6.2. 자율 이동 로봇의 경로 계획:

지형이 복잡하거나, 예측 불가능한 장애물이 많아 그래프로 표현하기 어려운 환경에서 자율 이동 로봇이 시작점에서 목표점까지 경로를 찾는 데 사용됩니다.

특히 샘플링 기반 RRT는 실시간 동적 장애물 회피가 가능합니다. 

6.3. 드론 및 무인 항공기의 비행 경로 계획:

복잡한 도시 환경이나 산악 지형에서 장애물(건물, 나무)과 충돌 없이 웨이포인트(Waypoint)를 따라 최적의 비행 경로를 계획합니다.

6.4. 멀티 로봇 시스템의 경로 계획:

여러 대의 로봇이 서로 충돌하지 않고 임무를 수행하기 위한 협력 경로를 계획하는 데 활용됩니다.

6.5. 게임 캐릭터 AI:

복잡한 게임 맵에서 캐릭터가 목표 지점까지 효율적으로 이동하는 경로를 찾는 데 사용될 수 있습니다.

RRT (Rapidly-exploring Random Tree) 및 RRT* (RRT-star) 알고리즘은 샘플링 기반 경로 계획의 대표 주자로, 복잡하고 고차원적인 환경에서 "무작위 샘플링을 통해 탐색 트리를 빠르게 확장"하여 경로를 찾아냅니다. RRT는 빠른 경로 탐색이 장점이지만 최적성을 보장하지 않으며, RRT*는 RRT의 빠른 탐색 능력에 **최적성(Probabilistically Optimal)**을 추가한 발전된 형태입니다.

로봇 개발에서 RRT 및 RRT* 알고리즘은 로봇 팔의 충돌 없는 모션 플래닝, 자율 이동 로봇의 경로 계획 등 복잡하고 동적인 환경에서 로봇에게 "빠르고 효율적인 의사 결정 능력"을 부여하는 데 필수적인 역량입니다. 이 강력한 알고리즘들의 원리와 작동 방식을 완벽하게 이해하고 로봇에 적용하는 것은 로봇에게 '스스로 복잡한 길을 개척하고 찾아가는 지능'을 불어넣어 미래의 자율 로봇 시대를 선도하는 중요한 발판이 될 것입니다.