[논문]uDEAS를 이용한 이동 로봇의 최적 전역 경로 계획

김조환; 김만석; 최민구; 김종욱

doi:10.5391/jkiis.2011.21.2.268

uDEAS를 이용한 이동 로봇의 최적 전역 경로 계획
Optimized Global Path Planning of a Mobile Robot Using uDEAS 원문보기

한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.21 no.2, 2011년, pp.268 - 275

김조환 (동아대학교 전자공학과) , 김만석 (동아대학교 전자공학과) , 최민구 (동아대학교 전자공학과) , 김종욱 (동아대학교 전자공학과)

초록
AI-Helper

본 논문에서는 uDEAS(Univariate Dynamic Encoding Algorithm for Searches)를 이용하여 두 가지의 이동 로봇 최적 전역 경로 계획을 제안한다. 이동 로봇의 자율 주행을 위해서는 빠른 시간 내에 작업 공간에서의 최적 경로를 생성해야 한다. 따라서 본 논문에서는 이동 로봇의 실시간 최적 경로 계획을 위해 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인하고, 지도상의 노드점과 노트점을 이용하여 출발 지점과 도착 지점 사이의 기본 경로를 생성한다. 그리고 기본 경로를 사용하여 두 가지의 방법으로 경로를 생성하게 된다. 첫 번째 방법은 기본 경로에서 세 개의 노드점을 이용하여 대각선 경로를 생성하는 방법이다. 두 번째는 혼합 다항식의 파라미터를 uDEAS를 이용하여 탐색하고, 곡선 궤적을 생성하는 방법이다. 시뮬레이션을 통해 두개의 방법에 대해 비교 분석하였다.

Abstract ▼ AI-Helper

This paper proposes two optimal path planning methods of a mobile robot using uDEAS (univariate Dynamic Encoding Algorithm for Searches). Before start of autonomous traveling, a self-controlled mobile robot must generate an optimal global path as soon as possible. To this end, numerical optimization method is applied to real time path generation of a mobile robot with an obstacle avoidance scheme and the basic path generation method based on the concept of knot and node points between start and goal points. The first improvement in the present work is to generate diagonal paths using three node points in the basic path. The second innovation is to make a smooth path plotted with the blending polynomial using uDEAS. Effectiveness of the proposed schemes are validated for several environments through simulation.

주제어

AI 본문요약
AI-Helper

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

문제 정의

따라서 본 논문에서는 실시간 최적화를 위해 탐색 속도가 가장 빠른 uDEAS를 이용하여 혼합 다항식의 파라미터를 검색한다. 그리고 이를 이용하여 기본 경로 과정을 통해 생성된 직선 경로를 곡선 경로로 새롭게 생성한다.
따라서 본 논문에서는 이러한 단점을 해결하기 위해 두가지 방법의 전역 경로 계획을 제안한다. 이동 로봇의 절대 좌표와 장애물의 정보를 이용하는 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인한다.
본 논문에서는 이동 로봇의 실시간 최적 경로 계획을 위해 이동 로봇의 절대 좌표와 장애물의 정보를 이용하는 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인하고 지도상에 노트점과 노드점을 이용하여 출발 지점과 도착 지점 사이의 기본 경로를 생성한다. 그리고 두 가지의 방법을 이용하여 개선된 경로를 생성한다.

가설 설정

2) 각도가 급격하게 변하는 지점을 기준으로 다음 노트점까지 한 변이 된다.
본 논문에서는 이동 로봇이 주행하기에 앞서 다음과 같은 조건이라고 가정하였다.

제안 방법

본 논문에서는 이동 로봇의 실시간 최적 경로 계획을 위해 이동 로봇의 절대 좌표와 장애물의 정보를 이용하는 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인하고 지도상에 노트점과 노드점을 이용하여 출발 지점과 도착 지점 사이의 기본 경로를 생성한다. 그리고 두 가지의 방법을 이용하여 개선된 경로를 생성한다. 첫 번째 방법은 세 개의 노트점을 이용하여 대각선 경로를 생성하여 최단 경로를 생성하는 방법이고, 두 번째 방법은 연산최적화 알고리듬인 uDEAS를 이용하여 혼합 다항식의 파라미터를 검색하여 곡선 경로를 생성하는 방법이다.
이동 로봇의 절대 좌표와 장애물의 정보를 이용하는 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인한다. 그리고 지도상에 이동 로봇이 이동할 수 있는 경로의 탐색점인 노트점과 노드점을 이용하여 출발 지점과 도착 지점 사이의 기본 경로를 생성한다. 생성된 기본 경로를 이용하여 본 논문에서는 두 가지 방법의 경로를 생성한다.
이를 위해서 고속의 연산 최적화 알고리듬인 uDEAS (Univariate Dynamic Encoding Algorithm for Searches)를 이용하여 혼합 다항식의 파라미터를 탐색하였다. 두 가지 방법을 시뮬레이션을 통해 검증하고 최적화된 경로 계획을 제안한다.
고정 장애물은 3m×3m와 2m×2m로 설정하였다. 두 개의 고정 장애물을 지나서 한개의 경유점을 지나는 경우와 세 개의 고정 장애물을 지나서 두 개의 경유점을 지나는 경우로 시뮬레이션을 수행했다.
따라서 본 논문에서 이러한 단점을 해결하기 위해서 혼합 다항식을 이용하여 부드러운 곡선을 생성하게 된다. 이러한 곡선 경로를 이용하여 이동 로봇이 속도를 줄이지 않고 계속 해서 경로를 따라 이동할 수 있으므로 에너지 소모 및 시간을 줄일 수 있다.
1의 시뮬레이션을 통해 곡선 경로의 경우가 가장 효율적임을 알 수 있었다. 또한 최단 경로 또한 기본 경로와 마찬가지로 각도가 급격하게 변하는 지점이 있는 단점이 있기 때문에 두 가지 방법 중 더 효율적인 곡선 경로에 대해 집중적으로 비교 분석하였다. 따라서 지금부터의 시뮬레이션의 경우 기본 경로와 곡선 경로만을 비교한다.
본 논문에서는 기본 경로에서 시간 t의 1/2지점을 경유점으로 하여 2개의 단위 궤적을 가지는 궤적을 설정하였고, 1/3, 2/3지점을 경유점으로 하여 3개의 부분 궤적을 가지는 궤적을 설정하였다.
본 논문에서는 기존에 사용되고 있는 경로 생성 방법을 기본 경로 계획 알고리듬으로 활용하여 기본 경로를 생성한다[7]. 그리고 생성된 기본 경로를 바탕으로 두 가지의 개선된 경로를 생성한다.
본 논문에서의 각 노드점 사이의 간격은 이동 로봇의 최소 회전 반경을 기준으로 고정값으로 설정하였고, 각 노드점마다의 노트점의 범위는 일정하게 하였다.
앞에서와 마찬가지로 각각의 경유점에서의 x좌표와 y좌표인 xm1, ym1, xm2, ym2와 그 속도인 vm1x, vm2x, vm1y, vm2y의 최적값 Θ3를 uDEAS를 이용하여 탐색하였다.
그림 6의 x좌표와 y좌표를 혼합다항식에 적용하여 새롭게 x좌표와 y좌표를 생성하고 이를 이용하여 곡선 경로를 만든다. 이 때 혼합다항식의 각 파라미터들을 uDEAS를 이용하여 탐색했다. 그림 6과 그림 7에 비해 부드러운 곡선을 생성하였고, 각도가 급격하게 변하는 지점이 없어진 것을 확인할 수 있다.
따라서 본 논문에서는 이러한 단점을 해결하기 위해 두가지 방법의 전역 경로 계획을 제안한다. 이동 로봇의 절대 좌표와 장애물의 정보를 이용하는 전역 경로 계획을 도입하여 장애물 지역과 비장애물 지역을 확인한다. 그리고 지도상에 이동 로봇이 이동할 수 있는 경로의 탐색점인 노트점과 노드점을 이용하여 출발 지점과 도착 지점 사이의 기본 경로를 생성한다.
그리고 두 가지의 방법을 이용하여 개선된 경로를 생성한다. 첫 번째 방법은 세 개의 노트점을 이용하여 대각선 경로를 생성하여 최단 경로를 생성하는 방법이고, 두 번째 방법은 연산최적화 알고리듬인 uDEAS를 이용하여 혼합 다항식의 파라미터를 검색하여 곡선 경로를 생성하는 방법이다. 이 두 가지 방법을 시뮬레이션을 통해 비교 분석하였으며, 시뮬레이션 결과 최단 경로와 곡선 경로 두 가지 모두 기본 경로보다 총 거리 및 총 각도변화에서 개선되었음을 확인할 수 있었다.

이론/모형

일반적으로 DEAS는 크게 지역최적화(local search)와 전역최적화(global search) 과정으로 나눌 수 있으며, 지역최적화는 탐색점 주변을 면밀히 탐색하는 bisectional search(BSS, 양분탐색)와 BSS에서 얻은 정보를 기반으로 이웃 영역을 확장 탐색하는 unidirectional search(UDS, 단향 탐색)로 나눌 수 있다. 그리고 전역최적화를 위해서는 가장 용이하면서도 간단하게 구현할 수 있는 multistart 기법을 채용했다[8].
본 논문에서 사용된 최적 경로 시뮬레이터는 Visual Studio를 사용하여 제작하였다. 고정 장애물은 3m×3m와 2m×2m로 설정하였다.
혼합 다항식의 경우 복잡한 수식으로 이루어져 있기 때문에 고속의 연산을 통하여 빠르게 파라미터를 탐색해야 한다. 이를 위해서 고속의 연산 최적화 알고리듬인 uDEAS (Univariate Dynamic Encoding Algorithm for Searches)를 이용하여 혼합 다항식의 파라미터를 탐색하였다. 두 가지 방법을 시뮬레이션을 통해 검증하고 최적화된 경로 계획을 제안한다.
그림 10은 두 개의 경유점을 지나는 곡선 경로를 생성한 예를 나타낸 것이다. 총 세 개의 장애물 사이를 통과하여 곡선을 생성하여야 하므로 두 개의 경유점을 가지는 혼합다항식을 이용하여 곡선을 생성하였다.

성능/효과

eDEAS는 가장 초기 알고리듬으로 개발되었고, 그 다음으로 각 변수 별로 BSS와 UDS를 생성하는 알고리즘인 uDEAS가 개발되었다. uDEAS는 모든 변수에게 동시에 변화를 주며 이웃행렬을 생성하는 방법 대신, 그림 4에서와 같이 나머지 변수는 고정한 채 한 변수에 대해서만 BSS와 UDS를 수행한 후 그 다음 변수로 진행시키는 방식으로 개선되었으며, x₁부터 x_n까지 생성된 이웃행렬의 총 수는 파라미터의 약 2배수에 불과하지만, 30차원의 고차 함수는 물론 저차의 테스트 함수에 대해서도 eDEAS와 거의 동등한 탐색 성능을 보였다. 그리고 다차원 문제나 비선형문제에 대해 탁월한 최적화 성능을 보였으며 DEAS series 중 가장 탐색 속도가 빠르다[9].
최단 경로의 경우 불필요한 노드점과 노트점을 통과하지 않으므로 보다 효율적이긴 하지만, 기본 경로의 정보로부터 직선 경로의 꺾임이 발생하는 코너점을 찾는 과정에서 탐색 시간이 소요되는 문제점이 있다. 곡선 경로의 경우 uDEAS를 이용함으로써 최단경로 탐색 시 보다 탐색시간이 짧았으며, 생성된 최적 곡선 경로가 가장 이동 거리가 짧고 각도 변화의 총합도 가장 작아 세 가지의 경로 중 최소 에너지가 소요되는 경로라고 할 수 있다.
첫 번째 방법은 세 개의 노트점을 이용하여 대각선 경로를 생성하여 최단 경로를 생성하는 방법이고, 두 번째 방법은 연산최적화 알고리듬인 uDEAS를 이용하여 혼합 다항식의 파라미터를 검색하여 곡선 경로를 생성하는 방법이다. 이 두 가지 방법을 시뮬레이션을 통해 비교 분석하였으며, 시뮬레이션 결과 최단 경로와 곡선 경로 두 가지 모두 기본 경로보다 총 거리 및 총 각도변화에서 개선되었음을 확인할 수 있었다.

후속연구

이것은 두 개의 경유점을 지나는 곡선의 경우 세 개의 부분 궤적을 이어 전체 궤적을 생성하므로 전체 곡선의 양이 많아 하나의 경유점을 지나는 곡선보다 다소 효율성이 떨어지기 때문이다. 향후 이에 대해 보다 효율적으로 개선할 수 있는 연구를 진행할 예정이다.
향후에는 이동 로봇의 실제 주행에 적용하기 위해, 본 논문에서 제안된 부드러운 전역경로를 기반으로 실시간 최적 지역경로를 생성하는 방법을 연구할 것이며, 실험을 통해 이동 로봇의 자율 주행 성능을 검증할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	전역 경로 계획은 무엇을 생성하는가?	전역 경로 계획은 출발 지점부터 목표 지점까지 주행할 모든 지역의 지형 정보 및 장애물 형태 등의 기하학적 정보를 통해 이동 로봇이 이동할 수 있는 전역 경로를 생성한다. 보통 실외에서 사용되며 GPS 등의 위성 항법 장치를 이용하여 로봇의 절대 위치 좌표를 추정할 수 있다.
	두 가지의 이동 로봇 최적 전역 경로 계획은 무엇인가?	그리고 기본 경로를 사용하여 두 가지의 방법으로 경로를 생성하게 된다. 첫 번째 방법은 기본 경로에서 세 개의 노드점을 이용하여 대각선 경로를 생성하는 방법이다. 두 번째는 혼합 다항식의 파라미터를 uDEAS를 이용하여 탐색하고, 곡선 궤적을 생성하는 방법이다. 시뮬레이션을 통해 두개의 방법에 대해 비교 분석하였다.
	로봇이 사람의 도움을 받지 않고 주어진 임무를 수행하기 위해서는 무엇이 필요한가?	로봇이 사람의 도움을 받지 않고 주어진 임무를 수행하기 위해서는 고정 및 이동 장애물을 회피하면서 목적지까지 이동할 수 있는 자율 주행 기술이 필요하다. 자율 주행에서는 로봇의 위치를 추정할 수 있는 자기 위치 추정(localization), 이동을 위한 경로 계획(path planning), 장애물들을 회피(obstacle avoidance) 할 수 있어야 한다[2].

참고문헌 (12)

박경진, 이기성. 이종수, “디중이동로봇의 장애물 회피 및 경로계획 알고리즘에 관한 연구," 대한전자공학회 하계종합학술대회 논문집, pp. 31-34, 2000.
김정민, 김연태, 김성신, “확장 칼만 필터를 이용한 로봇의 실내위치측정,” 한국지능시스템학회 논문지, 제18권, 5호, pp. 706-711, 2008.

원문보기 상세보기
T. J. Park, B. G. Ryu, C. S. Han, J. K. Park, J. Y. Lee and S. H. Back, “Development of the path algorithm for an unmanned ground vehicle," proceeding of KIMST, pp. 895-898, 2005.
김상겸, 김성균, 이용우, “무인자율차량을 위한 경로 계획 알고리즘 및 시뮬레이터 개발,” 한국자동차공학회 논문지, 제15권, 3호, pp. 1-9, 2009.

원문보기 상세보기
M. Montemerlo and S. Thrun, "Simultaneous Localization and Mapping with Unknown Data Association Using FastSLAM," Proc. of the 2003 IEEE International Conference on Robotics and Automation, pp. 1985-1991, 2003
윤희상, 박태형, “자율이동로봇의 부드러운 주행을 위한 통합적 경로계획방법,” CICS 2010 정보 및 제어 학술대회 논문집, pp.51-52, 2010.
김정민, 허정민, 김성신, “수정된 유전자 알고리즘과 퍼지 추론 시스템을 이용한 무인자율주행 이송장치의 다중경로계획,” 한국해양정보통신학회 논문지, 제13권, 8호, pp. 1483-1490, 2009.

원문보기 상세보기
J. -W. Kim and S. W. Kim, “Numerical method for global optimization: dynamic encoding algorithm for searches (DEAS)," IEE Proc.-Control Theory and Appl. vol. 151, no. 5, pp. 661-668, Sept. 2004.

상세보기
J. -W. Kim, T. Kim, J. -Y. Choi and S. W. Kim, “On the global convergence of univariate dynamic encoding algorithm for searches (uDEAS)," International Journal of Control, Automation, and Systems, vol. 6, no. 4, pp. 571-582, Aug. 2008.

원문보기 상세보기
J. -W. Kim and S. W. Kim, “PID control design with exhaustive Dynamic Encoding Algorithm for Searches (eDEAS)," International Journal of Control, Automation, and Systems, vol. 5, no. 6, pp. 691-700, Dec. 2007.

원문보기 상세보기
김은수, 김조환, 김종욱, “최적화 기법인 mDEAS의 개발 및 휴머노이드 이족보행 시 최적 관절궤적 생성에의 적용,” 대한전기학회 논문지, 제68권, 2호, pp. 382-390, 2009.

원문보기 상세보기
M. W. Spong, S. Hutchinson and M. Vjdyasagar, Robot modeling and control, John Wiley & Sons, INC, 2006.

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증