가중 8진트리를 이용한 3차원공간에서 최적경로설정

Abstract

경로설정은 로보트학, 인공지능, 작전연구와 같은 최적화분야의 가장 중요한 연구 주제이다. 본 학위논문에서는 DEM영상을 통하여 모델링된 3차원 공간에서의 경로설정 방법에 대해서 제안한다. 모델링된 3차원 공간은 복셀의 집합으로 구성되고 각각의 복셀은 가중치를 갖게된다. 모델링된 3차원 공간을 효과적으로 나타내기 위하여 본 학위논문에서는 가중8진트리라는 데이타구조를 제안한다. 가중8진트리는 가중치의 분포에따라 주어진 공간을 반복적이며 계층적으로 분해하게 된다. 만약 주어진 영역의 가중치의 합이 임계치보다 크다면 그것은 8개의 자식 노드로 분할되게 된다. 그러므로 주어진 임계치를 통하여 가중 8진트리의 복잡도를 조정할수 있다. 임계치의 정도를 조정함으로서 궁극적으로는 경로탐색시간을 조정할수가 있다. 공간을 단순히 크기와 좌표에의 해서 분해하는 규칙적인 격자 방식과 비교하여 4-6정도의 탐색시간의 단축을 얻어낼수 있었다.