[논문]무인자동차의 경로점 주행 시 장애물 회피를 위한 경로생성 알고리즘

임준혁; 유승환; 지규인; 이달호

doi:10.5302/j.icros.2011.17.8.843

무인자동차의 경로점 주행 시 장애물 회피를 위한 경로생성 알고리즘
A Path Generation Algorithm for Obstacle Avoidance in Waypoint Navigation of Unmanned Ground Vehicle 원문보기

제어·로봇·시스템학회 논문지 = Journal of institute of control, robotics and systems, v.17 no.8, 2011년, pp.843 - 850

임준혁 (건국대학교 전자정보통신공학과) , 유승환 (건국대학교 전자정보통신공학과) , 지규인 (건국대학교 전자공학과) , 이달호 (경원대학교 전자공학과)

Abstract ▼ AI-Helper

In this paper, an effective path generation algorithm for obstacle avoidance producing small amount of steering action as possible is proposed. The proposed path generation algorithm can reduce unnecessary steering because of the small lateral changes in generated waypoints when UGV (Unmanned Ground Vehicle) encounters obstacles during its waypoint navigation. To verify this, the proposed algorithm and $A^*$ algorithm are analyzed through the simulation. The proposed algorithm shows good performance in terms of lateral changes in the generated waypoint, steering changes of the vehicle while driving and execution speed of the algorithm. Especially, due to the fast execution speed of the algorithm, the obstacles that encounter suddenly in front of the vehicle within short range can be avoided. This algorithm consider the waypoint navigation only. Therefore, in certain situations, the algorithm may generate the wrong path. In this case, a general path generation algorithm like $A^*$ is used instead. However, these special cases happen very rare during the vehicle waypoint navigation, so the proposed algorithm can be applied to most of the waypoint navigation for the unmanned ground vehicle.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 무인자동차의 경로점 주행에 적합한 경로 생성 알고리즘을 제안한다. 차량은 주행 중 주차, 교차로 또는 급격한 코너 구간 주행, U턴 등 특별한 경우를 제외하면 급격한 조향 변화가 불필요하고 이는 무인자동차의 경로점 주행 시에도 마찬가지이다.
본 논문에서는 위의 일반적인 경로생성 알고리즘들이 갖는 단점을 보완하여 무인자동차의 경로점 주행에 적합한 경로생성 알고리즘을 제안하였다. 무인자동차의 경로점 주행 시에는 조향 변화를 최소화하여야 보다 안정적이고 효율적인 주행이 가능하며 또한 알고리즘의 수행속도 역시 최소화시켜야 돌발적인 근접 장애물 회피가 효과적일 수 있다.

가설 설정

마찬가지로 D가 10m 라면 제동거리가 10m 이하가 되는 속도를 낼 수 있다. 본 논문에서는 속도와 제동거리와의 관계를 정비례한다 가정하여 차량의 제한속도를 다음과 같이 설정하였다.

제안 방법

그림 8에서 차량의 주행 궤적을 살펴보면 A* 알고리즘의 경우 차량의 진행방향에 대해 횡방향 변화가 심한 반면 본 논문에서 제안한 알고리즘은 차량의 진행 방향에 대한 횡방향 변화가 적기 때문에 효율적인 경로점 주행이 이뤄졌음을 한눈에 알 수 있다. 그리고 제안한 알고리즘은 장애물 통과 후 최대한 현재 진행방향을 유지하도록 경로가 생성된다. 이는 본 논문에서 제안하는 경로생성 알고리즘이 전역경로가 아닌 차량의 현재 진행방향에 우선하기 때문이다.
무인자동차의 경로점 주행 중 장애물과 조우 시 그림 4와 같이 여러 센서들의 정보로부터 생성된 장애물 맵에서 차량의 폭을 고려하여 진행방향에 대해 일정영역만을 탐색한다. 전방에 대한 탐색을 마치면 몇 개의 경로 후보군(가장 긴 3개의 사각형이 나타내는 경로)이 선정되고 그 중에서 최적의 경로를 선택하여야 한다.
무인자동차의 주행 시뮬레이션은 정지상태인 장애물 구간을 주행하는 세 가지 상황과 돌발적인 장애물 발생 상황에 대해서 수행하였다. 정지상태인 장애물 구간을 주행하는 각각의 상황을 편의상 협로 구간, S자 구간, 중앙 장애물 구간으로 명명하고, 각각의 상황에 대해 본 논문에서 제안한 알고리즘의 시뮬레이션 결과와 A* 알고리즘의 시뮬레이션 결과를 생성된 경로점, 차량의 이동궤적, 수행속도, 주행 중 조향 변화 등의 비교를 통해 성능을 분석한다.
본 논문에서 제안하는 경로생성 알고리즘은 안전하고 효율적인 경로점 주행을 위해 주행 중 조향 변화와 수행속도의 최소화에 초점을 맞추었다. 본 논문의 알고리즘은 전역경로보다 차량의 진행방향에 중점을 두고 경로를 생성하기 때문에 무인차량의 경로점 주행 중 장애물과 조우 시에 최소한의 조향 변화만으로 장애물을 회피하여 주행할 수 있다.
본 논문에서는 위의 설명과 같이 A* 알고리즘의 가장 기본적이며 일반적인 방식으로 구현하여 시뮬레이션에 적용하였다.
본 논문의 경로생성 알고리즘은 그림 15의 예와 같이 차량이 목표지점까지 주행하는데 있어 차량진행방향으로 도로가 막혀 있지 않아야 한다. 그러나 그림 15와 같은 경우는 매우 특수한 경우로 이와 비슷한 환경은 드물기 때문에 본 논문의 알고리즘은 대부분의 경로점 주행에 적용될 수 있다.
본 논문의 알고리즘은 경로점 주행에 특화된 알고리즘으로 특수한 경우에 대해서는 잘못된 경로를 생성할 수 있는데, 이 때에는 A* 알고리즘과 같은 일반적인 경로생성 알고리즘으로의 전환을 통해 주행을 계속할 수 있다. 그러나 이러한 특수한 경우는 매우 드물기 때문에 본 논문의 알고리즘은 대부분의 경로점 주행에 적용될 수 있다.
본 논문에서 제안하는 경로생성 알고리즘은 안전하고 효율적인 경로점 주행을 위해 주행 중 조향 변화와 수행속도의 최소화에 초점을 맞추었다. 본 논문의 알고리즘은 전역경로보다 차량의 진행방향에 중점을 두고 경로를 생성하기 때문에 무인차량의 경로점 주행 중 장애물과 조우 시에 최소한의 조향 변화만으로 장애물을 회피하여 주행할 수 있다. 또한 장애물의 복잡도와 상관없이 계산 시간이 항상 0.
무인자동차의 주행 시뮬레이션은 정지상태인 장애물 구간을 주행하는 세 가지 상황과 돌발적인 장애물 발생 상황에 대해서 수행하였다. 정지상태인 장애물 구간을 주행하는 각각의 상황을 편의상 협로 구간, S자 구간, 중앙 장애물 구간으로 명명하고, 각각의 상황에 대해 본 논문에서 제안한 알고리즘의 시뮬레이션 결과와 A* 알고리즘의 시뮬레이션 결과를 생성된 경로점, 차량의 이동궤적, 수행속도, 주행 중 조향 변화 등의 비교를 통해 성능을 분석한다. 본 논문의 경로 생성 알고리즘은 경로점 주행에 특화된 알고리즘으로서 일반적인 경로점 주행 환경이 아닌 경우 잘못된 경로를 생성할수 있다.

데이터처리

본 논문에서 제안하는 경로생성 알고리즘의 성능은 A* 알고리즘과의 비교를 통해 검증하였다. 본 장에서는 A* 알고리즘을 구현한 방법에 대해 기술한다.

성능/효과

차량은 주행 중 주차, 교차로 또는 급격한 코너 구간 주행, U턴 등 특별한 경우를 제외하면 급격한 조향 변화가 불필요하고 이는 무인자동차의 경로점 주행 시에도 마찬가지이다. 본 논문에서 제안하는 경로생성 알고리즘은 전역경로가 아닌 차량의 현재 진행방향에 우선하기 때문에 조향 변화를 최소화시킬 수 있고, 수행속도 또한 빠르기 때문에 갑작스런 장애물에 대한 대처도 가능하다. 다음은 본 논문에서 제안하는 경로생성 알고리즘에 대하여 기술한다.
본 논문에서 제안한 경로생성 알고리즘은 경로를 생성함과 동시에 차량의 목표속도를 생성할 수 있다는 장점이 있다. 그림 6에서 차량이 현재 상태에서 주행 가능한 최대거리(D) 와 비례하여 목표속도를 설정할 수 있다.
무인자동차의 경로점 주행 시에는 조향 변화를 최소화하여야 보다 안정적이고 효율적인 주행이 가능하며 또한 알고리즘의 수행속도 역시 최소화시켜야 돌발적인 근접 장애물 회피가 효과적일 수 있다. 시뮬레이션 결과 본 논문에서 제안한 경로생성 알고리즘은 이 두 가지 조건에서 훌륭한 성능을 보여주는 것으로 판단된다.
그림 10, 11, 12, 13은 S자 구간과 중앙 장애물 구간에 대한 시뮬레이션 결과를 보여준다. 이는 협로 구간의 경우와 유사하며 차량의 궤적을 보아 본 논문에서 제안한 알고리즘이 A* 알고리즘에 비해 급격한 조향 변화가 현저히 적음을 파악할 수 있다. 그림 11에서 제안한 알고리즘의 경우에도 급격한 조향 변화가 발생하지만 이것은 장애물 회피 주행을 위해 발생하는 것으로 반드시 필요한 조향 변화이다.
이와 같이 본 논문의 경로생성 알고리즘을 이용하면 차량의 경로점 주행 시 조향 변화가 적어지기 때문에 보다 안전하고 효율적인 주행이 가능하며, 수행속도가 빨라 돌발적인 근접 장애물에 대한 회피 주행이 가능하다. 그러나 본 장의 첫 부분에 언급했듯이 이 알고리즘은 경로점 주행만을 우선 고려하였기 때문에 일반적인 경로점 주행 환경이 아닌 특수한 환경에서는 잘못된 경로를 생성할 수 있다.

후속연구

본 논문에서는 경로점을 기반으로 한 경로추종주행을 하기 때문에 새로운 경로점을 구하는 과정이 필요하다. 이를 위해 먼저 장애물의 좌표(P)를 구한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대표적인 경로생성 알고리즘에는 무엇이 있는가?	특히 경로점 주행에 있어 무인자동차가 주행해야 할 전역경로 상에 장애물이 있을 경우 이를 회피하여 주행할 수 있도록 경로를 재 생성하여야 한다. 대표적인 경로생성 알고리즘에는 Dijkstra 알고리즘, A 알고리즘, D(Dynamic A) 알고리즘, RRT (Rapidlyexploring Random Trees) 알고리즘 등*이 있다[1]. Dijkstra 알고리즘은 어떠한 간선도 음수 값을 갖지 않는 방향성 그래프에서 주어진 시작지점과 목표지점 사이의 최단 경로 문제를 푸는 너비 우선 탐색 알고리즘이다[2].
	Dijkstra 알고리즘은 무엇인가?	대표적인 경로생성 알고리즘에는 Dijkstra 알고리즘, A* 알고리즘, D(Dynamic A) 알고리즘, RRT (Rapidlyexploring Random Trees) 알고리즘 등이 있다[1]. Dijkstra 알고리즘은 어떠한 간선도 음수 값을 갖지 않는 방향성 그래프에서 주어진 시작지점과 목표지점 사이의 최단 경로 문제를 푸는 너비 우선 탐색 알고리즘이다[2]. 그러나 알고리즘의 특성상 많은 메모리를 사용하기 때문에 수행속도가 느린 단점이 있다.
	Dijkstra 알고리즘의 단점은 무엇인가?	Dijkstra 알고리즘은 어떠한 간선도 음수 값을 갖지 않는 방향성 그래프에서 주어진 시작지점과 목표지점 사이의 최단 경로 문제를 푸는 너비 우선 탐색 알고리즘이다[2]. 그러나 알고리즘의 특성상 많은 메모리를 사용하기 때문에 수행속도가 느린 단점이 있다. A* 알고리즘은 상태공간 안의 특정 노드에 인접한 노드 들을 조사해 나가면서 시작 지점으로부터 목표 지점에 이르는 가장 적은 비용의 경로를 찾는 알고리즘이다.

참고문헌 (7)

Y. J. Son, "Design of path planning & GPS estimation algorithm for unmanned autonomous ground vehicle," Graduate School of Automotive Engineering, Kookmin Univ., Doctoral Thesis, 2009.
M. Sniedovich, "Dijkstra's algorithm revisited: the dynamic programming connexion," Control and Cybernetics, vol. 35, no. 3, 2006.

상세보기
A. Stentz, "Optimal and efficient path planning for partiallyknown environments," Proc. IEEE International Conference on Robotics and Automation, vol. 4, pp. 3310-3317, May 1994.
J. J. Kuffner, Jr., S. M. LaValle, "RRT-connect an efficient approach to single-query path planning," Proc. 2000 IEEE International Conference on Robitics and Automation, vol. 2, pp. 995-1001, April 2000.
C. K. Yang and D. S. Shim, "Controller transition management of hybrid position control system for unmanned expedition vehicles," Journal of Institute of Control, Robotics and Systems, vol. 14, no. 10, pp. 969-976, 2008.

원문보기 상세보기
H. S. Yoon and T. H. Park, "Motion planning of autonomous mobile robot using dynamic programming," Journal of Institute of Control, Robotics and Systems (in Korean), vol. 16, no. 1, pp. 53-60, 2010.

원문보기 상세보기
D. H. Kim, C. J. Kim, and C. S. Han, "Geometric path tracking and obstacle avoidance methods for an autonomous navigation of nonholonomic mobile robot," Journal of Institute of Control, Robotics and Systems (in Korean), vol. 16, no. 8, pp. 771-779, 2010.

원문보기 상세보기

저자의 다른 논문 :

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

연합인증