[논문]샘플링 기법의 보완을 통한 RRT* 기반 온라인 이동 계획의 성능 개선

이희범; 곽휘권; 김준원; 이춘우; 김현진

doi:10.5302/j.icros.2016.15.0135

문제 정의

지형 I, II 모두 장애물이 많지 않은 비교적 단순한 형태이지만, 지형 II의 경우 최적 경로로 이동하기 위해서는 좁은 통로를 지나도록 장애물이 구성된 것이 특징이다. 개선된 샘플링 기법의 경우 샘플링 영역의 한정을 통해 이러한 좁은 영역에서 경로를 찾을 가능성이 기존 기법에 비해 높으므로, 이러한 지형에서의 성능 개선 여부를 확인하고자 하였다.
현재 경로 길이보다 짧은 경로는 타원 밖 영역에 존재하지 않으므로 타원의 목표점과 시작점을 타원의 초점으로 하고 시작점과 목표점을잇는 경로의 길이를 타원의 장축 길이로 하는 타원으로 샘플링 영역을 한정하여 샘플링의 효율을 높이도록 하였다. 본 논문에서는 기본 R* RT 를 기반으로 이루어진 온라인이동 계획 기법을 샘플링 방식이 개선된 R* RT 기반의 온라인 이동 계획 기법으로 확장하여, 계획된 경로가 좀 더 최적에 가까운 결과를 낼 수 있도록 알고리즘을 개선하였다. 제안하는 R* RT 의 샘플링 방식은 infbmied R* RT 기법의 샘플링 방식에 온라인 이동 계획 상황에 유리하도록 로봇에 의해 수행이 곧 예정되어있는 경로를 우선적으로 개선할 수 있는 샘플링 기법을 추가하여 두 가지 방식의 샘플링기법이 특정 비율로 시행되도록 하는 것이다.

제안 방법

수행하였다. R* RT 알고리즘의 비용은 이동 거리로 설정하였고 두 가지 지형에 대해 시뮬레이션을 수행하였다. 표 1에 각 지형의 크기, 로봇이 경로의 다음 노드로 이동하기 전에 수행하는 경로 탐색 및 개선 시간, 시뮬레이션 수행 횟수가 나타나 있다.
그러나 온라인이동 계획 상황에서는 시작점에서 목표점으로 이동해가는 동안 반복적으로 경로 개선이 이루어지므로 목표점에 가까운 경로는 경로 개선의 시도가 상대적으로 많은 반면, 시작점에 가까운 경로는 상대적으로 그 시도가 적다. 갱신되는 경로의 최적성을 보다 높이기 위해서는 시작점에 가까운 경로에 대해 경로 개선 시도를 높일 필요가 있고 이를 위해, 기존의 infbrmed R* RT 기법에 추가적인 샘플링 기법을 병행하여 사용하는 샘플링 방식을 제안한다.
기본 샘플링, informed R* RT 의 샘플링, 제안하는 샘플링방식을 이용하는 3가지의 R* RT 기반의 온라인 이동 계획 시뮬레이션을 수행하였다. R* RT 알고리즘의 비용은 이동 거리로 설정하였고 두 가지 지형에 대해 시뮬레이션을 수행하였다.
이와 같이 두 가지 샘플링 기법을 활용함으로써 온라인 이동 계획 상황에서 보다 최적의 경로를 얻을 수 있다. 본 논문에서는 infbmied R* RT 의 샘플링 방식과 전방 경로 최적화 샘플링기법의 비율을 8:2로 설정하여 시뮬레이션 하였다. 로봇 전방에 위치한 경로는 전체 경로에 비해 낮은 비율을 차지하고 있고, informed R* RT 의 샘플링과 전방 경로 최적화 샘플링에 의해 이중으로 샘플링 되므로 전방 경로 최적화 샘플링의 비율이 20%라 하더라도 상대적으로 높은 비율로 샘플링이 이루어지기 때문이다.
초기 경로가 생성되면 그림 1과 같이 생성된 경로 초반의 일정 부분은 로봇이 계획된 경로를 수행할 부분으로 할당하고 할당한 부분을 제외한 나머지 경로에 대해서는 R* RT 알고리즘을 반복적으로 수행하여 계획된 경로가 개선되도록 한다. 본 논문에서는 생성된 경로의 초기 두 개의 노드지점까지 로봇이 수행하는 경로로 할당하고 나머지 경로에 대해서는 이 두 번째 노드를 트리구조의 새로운 근원점(root)으로 하여 R* RT 알고리즘 수행을 반복하도록 하였다. 이 때, 기존의 구성된 트리구조에서 새로운 근원점과 연결 가능한 트리구조는 그대로 보존함으로써 처음부터 다시 이동 계획을 수행하는 낭비를 줄였다.
줄 필요가 있다. 이를 위해, 전방 경로 최적화(fix>nt path optimization) 샘플링 기법을 고안하였다. 그림 3(a)에서 보듯이, 삼각형 부등식 조건에 의하여 A에서 C로 이동하는데 A에서 B를 경유하여 C로 이동하는 것보다 A에서 C로 곧장 이동하는 것이 더 짧은 경로가 된다.
제안된 방식에서 설정한 두 샘플링 기법의 비율에 따른 성능 변화를 살펴보기 위해, 앞서의 시뮬레이션과 동일한 조건에서 이 비율만을 변경하여 시뮬레이션을 수행하였다. 시뮬레이션은 지형 II에 대해서만 수행하였고 그 결과가 표 4와 그림 6에 나타나있다.
본 논문에서는 기본 R* RT 를 기반으로 이루어진 온라인이동 계획 기법을 샘플링 방식이 개선된 R* RT 기반의 온라인 이동 계획 기법으로 확장하여, 계획된 경로가 좀 더 최적에 가까운 결과를 낼 수 있도록 알고리즘을 개선하였다. 제안하는 R* RT 의 샘플링 방식은 infbmied R* RT 기법의 샘플링 방식에 온라인 이동 계획 상황에 유리하도록 로봇에 의해 수행이 곧 예정되어있는 경로를 우선적으로 개선할 수 있는 샘플링 기법을 추가하여 두 가지 방식의 샘플링기법이 특정 비율로 시행되도록 하는 것이다. 기본 R* RT 와 informed R* RT 를 기반으로 구성한 온라인 이동 계획 기법들과의 시뮬레이션 결과 비교를 통해 제안 하는 기법이 가장 최적 경로에 근접한 결과를 나타내고 효율적인 샘플링 방법이 됨을 확인하였다.
informed R* RT 기법[9]은 타원 위의 한 점에서 두 초점을 잇는 직선 길이의 합은 장축의 길이와 동일하다는 타원의 성질을 이용하여 샘플링 영역을 한정한다. 현재 경로 길이보다 짧은 경로는 타원 밖 영역에 존재하지 않으므로 타원의 목표점과 시작점을 타원의 초점으로 하고 시작점과 목표점을잇는 경로의 길이를 타원의 장축 길이로 하는 타원으로 샘플링 영역을 한정하여 샘플링의 효율을 높이도록 하였다. 본 논문에서는 기본 R* RT 를 기반으로 이루어진 온라인이동 계획 기법을 샘플링 방식이 개선된 R* RT 기반의 온라인 이동 계획 기법으로 확장하여, 계획된 경로가 좀 더 최적에 가까운 결과를 낼 수 있도록 알고리즘을 개선하였다.

성능/효과

5%만큼의 차이를 보이며 최적 경로에 근접한 결과를 나타내었다. 또 경로 간의 편차 역시 (c) , (b), (a) 순으로 작은 값을 나타내어 제안한 샘플링 기법이 가장 안정적으로 경로계획 결과를 나타내는 것을 확인하였다.
(a)에 비해 대략 약 13%의 비용감소를 보이며 샘플링 방식 개선에 따른 효과를 수치적으로 확인할 수 있었다. (c)의 경우 (b)보다 약 0.
(c)의 경우 (b)보다 약 0.8정도 작은 비용으로 최적 경로의 비용에 비해 약 6.5%만큼의 차이를 보이며 최적 경로에 근접한 결과를 나타내었다. 또 경로 간의 편차 역시 (c) , (b), (a) 순으로 작은 값을 나타내어 제안한 샘플링 기법이 가장 안정적으로 경로계획 결과를 나타내는 것을 확인하였다.
3. 경로 개선 효율 증가를 위한 R* RT의 샘플링 기법 개선 * RRT 의 샘플링 방식을 개선하여 기존의 광범위한 영역에서 무작위로 이루어지던 샘플링을 보다 효율적으로 만들면 반복횟수 대비 경로 개선 효과를 증대시킬 수 있다. 개선된 샘플링 방식들은 샘플링 영역을 한정하거나, 특정 영역에서 샘플링이 일어나도록 샘플링을 유도하여 샘플링의 효율을 높인다.
7:3의 비율을 사용한 경우, 로봇 전방의 위치한 경로는 개선이 잘 이루어졌으나, 전방 경로에 샘플링이 과도하게 집중되어 전체적인 경로는 좋지 않은 결과를 나타내었다. 9:1의 비율을 사용한 경우, infbmied R* RT 의 샘플링만을 이용한 경우보다는 약간의 성능 개선이 있었으나, 앞서의 본 시뮬레이션에서 사용한 결과보다는 좋지 않은 결과를 얻었다. 이로서 현 시뮬레이션 조건에서는 앞서 사용한 8:2의 비율이 적당한 비율이 됨을 확인하였다.
제안하는 R* RT 의 샘플링 방식은 infbmied R* RT 기법의 샘플링 방식에 온라인 이동 계획 상황에 유리하도록 로봇에 의해 수행이 곧 예정되어있는 경로를 우선적으로 개선할 수 있는 샘플링 기법을 추가하여 두 가지 방식의 샘플링기법이 특정 비율로 시행되도록 하는 것이다. 기본 R* RT 와 informed R* RT 를 기반으로 구성한 온라인 이동 계획 기법들과의 시뮬레이션 결과 비교를 통해 제안 하는 기법이 가장 최적 경로에 근접한 결과를 나타내고 효율적인 샘플링 방법이 됨을 확인하였다.
보인다. 또 시뮬레이션 설정에서 의도한 바와 같이 한정된 영역에서 집중적인 샘플링을 할 때 경로를 찾기 유리한 좁은 통로 지형을 포함하고 있어 개선된 샘플링의 효과가 보다 극명하게 나타났다.
샘플링 기법이 개선된 R* RT 를 이용한 온라인 이동 계획을 구성하여, 기본 R* RT 를 이용하는 경우에 비해 경로의 비용이 감소하는 더 나은 이동 계획 결과를 얻을 수 있었다. 별도의 개선된 샘플링 기법을 이용하는 것은 기존의 R* RT 를 작동하는 것에 비해 약간의 추가 계산을 필요로 하나, 샘플링의 효율을 높임으로써 R* RT 를 보다 효율적으로 이용할 수 있는 좋은 방법이 된다.
시뮬레이션 2가 시뮬레이션 1에 비해 개선된 샘플링 기법의 의한 경로 개선 효과가 좀 더 가시적으로 보이는 결과를 얻었는데, 이는 지형 II의 경우가 지형 I의 경우에 비해 샘플링 영역을 한정할 시, 전체 영역에서 보다 많은 영역의 축소가 가능하여 샘플링의 효율이 크게 증가한 것으로 보인다. 또 시뮬레이션 설정에서 의도한 바와 같이 한정된 영역에서 집중적인 샘플링을 할 때 경로를 찾기 유리한 좁은 통로 지형을 포함하고 있어 개선된 샘플링의 효과가 보다 극명하게 나타났다.
9:1의 비율을 사용한 경우, infbmied R* RT 의 샘플링만을 이용한 경우보다는 약간의 성능 개선이 있었으나, 앞서의 본 시뮬레이션에서 사용한 결과보다는 좋지 않은 결과를 얻었다. 이로서 현 시뮬레이션 조건에서는 앞서 사용한 8:2의 비율이 적당한 비율이 됨을 확인하였다.
그렇지만 온라인으로 이루어지는 이동 계획 상황에서는 경로 수행이 예정되어 있는 로봇 전방에 위치한 경로에 대해 보다 가중치를 높여 경로의 개선이 이루어지도록 할 필요가 있다. 이에 전방 경로 최적화 샘플링 기법을 고안하여 informed R* RT 의 샘플링과 함께 병행하여 사용하는 샘플링 방식을 제안하였고, 이를 이용하여 기존의 informed R* RT 의 샘플링 기법만을 이용하는 경우보다 최적 경로에 근접한 이동 계획 결과를 얻었다.

후속연구

그림 3(b)에 본래의 경로를 단축시킨 경로(shorten path)가 점선으로 나타나 있다. 점선 경로는 이전의 경로에 비해 최적 경로에 가까운 경로가 되었으나, 보다 최적의 경로가 되기 위해서는 장애물에 좀 더 근접하여 이동하는 경로가 되어야 할 것이다. 따라서 점선 경로를 따라 점선 주위 영역에 대해 샘플링을 시도하면 불필요한 경유 지점들을 정리하면서 최적 경로로의 유도가 가능하다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

**샘플링 기법의 보완을 통한 RRT* 기반 온라인 이동 계획의 성능 개선
Improvement of Online Motion Planning based on RRT* by Modification of the Sampling Method** 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

연구과제 타임라인

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

샘플링 기법의 보완을 통한 RRT* 기반 온라인 이동 계획의 성능 개선 Improvement of Online Motion Planning based on RRT* by Modification of the Sampling Method 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

김현진 (17)

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

**샘플링 기법의 보완을 통한 RRT* 기반 온라인 이동 계획의 성능 개선
Improvement of Online Motion Planning based on RRT* by Modification of the Sampling Method** 원문보기

AI 본문요약
AI-Helper