[논문]로봇 경로 제어를 위한 속도기반 Dijkstra 알고리즘

천성권; 김근덕; 김종근

doi:10.9716/kits.2011.10.4.259

로봇 경로 제어를 위한 속도기반 Dijkstra 알고리즘
A Speed-Based Dijkstra Algorithm for the Line Tracer Control of a Robot 원문보기

한국IT서비스학회지 = Journal of Information Technology Services, v.10 no.4, 2011년, pp.259 - 268

천성권 (가톨릭상지대학 중국비지니스정보과) , 김근덕 (영남대학교 공과대학 컴퓨터공학과) , 김종근 (영남대학교 공과대학 컴퓨터공학과)

Abstract ▼ AI-Helper

A robot education system by emulation based on Web can be efficiently used for understanding concept of robot assembly practice and control mechanism of robot by control programming. It is important to predict the path of the line tracer robot which has to be decided by the robot. Shortest Path Algorithm is a well known algorithm which searches the most efficient path between the start node and the end node. There are two related typical algorithms. Dijkstra Algorithm searches the shortest path tree from a node to the rest of the other nodes. $A^*$ Algorithm searches the shortest paths among all nodes. The delay time caused by turning the direction of navigation for the line tracer robot at the crossroads can give big differences to the travel time of the robot. So we need an efficient path determine algorithm which can solve this problem. Thus, It is necessary to analyze the overhead of changing direction of robot at multi-linked node to determine the next direction for efficient routings. In this paper, we reflect the real delay time of directional changing from the real robot. A speed based Dijkstra algorithm is proposed and compared with the previous ones to analyze the performance.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 경로탐색 로봇에서 기본적으로 필요한 제어기술인 동작제어, 센서, 모터제어와 같은 로봇의 구동중심 알고리즘에 더하여 주행 시간을 줄일 수 있는 효율적인 경로 탐색방안을 연구하였다. 기존 탐색 알고리즘에 더하여 주행 로봇에 적용 가능한 효율적인 최단 경로를 탐색하는 속도 기반-Dijkstra 알고리즘을 제안하였다.
본 연구에서는 출발노드에서 도착노드에 이르는 경로 중에서 가장 시간 효율적인 경로를 찾는 알고리즘으로 속도기반-Dijkstra 알고리즘을 제안한다. 제안된 알고리즘의 실험을 위해 주행 로봇에뮬레이션에서 C# 언어를 이용한 경로탐색 인터페이스를 개발하고, 실제 경로탐색 로봇의 여러 가지 형태의 실습용 지도를 기반으로 각 지도의 교차점을 노드로 추출하고 경로 네트워크를 구축하여 테스트 한다.
이와 같은 시간적·공간적 제약을 줄이고 경로탐색 로봇의 모든 요소들을 고려한 에뮬레이션 시스템 환경을 구축하고[3], 더 나아가 경로탐색에 있어서 목표점까지 효율적인 최단 경로를 구하는 알고리즘을 연구하여 실습효과를 증진시키는 것이 본 연구의 목적이다.

제안 방법

본 논문에서는 경로탐색 로봇에서 기본적으로 필요한 제어기술인 동작제어, 센서, 모터제어와 같은 로봇의 구동중심 알고리즘에 더하여 주행 시간을 줄일 수 있는 효율적인 경로 탐색방안을 연구하였다. 기존 탐색 알고리즘에 더하여 주행 로봇에 적용 가능한 효율적인 최단 경로를 탐색하는 속도 기반-Dijkstra 알고리즘을 제안하였다.
다양한 경로를 가지는 실험 대상 네트워크에서 A* 알고리즘, Dijkstra 알고리즘, 속도 기반-Dijkstra 알고리즘의 세 가지 방법으로 경로탐색을 수행하여 성능을 비교·분석하였다.
본 연구에서는 출발노드에서 도착노드에 이르는 경로 중에서 가장 시간 효율적인 경로를 찾는 알고리즘으로 속도기반-Dijkstra 알고리즘을 제안한다. 제안된 알고리즘의 실험을 위해 주행 로봇에뮬레이션에서 C# 언어를 이용한 경로탐색 인터페이스를 개발하고, 실제 경로탐색 로봇의 여러 가지 형태의 실습용 지도를 기반으로 각 지도의 교차점을 노드로 추출하고 경로 네트워크를 구축하여 테스트 한다.
제안한 경로설정 알고리즘의 효율성을 검증하기 위해서 A* 알고리즘, Dijkstra 알고리즘, 속도기반-Dijkstra 알고리즘의 세 가지 방법으로 경로탐색을 시행하여 이를 비교·분석한다.
비교를 위해 세 가지 탐색 알고리즘에 적용한 이동시간은 산정된 거리에 대한 속도의 지체를 고려한 이동시간으로 환산한 값을 이용한다. 해당 분석에서 활용한 이동거리는 실제 경로탐색로봇의 지도를 비례축소 제작하였으며, 통행시간 또한 실제 이동시간을 통해 도출한 링크 통행시간을 사용하였고, 회전 시 적용한 시간의 지체는 앞 서 제시한 식 (1)～식 (3)을 통하여 도출된 값을 사용하였다.

이론/모형

본 연구에서는 회전속도에 따른 시간지체의 고려유무에 따라 탐색된 경로의 성능을 비교 · 분석하기 위해 기준이 되는 알고리즘으로 Dijkstra 알고리즘을 기준으로 한다.

성능/효과

거리 면에서 A^* 알고리즘 평균 1030.7픽셀, Dijkstra 알고리즘 평균 1016.4픽셀, 속도기반-Dijkstra 알고리즘 1016.4픽셀로 도출되었으며, A^* 알고리즘이 다른 알고리즘에 비해 평균적으로 14.3픽셀 더 길게 나타났다.
알고리즘과 비교하였을 경우, 경로의 거리가 커질수록 회전수의 차이가 크게 나타났으며 이는 곧 소요되는 시간이 커짐으로 인해 불합리한 경로를 탐색할 수도 있다는 것을 확인하였다. 따라서 제안된 알고리즘을 경로탐색 로봇의 최단 경로 탐색에 적용하면 시스템의 성능을 향상시킬 수 있다.
4%, 시간 면에서 약 20%의 감소효과가 나타났다. 또한 속도 기반-Dijkstra 알고리즘은 기준이 된 Dijkstra 알고리즘에 비하여 약 12%의 시간이 감소되는 효과가 도출된 것으로 분석되었다.
알고리즘, Dijkstra 알고리즘, 속도 기반-Dijkstra 알고리즘의 세 가지 방법으로 경로탐색을 수행하여 성능을 비교·분석하였다. 분석 결과 속도 기반-Dijkstra 알고리즘을 이용한 경우 평균 경로통행 시간이 가장 적게 나타났다.
시간 면에서는 A^* 알고리즘 평균 27.59초, Dijkstra 알고리즘 평균 25.33초, 속도기반-Dijkstra 알고리즘 평균 22.22초로 도출되었으며, 속도기반-Dijkstra 알고리즘이 A* 알고리즘에 비하여 거리 면에서 약 1.4%, 시간 면에서 약 20%의 감소효과가 나타났다. 또한 속도 기반-Dijkstra 알고리즘은 기준이 된 Dijkstra 알고리즘에 비하여 약 12%의 시간이 감소되는 효과가 도출된 것으로 분석되었다.
특히 A^* 알고리즘과 비교하였을 경우, 경로의 거리가 커질수록 회전수의 차이가 크게 나타났으며 이는 곧 소요되는 시간이 커짐으로 인해 불합리한 경로를 탐색할 수도 있다는 것을 확인하였다. 따라서 제안된 알고리즘을 경로탐색 로봇의 최단 경로 탐색에 적용하면 시스템의 성능을 향상시킬 수 있다.

후속연구

해당 연구의 결과는 주행 로봇 및 자동차 경로탐색에서 하나의 방안으로 활용이 가능할 것으로 판단된다. 추후 본 연구에서 사용한 속도기반-Dijkstra 알고리즘을 적용할 수 있는 실용적인 주행 시스템의 연구도 필요할 것이다.
해당 연구의 결과는 주행 로봇 및 자동차 경로탐색에서 하나의 방안으로 활용이 가능할 것으로 판단된다. 추후 본 연구에서 사용한 속도기반-Dijkstra 알고리즘을 적용할 수 있는 실용적인 주행 시스템의 연구도 필요할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	Dijkstra 알고리즘이란?	Dijkstra 알고리즘은 어떤 링크도 음수 값을 갖지 않는 방향 그래프에서 주어진 출발 노드와 도착 노드 사이의 최단 경로를 구하는 알고리즘으로서, 매 반복마다 거리의 누적 값이 가장 작은 노드의 경로를 표시하는 Label-setting 기법이다[6-8].
	경로를 탐색하는 대표 알고리즘에는 무엇이 있나?	경로를 탐색하는 대표 알고리즘으로 A(A-Star)알고리즘과 Dijkstra 알고리즘*이 있다. 이 알고리즘들은 계산시간, 사용메모리 등에서 차이가 있다.

참고문헌 (8)

심충섭, 김진석, "One-to-One 최단경로 알고리즘의 성능 평가", 정보과학회논문지, 제29권, 제11호(2002), pp.634-639.
민근홍 외, "신호 교차로에서 방향별 지체를 고려한 최적경로탐색 연구",？한국ITS학회 논문지, 제9권, 제3호(2010), pp.12-19.

원문보기 상세보기
김근덕 외, "웹 기반 로봇제어 교육 시스템", 한국정보과학회 학술심포지엄논문집, 제4권, 제1호(2010), pp.35-39.
김용민, 최인찬, "로봇을 위한 위치 인식 및 경로 안내 시스템에 관한 연구", 전자공학회논문지, 제29권, 제1호(2010), pp.12-21.
Zhipeng Liu, "A Study of Routing Protocols for Ad Hoc Networks", Yeungnam University, Masters of Engineering, 2008.
Hart, P. E., N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs", IEEE Trans. on Systems Science and Cybernetics, Vol.SSC-4, No.2(1968), pp.100-107.
Dijkstra, E. W., "A Note on Two Prooblems in connexion with Graphs", Numerische Mathematik, Vol.1(1959), pp.269-271.

상세보기
Cherkassky, B. V., A. V. Goldberg, and T. Redzik, "Shortest Paths Algorithms : Theory and Experimental Evaluation", Mathematical Programming, Vol.73, No.2(1996), pp.129-174.

상세보기

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

연합인증