가시성 그래프와 가변-셀-분할을 결합한 경로 계획 알고리즘

Jung Tae Kim∥, 김대진 · Open Access System for Information Sharing (Pohang University of Science and Technology) · 2009

경로 계획 알고리즘은 이동 로봇이 정해진 지도상에서 주어진 초기 위치로부터 주어진 목적지까지 찾아 가는 경로를 얻는 알고리즘을 말한다. 본 논문에서 제시하는 경로 계획 알고리즘은 2 차원 평면 공간상에서 이동 로봇을 하나의 점으로 보고 상하좌우의 움직임에 제한이 없다고 보았을 때 최적의 경로를 찾아주는 가시성 그래프(Visibility Graph) 알고리즘을 기반으로 한다. 다각형 공간상에서만 알고리즘이 동작하는 가시성 그래프의 단점을 극복하기 위하여, 또 다른 잘 알려진 셀-분할(Cell Decomposition) 알고리즘을 접목시켰으며, 알고리즘의 속도 향상을 위하여 셀-분할 알고리즘 중에서 트리를 기반으로 하는 가변-셀-분할(Adaptive Cell Decomposition) 알고리즘을 이용하였다. 성능 테스트를 위하여 동일한 지도 상에서 기존의 방법들과의 경로 찾기에 소요된 시간 비교를 통해, 본 논문에서 제시한 알고리즘이 기존 알고리즘에 비해 성능 우위에 있음을 보이고 있다.

Cited by 2 works.

Authors