Review of Motion Planning

Path Planning 알고리즘을 개발 원리 및 시기에 따라 Traditional Algorithm과 ML-based Algorithm으로 분류한다. Tradition Algorithm은 Graph Based method, Sampling based method, Curve Interpolation으로 구분한다. ML-based Algorithm 은  Supervised Learning, Optimal Value Reinforcement Learning, Policy Gradient Reinforcement Learning.

 

Graph Search Based Algorithm

1. Dijsktra's Algorithm

2. A* Algorithm

   Hybrid A*, Field D*, Anytime A*, State Lattice Algorithm

 

Sampling Based Algorithm

1. RRT (Rapidly exploring Random Tree)

2. PRM (Probably Roadmap Method)

 

Interpolating Curve Algorithm

1. Line and Circle (Dubins, Reeds and Shepp)

2. Clothoid

3. Polynomial (Hermite, 2차)

4. Bezier Curve (2, 3, 4차)

5. B Spline

 

ML-based Algorithm

1. Optimal Value RL

Markov Chain, Markov Decision Process, Model Free RL and Model Based dynamic programming, Temporal Difference and Monte Carlo methods