This thesis presents an incremental sampling based optimal motion planning algorithm for systems with nonlinear differential constraints. One of the most famous sampling-based motion planning algorithm is the Rapidly-exploring Random Tree(RRT). RRT algorithm has many advantages. First and foremost, RRT algorithm guarantees probabilistically completeness; the probability of failure decays to zero exponentially with number of samples. Also RRT can be applied to high dimensional planning problem even upto more than 1000 dimensions.
Recently, the study about RRT* algorithm has been growing due to its asymptotically optimality. This thesis extends the studies of RRT* for holonomic systems and systems with linear differential constraints. In order to extend RRT* algorithm for nonlinear systems, a two point boundary value problem(TPBVP) should be solved. However it is difficult and challenging to solve the TPBVP. In this thesis, a TPBVP solver is implemented by Successive Approximation Approach(SAA). By comparison with previous work which uses first-order Taylor approximations, the proposed algorithm(SA-RRT*) produces more realistic and near optimal result. In addition, proposed algorithm was applied to some motion planning problem; Motion planning of a inverted pendulum and two-wheeled mobile robot. SA-RRT* showed more fine results than existing algorithm.
이 논문은 비선형 시스템에 대한 점진적인 샘플링 기반 최적 운동 계획 알고리즘을 다룬다. RRT는 널리 쓰이는 샘플링 기반 운동계획 알고리즘이다. RRT는 많은 장점을 가지는데 무엇보다도 이는 확률적으로 완전하다. 즉, 샘플의 갯수가 증가함에 따라 실패할 확률이 0에 접근한다. 또한 RRT 알고리즘은 굉장히 높은 차원의 문제에도 적용할 수 있다.
RRT*의 점근적 최적 특징때문에, 최근 RRT* 알고리즘에 관한 많은 연구가 이루어지고 있다. 이 논문은 기존의 holonomic이나 선형시스템에 적용되는 RRT*를 비선형 시스템에 적용되도록 확장시킨다. 이를 위해 비선형 시스템에 대한 two point boundary value problem(TPBVP)을 풀어야 하는데 이는 쉽지 않은 문제이다. 이 논문은 연속 근사 접근을 통하여 TPBVP의 해를 구한다. 기존의 알고리즘과 비교하여 본 논문이 제시하는 알고리즘(SA-RRT*)는 비선형 시스템에 대해 더 현실적이고 최적의 결과를 찾아낸다. 또한 본 논문은 제시하는 알고리즘을 진자의 스윙 업문제와 두 바퀴 모바일 로봇 등 일반적인 운동 계획 문제에 적용해보았다.
