선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 느린 수렴 속도, 큰 메모리 요구성, 좁은 통로에서의 경로 생성 지연 문제를 모두 개선할 수 있는 Informed RRT*[5] 기반 경로 계획 기법을 제안한다. 제안된 기법은 수렴속도와 메모리 요구성을 개선한 Informed RRT*를 이용하여 경로 최적화를 진행한다.
- 본 논문에서는 최적 비용 경로로의 수렴 속도, 메모리 요구성, 좁은 통로 문제에 대응하기 위해 골격화를 이용한 Informed RRT* 개선 알고리즘을 제안하였으며, 그 성능을 잘알려진 환경의 격자 지도를 이용하여 검증하였다. 초기 경로 생성을 위해 RRT*가 아닌 격자 지도의 골격화를 이용하면, 복잡한 구조 및 좁은 통로가 존재하는 환경에서 최적 비용에 근사한 초기경로를 얻을 수 있다.
제안 방법
- 샘플링 기반 기법들은, ‘샘플링 기반을 대표하는 기법’, ‘골격화를 이용하는 RRT기반 기법’, ‘서론에서 언급한 세 가지 문제(수렴 속도, 메모리 효율성, 좁은 통로 문제)를 개선하기 위한 RRT* 기반 기법’들로 재분류하여 각각에 대한 특징 및 장단점을 살펴보고, 제안기법과 비교를 수행한다.
- 세 가지의 출발/도착 지점에 대해 시뮬레이션을 각각 백번 실행하여, 초기 경로 생성 시간, 초기 경로 비용, 최종 경로 생성 시간, 전체 노드 수의 평균과 표준편차를 계산하여 비교하였다.
- 본 논문에서 제안된 알고리즘의 성능을 평가하기 위해 Informed RRT*와 A*로 생성한 초기 경로를 이용하는 Informed RRT*와의 성능 비교를 실시하였다. 이때, A*로 생성된 초기 경로를 이용하는 Informed RRT*는 A*로 초기 경로를 생성한 후, 생성된 초기 경로를 기반으로 Informed RRT* 샘플링을 진행하여 경로 최적화를 진행하였다. 시뮬레이션을 수행한 컴퓨터는 Intel Core i7-2620M 2.
- Cloud RRT*는 GVG를 이용하여 샘플링 영역을 부분적으로 편향시킨다. 이산적으로 분할된 원 형태의 샘플링 영역을 줄이는 방식으로 수렴 속도를 개선하였다. 하지만, 샘플링이 진행됨에 따라 최적 비용 경로로의 수렴 시, 최적 비용 경로 부근으로 편향된 샘플링 원들은 주변 샘플링 영역의 일부 확률만 가져오므로 수렴 속도에 한계가 존재한다.
- 제안된 기법에서 Prim 알고리즘은 사용자가 지정한 시작점을 설정하여 시작점에서 가장 가까운 노드를 찾아 트리를 확장하게 된다. 트리의 노드들에서 아직 연결되지 않은 노드 중 가장 가까운 노드를 찾아 연결하는 과정을 모든 노드가 트리에 연결될 때까지 진행하게 된다.
- 기반 경로 계획 기법을 제안한다. 제안된 기법은 수렴속도와 메모리 요구성을 개선한 Informed RRT*를 이용하여 경로 최적화를 진행한다. 이때, 초기 경로 생성을 위해 RRT*가 아닌 골격화(skeletonization) 알고리즘을 이용한다.
- ’[21]이며, 이 격자 지도 상에는 복도 및 문과 같은 좁은 통로가 다수 존재한다. 출발지점과 도착 지점을 임의로 선택하여 각기 다른 세 가지 경우의 시뮬레이션을 수행하였다.
- 이와 비슷한 결과를 도출하는 기법으로 GVG(Generalized Voronoi Graph)[8]를 이용한 방법이 존재한다. 하지만, GVG는 격자 지도와 같은 복잡한 환경에서 골격 이미지를 생성하기 위해 정점[15]이나 형상[16]과 같은 특징 추출이 필요한 반면, 골격화는 특징 추출이 필요하지 않아 보다 간단하게 수행이 가능하므로 제안 기법에서는 골격화를 이용하였다. 골격화 알고리즘에는 대표적으로 형태적(morphological) 방식[17]과 zhang-suen 방식[18], guo-hall 방식[19]이 존재한다.
- Informed RRT*는 RRT*를 이용한 초기 경로 생성 시 샘플링이 진행됨에 따라 지도 전역에 걸쳐 트리가 생성되었다. 하지만, 제안 알고리즘은 골격화를 이용하여 생성된 초기 경로 부근의 영역에만 트리를 생성하여 경로의 비용 최적화를 진행하였다. 이는, 골격화로 생성한 초기 경로의 비용이 최적 경로의 비용에 근접하기 때문이다.
대상 데이터
- 이때, A*로 생성된 초기 경로를 이용하는 Informed RRT*는 A*로 초기 경로를 생성한 후, 생성된 초기 경로를 기반으로 Informed RRT* 샘플링을 진행하여 경로 최적화를 진행하였다. 시뮬레이션을 수행한 컴퓨터는 Intel Core i7-2620M 2.7GHz, 8GB RAM로 구성되어 있다. 운영체제는 Ubuntu 16.
데이터처리
- 본 논문에서 제안된 알고리즘의 성능을 평가하기 위해 Informed RRT*와 A*로 생성한 초기 경로를 이용하는 Informed RRT*와의 성능 비교를 실시하였다. 이때, A*로 생성된 초기 경로를 이용하는 Informed RRT*는 A*로 초기 경로를 생성한 후, 생성된 초기 경로를 기반으로 Informed RRT* 샘플링을 진행하여 경로 최적화를 진행하였다.
이론/모형
- 3.1.2에서 Harris Corner Detector를 이용하여 얻은 노드들의 좌표만으로는 초기 경로를 산출할 수 없으므로, 최소 신장 트리(Minimal Spanning Tree) 알고리즘을 이용한다. 최소 신장 트리 알고리즘은 대표적으로 Prim 알고리즘[23]과 Kruskal 알고리즘[24]이 존재한다.
- 1에서 격자 지도 이미지의 골격화를 수행한 이후 얻은 이미지에서는 RRT 기반 알고리즘에서 사용될 노드 정보를 얻을 수 없다. 따라서, 본 논문에서는 Harris Corner Detector[22]를 이용하여 골격 이미지로부터 노드 정보를 추출한다. 그러나 Harris Corner Detector를 이용하여 노드를 추출하면, 한 코너에서 중복으로 노드가 검출되는 경우가 발생한다.
- 반면, Prim 알고리즘은 경로의 출발 지점부터 트리 생성을 시작하고, 트리에 등록된 노드는 연산에서 제외하기 때문에 연산량이 훨씬적어 신속한 초기 경로 생성이 가능하다. 따라서, 초기경로 생성을 위해 Prim 알고리즘을 이용하였다.
- 제안된 기법은 수렴속도와 메모리 요구성을 개선한 Informed RRT*를 이용하여 경로 최적화를 진행한다. 이때, 초기 경로 생성을 위해 RRT*가 아닌 골격화(skeletonization) 알고리즘을 이용한다. 골격화 알고리즘으로 생성된 경로는 RRT*와 달리 좁은 통로에 의해 경로 생성이 지연되지 않고 신속한 경로를 생성한다.
- 제안된 기법에서는, 초기 경로 생성 후 보다 신속한 경로 최적화를 위해서 Informed RRT*[5]의 샘플링 기법을 이용한다. Informed RRT*는 지도 전역에서 샘플링을 진행하는 RRT*와달리, 최적 비용을 갖게 될 것으로 예상되는 영역 내에서만 샘플링을 진행하므로 연산 시간 면에서 우수한 성능을 보인다.
- ’[21] 격자 지도에 대해서 알고리즘마다 10회씩 수행한 결과의 연산 시간 평균값이다. 형태적 방식의 평균 연산 속도가 약 2배정도 더 빠른 것을 확인하였고, 따라서 Informed RRT* 개선 기법을 위해 형태적 골격화 알고리즘을 적용하기로 하였다.
성능/효과
- 이는 A*의 경로 생성 시간이 시작점과 도착점의 위치, 장애물의 위치에 대해 큰 영향을 받기 때문이다. Informed RRT*에 비해 제안 알고리즘의 초기 경로 생성 시간은 최소 약4배에서 최대 29배 감소되었다. 또한, 골격화를 이용한 알고리즘의 초기 경로 생성 시간 표준편차는 0.
- 가 존재한다. RRT*FN은 트리에 포함된 노드의 수를 사용자가 지정한 최대 노드의 수 까지만 유지되게 하여 메모리 효율을 높였다. 하지만, 경로 개선 시, 최적 비용 경로로의 수렴 속도가 느린 단점이 존재한다.
- [Table 3] ~ [Table 5]에서 볼 수 있는 바와 같이, 제안된 알고리즘의 초기 경로 생성 시간이 A* 초기 경로를 이용한 Informed RRT*에 비해 약3.6배에서 43배까지 감소되었다. 이는 A*의 경로 생성 시간이 시작점과 도착점의 위치, 장애물의 위치에 대해 큰 영향을 받기 때문이다.
- A*와 골격화는 같은 조건에서 항상 같은 경로를 생성하기 때문에 초기 경로 비용의 표준편차가 0으로 일정하다. 골격화를 이용하여 생성된 초기 경로의 비용은 RRT*를 이용하여 생성된 초기 경로에 비해 시뮬레이션 1에서는 약250 pixel, 시뮬레이션 3에서는 약130 pixel 단축된 것을 확인할 수 있다. 시뮬레이션 2에서는 Informed RRT*의 RRT* 의한 초기 경로가 약 50 pixel 짧게 생성되었지만, 초기 경로 생성을 위해 29배 정도 더 긴 시간이 소요되었다.
- 전체 노드 수를 비교해 보면, 제안 알고리즘에 의해 생성된 노드 수가 Informed RRT*에 비해 평균적으로 약 900 ~2,800개 더 적고 편차가 약 1,000이상 적다. 따라서 생성된 노드의 수가 더 적다는 것은 메모리 사용량이 더 적다는 것을 의미하기 때문에, 제안된 알고리즘이 Informed RRT*에 비해 메모리 효율성이 더 높다는 것을 입증할 수 있다. 제안된 알고리즘의 생성된 노드 수가 A*를 이용한 Informed RRT*에 비해 약 1.
- 하지만, 골격화 알고리즘으로 생성된 경로는 최적 비용 경로보다 더 큰 비용을 갖게 되어 경로 개선이 필요하다. 따라서, 제안된 기법을 이용하면 복잡한 환경 및 좁은 통로가 존재하는 환경에서 보다 최적 비용에 근사한 초기 경로를 얻으므로 경로 탐색 시간을 줄여 신속한 경로 계획이 가능하다.
- Informed RRT*에 비해 제안 알고리즘의 초기 경로 생성 시간은 최소 약4배에서 최대 29배 감소되었다. 또한, 골격화를 이용한 알고리즘의 초기 경로 생성 시간 표준편차는 0.04 이하로 작은 값을 보여, 초기 경로 생성 시간 차이가 적음을 입증하였다. 반면에, Informed RRT*의 표준편차는 최소 약11에서 최대 약150이므로 매시행 마다 큰 차이를 보인다.
- 따라서, 전체적인 경로 탐색 시간을 줄여 신속한 경로 계획이 가능하다. 또한, 실행할 때마다 생성된 경로의 비용 및 연산 시간 면에서 큰 편차를 보인 기존의 Informed RRT*와 달리 제안된 골격화를 이용한 방법은 편차가 작은 안정된 결과를 보여주었다. 또한, 초기 경로 생성 시, 제안된 골격화 대신 A*를 적용한 결과에서는 골격화를 이용한 방법이 연산 시간면에서 더 우수함을 입증하였다.
- 또한, 실행할 때마다 생성된 경로의 비용 및 연산 시간 면에서 큰 편차를 보인 기존의 Informed RRT*와 달리 제안된 골격화를 이용한 방법은 편차가 작은 안정된 결과를 보여주었다. 또한, 초기 경로 생성 시, 제안된 골격화 대신 A*를 적용한 결과에서는 골격화를 이용한 방법이 연산 시간면에서 더 우수함을 입증하였다. RRT 기반 알고리즘들은 2차원 공간뿐만 아니라 고차원 공간에서도 많이 활용되고 있다.
- 골격화를 이용하여 생성된 초기 경로의 비용은 RRT*를 이용하여 생성된 초기 경로에 비해 시뮬레이션 1에서는 약250 pixel, 시뮬레이션 3에서는 약130 pixel 단축된 것을 확인할 수 있다. 시뮬레이션 2에서는 Informed RRT*의 RRT* 의한 초기 경로가 약 50 pixel 짧게 생성되었지만, 초기 경로 생성을 위해 29배 정도 더 긴 시간이 소요되었다. 초기 경로 비용의 표준 편차는 Informed RRT*의 경우 경로에 따라 큰 차이를 보였다.
- 이는 초기 경로 생성을 위해 사용되는 RRT*가 좁은 통로에 효율적으로 대처하지 못하기 때문이다. 이로써, 제안된 알고리즘은 골격화를 이용하여 좁은 통로와 상관 없이 신속한 초기 경로 생성이 가능함을 입증할 수 있다. A*와 골격화는 같은 조건에서 항상 같은 경로를 생성하기 때문에 초기 경로 비용의 표준편차가 0으로 일정하다.
- RRT*를 이용하여 초기 경로를 생성하는 Informed RRT*에 비해, 제안된 알고리즘은 초기 경로 생성 시 좁은 통로에 영향을 받지 않고 최적 비용 경로에 근접하여 빠르게 진행하였기 때문이다. 전체 노드 수를 비교해 보면, 제안 알고리즘에 의해 생성된 노드 수가 Informed RRT*에 비해 평균적으로 약 900 ~2,800개 더 적고 편차가 약 1,000이상 적다. 따라서 생성된 노드의 수가 더 적다는 것은 메모리 사용량이 더 적다는 것을 의미하기 때문에, 제안된 알고리즘이 Informed RRT*에 비해 메모리 효율성이 더 높다는 것을 입증할 수 있다.
- 국소 최저점에 빠지지 않는 경로 생성이 가능하지만, 경로 개선이 어려우므로 경로 비용을 줄이는데 한계가 있다. 제안 기법은 위 방식들과 달리 경로 개선이 수월하고 국소 최저점에 빠지지 않으며 신속하게 최적비용 경로로의 수렴이 가능하다.
- 골격화 알고리즘에는 대표적으로 형태적(morphological) 방식[17]과 zhang-suen 방식[18], guo-hall 방식[19]이 존재한다. 제안된 기법에서 골격화 알고리즘은 빠른 초기 경로 생성을 위해 사용되므로, 위 세 방식 중에서 연산 시간이 가장 빠른 방법을 선정하였다. Gulshan Goyal은 zhang-suen 방식과 guo-hall 방식의 성능 비교를 실시하였는데, zhang-suen 방식이 연산 시간과 최대 신호대 잡음 비 방면에서 guo-hall에 비해 우수함을 입증하였다[20].
- 87이다. 제안된 알고리즘은 모든 시뮬레이션에서 0이며, 이는 골격화를 이용한 알고리즘이 훨씬 안정적인 초기 경로를 생성하는 것을 의미한다. A*를 이용한 Informed RRT*는 제안 알고리즘에 비해 초기 경로의 비용이 모든시뮬레이션에서 더 적지만, 초기 경로 연산 시간이 최소 약3.
- 따라서 생성된 노드의 수가 더 적다는 것은 메모리 사용량이 더 적다는 것을 의미하기 때문에, 제안된 알고리즘이 Informed RRT*에 비해 메모리 효율성이 더 높다는 것을 입증할 수 있다. 제안된 알고리즘의 생성된 노드 수가 A*를 이용한 Informed RRT*에 비해 약 1.5~4배정도 더 많다. 이는 A* 알고리즘 수행 시 트리에 포함되지 않은 노드의 수는 고려되지 않았기 때문이다.
- 6배 이상 더 소요된다. 총 연산 시간은 세 시뮬레이션 모두 제안된 알고리즘을 사용한 결과가 Informed RRT*에 비해 약3~10배, A*를 이용한 Informed RRT*에 비해 약 1.7~2.4배 덜 소요되었다. RRT*를 이용하여 초기 경로를 생성하는 Informed RRT*에 비해, 제안된 알고리즘은 초기 경로 생성 시 좁은 통로에 영향을 받지 않고 최적 비용 경로에 근접하여 빠르게 진행하였기 때문이다.
후속연구
- 따라서, 사전 작업을 진행한 격자 지도로 제안 기법을 이용한 경로 계획 시, 로봇을 크기가 없는 점으로 표현하더라도 보다 실제 주행에 적합한 경로 생성이 가능하다. 위 부분은 향후 추가적인 연구를 통해 수행될 예정이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.