Path planning is one of the most important research areas of robotics, operations research, artificial intelligence and other optimization fields.
In this paper, We propose a method of path planning in 3D-Workspace that is modeled with a DEM(Digital Elevation Model) Image. A modeled 3D workspace consist of a set of voxel and each voxel has a given weight. To represent modeled 3D-workspace efficiently, We propose Octtree data structure. Weighted Octtree decompose the work space hierchically and recursivelly according to distribution of weight. If the total weight sum of area is larger than threshold, the area is decomposed into 8 child nodes. So given threshold, we can control the complexity of weighted octtree structure. By controlling the level of threshold, Ultimately we can control the speed of path search time.
Comparing out method with regular grid method that decompose whole workspace only according to the size and coordinate without any consideration of weight, We can get 4-6times speedup.
경로설정은 로보트학, 인공지능, 작전연구와 같은 최적화분야의 가장 중요한 연구 주제이다. 본 학위논문에서는 DEM영상을 통하여 모델링된 3차원 공간에서의 경로설정 방법에 대해서 제안한다. 모델링된 3차원 공간은 복셀의 집합으로 구성되고 각각의 복셀은 가중치를 갖게된다. 모델링된 3차원 공간을 효과적으로 나타내기 위하여 본 학위논문에서는 가중8진트리라는 데이타구조를 제안한다. 가중8진트리는 가중치의 분포에따라 주어진 공간을 반복적이며 계층적으로 분해하게 된다. 만약 주어진 영역의 가중치의 합이 임계치보다 크다면 그것은 8개의 자식 노드로 분할되게 된다. 그러므로 주어진 임계치를 통하여 가중 8진트리의 복잡도를 조정할수 있다. 임계치의 정도를 조정함으로서 궁극적으로는 경로탐색시간을 조정할수가 있다. 공간을 단순히 크기와 좌표에의 해서 분해하는 규칙적인 격자 방식과 비교하여 4-6정도의 탐색시간의 단축을 얻어낼수 있었다.
