[논문]자율이동로봇을 위한 동적 경로 계획 방법

윤희상; 유진오; 박태형

doi:10.5302/j.icros.2008.14.4.392

문제 정의

본 논문은 골격선 그래프 상에 생성된 경로를 개선시키기 위하여 격자지도(grid map)를 도입한다. 초기 경로 p=< 知… 를 구성하는 경유점 중 시작점 0] 및 목표점 0財을 제외한 나머지 경유점 说, .
본 논문은 최단 거리 경로계획을 목표로 하여 로드 맵 방식 기반의 새로운 경로계획방법을 제안한다. 로드 맵 방식 기반의 방법은 그래프 지도 구성 방법에 따라 다시 가시도 그래프 기반의 방법과 골격선 그래프 기반의 방법으로 구분될 수 있다.

가설 설정

S2: 누적거리 X가 최소인 정점 %를 찾는다. 정점 %와간선으로 직접 연결된 모든 정점 n} 에 대하여, 새로운 누적 거리를 다음과 같이 계산한다.
S3: 모든 정점이 최소의 누적거리를 갖는 정점으로 선택될 때까지, S2를 반복하여 수행한다.
S4: 골격선의 분기점들을 찾아 정점의 집합「를 구성하고, 분기점 사이의 간선으로 간선 집합 厶를 구성한다.
S4: 스테이지를 k = 로 감소시키면서 지시자를 역 추적하며, 각 스테이지의 최적 격자점 涉을 찾는다. 개선 경로 p'는 각 스테이지의 최적 격자점으로 다음과 같이 구성된다.
하기 위하여 점의 이동으로 표현한다. 이때 장애물과 로봇의 간섭을 고려하기 위하여, (1)의 장애물 영역에 로봇이 차지하는 영역이 포함되어 있다고 가정한다. 로봇의 이동 경로 p는 다음과 같이 시작점과 목표점 사이에 존재하는 경유점 %.

제안 방법

기존에 발표된 대표적인 경로계획 방법인 골격선 그래프를 사용하는 방법과 가시도 그래프를 사용하는 방법 각 하나 씩을 구현하였다. 골격선 그래프를 사용한 방법 중 세선화를 적용한 방법은 본 논문의 초기경로 생성 단계에서 이미 구현되었다. 세선화 알고리즘으로 골격선 그래프를 구성하고, 딕스트라 알고리즘으로 최단 경로를 탐색하였다.
이를 위하여 동적 프로그래밍기법을 적용하였다. 기존 방법 대비 상대적으로 적은 계산 시간으로 상대적으로 짧은 이동거리의 경로를 생성함을 비교 시뮬레이션으로 확인하였다.
방법을 구현하였다. 기존에 발표된 대표적인 경로계획 방법인 골격선 그래프를 사용하는 방법과 가시도 그래프를 사용하는 방법 각 하나 씩을 구현하였다. 골격선 그래프를 사용한 방법 중 세선화를 적용한 방법은 본 논문의 초기경로 생성 단계에서 이미 구현되었다.
기존의 방법들이 그래프 생성 후, 그래프를 고정시킨 상태에서 경로를 탐색하는 정적 계획 방법인데 반하여, 본 제안 방법은 생성된 그래프 및 경로를 동시에 변경시키는 과정이 추가된 동적 계획 방법이다. 또한 한 번 경로를 생성하고 종료되는 것이 아니라, 생성된 경로를 계속개선시켜 나가는 방법이다.
본 논문은 자율이동로봇의 경로 계획 문제에 국지적 최적화 기법을 적용한다. 전체의 단계는 초기 경로를 생성하는 경로 생성 단계와 경로를 개선하는 경로 개선 단계로 구분한다.
골격선 그래프를 사용한 방법 중 세선화를 적용한 방법은 본 논문의 초기경로 생성 단계에서 이미 구현되었다. 세선화 알고리즘으로 골격선 그래프를 구성하고, 딕스트라 알고리즘으로 최단 경로를 탐색하였다. 가시도 그래프를 사용하는 방법은 별도로 구현되었다.
자율이동로봇의 효율적인 경로 계획을 위하여, 기존의 로드 맵 방식에 셀 분해 방식을 추가한 새로운 방법을 제안하였다. 기존의 방법들이 그래프 생성 후, 그래프를 고정시킨 상태에서 경로를 탐색하는 정적 계획 방법인데 반하여, 본 제안 방법은 생성된 그래프 및 경로를 동시에 변경시키는 과정이 추가된 동적 계획 방법이다.
보여준다. 정애물의 수가 다른 다양한 경로 계획 문제에 적용하여 결과를 비교하였다. 제안 방법은 골격선 방법의 결과를 개선시키는 방법으로서, 평균 13% 정도의 경로 단축 효과가 있음을 확인하였다.
제안된 방법의 성능을 비교 평가하기 위하여 다른 경로계획 방법을 구현하였다. 기존에 발표된 대표적인 경로계획 방법인 골격선 그래프를 사용하는 방법과 가시도 그래프를 사용하는 방법 각 하나 씩을 구현하였다.
한 번의 그래프 구성과 경로 탐색으로 최종경로를 생성하는 기존의 정적 경로계획 방법이 아니라, 그래프 구성과 경로탐색을 반복하여 그래프와 경로를 계속 변화시키는 동적 경로계획 방법이다. 제안하는 방법은 경로 생성 단계와 경로 개선 단계로 구성된다. 각 단계는 그래프 구성과 경로 탐색 과정을 포함한다.
제안한 경로계획 방법의 성능을 평가하기 위한 시뮬레이션을 수행하였다. 알고리즘은 IBM-PC Pentium
대상 데이터
- 13, 000(mm)xl0, 000(mm) 크기의 평면에 다양한 크기의 장애물 5-230개를 배치하여 경로를 생성하였다. 경로 생성 단계의 그래프 구성 단계에서 필요한 비트맵 데이터의 총 화소 수는 3® X耳 =640x480로 설정하였다.
- 경로 생성 단계의 그래프 구성 단계에서 필요한 비트맵 데이터의 총 화소 수는 3® X耳 =640x480로 설정하였다. 경로 개선 단계에 사용되는 격자 지도의 단위격자의 크기는 100(mm)xl00 (mm)로 설정하였으며, 격자 수 疋X W는 3×3로 설정하였다. 주어진 조건에 따라 다소 차이가 있으나 약 30 회 정도 반복 한 후 개선 과정이 종료되었다.
- 5-230개를 배치하여 경로를 생성하였다. 경로 생성 단계의 그래프 구성 단계에서 필요한 비트맵 데이터의 총 화소 수는 3® X耳 =640x480로 설정하였다. 경로 개선 단계에 사용되는 격자 지도의 단위격자의 크기는 100(mm)xl00 (mm)로 설정하였으며, 격자 수 疋X W는 3×3로 설정하였다.

이론/모형

격자지도에서 최적의 격자점을 선택하는 문제 또한 최적화 문제로서, 동적 프로그래밍(Dynamic Programming, DP) 알고리즘을 적용한다. DP는 최적성의 원리 [8]에 의하여 최적성이 입증된 최적화 기법으로서, 광범위한 범주의 최적화 문제에 널리 활용되고 있다[15-17].
각 단계는 그래프 구성과 경로 탐색 과정을 포함한다. 경로 생성 단계에서는 기존의 방법과 같이 세선화 알고리즘으로 골격선 그래프를 구성하고, 딕스트라 알고리즘을 적용하여 경로를 탐색하여 이동로봇의 초기 경로를 생성한다. 경로 개선 단계에서는 동적 프로그래밍(Dynamic Programming, DP) 알고리즘을 적용하여, 그래프 및 경로를 동시에 개선시킨다.
모든 장애물의 네 꼭지점을 정점으로 하고, 가시거리에 있는 정점과 정점 사이를 간선으로 하는 그래프를 구성하였다. 구성된 그래프에 딕스트라 알고리즘을 적용하여 최단 경로를 탐색하였다.
탐색하는 방법이다. 세선화 알고리즘, 보르노이 알고리즘 등을 적용하여 그래프를 생성할 수 있으며, 딕스트라 알고리즘 또는 A* 알고리즘 등을 적용하여 경로를 탐색할 수 있다. 적은 계산 시간으로 그래프의 생성 및 경로 탐색이 가능하나, 총 이동 경로의 단축 측면에서는 효율이 떨어지는 방법이다.
또한 한 번 경로를 생성하고 종료되는 것이 아니라, 생성된 경로를 계속개선시켜 나가는 방법이다. 이를 위하여 동적 프로그래밍기법을 적용하였다. 기존 방법 대비 상대적으로 적은 계산 시간으로 상대적으로 짧은 이동거리의 경로를 생성함을 비교 시뮬레이션으로 확인하였다.

성능/효과

결과적으로 본 시뮬레이션 결과는 제안된 방법이 경로단축율 측면에서는 가시도 방법에 근사하고, 소요 계산 시간 측면에서는 골격선 방법에 근사한 방법임을 입증한다
정애물의 수가 다른 다양한 경로 계획 문제에 적용하여 결과를 비교하였다. 제안 방법은 골격선 방법의 결과를 개선시키는 방법으로서, 평균 13% 정도의 경로 단축 효과가 있음을 확인하였다. 가시도 방법은 경로 단축 효과가 매우 뛰어난 방법으로 알려져 있다.
가시도 방법은 경로 단축 효과가 매우 뛰어난 방법으로 알려져 있다. 제안 방법을 적용한 경우, 가시도 방법을 적용한 경우 대비 평균 1.4% 정도의 총 이동거리만 증가하였음을 볼 수 있다. 제안한 방법은 가시화 방법과 근사한 수준의 경로 단축 효과를 갖고 있음을 알 수 있다.
이는 장애물 각 꼭지점을 연결하는 간선의 수가 장애물의 수에 따라 기하급수적으로 증가하기 때문이다. 제안 방법의 계산시간은 골격선 방법의 계산 시간과 거의 차이가 없음을 볼 수 있다. 이는 골격선 방법에 추가된 경로 개선 단계의 DP 알고리즘이 전체 계산시간에 별 영향을 주지 않음올 의미한다
4% 정도의 총 이동거리만 증가하였음을 볼 수 있다. 제안한 방법은 가시화 방법과 근사한 수준의 경로 단축 효과를 갖고 있음을 알 수 있다. 또한 장애물의 수와 경로 단축율과는큰 상관관계가 없었다.
경로 개선 단계에 사용되는 격자 지도의 단위격자의 크기는 100(mm)xl00 (mm)로 설정하였으며, 격자 수 疋X W는 3×3로 설정하였다. 주어진 조건에 따라 다소 차이가 있으나 약 30 회 정도 반복 한 후 개선 과정이 종료되었다. 격자수가 증가하는 경우 반복 횟수는 단축되나 계산시간이 증가하므로 실험을 통하여 적절한 값을 선택하였다.

후속연구

제안 방법의 결과는 다양한 종류의 자율이동로봇의 경로계획시스템에 적용될 있다. 특히 복잡한 작업환경에서 실시간으로 최단 경로를 생성하여야 하는 이동로봇에 효과적으로 적용될 수 있으리라 기대한다.
특히 복잡한 작업환경에서 실시간으로 최단 경로를 생성하여야 하는 이동로봇에 효과적으로 적용될 수 있으리라 기대한다. 추후 연구를 통하여, 이동 로봇의 동력학적 특성을 고려한 경로계획 문제의 새로운 해법을 제시하고자 한다.
적용될 있다. 특히 복잡한 작업환경에서 실시간으로 최단 경로를 생성하여야 하는 이동로봇에 효과적으로 적용될 수 있으리라 기대한다. 추후 연구를 통하여, 이동 로봇의 동력학적 특성을 고려한 경로계획 문제의 새로운 해법을 제시하고자 한다.

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

연합인증

자율이동로봇을 위한 동적 경로 계획 방법
Dynamic Path Planning for Autonomous Mobile Robots 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (17)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

자율이동로봇을 위한 동적 경로 계획 방법 Dynamic Path Planning for Autonomous Mobile Robots 원문보기

Abstract ▼ AI-Helper

주제어

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

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (17)

이 논문을 인용한 문헌

저자의 다른 논문 :

윤희상 (3) 박태형 (39)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

자율이동로봇을 위한 동적 경로 계획 방법
Dynamic Path Planning for Autonomous Mobile Robots 원문보기

AI 본문요약
AI-Helper