Current Issue

앞서 언급했듯이 기존 RRT 알고리즘을 개선한 많은 알고리즘이 존재하며 표 1과 요약될 수 있다. 대표적으로 비용 함수 및 Rewire 과정을 추가하여 성능을 개선한 RRT*[3]-[5]가 있다. Rewire 과정은 각 노드에서 계산된 비용 함수의 값을 비교하여 더 낮은 값의 노드가 있다면 기존에 이어진 노드를 끊고 비용 함수 값이 더 낮은 노드로 새로 연결하는 것을 뜻한다.

fast-RRT[6]는 샘플링 전략을 수정한 것으로, 각 노드마다 원형의 탐색된 구역을 설정하고 탐색된 구역 내에서는 샘플링을 하지 않도록 하여 속도 개선을 이루어낸 알고리즘이다. 추가적으로 장애물을 만났을 때 랜덤한 각도의 노드를 생성하여 RRT의 단점인 좁은 길목을 지나지 못하는 점을 극복하였다. RRT*-SMART 알고리즘은[7]-[9] RRT*를 이용하여 최초로 경로를 생성한 이후 생성된 노드들의 노드, 부모 노드, 부모 노드의 부모 노드의 위치를 바탕으로 삼각형을 만들고, 삼각형의 가장 긴 변은 나머지 변의 합보다 작다는 삼각 부등식의 조건을 활용하여 경로를 최적화하는 알고리즘이다. Informed RRT* 알고리즘[10]-[12]은 타원 위의 한점에서 두 초점을 잇는 직선 길이의 합이 장축과 동일하다는 성질을 이용하여 샘플링 영역을 한정하여 연산 속도를 개선하였다. RRT*-FN[13][14] 알고리즘은 tree에 존재하는 leaf 노드들을 랜덤하게 제거하여 노드의 수를 줄여서 소모되는 자원을 줄이면서도 기존 성능을 유지할 수 있도록 개선하였다. anytime RRT* 알고리즘[15]은 분기한정법(Branch and bound)을 이용하여 필요 없는 노드들을 제거하여 최적성과 연산 시간에서의 개선을 이루어냈다. B-RRT*[16]는 두 가지 유형의 노드를 사용함으로써 고차원에서의 경로 계획을 가능하게 하고, 휴리스틱한 방법을 적용하여 경로 개선 및 수렴 속도에서의 개선을 하였다.

이 외에도 다양한 RRT 기반의 알고리즘들이 있으나, 대부분 자유 공간에 대한 결과를 나타내고 있다. 좁은 길목을 찾아내어 지나가는 알고리즘은 존재했으나[6], 길고 좁은 환경이 지속되는 것이 아닌 free space에서 장애물 사이의 협소한 공간을 지나가는 정도로 그쳤다.

복도 환경은 건물 내부에서 쉽게 찾을 수 있고 대체로 길고 좁은 길이다. 장애물은 건물의 기둥, 소수의 가구 정도로 다른 환경에 비해 비교적 적다는 특징이 있다. 길고 좁다는 특징으로 인해 로봇의 진행 경로가 단순하며 직선적이다. 이는 샘플링을 해야 할 영역 또한 단순하고 직선적이라는 것을 의미한다. 따라서 기존 RRT 기법을 사용하게 되면 샘플링 횟수가 불필요하게 많아질 수 있고 이는 경로 계획의 비효율성을 초래한다. 그리고 생성된 경로 역시 복도의 양 쪽 벽에 치우친 불안정한 경로를 생성할 수 있다. 또한 직선적이라는 것은 방향 전환이 자주 일어나지 않는다는 것을 의미한다.

본 논문에서는 이러한 문제점들에 초점을 맞추어 복도 환경에서 보다 효율적인 샘플링 기반 경로 계획을 수행할 수 있는 방향적 탐색 랜덤 트리(DRT, Directionally-exploring Random Trees) 기법을 제안한다.

점진적 지역 목표점 설정은 출발지에서 목적지까지 구간을 나누는 것이다[17]. 구간의 크기는 직접 설정 할 수 있고, 구간의 개수는 크기에 따라 변한다. 또한 일정한 크기로 나누지 않고 랜덤 함수를 거쳐 약간의 무작위성을 지닌다. 보다 자세한 점진적 지역 목표점 설정 방법은 다음과 같다. 먼저 출발점과 최종 목적지를 설정한다. 그리고 점진적 지역 목표점 설정을 위한 임시 목적지를 설정한다. 이는 2가지 이상 설정이 가능하다. 출발점, 최종 목적지, 임시 목적지를 설정한 이후 구간의 크기를 설정한다. 설정값에 맞게 구간을 나누어 목표점을 설정하는데, 이때 랜덤 함수값에 따라 무작위하게 목표점이 설정된다. 모든 설정을 마쳤다면, 첫 번째 출발지에서 첫 번째 임시 목적지로 점진적 지역 목표점 설정을 완료하고, 첫 번째 임시 목적지에서 두 번째 임시 목적지까지 점진적 지역 목표점 설정을 완료하게 되고 이 과정을 N 번째 임시 목적지까지 반복 수행한다. 이후 최종 목적지까지 점진적 지역 목표점 설정을 완료한다.

그림 3은 점진적 지역 목표점 설정의 예로 오른쪽 상단에서 좌측 상단까지 점진적 지역 목표점(보라색 점)들이 생성된 것을 보여준다.

Fig. 3. 
Example of the progressive determination of local goals

극좌표계 기반 샘플링은 목표점과 목표점 사이를 지정한 Theta 값으로 좁혀 제한된 영역에서 샘플링을 수행한다. 복도 환경에서 경로 계획을 진행할 때 진행 방향은 직진성을 지니고 있어서, 진행 방향의 뒤, 위, 아래쪽은 샘플링을 할 필요성이 상대적으로 적다. 기존 직교좌표계 기반 샘플링은 모든 방향으로 샘플링을 진행하기에 여기서 연산의 낭비가 이루어진다. 또한 RRT 알고리즘의 단점 중 하나인 최적성를 고려하지 않는다. 제안하는 알고리즘의 극좌표계 기반 샘플링은 경로 계획의 진행 방향으로 샘플링을 수행함과 동시에 샘플링을 해야할 가치가 비교적 떨어지는 영역을 제한함으로써 연산의 낭비 및 최적성을 극복하였다.

그림 4는 점진적 지역 목표점에 따른 구간마다 Theta 값을 지정하여 랜덤 샘플링을 하는 과정을 설명한다. Nearest는 트리에서 가장 가까운 노드이며, node1과 node2는 샘플링된 노드이다. 여기서 node1은 지정된 Theta 각도에서 벗어났으므로 제외하며, node2가 선택된다. 이와 같은 과정을 각 목표점(local goal)마다 지정된 Theta 값을 통해 반복 수행된다.

Fig. 4. 
Concept of sampling in polar coordinate system

극좌표계 기반 샘플링을 적용하게 되면서 기존의 RRT*에서 사용하던 비용 함수가 비효율적이라 판단되어 비용 함수를 재정의하여 새로운 비용 함수를 사용하였다. 기존의 비용 함수는 다음과 같다.

여기서 Cost 함수는 정점 v까지의 누적 비용으로, Euclidean 거리를 합산한 값을 사용한다. c는 v의 부모로부터 v까지의 연결 비용을 뜻하며, Line 함수는 두 정점간의 Euclidean 거리이다. 제안된 알고리즘에서의 비용 함수는 Euclidean 거리값에 추가적으로 각도 값을 더하여 극좌표계 기반 샘플링에 맞도록 재정의되었다.

여기서 Angle 함수는 각각의 정점과 그 정점의 부모의 좌표 값을 이용해 각도를 구하여 그 값의 차를 반환하는 함수이다.

표 2는 제안하는 알고리즘(DRT)의 Pseudo code이다. Pseudo code와 함께 주요 함수에 대한 목록을 기술한다.

• ⦁ InitialDestnationPoint : 점진적 지역 목표점을 설정 한다.
• ⦁ Nearest(T, x) : Euclidean 거리를 계산하여 x와 사이 거리를 계산하고 가장 가까운 정점 v를 반환한다.
• ⦁ Steer(x, y) : x와 y 사이의 거리가 stepsize에 맞는지 확인 및 조절한다.
• ⦁ ObstacleFree(x ,y) : x와 y 사이에 장애물이 있는지 판단한다.
• ⦁ Near(T, x, V) : x의 특정 반경 안에 있는 정점들을 반환한다.
• ⦁ Rewiring(X_near, x_new, E) : X_near의 각각의 노드들 과 x_new 사이에 장애물 충돌 여부를 판단하고, 충돌이 없다면 비용 함수 값을 비교한다. 비교 후 더 낮은 비용 함수값이 있다면 해당 노드로 재연결한다.

실험 환경은 모두 복도 환경으로 구성되어 있었다. 공용 데이터셋의 환경은 좌측과 우측에 곡선 형태로 이어진 복도가 특징이고, 중앙의 큰 복도 외곽에 방들이 이어져 있고 중앙에도 통로가 존재한다. 실제 실험 환경은 길고 좁은 복도 2개와 비교적 넓은 복도가 ㄷ자 형태로 이어져 있는 구조이다. 좁은 복도는 벽과 벽 사이의 간격이 약 2.4m 정도로 좁은 편이며, 넓은 복도는 벽과 벽 사이의 간격이 5.0m 이상의 넓은 구간이 이어지는 환경이다.

우측의 넓은 복도에는 학생들이 공부를 하거나 쉬는 용도의 책상, 의자가 비치되어 있는 라운지와 건물을 지지하는 둥근 기둥이 존재한다. 시뮬레이션에서 장애물 회피 성능 확인을 위해 임의의 크고 작은 사각형의 장애물을 배치하였고 이는 총 6개로 진한 검은색 사각형으로 표시되어 있다.

본 논문에서 제안하는 DRT 알고리즘의 성능을 확인하기 위해 두 가지 지도에서 기존의 RRT* 알고리즘, 점진적 지역 목표점을 추가한 RRT*-P 알고리즘 그리고 제안하는 DRT 알고리즘과 비교하는 방법으로 진행하였다.

성능 비교는 두 가지 지도에서 기존 RRT* 알고리즘, RRT*-P 알고리즘, DRT 알고리즘 시뮬레이션을 각각 10회 수행한 결과물로 진행한다. 시뮬레이션은 다음과 같은 조건에서 수행되었다. 샘플링 횟수 제한을 3000회, stepsize 길이는 10으로 설정하였고 로봇의 크기, holonomic의 여부는 고려되지 않았다.

그림 7은 첫 번째 지도에서 경로 계획을 수행한 시뮬레이션 결과의 일부이다. 시뮬레이션에서 빨간색 마름모는 출발점, 초록색 마름모는 도착지이며 보라색 마름모는 점진적 지역 목표점이다. 파란색 직선은 샘플링 후 ObstacleFree가 고려된 노드이며 빨간색 점선은 출발지에서 목적지까지 연결된 이후 최종적인 path이다.

Fig. 7. 
Path planning results in grid map #1, (a) RRT* (b) RRT*-P (c) DRT

각각의 경로를 비교하였을 때 그림 7(a)의 기존 RRT* 알고리즘의 노드들은 불필요한 영역까지 샘플링하는 경향을 보이고 있으며 목적지에서 벗어난 방향도 탐색을 수행하고 있다. 그림 7(b)과 그림 7(c)에 해당하는 점진적 지역 목표점을 더한 RRT* 알고리즘과 DRT 알고리즘으로 수행된 결과에서는 꾸준히 목적지 방향을 향하여 샘플링됨으로써 효율적인 경로를 생성하고 있다.

조금 더 정확한 비교를 위한 최종 경로만을 그려진 그림 8(a) 및 그림 8(b)에서 볼 수 있듯이 기존 RRT* 알고리즘과 점진적 지역 목표점을 설정한 RRT* 알고리즘에 의해 생성된 경로는 다소 불안정한 모습을 나타내고 있고 복도의 양 쪽 벽에 근접한 경로까지 생성된 결과가 나타난다. 반면 DRT 알고리즘에서는 앞선 결과들과 비교했을 때 보다 직선적으로 경로를 생성하며 복도의 양 쪽 벽으로부터도 어느 정도 거리를 잘 유지하는 안정적인 경로를 생성했음을 알 수 있다. 따라서 RRT* 알고리즘의 경로에 비해 DRT 알고리즘 보다 효율적이고 안정적인 경로를 생성했다고 판단된다.

Fig. 8. 
Final path in grid map #1, (a) RRT* (b) RRT*-P (c) DRT

그림 9는 두 번째 지도에서 경로 계획을 수행한 시뮬레이션 결과의 일부이며, 각각의 경로를 비교하였을 때 그림 9(a)의 기존 RRT* 알고리즘의 노드들은 복도를 전체적으로 샘플링하는 경향을 보이고 있으며 목적지에서 벗어난 방향도 탐색을 수행 하고 있다. 그림 9(b)과 그림 9(c)에 해당하는 점진적 지역 목표점을 더한 RRT* 알고리즘과 DRT 알고리즘으로 수행된 결과에서는 꾸준히 목적지 방향을 향하여 샘플링됨으로써 보다 효율적인 경로를 생성하고 있다.

Fig. 9. 
Path planning results in grid map #2

조금 더 정확한 비교를 위한 최종 경로만을 그려진 그림 10(a) 및 그림 10(b)에서 볼 수 있듯이 기존 RRT* 알고리즘과 점진적 지역 목표점을 설정한 RRT* 알고리즘의 경로는 직선적이지 못한 구간이 자주 관측되기 때문에 효율성이 떨어진다. 반면 DRT 알고리즘에서는 앞선 결과들과 비교했을 때 보다 직선적으로 경로를 생성함으로써 향상된 결과를 나타내고 있다.

Fig. 10. 
Final path in grid map #2

표 3, 표 4, 표 5는 첫 번째 지도에 대해 각각 샘플링 횟수, 수행 시간 최종 거리에 대한 정량적인 수치 비교 결과이다. 먼저 표 3에서 나타난 바와 같이, 샘플링 횟수에서 제안된 DRT 기법이 다른 두 기법들에 비해 상당히 작은 결과를 나타내었다. 이는 수행 시간과도 관련이 있으며, 표 4와 같이 DRT 기법이 다른 두 기법들에 비해 매우 작은 수행시간을 나타내었음을 알 수 있다. 표 5에서 최종 거리는 빨간색 직선의 길이로 측정하였고 픽셀 당 실제 거리를 환산하여 측정하였다. 최종 거리 부분에서도 DRT 기법이 다른 두 기법들에 비해 짧은 거리를 나타냄으로써 보다 효율적인 경로를 생성했음을 알 수 있다.

표 6, 표 7, 표 8은 두 번째 지도에 대해 각각 샘플링 횟수, 수행 시간 최종 거리에 대한 정량적인 수치 비교 결과이다. 먼저 샘플링 횟수에서 점진적 지역 목표점 설정을 하지 않은 RRT* 알고리즘과 나머지 2개의 알고리즘 간의 차이가 200회 가량 차이가 난다. 이는 수행 시간과도 관련이 있으며 약 25초의 차이를 보인다는 것을 알 수 있다. 최종 거리는 빨간색 직선의 길이로 측정하였고 픽셀 당 실제 거리를 환산하여 측정하였다. 최종 거리 부분에서도 DRT 알고리즘이 기존 RRT* 알고리즘에 비해 약 900의 차이, 점진적 지역 목표점을 설정한 RRT* 알고리즘에 비해 약 650의 차이로 더 짧은 거리로 경로 계획을 수행함을 보여준다. 따라서 제안된 DRT 기법이 정량적으로도 다른 두 기법들에 비해 뛰어난 성능을 나타내었음을 알 수 있다.

최종 경로의 효율성을 평가하기 위해, 그림 11 및 그림 12와 같이 최종 경로를 구성하는 노드들 간 각도 변화량에 대한 히스토그램을 비교하였다. 기법들마다 최종 경로의 길이가 다르므로, 확률적 정규화를 적용 후 히스토그램 분석을 하였고 간격은 시각적 판별의 용이성을 위해 30도로 설정하였다. 두 지도 모두에서 제안된 기법인 DRT가 최종 결로 대비 작은 각도 변화량을 나타냄으로써 가장 효율적인 경로를 생성했음을 알 수 있었다.

Fig. 11. 
Histogram of the angle difference between nodes on the final path in grid map #1

Fig. 12. 
Histogram of the angle difference between nodes on the final path in grid map #2