RRT 기법의 단순화 및 새로운 충돌 회피 경로 생성 방법

1. 서 론

스마트 팩토리, 물류 자동화 등 많은 산업 분야에서 생산 최적화를 위해 자율 주행 로봇의 필요성은 증가하고 있다. 자율 주행 로봇의 중요한 과제 중 하나는 장애물을 회피하여 목적지에 도달하는 것이다. 이에 따라 다양한 경로 탐색 기법이 지속적으로 연구되어 왔다.^1-3) 일반적으로 사용하는 경로 탐색 기법의 하나로 RRT(Rapidly-exploring Random Tree)가 있다. RRT의 장점은 노드가 랜덤하게 뻗어 나가 빠르게 경로를 찾는다는 것이다. 하지만 장애물을 회피하여 생성된 경로가 자율 주행 로봇이 이동 불가능한 경로로 생성될 수 있다.⁴⁾ 또한 RRT는 비용함수를 고려하지 않기 때문에 탐색 된 경로가 복잡해질 우려가 있어 경로를 단순화하는 과정도 필요하다.⁵⁾ 본 연구에서는 RRT로 생성된 경로 중 목적지에 도달하는데 필요하지 않은 노드를 제거함으로 단순화를 진행하였다.

경로의 단순화를 진행하여도 최종적인 경로는 노드와 노드 사이를 잇는 직선의 형태이다. 회전 반경을 갖는 차륜형 로봇이 주행하기에는 적합하지 않다. 따라서 생성된 경로를 로봇이 주행하기 원활한 경로로 변환하는 과정이 필요하다.

곡선 경로의 변환 방법의 하나로 Bezier-Spline을 사용한다.²⁾ Bezier-Spline은 n개의 노드가 있을 때 n-1차 곡선의 형태로 산출된다. 따라서 노드의 개수가 많아지면 연산이 복잡해진다. RRT로 생성된 경로의 특성상 노드의 개수가 항상 일정하지 않으므로 연산하는 곡선의 차수가 매번 달라져야 한다. 또한 전체 경로를 작은 구간으로 나누어 연산하면, 모든 구간에서 미분 가능한 형태의 곡선으로 나타나지 않는 경우가 발생한다.

또 다른 곡선 경로의 변환 방법으로 B-Spline을 이용한 방법이 있다. B-Spline은 모든 구간에서 위치 및 기울기의 연속성을 가지는 C2 연속성을 만족한다. 따라서 전체 경로를 구간으로 나누어 연산하여도 Bezier-Spline과 달리 매끄러운 곡선으로 나타난다. 또한 B-Spline은 제어점을 수정해도 해당 제어점이 영향을 미치는 구간에서만 곡선의 국부적인 변화가 일어난다.⁶⁾ 따라서 장애물과의 충돌을 방지하기 위해 임의의 제어점을 추가하여 경로와 장애물의 거리를 증가시켜도 전체 곡선의 형태는 변하지 않는다. 본 연구에서는 이러한 특성을 가진 B-Spline을 적용하여 RRT로 생성된 경로의 곡선화를 진행하였다.

본 연구에서는 로봇의 크기를 고려한 안전 구역을 설정하고,⁴⁾ 경로 생성 후 불필요한 노드를 제거함으로써 단순화된 경로를 도출한다. 이후 B-Spline을 이용하여 직선으로 구성된 경로를 곡선 경로로 변환한다.⁷⁾ 이러한 과정을 통해 모든 구간에서 연속적인 곡률을 가진 곡선 경로를 생성한다. 또한 생성 경로에 제어점을 추가하는 방식으로 장애물과 충돌하지 않고 목적지까지의 곡선 경로 탐색법을 제안한다.

2. RRT 기법의 단순화 알고리즘

RRT는 샘플링 기반 경로 탐색 기법의 하나이다. 현재 노드와 랜덤하게 샘플링된 노드 사이를 직선으로 잇는다. 장애물과 충돌하지 않으면 현재 위치를 부모 노드, 샘플링된 노드를 자식 노드라 한다. 이 과정을 도식화한 것이 Fig. 1이다. 위 과정을 반복하여 새로운 노드를 생성하고 가지를 확장한다. 목적지에 도달하면 각 자식 노드에 대응하는 부모 노드를 추적하여 경로를 산출한다. 산출된 경로는 노드의 집합이므로 노드의 좌표값을 통해 경로점 P₁, P₂, P₃ ⋯ P_n을 저장한다.

Fig. 1

RRT Algorithm

RRT를 이용하여 경로 생성 시 장애물과 필요 이상으로 근접한 노드가 생성될 수 있다. 이 경우, 생성된 경로를 주행 시 차량과 장애물의 충돌 우려가 있다. 따라서 차량의 폭과 회전반경을 고려하여 안전공간을 설정해야 한다. 실제 인식한 장애물 주변에 가상의 공간을 설정함으로 장애물과 근접한 경로가 생성되는 것을 방지할 수 있었다.

또한 RRT는 랜덤하게 샘플링된 경로이므로, 효율적이지 못하여 단순화하는 과정이 필요하다. 생성된 경로 중 시작점에서 그다음 경로점들과 순차적으로 연결한다. 연결된 직선은 순차적으로 장애물과 충돌 여부를 판단한다. 충돌이 없을 경우 직선의 끝점에 해당하는 경로점은 임시로 보관한다.

충돌이 발생한 경우, 직전에 비교한 직선이 새로운 경로가 된다. 해당 경로의 끝점에 위치한 경로점은 시작점이 되며, 임시로 보관한 경로점들을 제거한다. 이 과정을 목적지에 도달할 때까지 반복한다. 랜덤하게 샘플링된 RRT 경로의 단순화한 것을 Fig. 2와 Fig. 3에서 확인할 수 있다.

Fig. 2

Method of Simplification

Fig. 3

Path planning with RRT (A) and Simplification of routes by eliminating inefficient coordinates (B)

3. 곡선 주행 경로 생성을 위한 B-Spline 곡선

RRT와 단순화를 통하여 생성된 경로는 노드와 노드 사이를 잇는 형태이므로 매끄럽지 않은 경로로 표현된다. 이는 회전 반경을 가지는 차륜형 로봇이 주행하기 어려운 경로이다. 따라서 B-Spline을 이용하여 경로를 곡선 변환하는 과정을 통해 주행이 원활한 경로를 산출하였다.

우선 3차 B-Spline 곡선을 생성하기 위해 N개의 경로점 P₁, P₂, P₃ ⋯ P_n중에서 연속된 4개 점을 사용한다. B-Spline 곡선을 나타내는 다항식 P(t)는 제어점 P_t, P_t+1, P_t+2, P_t+3와 기저 행렬 B와의 연산을 통하여 식 (1)과 같이 표현할 수 있다.

t는 제어점 4개로 표현되는 B-Spline의 연속되는 구간의 전체를 나타내며, t = 0은 구간의 시작점, t = 1은 구간의 끝점을 의미한다. 각 제어점이 곡선에 가하는 가중치를 나타낸 기저 행렬 B는 식 (2)와 같다.

기저 행렬 B를 통하여 하나의 구간에서 각 제어점이 B-Spline 곡선을 생성하기 위한 가중치를 나타내는 기저 함수 B(t)는 식 (3)으로 연산된다.

한 구간에서의 기저 함수를 그래프로 표현하면 Fig. 4와 같다. Fig. 4를 통해 하나의 구간에서 각 제어점이 가지는 가중치를 확인할 수 있다. 0 ≤ t ≤ 1를 만족하는 어떠한 시점 t에서 기저 함수와 각 제어점을 통해 B-Spline 곡선상에 존재하는 한 점의 위치를 결정할 수 있다.

Fig. 4

B-Spline Base Function

하나의 구간에서 곡선에 대한 모든 가중치를 가지는 제어점은 존재하지 않는다. 이러한 특성때문에 B-Spline 곡선은 제어점을 통과하지 않는다. 제어점을 통과하지 않기 때문에 B-Spline 곡선의 양 끝점은 RRT로 생성된 경로의 출발점과 도착점으로 연결되지 않는다. 이 문제를 해결하기 위해 P₁과 P_n을 각각 3번씩 추가하여 곡선의 매듭을 생성하였다. 따라서 최종적인 B-Spline 곡선의 제어점은 P₁, P₁, P₁, P₁, P₂ ⋯ P_n-1, P_n, P_n, P_n, P_n으로 구성된다. 이 제어점들을 통해 B-Spline 곡선은 시작점으로부터 1차, 2차 3차 순으로 그려지며 다시 3차, 2차, 1차 순으로 끝점과 연결된다.

4. 충돌 회피 경로 생성을 위한 제어점 추가방법 제안

B-Spline을 통한 경로의 변환 시 과도한 변형으로 인해 Fig. 5와 같이 장애물과의 충돌이 발생할 수 있다. 이러한 문제를 해결하기 위해 B-Spline의 특징 중 하나를 이용해 제어점을 추가하였다.

Fig. 5

The path on where the collision occurred (A) and path modified path (B)

Fig. 6을 통해 확인할 수 있듯이 하나의 제어점은 연속된 4개의 구간에만 가중치를 가진다. 이에 일부 제어점을 추가하더라도 B-Spline 곡선은 국부적인 변동만 발생한다. 이러한 B-Spline 곡선의 특성과 생성된 경로의 좌표를 이용한 충돌 회피 B-Spline 경로 생성 방법을 제안하였다. 생성된 경로 중 한 점 P_n과 이전 점 P_n-1, 다음 점 P_n+1을 통해 각각의 단위 벡터를 구한다.

Fig. 6

B-Spline Base Function on continuous intervals

생성된 단위 벡터를 기반으로 추가되는 제어점의 위치를 결정하였다. 각 단위 벡터의 연장선에 점 P_n으로부터 거리가 D_b, D_f인 제어점 P_nb, P_nf을 추가하였다. 이를 통해 $$ \overline{P_n{P}_{n+1}}$$ 구간에서 생성된 제어점의 순서는 P_n, P_nf, P_n+1b, P_n+1이다. D_f의 크기가 $$ \overline{P_n{P}_{n+1}}$$의 절반보다 큰 경우 생성되는 제어점의 순서는 P_n, P_n+1b, P_nf, P_n+1이 된다. 이때 Fig. 7의 (A)와 같이 이전 제어점의 영역이 이후 제어점의 영역과 겹치므로 D_f의 최대 크기 D_max는 $$ \overline{P_n{P}_{n+1}}$$의 크기의 절반보다 작아야 한다. D의 크기가 커지는 경우 장애물에 가까워지는 경향이 있으므로 크기가 작을수록 유리하며 차량의 회전 반경을 고려하였을 때 D의 최소 거리는 보장되어야 한다. D의 최소 거리와 추가되는 제어점의 위치는 차량의 회전 반경을 고려하여 계산하였다. 이 방식을 통해 다양한 지도에서 제안한 방법을 이용하여 탐색한 경로를 Fig. 8을 통해 확인할 수 있다. Fig. 8에서 각각의 지도에 표시된 녹색 노드는 기존 RRT를 이용하여 생성된 경로를 나타낸다. 적색 실선으로 표시된 경로는 단순화 이후 제어점이 추가된 경로이다. 마지막으로 청색 실선으로 표시된 경로는 B-Spline을 이용하여 최종적으로 생성된 경로를 나타낸다.

Fig. 7

Determination of the size of Df and Db. (A) where an overlapping section occurs, and (B) which is an independent section

Fig. 8

Results of modified path planning on different maps

1,000×1,000픽셀 크기의 각 지도에서 RRT, 단순화한 경로, 제안한 경로를 100회씩 생성한 결과, 각 경로의 거리를 Table 1에서 확인할 수 있다.

Table 1

Comparison of RRT, Simplification Path, and Modified Path

Table 1을 통하여 기존 RRT만으로 생성된 경로에 비해 단순화한 경로와 B-Spline을 이용한 경로가 평균적으로 각각 15%, 19% 감소함을 확인하였다.

실 차량을 이용한 무인 주행을 위해서는 제어점의 적합한 위치를 찾기 위해 차량의 회전 반경, 장애물과의 거리 등 여러 요소를 고려가 필요할 것으로 생각된다.

5. 결 론

RRT로 생성된 내비게이션 경로는 랜덤하게 샘플링된 결과이므로 효율적이지 못한 형태를 보인다. 단순화를 통해 생성된 경로의 불필요한 구간을 줄이면, 기존 RRT에 비해 최적화된 경로의 모습을 보여 준다. 이 과정으로 생성된 경로는 직선 경로이므로, 자율 주행 로봇의 주행을 위해서는 곡선 경로의 생성이 필요하다. 이를 위해 B-Spline을 이용하여 직선 경로가 매끄러운 형태의 곡선으로 변환되도록 하였다. 곡선 변환 과정에서 과도한 경로 변형은 장애물과 충돌을 유발하는 경로를 생성하기도 한다. 이에 본 연구에서는 B-Spline을 통해 생성되는 경로에 제어점을 추가하는 방식으로 매끄러운 경로 생성과 장애물과의 충돌을 방지하는 방법을 제안하였다. 제안된 방법은 시뮬레이션 환경에서 RRT 기법의 장점을 유지하면서, 장애물의 충돌을 방지하고 로봇의 주행이 용이한 경로 생성이 가능함을 보였다.

Acknowledgments

본 논문(저서)는 부산광역시 및 (재)부산테크노파크의 BB21plus 사업으로 지원된 연구임.

References

• E. Koyuncu, N. K. Ure and G. Inalhan, 2009, “Integration of Path/Maneuver Planning in Complex Environments for Agile Maneuvering UCAVs”, Journal of Intelligent and Robotic Systems, 57, 143-170. [https://doi.org/10.1007/s10846-009-9367-1]
• J. W. Choi, R. Curry and G. Elkaim, 2008, “Path Planning Based on Bézier Curve for Autonomous Ground Vehicles”, Advances in Electrical and Electronics Engineering, 158-166. [https://doi.org/10.1109/WCECS.2008.27]
• G. Tang, C. Tang, C. Claramunt, X. Hu and P. Zhou, 2021, “Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment”, IEEE Access, 9, 59196-59210. [https://doi.org/10.1109/ACCESS.2021.3070054]
• T. Maekawa, T. Noda, S. Tamura, T. Ozaki and K. Machida, 2010, “Curvature continuous path generation for autonomous vehicle using B-spline curves”, Computer-Aided Design, 42(4), 350-359. [https://doi.org/10.1016/j.cad.2009.12.007]
• H. Y. Song, 2020, “Improved path planning algorithm based on RRT-Connect guided by probabilistically estimated collision region”, MS thesis, Hanyang University, Korea.
• W. J. Gordon and R. F. Riesenfeld, 1974, “B-SPLINE CURVES AND SURFACES”, Computer Aided Geometric Design, 95-126. [https://doi.org/10.1016/B978-0-12-079050-0.50011-4]
• C. H. Park and J. H. Sim, 1998, “The Method of The Geometric Shape-Matching using spline”, The Transactions of the Korea Information Processing Society, 5(1), 181-190.