[논문]최적 경로 계획을 위한 RRT*-Smart 알고리즘의 개선과 2, 3차원 환경에서의 적용

탁형태; 박천건; 이상철

doi:10.12985/ksaa.2019.27.2.001

**최적 경로 계획을 위한 RRT-Smart 알고리즘의 개선과 2, 3차원 환경에서의 적용
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, v.27 no.2, 2019년, pp.1 - 8

탁형태 (한국항공대학교 학부 항공우주 및 기계공학과) , 박천건 (한국항공대학교 대학원 항공우주 및 기계공학과) , 이상철 (한국항공대학교 항공우주 및 기계공학부)

Abstract ▼ AI-Helper

Optimal path planning refers to find the safe route to the destination at a low cost, is a major problem with regard to autonomous navigation. Sampling Based Planning(SBP) approaches, such as Rapidly-exploring Random Tree Star($RRT^*$), are the most influential algorithm in path planning due to their relatively small calculations and scalability to high-dimensional problems. $RRT^*$-Smart introduced path optimization and biased sampling techniques into $RRT^*$ to increase convergent rate. This paper presents an improvement plan that has changed the biased sampling method to increase the initial convergent rate of the $RRT^*$-Smart, which is specified as m$RRT^*$-Smart. With comparison among $RRT^*$, $RRT^*$-Smart and m$RRT^*$-Smart in 2 & 3-D environments, m$RRT^*$-Smart showed similar or increased initial convergent rate than $RRT^*$ and $RRT^*$-Smart.

주제어

표/그림 (14)

그림 Fig 1. RRT, RRT* Algorithm
그림 Fig 2. RRT* pseudo code
그림 Fig 3. Path Optimization
그림 Fig 4. mRRT*-Smart pseudo code
그림 Fig 5. Modified beacon node
표 Table 1. Simulation setting
표 Table 2. Bias sampling setting
그림 Fig 6. A comparison of 2-D simulation results. RRT* is shown in (a)-(d), RRT*-Smart is shown in (e)-(f) and mRRT*-Smart is shown in (i)-(l)
그림 Fig 7. Costs against iterations(S=RRT*-Smart, M=mRRT*-Smart)
그림 Fig 8. A comparison of 3-D simulation results at n=2000
표 Table 3. Path planning results at 1000, 1500, 2000 and 2500 iterations for 2-D case 1, 2, 3 & 3000, 3500, 4000, and 4500 iterations for 2-D case 4
그림 Fig 9. Costs against iterations(S=RRT*-Smart, M=mRRT*-Smart)
그림 Fig 10. Nodes at 2000 iterations
표 Table 4. Path planning results at 1000, 1500, 2000 and 2500 iterations for 3-D Case

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 RRT*-Smart의 초기 수렴 속도 증가를 위해 편향 샘플링 방식을 개선한 mRRT*-Smart를 제안하고 2, 3차원에서의 적용에 대한 연구를 수행하였다. 또한 임의로 설정된 2-D, 3-D 환경에서 시뮬레이션을 진행하여 얻은 경로의 평균 비용을 기준으로 개선안과 RRT*, RRT*-Smart의 성능을 비교하였다.
본 논문에서는 장애물 정보를 활용하여 RRT*-Smart의 편향 샘플링 단계에서 샘플링 영역을 변경한 개선안인 mRRT*-Smart를 제안하였다. 2, 3차원의 환경에서 기존 알고리즘인 RRT*, RRT*-Smart와 개선안인 mRRT*-Smart를 이용하여 시뮬레이션을 수행하였다.
따라서 경로 최적화가 완료되면 연속된 세 비콘 노드 (x₁, x₂, x₃)로 만들어지는 삼각형 내부에 최종적으로 수렴해야 할 지점이 존재하게 된다. 이에 착안하여 본 논문은 해당 지점으로 빠르게 수렴하도록 편향 샘플링 영역을 변경하였다.

제안 방법

본 논문에서는 장애물 정보를 활용하여 RRT*-Smart의 편향 샘플링 단계에서 샘플링 영역을 변경한 개선안인 mRRT*-Smart를 제안하였다. 2, 3차원의 환경에서 기존 알고리즘인 RRT*, RRT*-Smart와 개선안인 mRRT*-Smart를 이용하여 시뮬레이션을 수행하였다. 시뮬레이션 결과, 2차원 환경에서 기존 알고리즘인 RRT*, RRT*-Smart보다 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다.
Table 3은 임의로 설정한 초기 반복 수에서의 알고리즘별 평균 비용을 나타낸다. 2-D Case 4의 경우 좁은 길을 통과해야 하는 문제점으로 인해 2916번째의 반복 수에서 최초 경로가 찾아지므로 다른 환경보다 높은 반복 수를 기준으로 비교하였다.
RRT*, RRT*-Smart, mRRT*-Smart을 비교하였다. 2-D 환경은 하나의 사각형 장애물이 존재하는 단순한 환경과 Nasir(2013)가 사용하였던 환경[4] 중 임의로 세 가지 환경을 선택하여 총 4가지의 환경을 설정하였다. 3-D 환경은 일반적으로 접할 수 있는 계단 환경으로, 3-D 환경에서 편향 샘플링 영역은 구형으로 설정하였다.
RRT*, RRT*-Smart, mRRT*-Smart을 비교하였다. 2-D 환경은 하나의 사각형 장애물이 존재하는 단순한 환경과 Nasir(2013)가 사용하였던 환경[4] 중 임의로 세 가지 환경을 선택하여 총 4가지의 환경을 설정하였다.
개선안은 경로 최적화를 동일하게 실시한 뒤, 편향 샘플링이 이루어지는 반복 수마다 임의의 연속된 세 비콘 노드(x₁, x₂, x₃)를 선택한다. 그 후 Figure 3과 비콘 노드 간의 모서리 e(x₁,x₂),e(x₂,x₃)을 포함하는 두 직선을 각각 x₁과 x₃을 기준으로 일정 각도씩 회전 시키며 맞은 편 모서리로의 교선을 생성한다.
여기서 biasing radius 값의 경우 RRT*-Smart가 가장 좋은 결과를 나타내는 값인 3을 선택하여 mRRT*-Smart와 비교하였다. 또한 biasing ratio 값의 경우 RRT*-Smart와 mRRT*-Smart의 특성이 가장 잘 나타나는 값인 2를 선택하여 비교하였다. Figure 7은 각 2-D 환경별로 20,000번의 반복 수(i)에 대한 비용의 그래프를 나타낸다.
그 후 Figure 3과 비콘 노드 간의 모서리 e(x₁,x₂),e(x₂,x₃)을 포함하는 두 직선을 각각 x₁과 x₃을 기준으로 일정 각도씩 회전 시키며 맞은 편 모서리로의 교선을 생성한다. 생성된 교선이 장애물과의 충돌이 발생할 때까지 위 과정을 반복하고 충돌이 발생하면 충돌 직전의 마지막 교선들의 교점을 샘플링이 이루어지는 비콘 노드(x_beabon)로 설정하고 특정 반경 이내의 영역에서 샘플링을 실시한다.
알고리즘 구현은 C++를 이용하였고 AMD Ryzen 5 2600 3.4GHz, 16.00GB ram, VGA Radeon RX 580의 사양에서 시뮬레이션을 수행하였다.

데이터처리

본 논문에서는 RRT*-Smart의 초기 수렴 속도 증가를 위해 편향 샘플링 방식을 개선한 mRRT*-Smart를 제안하고 2, 3차원에서의 적용에 대한 연구를 수행하였다. 또한 임의로 설정된 2-D, 3-D 환경에서 시뮬레이션을 진행하여 얻은 경로의 평균 비용을 기준으로 개선안과 RRT*, RRT*-Smart의 성능을 비교하였다.
Figure 6는 Case 1, 2, 3에 대하여 반복 수 2,000일 때, Case 4에 대하여 반복 수가 3,500일 때 시뮬레이션 결과이다. 여기서 biasing radius 값의 경우 RRT*-Smart가 가장 좋은 결과를 나타내는 값인 3을 선택하여 mRRT*-Smart와 비교하였다. 또한 biasing ratio 값의 경우 RRT*-Smart와 mRRT*-Smart의 특성이 가장 잘 나타나는 값인 2를 선택하여 비교하였다.

성능/효과

시뮬레이션 결과, 2차원 환경에서 기존 알고리즘인 RRT*, RRT*-Smart보다 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다. 3차원의 환경은 Biasing radius가 충분히 큰 경우에 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다. 높은 biasing ratio, 낮은 biasing radius를 사용 할 경우에는 적은 반복 수에서도 RRT*-Smart의 성능이 더 좋아지는 경향을 보였다.
83)으로 수렴이 이루어졌다. 그 결과 13811회의 반복 수 이후부터 RRT*-Smart이 더 빠르게 수렴하는 것으로 나타났다. Figure 9.
00)은 최적 경로에 더 근접하였다. 그러나 초기 수렴 속도가 느려져 2356회 이후로 RRT*-Smart의 성능이 더 좋게 나타나는 것을 확인 할 수 있었다.
3차원의 환경은 Biasing radius가 충분히 큰 경우에 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다. 높은 biasing ratio, 낮은 biasing radius를 사용 할 경우에는 적은 반복 수에서도 RRT*-Smart의 성능이 더 좋아지는 경향을 보였다. 제시된 알고리즘을 통해 생성된 경로는 I.
2, 3차원의 환경에서 기존 알고리즘인 RRT*, RRT*-Smart와 개선안인 mRRT*-Smart를 이용하여 시뮬레이션을 수행하였다. 시뮬레이션 결과, 2차원 환경에서 기존 알고리즘인 RRT*, RRT*-Smart보다 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다. 3차원의 환경은 Biasing radius가 충분히 큰 경우에 mRRT*-Smart의 초기 수렴 속도가 빠른 것을 확인하였다.

후속연구

높은 biasing ratio, 낮은 biasing radius를 사용 할 경우에는 적은 반복 수에서도 RRT*-Smart의 성능이 더 좋아지는 경향을 보였다. 제시된 알고리즘을 통해 생성된 경로는 I. Skrjanc(2010)가 사용한 Bezier curves[6]나 B. Lau가 사용한 spline[7] 등을 이용하여 실제 각종 이동 로봇(Mobile robot)에 적용 할 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	최적 경로 계획 알고리즘의 대표적인 방법은 무엇이 있는가?	특히 각종 군사목적과 상업목적으로 각광받고 있는 무인 멀티콥터의 자율주행에 있어 경로 계획 문제의 해결은 필수적인 요소이다. Noreen(2016)에 따르면 대표적인 최적 경로 계획 알고리즘으로 Probability Roadmaps(PRM), Rapidly-exploring Random Tree(RRT)[1]와 같은 샘플링 기반의 알고리즘을 들 수 있다[2].
	RRT*-Smart의 알고리즘은 어떤 과정은 거치는가?	RRT-Smart의 알고리즘을 Figure 4에 나타내었다. RRT-Smart는 처음 경로가 찾아지기 전까지 RRT*와 동일한 과정을 거쳐 노드들을 추가한다. 처음으로 경로가 찾아지면 전체 알고리즘이 실행된 횟수인 반복 수(i)를 n으로 저장한다. 경로가 찾아진 이후부터 Figure 3과 같이 삼각부등식 조건을 사용하여 경로 최적화(PathOptimization)를 실시한다. 최적화된 경로가 기존 최적화 경로보다 낮은 비용을 가질 경우 해당 경로상의 노드들(x1, x2,x3)을 비콘 노드로 설정한다. n이후의 반복 수부터 특정 반복 수(Biasing ratio; b)마다 편향 샘플링(Randomsample(i,xbeabons))이 진행된다. 편향 샘플링은 저장 된 비콘 노드들 중 임의로 선택된 하나의 비콘 노드로부터 특정 반경(Biasing Radius)이내의 원형 영역에서 랜덤으로 노드를 생성하여 수렴 속도를 증가시킨다.
	최적 경로 계획의 목적은 무엇인가?	최적 경로 계획(Optimal path planning) 의 목적은 시작 지점과 목표 지점 사이에서 장애물과의 충돌이 없는 가장 짧은 경로를 찾는 것이다. 이는 운송, 탐색 및 구조 등의 분야에서 효율적인 유무인기의 운용을 위해 중요하다.

참고문헌 (7)

S. M. Lavalle, “Rapidly-exploring random trees: A new tool for path planning”, 1998.
10.14569/IJACSA.2016.071114 Noreen, I., Khan, A., and Habib, Z. , “Optimal path planning using RRT* based approaches: a survey and future directions”, Int. J. Adv. Comput. Sci. Appl, 7(11), The Science and Information (SAI) Organization , 2016, pp. 97~107 10.14569/IJACSA.2016.071114

상세보기
10.1177/0278364911406761 Karaman, S., and Frazzoli, E,. “ Sampling-based algorithms for optimal motion planning”, The international journal of robotics research, 30(7), Sage Publications, 2011, pp. 846~894. 10.1177/0278364911406761

상세보기
10.5772/56718 Nasir, J., Islam, F., Malik, U., Ayaz, Y., Hasan, O., Khan, M., and Muhammad, M. S,. “RRT*-SMART: A rapid convergence implementation of RRT”, International Journal of Advanced Robotic Systems, 10(7), Sage Publications, 2013, pp. 299. 10.5772/56718

상세보기
H, Lee, H, Kim, “2D Optimal Path Plannin using RRT*smart algorithm”, KSAS 2014 Fall Conference, The Korean Society for Aeronautical and Space Sciences, Jeju, 2014, pp. 1,237-1,240.
10.1016/j.robot.2009.09.003 I. Skrjanc, G. Klancar, “Optimal cooperative collision avoidance between multiple robots based on Bernstein-Bezier curves”, Robot. Auton. syst. Elsevier, 58(1), 2010, pp. 1-9. 10.1016/j.robot.2009.09.003

상세보기
10.1109/IROS.2009.5354805 B. Lau, C. Sprunk, W. Burgard, “Kinodynamic Motion Planning for Mobile Robots Using Splines”, Proceedings of the EEE/RSJ International Conference on Intelligent Robots and Systems, St Louis, MO, USA, 2009, pp. 2427-2433. 10.1109/IROS.2009.5354805 19641951

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증