Motion planning is essential part of robotics. Sampling-based algorithms are widely used to solve motion planning problems. In this dissertation, a novel sampling-based motion planning algorithm is proposed to reduce time to find the initial solution and increase the convergence rate.
The proposed $Q-RRT^{\ast}$ algorithm increases the convergence rate and finds a solution significantly by preserving the failed samples. The proposed algorithm is analyzed with complexity analysis and numerical simulations.
Anytime extension for the proposed algorithm is presented in order to improve the remaining solution while a robot is moving toward the goal. In addition to the anytime extension, a cost functional for safe trajectory preventing collision is also proposed.
The effectiveness of the proposed algorithm is verified with simulations and experiments.
로봇이 장애물과 부딪히지 않으면서 주어진 임무를 수행할 수 있는 행동을 계획하는 일은 매우 중요하다. 효과적으로 행동 계획 문제를 푸는 데는 샘플링 기반 알고리즘이 널리 사용되는데, 본 논문에서는 샘플링 기반 알고리즘 중 하나인 $RRT^{\ast}$를 개선하여 문제를 푸는 시간을 단축시키고 최적의 해를 좀 더 빨리 찾을 수 있도록 새로운 알고리즘을 제안하였다.
본 논문에서 제안하는 $Q-RRT^{\ast}$ 알고리즘은 수렴 속도를 효과적으로 증가시킬 수 있는 방법을 제시하고, 샘플을 가능한 한 보존함으로써 문제 풀이 시간을 크게 단축시키는 방법을 제시하였다. 계산 시간 복잡도 분석과 통계적 분석을 통해 제안된 알고리즘이 기존의 알고리즘에 비해 크게 개선됨을 보였다.
Q-RRT*를 이용하여 지속적인 해의 개선을 시도할 수 있도록 $Q-RRT^{\ast}$의 Anytime 확장을 추가적으로 제안하였다. 또한 위치 추정, 로봇 모델, 또는 제어 과정에서 발생하는 오차를 감안하여 장애물로부터 일정 거리 이상 유지하는 안전한 경로를 생성하는 비용 함수를 제안하여 복잡한 환경에서도 빠르게 해를 구할 수 있음을 보였다.
최종적으로, 본 논문에서 제안하는 알고리즘을 이용한 시뮬레이션과 실험을 통해 기존의 알고리즘과 성능을 비교하였다. 이를 통해 제안된 알고리즘이 효과적임을 입증하였다.
