We present a novel biased sampling technique, Cloud RRT, for efficiently computing high-quality collisionfree
paths, while maintaining the asymptotic convergence to the optimal solution. Our method uses sampling
cloud for allocating samples on promising regions. Our sampling cloud consists of a set of spheres containing a
portion of the C-space. Especially, each sphere projects to a collision-free spherical region in the workspace. We
initialize our sampling cloud by conducting a workspace analysis based on the generalized Voronoi graph. We then
update our sampling cloud to refine the current best solution, while maintaining the global sampling distribution
for exploring understudied other homotopy classes. We have applied our method to a 2D motion planning problem
with kinematic constraints, i.e., the Dubins vehicle model, and compared it against the state-of-the-art methods.
We achieve better performance, up to three times, over prior methods in a robust manner.
모션 플래닝 분야에서 이론적인 관점에서 모션 플래닝 문제의 최적해를 구하는 연구는 비교적 진행되어온 연구가 적었고, 몇 년전 제안된 RRT(Rapidly-exploring Random Tree)*에 의해 실용적인 관점의 최적해 모션 플래닝 연구가 활발히 시작되어 많은 파생 연구의 가능성을 시사하였다. 본 연구는 이러한 흐름 속에서 기존의 RRT* 알고리즘을 개선하여 최적해로의 수렴 특성을 유지하고 더욱 효율적이며 빠른 최적해로의 수렴성을 보이는 편차샘플링 기법을 제안하였다. 본 알고리즘은 첫째로 주어진 공간을 샘플링 구름이라 정의된 구의 집합으로 표현하여 이를 샘플링의 기반으로 삼았다. 이 샘플링 구름은 최적해에 포함될 가능성이 높은 샘플을 추출해낼 수 있도록 가중치와 새로운 샘플링 구를 생성하며, 궁극적으로 최적해를 찾기 위해 샘플링 구름 자체의 샘플링 패턴을 수렴시키는 것으로 문제 해결에 다가가게 된다. 샘플링 구름은 exploitation과 exploration의 균형 문제를 명시적으로 고려하지 않고도 샘플링 구름 구조를 통해 이 문제를 해결하고 나아가 순수 RRT* 알고리즘과 더불어 수렴성을 고려한 최신 알고리즘과의 비교를 통해 우수성을 입증하였다.
