[논문]소프트 컴퓨팅에 의한 자율 이동로봇의 충돌 회피 및 최적 경로계획

하상형; 최인찬; 김현성; 전홍태

doi:10.5391/jkiis.2010.20.2.195

소프트 컴퓨팅에 의한 자율 이동로봇의 충돌 회피 및 최적 경로계획
Collision-Avoidance and Optimal Path Planning of Autonomous Mobile Robot using Soft-Computing 원문보기

한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.20 no.2, 2010년, pp.195 - 201

하상형 (중앙대학교 전자전기공학부) , 최인찬 (중앙대학교 전자전기공학부) , 김현성 (중앙대학교 전자전기공학부) , 전홍태 (중앙대학교 전자전기공학부)

초록
AI-Helper

최근 넓은 활동 범위를 제공하고 작업 환경의 변화에 능동적으로 대처하기 위해 자율 이동 로봇에 대한 필요성이 높아지고 있다. 이 논문은 이동로봇이 장애물을 회피하여 최단 경로를 통해 목적지에 도착할 수 있는 알고리즘을 제안하고 시뮬레이션을 통해 그 유용성을 검증하도록 한다. 제안된 알고리즘은 micro-GA와 $\lambda$-geometry MRA을 사용한 알고리즘이다. 시뮬레이션 영역은 320(가로)$\times$200(세로) 픽셀로 제한하고, 한 픽셀의 단위를 1cm로 하였다. $\lambda$-geometry MRA 만을 사용하여 경로를 계획했을 경우에는 경로 계획을 위한 방향성은 제공하였지만 최단 거리 경로는 제공하지 못했다. 반면 micro-GA를 함께 사용했을 경우에는 최단 경로 탐색이 가능하였다. 따라서 제안된 알고리즘은 경로의 방향성과 함께 최단 경로 탐색을 제공하고 있다.

Abstract ▼ AI-Helper

Recently, the necessity of the autonomous mobile robot is emphasized in order to enlarge the scope of activity and actively cope with the change of work environment. This paper proposes the algorithm which enables the mobile robot to avoid obstacles and lead it to the destination by the shortest path. And we verify the usability by a simulation. We made the algorithm with micro-GA and $\lambda$-geometry MRA. The area of simulation is limited to 320(width)$\times$200(length) pixels and one pixel is one centimeter. When we planned the path with only $\lambda$-geometry MRA, we could find the direction for path planning but could not find the shortest path. But when we planned the path with $\lambda$-geometry MRA and micro-GA, we could find the shortest path. So the algorithm enables us to find the direction for path planning and the shortest path.

주제어

AI 본문요약
AI-Helper

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

문제 정의

즉 빠른 시간 내에 경로 탐색이 가능하지만 이 알고리즘만으로는 최단 경로를 찾는데 다소 한계가 있다. 그래서 이 논문에서는 개선된 micro-GA를 이용하여 효율적으로 최단 경로를 탐색할 수 있도록 한다. 그림 5는 기존의 마이크로 유전자 알고리즘과 이 논문에서 제안한 개선된 마이크로 유전자 알고리즘의 간의 차이를 설명해주는 flowchart이다.
이 논문에서는 자율 이동 로봇의 최적 경로 계획을 함에 있어 기존의 방식보다 빠르고 안정된 경로 계획 알고리즘을 제안한다. 그리고 이동 로봇이 경로를 추종함에 있어 발생되는 새로운 고정 장애물이나 동적 장애물의 회피 문제를 해결하기 위한 알고리즘을 제안하여 시뮬레이션을 통해 그 유용성을 검증하도록 한다.

가설 설정

이 논문의 시뮬레이션 환경에서 사용된 자율 이동 로봇은 이륜 차동 구동 로봇으로서 장애물과의 거리를 측정하기 위해 7개의 센서가 장착되어 있다고 가정한다.

제안 방법

7개의 센서는 30°간격으로 배치하여 전방으로부터 좌우 90°만큼의 범위를 가지고 20∼ 50cm를 센싱할 수 있도록 하였다.
고정 및 이동 장애물의 충돌 회피에 대해 고려해 볼 수 있는 여러 조건 중 대표적인 몇 가지 경우에 대해 컴퓨터 시뮬레이션을 해보았다. 그림 14는 LPP의 출력값을 보여주고 있다.
그래서 λ-geometry MRA에 추가로 modified micro-GA를 사용하여 경로 계획을 함으로써 이와 같은 최적 경로 탐색이 가능하게 되었다.
하지만 휴리스틱 알고리즘의 특성상 빠른 시간 안에 경로 탐색이 가능하지만 휴리스틱 평가 함수에 의해 다음 노드를 추정함으로써 경로를 탐색하기 때문에 최단 경로를 찾는 데에는 다소 한계가 있다. 그래서 이 논문에서는 광역 경로 계획을 수행함에 있어서 추가적으로 유전자 알고리즘을 사용하여 최단 경로를 찾도록 한다.
이 논문에서는 자율 이동 로봇의 최적 경로 계획을 함에 있어 기존의 방식보다 빠르고 안정된 경로 계획 알고리즘을 제안한다. 그리고 이동 로봇이 경로를 추종함에 있어 발생되는 새로운 고정 장애물이나 동적 장애물의 회피 문제를 해결하기 위한 알고리즘을 제안하여 시뮬레이션을 통해 그 유용성을 검증하도록 한다.
그림 5에서 볼 수 있듯이 이 논문에서 제안하고 있는 개선된 micro-GA는 기존의 micro-GA에서의 재생산과 공칭 수렴 단계를 배제하고 경로의 중간 경유지 노드를 줄이기 위해 돌연변이를 사용함으로써 보다 빠르고 효율적으로 최적 해를 탐색할 수 있도록 한다.
또한 이 논문에서 제안하고 있는 micro-GA는 재생산 단계를 없애는 대신 다중 교배(multiple crossover) 방식을 사용하여 이러한 부분을 보완한다. 다중 교배 방식은 부모 염색체에 N개의 교배점이 존재함으로써 다양한 스키마 생성이 가능하고 다소의 지역 최적화 기능과 교란에 대한 회복력이 강하다는 장점을 가지고 있다.
본 연구에서 목표로 하고 있는 자율 이동 로봇의 최적 경로 계획과 충돌 회피에 대한 문제를 해결하기 위해 개선된 micro-GA와 LPP를 이용한 방법을 제안하고 시뮬레이션을 통해 그 유용성을 검증하였다.
이동 로봇의 주행 시 환경 인식을 위해 측정된 입력 변수의 값은 먼저 언어적인 변수로 나타내기 위해 소속 함수를 이용한 퍼지화 과정이 필요하다. 여기서는 삼각형 형태의 멤버십 함수를 이용하여 퍼지화를 수행하였다. 표 1은 LPP의 입/출력 변수에 대한 설명이다.
이 논문에서는 인간의 경험적인 움직임을 바탕으로 로봇의 경로 계획시 λ-geometry MRA(maze routing algorithm)과 개선된 micro-GA(genetic algorithm)을 이용하여 광역 경로 계획을 선행함으로써 미리 정의된 고정 장애물을 수용하여 최적 경로를 탐색하도록 한다.
그리고 이를 바탕으로 로봇이 목적지까지 경로를 추종할 때 발생되는 새로운 고정 장애물이나 동적 장애물에 대처할 수 있는 국지적 경로계획은 퍼지 알고리즘을 사용하여 구현하였다. 이 알고리즘은 로봇의 조향 각과 주행 속도를 결정함으로써 충돌 회피 문제를 해결하고 실시간으로 최적 경로를 추종할 수 있도록 하였다. 그림 1은 이동로봇의 광역 경로 계획과 국지적 경로 계획에 각각 사용되는 알고리즘을 설명하고 있다.
위치 기반 부호화(locus-based encoding) 방식은 유전자의 위치가 해당 유전자의 속성을 결정하게 된다. 즉 밀접한 관계를 갖는 노드들이 염색체 상에서 비교적 가까운 위치에 자리하여 교배 연산 시 중요한 스키마의 생존 확률을 높일 가능성이 많기 때문에 이 논문에서는 이러한 방식을 사용하여 부호화 하도록 한다. 또한 λ-geometry MRA에 의해 탐색된 경로를 기반으로 하기 때문에 똑같은 유전자를 가지는 10개의 집단을 생성하여 초기 집단으로 사용하였다.
일반적으로 유전자 알고리즘은 돌연변이율을 낮게 설정 하여 진화가 이루어진다. 하지만 이 논문에서는 돌연변이가 노드를 삭제하기 위한 중요한 변수로 작용하기 때문에 최적경로에 빠르게 수렴하도록 하기 위해 돌연변이율을 40%로 설정하여 진화가 이루어지도록 한다. 이때 유전자 알고리즘이 진행됨에 따라 돌연변이가 강하면 품질 향상이 어렵기 때문에 유전자 알고리즘이 진행됨에 따라 점차적으로 돌연변이 강도를 줄여나가는 비균등 돌연변이(non-uniform mutation) 방식을 사용하였다.

대상 데이터

시뮬레이션 환경은 320(가로) × 200(세로) 픽셀로 제한하고, 한 픽셀의 단위를 1cm로 한다.
시뮬레이션 환경은 320(가로) × 200(세로) 픽셀로 제한하고, 한 픽셀의 단위를 1cm로 한다. 시뮬레이션에 사용된 장애물 벽의 두께는 10cm이고 로봇의 유효 센싱 범위는 30cm로 한다. 또한 로봇의 최대 속도는 15cm/sec로 제한한다.
그림 8은 이동 로봇에 장착된 센서의 영역을 보이고 있다. 이 논문에서 사용된 로봇 모델은 가, 감속으로 이동하며, 양 바퀴의 차동 구동에 의한 조향을 한다. 7개의 센서는 30°간격으로 배치하여 전방으로부터 좌우 90°만큼의 범위를 가지고 20∼ 50cm를 센싱할 수 있도록 하였다.

이론/모형

이 논문에서는 인간의 경험적인 움직임을 바탕으로 로봇의 경로 계획시 λ-geometry MRA(maze routing algorithm)과 개선된 micro-GA(genetic algorithm)을 이용하여 광역 경로 계획을 선행함으로써 미리 정의된 고정 장애물을 수용하여 최적 경로를 탐색하도록 한다. 그리고 이를 바탕으로 로봇이 목적지까지 경로를 추종할 때 발생되는 새로운 고정 장애물이나 동적 장애물에 대처할 수 있는 국지적 경로계획은 퍼지 알고리즘을 사용하여 구현하였다. 이 알고리즘은 로봇의 조향 각과 주행 속도를 결정함으로써 충돌 회피 문제를 해결하고 실시간으로 최적 경로를 추종할 수 있도록 하였다.
이 논문에서는 광역 경로 계획을 위한 알고리즘으로 λ-geometry MRA와 개선된 micro-genetic algorithm을 사용하도록 한다.
국지적 경로 계획은 실시간으로 바뀌는 상황에 적응하여 충돌 등을 회피하기 위해 온라인으로 수립되는 경로 계획이다. 이 논문에서는 효율적인 충돌 회피를 위해 퍼지알고리즘을 사용한다. 회피를 위한 LPP(local path planner)의 입력치는 로봇과 장애물이 이루는 각도와 퍼지 환경지도에서의 장애물 퍼지 멤버십, 장애물과 이동 로봇간의 상대속도이고, LPP의 출력치는 이동 로봇의 조향 각과 주행 속도가 된다.
하지만 이 논문에서는 돌연변이가 노드를 삭제하기 위한 중요한 변수로 작용하기 때문에 최적경로에 빠르게 수렴하도록 하기 위해 돌연변이율을 40%로 설정하여 진화가 이루어지도록 한다. 이때 유전자 알고리즘이 진행됨에 따라 돌연변이가 강하면 품질 향상이 어렵기 때문에 유전자 알고리즘이 진행됨에 따라 점차적으로 돌연변이 강도를 줄여나가는 비균등 돌연변이(non-uniform mutation) 방식을 사용하였다.
이를 미루어 볼 때 λ의 값이 커질수록 선택 가능한 셀의 방향이 두 배가 되고 얻어진 경로가 보다 부드러워지지만 계산에 필요한 실행 시간도 거의 두 배가 되기 때문에 이 논문에서는 가장 적절하다고 판단되는 8-geometry를 사용한다.
그림 4는 λ-geometry MRA에 대한 흐름도이다. 현재 위치에서 다음 노드까지의 거리와 다음 노드에서 목표점까지의 거리를 휴리스틱 평가 함수 H(i)로 사용하여 그 결과 비용인 적합도(fitness)가 최소인 노드들에 대한 리스트를 광역 경로로 사용한다. 광역 경로 계획 결과는 중간 기착지점들의 경로 리스트이다.

후속연구

이 논문에서는 환경 지도를 미리 생성하고 시뮬레이션 하였지만 실제 자율 이동 로봇에 적용할 경우 환경 지도에 대한 정보 없이 주행 중에 환경 지도를 동적으로 생성할 필요가 있기 때문에 효율적으로 환경 지도를 작성할 수 있는 알고리즘 개발도 과제로 남아있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	퍼지 환경지도에서의 각 노드는 무엇을 가지고 있는가?	퍼지 환경지도는 토폴로지컬 환경지도에서의 특징 점과 같은 노드를 가진다. 각 노드는 격자 기반 환경지도상 모서리 특징 점 또는 곡면 특징 점들을 포함하고 있으며 각 특징 점들은 장애물에 대한 방향을 표시하며 장애물과의 거리를 표현하는 퍼지 멤버십을 갖는다. 또한 각 특징 점들은 서로 링크되어 있으며 각 링크는 특징 점들 간의 거리를 가지고 있다. 그림 2는 퍼지 환경지도의 구성을 설명하는 것으로서 환경지도 중간에 원형으로 표시된 부분이 특징 점 노드이다.
	광역 경로 계획은 무엇을 이용하는가?	자율 이동 로봇의 지능화란 어떤 임무가 주어졌을 때 자기 스스로 감지기(sensor)로 주변의 환경과 자신의 위치나 상태를 파악해서 이동하고자하는 경로 계획(path planning)을 해야 하며 이러한 경로는 주행 시간, 소모되는 에너지, 안정성에 대한 고려가 되어야 하고 계산된 경로를 따라가기 위한 경로 추종(path tracking) 제어기가 있어야 한다. 그리고 경로 계획은 크게 두 부분으로 나뉘어지는데 먼저 오프라인(off-line)으로 이미 알려진 환경의 지도나 모델을 이용하는 광역 경로 계획(global path planning)과 실시간으로 바뀌어가는 환경에 적응하기 위해 온라인(on-line)으로 상황을 판단하는 국지적 경로 계획(local path planning)이 있다.
	국지적 경로 계획은 무엇인가?	자율 이동 로봇의 지능화란 어떤 임무가 주어졌을 때 자기 스스로 감지기(sensor)로 주변의 환경과 자신의 위치나 상태를 파악해서 이동하고자하는 경로 계획(path planning)을 해야 하며 이러한 경로는 주행 시간, 소모되는 에너지, 안정성에 대한 고려가 되어야 하고 계산된 경로를 따라가기 위한 경로 추종(path tracking) 제어기가 있어야 한다. 그리고 경로 계획은 크게 두 부분으로 나뉘어지는데 먼저 오프라인(off-line)으로 이미 알려진 환경의 지도나 모델을 이용하는 광역 경로 계획(global path planning)과 실시간으로 바뀌어가는 환경에 적응하기 위해 온라인(on-line)으로 상황을 판단하는 국지적 경로 계획(local path planning)이 있다.

참고문헌 (7)

변증남, 퍼지논리 제어, 홍릉과학출판사, pp. 110-128, 1997.
Bart Kosko, Neural Networks and Fuzzy Systems; A Dynamical Systems Approach To Machine Intelligence, Prentice Hall Inc., pp. 263-275, 1992.
Gene Eu Jan, Ki Yin Chang and Ian Parberry, "Optimal Path Planning for Mobile Robot Navigation", IEEE/ASME Transactions on Mechatronics, Vol. 13, No. 4, pp. 2-9, August 2008.

상세보기
X. Yuan and Simon X. Yang, "Multirobot-based Nanoassembly Planning with Automated Path Generation", IEEE/ASME Transactions on Mechatronics, Vol. 12, No. 3, pp. 2-5, Jun 2007.

상세보기
Jyh-Shing Roger Jang, Chuen-Tsai Sun and EiJi Mizutani, Neuro-Fuzzy and Soft-Computing; A Computational Approach to Learning and Machine Intelligence, Prentice Hall Inc., pp. 273-278, 1997.
문병로, 유전 알고리즘, 두양사, pp. 39-52, 2005.
심귀보, 인공생명의 방법론, 드림미디어, pp. 30-44, 2000.

저자의 다른 논문 :

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

연합인증