Korean Institute of Information Technology
[ Article ]
The Journal of Korean Institute of Information Technology - Vol. 20, No. 4, pp.57-68
ISSN: 1598-8619 (Print) 2093-7571 (Online)
Print publication date 30 Apr 2022
Received 16 Mar 2022 Revised 21 Apr 2022 Accepted 24 Apr 2022
DOI: https://doi.org/10.14801/jkiit.2022.20.4.57

복도 환경에서 효율적 로봇 경로 계획을 위한 방향적 탐색 랜덤 트리 기법

김석영* ; 남성현** ; 이헌철***
*금오공과대학교 IT융복합공학과 석사과정
**한국전자기술연구원 연구원
***금오공과대학교 IT융복합공학과 교수(교신저자)
Directionally-Exploring Random Trees for Efficient Robot Path Planning in Corridor Environments
Seokyoung Kim* ; Sunghyun Nam** ; Heoncheol Lee***

Correspondence to: Heoncheol Lee Dept. of IT Convergence Engineering, School of Electronic Engineering Kumoh National Institute of Technology, Korea Tel.: +82-54-478-7476, Email: hclee@kumoh.ac.kr

초록

본 논문에서는 복도 환경에서 로봇 자율 주행을 위한 경로 계획 문제를 다룬다. 로봇 경로 계획에 널리 사용되고 있는 RRT(Rapid-exploring Random Tree) 기법은 복도 환경과 같이 특정 방향으로 공간이 편중되어 있는 경우, 경로 생성을 위해 소요되는 샘플링 횟수가 불필요하게 많아짐에 따라 비효율적 경로 계획을 수행한다. 또한 생성된 경로도 복도의 양 쪽 벽에 치우친 불안정한 경로를 생성할 수 있다. 이 문제들을 해결하기 위해 본 논문에서는 샘플링 영역 설정 및 랜덤 노드 생성시에 방향적 요소를 반영하고 재정의된 비용 함수를 사용하는 방향적 탐색 랜덤 트리(Directionally-exploring random trees) 기법을 제안한다. 제안된 기법은 공용 데이터셋 및 실제 실험을 통해 획득한 격자 지도를 기반으로 수행되었고, 기존 RRT보다 알고리즘에 비해 샘플링 횟수, 수행 시간, 최종 거리를 감소시킴으로써 향상된 성능을 나타내었다.

Abstract

This paper addresses the problem of path planning for autonomous navigation in corridor environments. When the RRT(Rapid-Exploring Random Tree) which has been widely used in robot path planning is applied to corridor environments with a biased direction, its efficiency degenerates due to unnecessary sampling. Besides, the produced path causes unstable navigation close to walls on both sides. To resolve the problems, this paper proposes a DRT(Directionally-Exploring Random Trees) which not only applies directionality to search space determination and node generation but also uses a redefined cost function for corridor environments. The proposed method was tested with grid maps produced by both a public dataset and real experiments and showed improved performance by reducing the number of sampling, computation time, and final path length by comparison with the conventional RRT.

Keywords:

path planning, corridor environments, random sampling, autonomous navigation

Ⅰ. 서 론

경로 계획은 로봇 공학, 자율 주행 등 많은 분야에서 활용되고 있으며 현재까지도 많은 연구자들이 연구를 지속하고 있다. 경로 계획은 원하는 객체가 시작점에서부터 목적지까지 장애물을 최대한 회피하며 최단 경로를 찾는 것을 말한다. 경로 계획을 위한 방법은 여러 가지 존재한다. Grid-based search, Artificial potential fields, Sampling-based search 등 여러 알고리즘을 통해 경로 계획을 수행할 수 있다. 그 중에서도 샘플링 기반 알고리즘은 여러 다양한 시스템에 적용하기 쉽다는 점, 제한 조건이 적다는 점, 높은 차원의 상태의 공간에서도 구현이 비교적 쉽다는 점 등의 장점을 가진 알고리즘으로 폭넓게 활용되고 있다. 샘플링 기반 경로 계획 알고리즘은 대표적으로 RRT(Rapid-Exploring Random Tree)[1]와 PRM(Probabilistic Road Map)[2]을 꼽을 수 있다. 그 중에서도 RRT는 PRM에 비해 좀 더 복잡한 환경에서도 동작하며, 최적화, 계산 시간 등에 있어서 장점이 있기에 RRT에 주목하였다.

RRT는 상태 공간에서 새로운 노드를 임의로 샘플링하여 탐색 가능한 트리를 생성하고 목적지까지 이어나가는 알고리즘이다. RRT는 뛰어난 알고리즘이지만 최적성(Optimality)를 보장하지 않는 점, 샘플링 영역이 광범위하기에 불필요한 연산을 계속 수행한다는 등의 단점이 존재한다. 이를 극복하기 위해 RRT를 기반으로 하여 개량된 많은 알고리즘이 최근까지도 연구되어왔다. 그중에서도 RRT*[3]-[5]는 기존 RRT에서 비용 함수를 추가하고 그에 따라 노드의 Rewire 과정을 수행하여 RRT와 비슷한 연산량으로 더 효과적인 경로 계획을 수행한다.

그림 1은 RRT*를 실행한 예로, 출발지(빨간색 점)에서 목적지(초록색 점)까지 랜덤하게 샘플링한 노드로 트리를 구성하여(파란색 실선) 경로(빨간색 실선)를 찾아가는 것을 보여준다. RRT* 알고리즘은 또 다른 기반이 되어 연산량 감소, 최적 경로 수렴 속도 등을 개선한 다양한 알고리즘을 낳았다. 여기서 우리는 복도라는 좁고 긴 환경에 주목하고, 이 특수한 환경에서 효과적인 경로 계획을 구현하였다. 기존의 RRT* 알고리즘은 복도 환경에서 적용한다면 샘플링 영역이 비교적 광범위하다.

Fig. 1.

Example of the conventional RRT* producing a path with a red dotted line from red dot to green dot

복도 환경에 맞추어 샘플링 영역 제한 및 최적화를 통해 연산량 감소 및 최적 경로 생성을 구현한 알고리즘을 제안한다. 이후 논문은 다음과 같이 구성된다. 2장에서는 복도 환경의 특징 및 경로 계획 시의 문제점에 대해서 다룬다. 3장에서는 제안하는 알고리즘의 전체적인 개요 및 세부적인 작동 원리에 대해 설명한다. 4장에서는 기존의 RRT* 알고리즘과 제안된 알고리즘과의 비교 분석을 통해 정성적, 정량적인 성과를 제시하고 마지막으로 5장에서 결론에 대해 언급한다.


Ⅱ. 관련 연구

2.1 기존 RRT 기반 연구 분석

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

Related works for performance improvement of the conventional RRT

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에서 장애물 사이의 협소한 공간을 지나가는 정도로 그쳤다.

2.2 복도 환경의 문제점

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

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


Ⅲ. 방향적 탐색 랜덤 트리 기법

기존의 RRT* 알고리즘에서 추가적인 과정을 거쳐서 복도 환경에서의 경로 계획을 개선하고자 한다. 추가된 것으로는 3가지가 있다. 첫째, 점진적 지역 목표점 설정으로 출발지에서 목적지까지 구간을 나누는 것이다. 이는 극좌표계 기반 샘플링을 위한 것으로, 샘플링 범위를 조절할 때 지도 전체가 아닌 일부 구간 내에서 하는 것이 보다 효과적이다. 둘째, 기존의 직교좌표계 기반 샘플링이 아닌 극좌표계 기반 샘플링을 수행한다. 구간 내의 모든 범위를 샘플링 하는 것이 아닌, 파라미터(Theta) 값을 두고 파라미터 값의 범위 내의 제한된 영역에서 샘플링을 수행하여 불필요한 연산 시간을 줄일 수 있다. 기존 RRT*에서 사용되는 비용 함수는 노드에서 목적지까지의 거리만을 계산하고 있다. 이는 극좌표계 기반 샘플링과는 적합하지 않다고 판단하여 거리 및 각도를 포함한 재정의된 비용 함수를 적용하였다.

그림 2는 제안된 기법의 순서도로, 파란색 도형은 기존 RRT*의 알고리즘의 순서도의 일부이며 붉은색 도형은 제안된 기법으로, 기존 RRT* 알고리즘에서 추가되거나 대체된 부분이다.

Fig. 2.

Flowchart of the proposed algorithm

기존 RRT* 알고리즘 대비 변경 및 추가사항은 다음과 같다. 첫째, 극좌표계 기반 샘플링을 통한 랜덤 노드 생성이다. 이는 기존 RRT* 알고리즘에서는 직교좌표계 기반 샘플링을 대체한 부분이다. 둘째, 재정의된 비용 함수이다. 주변 노드의 비용 계산으로 기존 RRT* 알고리즘의 각도를 포함하지 않는 비용 함수를 사용한 비용 계산을 대체하고 있다.

3.1 점진적 지역 목표점 설정

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

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

Fig. 3.

Example of the progressive determination of local goals

3.2 극좌표계 기반 샘플링

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

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

Fig. 4.

Concept of sampling in polar coordinate system

3.3 비용 함수 재정의

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

Costυ=CostParentυ+cLineParentυ,υ(1) 

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

Costυ=CostParentυ+cLineParentυ,υ+AngleParentυ,υ(2) 

여기서 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(Xnear, xnew, E) : Xnear의 각각의 노드들 과 xnew 사이에 장애물 충돌 여부를 판단하고, 충돌이 없다면 비용 함수 값을 비교한다. 비교 후 더 낮은 비용 함수값이 있다면 해당 노드로 재연결한다.

Pseudo code of the DRT


Ⅳ. 결과 및 분석

구현을 위해 파이썬을 활용하여 프로그래밍을 하였으며 본 논문의 시뮬레이션에서는 3.10.2 버전을 사용하였다. 시뮬레이션 결과를 시각화하기 위한 툴은 matplotlib 라이브러리를 활용하였다. 실험을 위한 격자지도는 두 가지였다. 하나는 그림 5와 같이 Intel Reserach Lab 공용 데이터셋[18]에 의해 획득된 격자 지도였다. 크기는 약 28m×28m였고 격자 지도는 GMapping 알고리즘을 이용하여 획득된 것으로 격자의 크기는 2.5cm×2.5cm였다.

Fig. 5.

Grid map #1 in corridor environments

다른 하나는 그림 6과 같이 실제 실험을 통해 획득된 격자 지도였다. 환경의 크기는 약 76.25m×75m였고 Google Cartographer[19]를 활용하여 획득한 것으로 격자의 크기는 5cm×5cm였다. 격자 지도에서 흰색 부분은 탐색된 영역 중 free space를 뜻하며, 검은색 부분은 탐색된 영역 중 occupied space, 장애물이나 벽을 뜻한다. 회색 부분은 탐색되지 않은 영역으로 free space인지 occupied space인지 알 수 없는 영역이다.

Fig. 6.

Grid map #2 in corridor environments

4.1 복도 환경

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

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

4.2 경로 계획 결과

본 논문에서 제안하는 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

4.3 정량적 비교 결과

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

Comparison of sampling numbers in grid map #1

Comparison of computation times in grid map #1

Comparison of final path lengths in grid map #1

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

Comparison of sampling numbers in grid map #2

Comparison of computation times in grid map #2

Comparison of final path lengths in grid map #2

최종 경로의 효율성을 평가하기 위해, 그림 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


Ⅴ. 결 론

본 논문에서는 복도 환경에서 효율적인 경로 계획을 위한 방향적 탐색 랜덤 트리(DRT) 기법을 제안하였다. 먼저 점진적 지역 목표점 설정을 통해 극좌표계 기반 샘플링을 위한 사전 준비를 한다. 그리고 목표점과 목표점 사이를 지정한 Theta 값으로 좁혀 제한된 영역에서 샘플링을 수행하도록 한다. 이후 비용 함수를 극좌표계 기반 샘플링에 맞도록 재정의한 RRT* 알고리즘을 수행하여 경로 계획을 수행하였다. 제안된 기법은 공용 데이터셋 및 실제 실험을 통해 획득한 격자지도들을 기반으로 수행되었다. 비교 및 분석 결과, 제안된 기법은 기존 기법들에 비해 낮은 샘플링 횟수, 수행시간 및 최종 경로 길이를 나타냄으로써 향상된 효율성이 검증되었다. 향후 연구에서는 제안된 기법을 다중 로봇 시스템으로 확장하는 연구를 수행하고자 한다.

Acknowledgments

본 연구는 금오공과대학교 학술연구비로 지원되었음(202001550001).

References

  • S. M. LaValle and J. J. Kuffner, "Randomized kinodynamic planning", The International Journal of Robotics Research, Vol. 20, No. 5, pp. 378-400, May 2001. [https://doi.org/10.1177/02783640122067453]
  • L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, "Probabilistic roadmaps for path planning in high-dimensional configuration spaces", IEEE Trans. Robotics Autom, Vol. 12 No. 4, pp. 566-580, Aug. 1996. [https://doi.org/10.1109/70.508439]
  • S. Karaman and E. Frazzoli, "Sampling-based algorithms for optimal motion planning", The International Journal of Robotics Research, Vol. 30, No. 7, pp. 846–894, Jun. 2011. [https://doi.org/10.1177/0278364911406761]
  • S. Karaman and E. Frazzoli, "Incremental sampling-based algorithms for optimal motion planning", ArXiv abs/1005.0416, , May 2010. [https://doi.org/10.15607/RSS.2010.VI.034]
  • I. Noreen, A. Khan, and Z. Habib. "Optimal path planning using RRT* based approaches: a survey and future directions", International Journal of Advanced Computer Science and Applications, Vol. 7, No. 11, pp. 97-107, 2016. [https://doi.org/10.14569/IJACSA.2016.071114]
  • Z. Wu, Z. Meng, W. Zhao, and Z. Wu, "Fast-RRT: A RRT-based optimal path finding method", Applied Sciences, Vol. 11, No. 24, pp. 11777(1-18), Dec. 2021. [https://doi.org/10.3390/app112411777]
  • F. Islam, J. Nasir, U. Malik, Y. Ayaz, and O. Hasan, "RRT*-Smart: rapid convergence implementation of RRT* towards optimal solution", Proc. IEEE International Conference on Mechatronics and Automation, Chengdu, China, pp. 1651-1656, Aug. 2012. [https://doi.org/10.1109/ICMA.2012.6284384]
  • J. Nasir et al., "RRT*-SMART: A rapid convergence implementation of RRT*", International Journal of Advanced Robotic Systems, Vol. 10, No. 7, pp. 299(1-12), Jan. 2013. [https://doi.org/10.5772/56718]
  • H. T. Tak, C. G. Park, and S. C. Lee, "Improvement of RRT*-Smart algorithm for optimal path planning and application of the algorithm in 2 & 3-dimension environment", Journal of the Korean Society for Aviation and Aeronautics Vol. 27 No. 2, pp. 1–8, Jun. 2019. [https://doi.org/10.12985/ksaa.2019.27.2.001]
  • H. B. Lee, H. Kwak, J. Kim, C. Lee, and H. J. Kim, "Improvement of online motion planning based on RRT* by modification of the sampling method", Journal of Institute of Control, Robotics and Systems, Vol. 22, No. 3, pp. 192–198, Mar. 2016. [https://doi.org/10.5302/J.ICROS.2016.15.0135]
  • R. Mashayekhi et al., "Informed RRT*-Connect: an asymptotically optimal single-query path planning method", IEEE Access, Vol. 8, pp. 19842-19852, Jan. 2020. [https://doi.org/10.1109/ACCESS.2020.2969316]
  • Y. Park and H. Ryu, "Improved path planning algorithm based on Informed RRT* using gridmap skeletonization", Journal of Korea Robotics Society, Vol. 13, No. 2. pp. 142–149, Jun. 2018. [https://doi.org/10.7746/jkros.2018.13.2.142]
  • O. Adiyatov and H. A. Varol, "Rapidly-exploring random tree based memory efficient motion planning", Proc. IEEE International Conference on Mechatronics and Automation, Takamatsu, Japan, pp. 354-359, Aug. 2013. [https://doi.org/10.1109/ICMA.2013.6617944]
  • B. Tong, Q. Liu, and C. Dai, "A RRT*FN based path replanning algorithm", Proc. IEEE Advanced Information Technology, Electronic and Automation Control Conference, Chengdu, China, pp. 1435-1445, Dec. 2019. [https://doi.org/10.1109/IAEAC47372.2019.8997746]
  • S. Karaman et al., "Anytime motion planning using the RRT*", Proc. IEEE International Conference on Robotics and Automation, Shanghai, China, pp. 1478-1483, May 2011. [https://doi.org/10.1109/ICRA.2011.5980479]
  • B. Akgün and M. Stilman, "Sampling heuristics for optimal motion planning in high dimensions", Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, USA, pp. 2640-2645, Sep. 2011. [https://doi.org/10.1109/IROS.2011.6095077]
  • Ji-Gwan Park and Jin-Ho Shin, "Local path planning using a potential field method and temporary guidance points for autonomous navigation of a mobile robot," Journal of Korean Institute of Information Technology, Vol. 10, No. 8, Aug. 2012.
  • C. Stachniss, Robotics datasets, Intel reserach lab, http://www2.informatik.uni-freiburg.de/~stachnis/datasets.html, [accessed: Jan. 05, 2016]
  • W. Hess, D. Kohler, H. Rapp, and D. Andor, "Real-time loop closure in 2D LIDAR SLAM", Proc. IEEE International Conference Robotics and Automation, Stockholm, Sweden, pp. 1271–1278, May 2016. [https://doi.org/10.1109/ICRA.2016.7487258]
저자소개
김 석 영 (Seokyoung Kim)

2022년 2월 : 금오공과대학교 전자공학부 전자IT융합전공(학사)

2022년 2월 ~ 현재 : 금오공과대학교 IT융복합공학과(석사) 재학

관심분야 : path planning, SLAM, scheduling algorithm

남 성 현 (Sunghyun Nam)

2022년 2월 : 금오공과대학교 전자공학부 전자IT융합전공(공학사)

2022년 2월 ~ 현재 : 한국전자기술연구원 지능로보틱스연구센터 연구원

관심분야 : SLAM, 자율주행

이 헌 철 (Heoncheol Lee)

2006년 8월 : 경북대학교 전자전기컴퓨터학부(공학사)

2008년 8월 : 서울대학교 전기컴퓨터공학과(공학석사)

2013년 8월 : 서울대학교 전기컴퓨터공학과(공학박사)

2013년 9월 ~ 2019년 2월 : 국방과학연구소 선임연구원

2019년 3월 ~ 현재 : 금오공과대학교 전자공학부 IT융복합공학과 조교수

관심분야 : SLAM, 자율주행, 인공지능, 알고리즘 가속화

Fig. 1.

Fig. 1.
Example of the conventional RRT* producing a path with a red dotted line from red dot to green dot

Fig. 2.

Fig. 2.
Flowchart of the proposed algorithm

Fig. 3.

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

Fig. 4.

Fig. 4.
Concept of sampling in polar coordinate system

Fig. 5.

Fig. 5.
Grid map #1 in corridor environments

Fig. 6.

Fig. 6.
Grid map #2 in corridor environments

Fig. 7.

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

Fig. 8.

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

Fig. 9.

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

Fig. 10.

Fig. 10.
Final path in grid map #2

Fig. 11.

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

Fig. 12.

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

Table 1.

Related works for performance improvement of the conventional RRT

Approach Reference Research contributions
RRT* [3], [4], [5] Add cost functions and Rewire processes from conventional RRT to improve path planning more efficiently
fast-RRT [6] Improve sampling algorithms to reduce unnecessary sampling and improve path generation problems at narrow streets
RRT*-MART [7], [8],[9] Add a path optimization algorithm using triangular inequality to create a path close to the optimal path and reduce time
Informed RRT* [10], [11], [12] Improve sampling efficiency by limiting sampling area using elliptic properties
RRT*-FN [13], [14] Reduce the number of nodes stored in the tree to limit the resources while maintaining original performance
Anytime RRT* [15] Improves optimality and computational efficiency by eliminating nodes that are considered impossible to improve in the path being resolved
B-RRT* [16] Different node types enable path generation in high-dimensional environments and heuristic methods to improve convergence and path optimization

Table 2.

Pseudo code of the DRT

1 P ← InitialDestinationPoint();
2 T ← InitialTree();
3 T ← InitialNode(∅, xinit, T);
4 for Pj = 1 to j=M do
for i = 1 to i=N do
6  xrand ← PolarCoordinateSample(i);
7  xnearest ← Nearest(T, xrand);
8  xnew ← Steer(xnearest, xrand);
9  if ObstacleFree(xnearest, xnew) then
10    V ← V∪{xnew};
11    Xnear ← Near(T, xnew, r);
12    ChooseParent(Xnear, xnearest, xnew, E);
13    Rewiring(Xnear, xnew, E);
14  end
15  if NearDestination(Pj, xnew) then
16    j++;
17  end
18 end
19 return T, E

Table 3.

Comparison of sampling numbers in grid map #1

Category RRT* RRT*-P DRT
Average 1375 times 1258 times 454 times
Standard deviation 286.4 times 433.9 times 107.2 times

Table 4.

Comparison of computation times in grid map #1

Category RRT* RRT*-P DRT
Average 32.1 s 25.9 s 4.3 s
Standard deviation 11.63 s 20.16 s 1.47 s

Table 5.

Comparison of final path lengths in grid map #1

Category RRT* RRT*-P DRT
Average 52.427m 47.051m 37.819m
Standard deviation 3.099m 1.437m 0.595m

Table 6.

Comparison of sampling numbers in grid map #2

Category RRT* RRT*-P DRT
Average 1382 times 1150 times 1107 times
Standard deviation 227.9 times 110.7 times 98.9 times

Table 7.

Comparison of computation times in grid map #2

Category RRT* RRT*-P DRT
Average 46.1 s 21.9 s 20.0 s
Standard deviation 7.98 s 4.97 s 4.44 s

Table 8.

Comparison of final path lengths in grid map #2

Category RRT* RRT*-P DRT
Average 220.450m 208.350m 175.500m
Standard deviation 5.725m 4.475m 4.945m