Thanks to the probabilistic completeness and almost-sure asymptotic optimality, sampling-based motion planning algorithms have been widely and deeply studied for the past decades. It is, however, a well-known fact that the computational overhead of sampling-based algorithm can dramatically increase with respect to the complexity of a given problem. For this reason, improving the convergence speed toward the optimal solution in motion planning problem is a still-always open problem. In the aspect of computational importance, Sampling, Collision Checking, Nearest Neighbor Search have been considered major components in sampling-based approaches which can greatly affect the resulting random geometric graph.
To this context, the thesis of this dissertation is that in order to achieve the faster convergence speed toward the optimal solution we analyze the aforementioned three major components to improve the overall performance of the sampling-based planning, i.e., convergence speed toward the optimal solution. We particularly consider spherical representations to discretize space for various purpose and exploit those for biased-sampling, probabilistic collision checking, and adaptive sparse graph construction. We also hybridize sampling-based and optimized-based planning in conjunction with the spherical representations for faster convergence speed.
샘플링 기반의 경로 생성 알고리즘은 확률적 완전성과 점진적 최적성을 보장하는 특징을 갖고 있어 로보틱스 분야에서 지난 수십년간 다양하고도 깊게 연구되어 온 분야 중 하나이다. 하지만 주어진 문제의 복잡도에 따라 증가하는 계산량으로 인해 최적해로의 수렴 속도를 높이기 위한 연구는 중요한 문제로 남겨져있다. 샘플링 기반 알고리즘의 주요 구성 요소는 샘플링, 충돌 검사, 근접 이웃 탐색 으로 이루어져있고, 이들을 통해 어떠한 형태의 랜덤 기하 그래프를 어떻게 구축하는지에 따라 전체 알고리즘의 성능이 크게 영향 받는다.
이에 따라 본 논문이 담고 있는 논제는 다음과 같다. 샘플링 기반 알고리즘의 최적해로의 수렴 속도를 개선하기 위해 3개의 주요 구성 요소를 분석하고 각각의 성능을 끌어올리기 위한 알고리즘 연구를 중심으로 한다. 특히 주어진 공간을 구형 표현법을 통해 다양한 형태로 이산화하고, 이의 효율적 활용 및 최적화 기반 경로 생성과의 혼성화를 통해 경로 생성 알고리즘의 전체적인 성능 향상을 추구하는 연구를 목표로 하고자 한다.
